001/* 002 * Copyright 2006 - 2013 003 * Stefan Balev <stefan.balev@graphstream-project.org> 004 * Julien Baudry <julien.baudry@graphstream-project.org> 005 * Antoine Dutot <antoine.dutot@graphstream-project.org> 006 * Yoann Pigné <yoann.pigne@graphstream-project.org> 007 * Guilhelm Savin <guilhelm.savin@graphstream-project.org> 008 * 009 * This file is part of GraphStream <http://graphstream-project.org>. 010 * 011 * GraphStream is a library whose purpose is to handle static or dynamic 012 * graph, create them from scratch, file or any source and display them. 013 * 014 * This program is free software distributed under the terms of two licenses, the 015 * CeCILL-C license that fits European law, and the GNU Lesser General Public 016 * License. You can use, modify and/ or redistribute the software under the terms 017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following 018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by 019 * the Free Software Foundation, either version 3 of the License, or (at your 020 * option) any later version. 021 * 022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY 023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 024 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 025 * 026 * You should have received a copy of the GNU Lesser General Public License 027 * along with this program. If not, see <http://www.gnu.org/licenses/>. 028 * 029 * The fact that you are presently reading this means that you have had 030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms. 031 */ 032package org.graphstream.stream; 033 034import java.util.Iterator; 035import java.util.LinkedList; 036 037import org.graphstream.graph.Edge; 038import org.graphstream.graph.Graph; 039import org.graphstream.graph.Node; 040import org.graphstream.graph.implementations.AdjacencyListGraph; 041import org.graphstream.graph.implementations.Graphs; 042import org.graphstream.util.GraphDiff; 043import org.graphstream.util.VerboseSink; 044 045public class Timeline implements Source, Replayable, Iterable<Graph> { 046 047 public static final String TIME_PREFIX = "time"; 048 049 private class StepDiff { 050 double step; 051 GraphDiff diff; 052 053 StepDiff(double step, GraphDiff diff) { 054 this.step = step; 055 this.diff = diff; 056 } 057 } 058 059 LinkedList<StepDiff> diffs; 060 061 protected boolean changed; 062 protected Graph initialGraph, currentGraph; 063 protected GraphDiff currentDiff; 064 protected Connector connector; 065 protected PipeBase pipe; 066 protected int seeker; 067 068 public Timeline() { 069 this.diffs = new LinkedList<StepDiff>(); 070 this.changed = false; 071 this.connector = new Connector(); 072 this.currentDiff = null; 073 this.pipe = new PipeBase(); 074 } 075 076 public void reset() { 077 078 } 079 080 public void play(double from, double to) { 081 play(from, to, pipe); 082 } 083 084 public void play(double from, double to, Sink sink) { 085 if (diffs.size() == 0) 086 return; 087 088 if (from > to) { 089 int i = diffs.size() - 1, j; 090 091 while (i > 0 && diffs.get(i).step > from) 092 i--; 093 094 j = i; 095 096 while (j > 0 && diffs.get(j).step >= to) 097 j--; 098 099 for (int k = i; k >= j; k--) 100 diffs.get(k).diff.reverse(sink); 101 } else { 102 int i = 0, j; 103 104 while (i < diffs.size() - 1 && diffs.get(i).step < from) 105 i++; 106 107 j = i; 108 109 while (j < diffs.size() - 1 && diffs.get(j).step <= to) 110 j++; 111 112 for (int k = i; k <= j; k++) 113 diffs.get(k).diff.apply(sink); 114 } 115 } 116 117 public void play() { 118 play(initialGraph.getStep(), currentGraph.getStep()); 119 } 120 121 public void play(Sink sink) { 122 play(initialGraph.getStep(), currentGraph.getStep(), sink); 123 } 124 125 public void playback() { 126 play(currentGraph.getStep(), initialGraph.getStep()); 127 } 128 129 public void playback(Sink sink) { 130 play(currentGraph.getStep(), initialGraph.getStep(), sink); 131 } 132 133 public void seek(int i) { 134 seeker = i; 135 } 136 137 public void seekStart() { 138 seeker = 0; 139 } 140 141 public void seekEnd() { 142 seeker = diffs.size(); 143 } 144 145 public boolean hasNext() { 146 return seeker < diffs.size(); 147 } 148 149 public void next() { 150 if (seeker >= diffs.size()) 151 return; 152 153 diffs.get(seeker++).diff.apply(pipe); 154 } 155 156 public boolean hasPrevious() { 157 return seeker > 0; 158 } 159 160 public void previous() { 161 if (seeker <= 0) 162 return; 163 164 diffs.get(--seeker).diff.reverse(pipe); 165 } 166 167 /** 168 * 169 * @param source 170 */ 171 public void begin(Source source) { 172 initialGraph = new AdjacencyListGraph("initial"); 173 currentGraph = new AdjacencyListGraph("initial"); 174 begin(); 175 } 176 177 /** 178 * 179 * @param source 180 */ 181 public void begin(Graph source) { 182 initialGraph = Graphs.clone(source); 183 currentGraph = source; 184 begin(); 185 } 186 187 protected void begin() { 188 currentGraph.addSink(connector); 189 pushDiff(); 190 } 191 192 /** 193 * 194 */ 195 public void end() { 196 if (currentDiff != null) { 197 currentDiff.end(); 198 diffs.add(new StepDiff(currentGraph.getStep(), currentDiff)); 199 } 200 201 currentGraph.removeSink(connector); 202 currentGraph = Graphs.clone(currentGraph); 203 } 204 205 protected void pushDiff() { 206 if (currentDiff != null) { 207 currentDiff.end(); 208 diffs.add(new StepDiff(currentGraph.getStep(), currentDiff)); 209 } 210 211 currentDiff = new GraphDiff(); 212 currentDiff.start(currentGraph); 213 } 214 215 /* 216 * (non-Javadoc) 217 * 218 * @see java.lang.Iterable#iterator() 219 */ 220 public Iterator<Graph> iterator() { 221 return new TimelineIterator(); 222 } 223 224 /* 225 * (non-Javadoc) 226 * 227 * @see org.graphstream.stream.Replayable#getReplayController() 228 */ 229 public Controller getReplayController() { 230 return new TimelineReplayController(); 231 } 232 233 protected class Connector extends SinkAdapter { 234 @Override 235 public void stepBegins(String sourceId, long timeId, double step) { 236 Timeline.this.pushDiff(); 237 } 238 } 239 240 protected class TimelineReplayController extends PipeBase implements 241 Controller { 242 public void replay() { 243 play(this); 244 } 245 246 public void replay(String sourceId) { 247 String tmp = this.sourceId; 248 this.sourceId = sourceId; 249 play(this); 250 this.sourceId = tmp; 251 } 252 } 253 254 protected class TimelineIterator implements Iterator<Graph> { 255 Graph current; 256 int idx; 257 258 public TimelineIterator() { 259 current = Graphs.clone(initialGraph); 260 idx = 0; 261 } 262 263 /* 264 * (non-Javadoc) 265 * 266 * @see java.util.Iterator#hasNext() 267 */ 268 public boolean hasNext() { 269 return idx < diffs.size(); 270 } 271 272 /* 273 * (non-Javadoc) 274 * 275 * @see java.util.Iterator#next() 276 */ 277 public Graph next() { 278 if (idx >= diffs.size()) 279 return null; 280 281 diffs.get(idx++).diff.apply(current); 282 return Graphs.clone(current); 283 } 284 285 /* 286 * (non-Javadoc) 287 * 288 * @see java.util.Iterator#remove() 289 */ 290 public void remove() { 291 } 292 293 } 294 295 /* 296 * (non-Javadoc) 297 * 298 * @see org.graphstream.stream.Source#addSink(org.graphstream.stream.Sink) 299 */ 300 public void addSink(Sink sink) { 301 pipe.addSink(sink); 302 } 303 304 /* 305 * (non-Javadoc) 306 * 307 * @see 308 * org.graphstream.stream.Source#removeSink(org.graphstream.stream.Sink) 309 */ 310 public void removeSink(Sink sink) { 311 pipe.removeSink(sink); 312 } 313 314 /* 315 * (non-Javadoc) 316 * 317 * @see 318 * org.graphstream.stream.Source#addAttributeSink(org.graphstream.stream 319 * .AttributeSink) 320 */ 321 public void addAttributeSink(AttributeSink sink) { 322 pipe.addAttributeSink(sink); 323 } 324 325 /* 326 * (non-Javadoc) 327 * 328 * @see 329 * org.graphstream.stream.Source#removeAttributeSink(org.graphstream.stream 330 * .AttributeSink) 331 */ 332 public void removeAttributeSink(AttributeSink sink) { 333 pipe.removeAttributeSink(sink); 334 } 335 336 /* 337 * (non-Javadoc) 338 * 339 * @see org.graphstream.stream.Source#addElementSink(org.graphstream.stream. 340 * ElementSink) 341 */ 342 public void addElementSink(ElementSink sink) { 343 pipe.addElementSink(sink); 344 } 345 346 /* 347 * (non-Javadoc) 348 * 349 * @see 350 * org.graphstream.stream.Source#removeElementSink(org.graphstream.stream 351 * .ElementSink) 352 */ 353 public void removeElementSink(ElementSink sink) { 354 pipe.removeElementSink(sink); 355 } 356 357 /* 358 * (non-Javadoc) 359 * 360 * @see org.graphstream.stream.Source#clearElementSinks() 361 */ 362 public void clearElementSinks() { 363 pipe.clearElementSinks(); 364 } 365 366 /* 367 * (non-Javadoc) 368 * 369 * @see org.graphstream.stream.Source#clearAttributeSinks() 370 */ 371 public void clearAttributeSinks() { 372 pipe.clearAttributeSinks(); 373 } 374 375 /* 376 * (non-Javadoc) 377 * 378 * @see org.graphstream.stream.Source#clearSinks() 379 */ 380 public void clearSinks() { 381 pipe.clearSinks(); 382 } 383 384 public static void main(String... strings) throws Exception { 385 Graph g = new AdjacencyListGraph("g"); 386 Timeline timeline = new Timeline(); 387 timeline.addSink(new VerboseSink()); 388 389 timeline.begin(g); 390 391 g.stepBegins(0.0); 392 g.addNode("A"); 393 g.addNode("B"); 394 g.stepBegins(1.0); 395 g.addNode("C"); 396 397 timeline.end(); 398 399 System.out.printf("############\n"); 400 System.out.printf("# Play :\n"); 401 timeline.play(); 402 System.out.printf("############\n"); 403 System.out.printf("# Playback :\n"); 404 timeline.playback(); 405 System.out.printf("############\n"); 406 System.out.printf("# Sequence :\n"); 407 int i = 0; 408 for (Graph it : timeline) { 409 System.out.printf(" Graph#%d %s\n", i, toString(it)); 410 } 411 System.out.printf("############\n"); 412 } 413 414 private static String toString(Graph g) { 415 StringBuilder buffer = new StringBuilder(); 416 buffer.append("id=\"").append(g.getId()).append("\" node={"); 417 418 for (Node n : g) 419 buffer.append("\"").append(n.getId()).append("\", "); 420 buffer.append("}, edges={"); 421 for (Edge e : g.getEachEdge()) 422 buffer.append("\"").append(e.getId()).append("\":\"") 423 .append(e.getSourceNode().getId()).append("\"--\"") 424 .append(e.getTargetNode().getId()).append("\", "); 425 buffer.append("}"); 426 427 return buffer.toString(); 428 } 429}