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 * GraphStream is a library whose purpose is to handle static or dynamic
010 * graph, create them from scratch, file or any source and display them.
011 * 
012 * This program is free software distributed under the terms of two licenses, the
013 * CeCILL-C license that fits European law, and the GNU Lesser General Public
014 * License. You can  use, modify and/ or redistribute the software under the terms
015 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
016 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
017 * the Free Software Foundation, either version 3 of the License, or (at your
018 * option) any later version.
019 * 
020 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
021 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
022 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
023 * 
024 * You should have received a copy of the GNU Lesser General Public License
025 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
026 * 
027 * The fact that you are presently reading this means that you have had
028 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
029 */
030package org.graphstream.util;
031
032import java.io.ByteArrayInputStream;
033import java.io.ByteArrayOutputStream;
034import java.io.IOException;
035import java.lang.reflect.Array;
036import java.util.LinkedList;
037import java.util.zip.GZIPInputStream;
038import java.util.zip.GZIPOutputStream;
039
040import org.graphstream.graph.Edge;
041import org.graphstream.graph.Element;
042import org.graphstream.graph.ElementNotFoundException;
043import org.graphstream.graph.Graph;
044import org.graphstream.graph.Node;
045import org.graphstream.graph.implementations.AdjacencyListGraph;
046import org.graphstream.stream.Sink;
047import org.graphstream.stream.file.FileSinkDGS;
048import org.graphstream.stream.file.FileSourceDGS;
049
050public class GraphDiff {
051        protected static enum ElementType {
052                NODE, EDGE, GRAPH
053        }
054
055        private Bridge bridge;
056        private final LinkedList<Event> events;
057
058        /**
059         * Create a new empty diff.
060         */
061        public GraphDiff() {
062                this.events = new LinkedList<Event>();
063                this.bridge = null;
064        }
065
066        /**
067         * Create a diff between two graphs.
068         * 
069         * @param g1
070         * @param g2
071         */
072        public GraphDiff(Graph g1, Graph g2) {
073                this();
074
075                if (g2.getNodeCount() == 0 && g2.getEdgeCount() == 0
076                                && g2.getAttributeCount() == 0
077                                && (g1.getNodeCount() > 0 || g1.getEdgeCount() > 0)) {
078                        events.add(new GraphCleared(g1));
079                } else {
080                        for (int idx = 0; idx < g2.getNodeCount(); idx++) {
081                                Node n2 = g2.getNode(idx);
082                                Node n1 = g1.getNode(n2.getId());
083
084                                if (n1 == null)
085                                        events.add(new NodeAdded(n2.getId()));
086
087                                attributeDiff(ElementType.NODE, n1, n2);
088                        }
089
090                        for (int idx = 0; idx < g1.getNodeCount(); idx++) {
091                                Node n1 = g1.getNode(idx);
092                                Node n2 = g2.getNode(n1.getId());
093
094                                if (n2 == null) {
095                                        attributeDiff(ElementType.NODE, n1, n2);
096                                        events.add(new NodeRemoved(n1.getId()));
097                                }
098                        }
099
100                        for (int idx = 0; idx < g2.getEdgeCount(); idx++) {
101                                Edge e2 = g2.getEdge(idx);
102                                Edge e1 = g1.getEdge(e2.getId());
103
104                                if (e1 == null)
105                                        events.add(new EdgeAdded(e2.getId(), e2.getSourceNode()
106                                                        .getId(), e2.getTargetNode().getId(), e2
107                                                        .isDirected()));
108
109                                attributeDiff(ElementType.EDGE, e1, e2);
110                        }
111
112                        for (int idx = 0; idx < g1.getEdgeCount(); idx++) {
113                                Edge e1 = g1.getEdge(idx);
114                                Edge e2 = g2.getEdge(e1.getId());
115
116                                if (e2 == null) {
117                                        attributeDiff(ElementType.EDGE, e1, e2);
118                                        events.add(new EdgeRemoved(e1.getId(), e1.getSourceNode()
119                                                        .getId(), e1.getTargetNode().getId(), e1
120                                                        .isDirected()));
121                                }
122                        }
123
124                        attributeDiff(ElementType.GRAPH, g1, g2);
125                }
126        }
127
128        /**
129         * Start to record changes. If a record is already started, then it will be
130         * ended.
131         * 
132         * @param g
133         *            the graph to start listening for changes.
134         */
135        public void start(Graph g) {
136                if (bridge != null)
137                        end();
138
139                bridge = new Bridge(g);
140        }
141
142        /**
143         * Stop to record changes. If there is no record, calling this method has no
144         * effect.
145         */
146        public void end() {
147                if (bridge != null) {
148                        bridge.end();
149                        bridge = null;
150                }
151        }
152
153        /**
154         * Clear all recorded changes.
155         */
156        public void reset() {
157                events.clear();
158        }
159
160        /**
161         * Considering this object is a diff between g1 and g2, calling this method
162         * will applied changes on g1 such that g1 will look like g2.
163         * 
164         * @param g1
165         */
166        public void apply(Sink g1) {
167                String sourceId = String.format("GraphDiff@%x", System.nanoTime());
168                apply(sourceId, g1);
169        }
170
171        public void apply(String sourceId, Sink g1) {
172                for (int i = 0; i < events.size(); i++)
173                        events.get(i).apply(sourceId, i, g1);
174        }
175
176        /**
177         * Considering this object is a diff between g1 and g2, calling this method
178         * will applied changes on g2 such that g2 will look like g1.
179         * 
180         * @param g2
181         */
182        public void reverse(Sink g2) {
183                String sourceId = String.format("GraphDiff@%x", System.nanoTime());
184                reverse(sourceId, g2);
185        }
186
187        public void reverse(String sourceId, Sink g2) {
188                for (int i = events.size() - 1; i >= 0; i--)
189                        events.get(i).reverse(sourceId, events.size() + 1 - i, g2);
190        }
191
192        private void attributeDiff(ElementType type, Element e1, Element e2) {
193                if (e1 == null && e2 == null)
194                        return;
195                else if (e1 == null) {
196                        for (String key : e2.getAttributeKeySet())
197                                events.add(new AttributeAdded(type, e2.getId(), key, e2
198                                                .getAttribute(key)));
199                } else if (e2 == null) {
200                        for (String key : e1.getAttributeKeySet())
201                                events.add(new AttributeRemoved(type, e1.getId(), key, e1
202                                                .getAttribute(key)));
203                } else {
204                        for (String key : e2.getAttributeKeySet()) {
205                                if (e1.hasAttribute(key)) {
206                                        Object o1 = e1.getAttribute(key);
207                                        Object o2 = e2.getAttribute(key);
208
209                                        if (!(o1 == null ? o2 == null : o1.equals(o2)))
210                                                events.add(new AttributeChanged(type, e1.getId(), key,
211                                                                o2, o1));
212                                } else
213                                        events.add(new AttributeAdded(type, e1.getId(), key, e2
214                                                        .getAttribute(key)));
215                        }
216
217                        for (String key : e1.getAttributeKeySet()) {
218                                if (!e2.hasAttribute(key))
219                                        events.add(new AttributeRemoved(type, e1.getId(), key, e1
220                                                        .getAttribute(key)));
221                        }
222                }
223        }
224
225        /*
226         * (non-Javadoc)
227         * 
228         * @see java.lang.Object#toString()
229         */
230        @Override
231        public String toString() {
232                StringBuilder buffer = new StringBuilder();
233
234                for (int i = 0; i < events.size(); i++)
235                        buffer.append(events.get(i).toString()).append("\n");
236
237                return buffer.toString();
238        }
239
240        protected abstract class Event {
241                /**
242                 * Apply this event on a given graph.
243                 * 
244                 * @param g
245                 *            the graph on which the action should be applied
246                 */
247                abstract void apply(String sourceId, long timeId, Sink g);
248
249                /**
250                 * Apply the dual event on a given graph.
251                 * 
252                 * @param g
253                 *            the graph on which the dual action should be applied.
254                 */
255                abstract void reverse(String sourceId, long timeId, Sink g);
256        }
257
258        protected class NodeAdded extends Event {
259                String nodeId;
260
261                public NodeAdded(String nodeId) {
262                        this.nodeId = nodeId;
263                }
264
265                /*
266                 * (non-Javadoc)
267                 * 
268                 * @see
269                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
270                 * Graph)
271                 */
272                public void apply(String sourceId, long timeId, Sink g) {
273                        g.nodeAdded(sourceId, timeId, nodeId);
274                }
275
276                /*
277                 * (non-Javadoc)
278                 * 
279                 * @see
280                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
281                 * .Graph)
282                 */
283                public void reverse(String sourceId, long timeId, Sink g) {
284                        g.nodeRemoved(sourceId, timeId, nodeId);
285                }
286
287                /*
288                 * (non-Javadoc)
289                 * 
290                 * @see java.lang.Object#toString()
291                 */
292                @Override
293                public String toString() {
294                        return String.format("an \"%s\"", nodeId);
295                }
296        }
297
298        protected class NodeRemoved extends NodeAdded {
299                public NodeRemoved(String nodeId) {
300                        super(nodeId);
301                }
302
303                /*
304                 * (non-Javadoc)
305                 * 
306                 * @see
307                 * org.graphstream.util.GraphDiff.NodeAdded#apply(org.graphstream.graph
308                 * .Graph)
309                 */
310                public void apply(String sourceId, long timeId, Sink g) {
311                        super.reverse(sourceId, timeId, g);
312                }
313
314                /*
315                 * (non-Javadoc)
316                 * 
317                 * @see
318                 * org.graphstream.util.GraphDiff.NodeAdded#reverse(org.graphstream.
319                 * graph.Graph)
320                 */
321                public void reverse(String sourceId, long timeId, Sink g) {
322                        super.apply(sourceId, timeId, g);
323                }
324
325                /*
326                 * (non-Javadoc)
327                 * 
328                 * @see org.graphstream.util.GraphDiff.NodeAdded#toString()
329                 */
330                @Override
331                public String toString() {
332                        return String.format("dn \"%s\"", nodeId);
333                }
334        }
335
336        protected abstract class ElementEvent extends Event {
337                ElementType type;
338                String elementId;
339
340                protected ElementEvent(ElementType type, String elementId) {
341                        this.type = type;
342                        this.elementId = elementId;
343                }
344
345                protected Element getElement(Graph g) {
346                        Element e;
347
348                        switch (type) {
349                        case NODE:
350                                e = g.getNode(elementId);
351                                break;
352                        case EDGE:
353                                e = g.getEdge(elementId);
354                                break;
355                        case GRAPH:
356                                e = g;
357                                break;
358                        default:
359                                e = null;
360                        }
361
362                        if (e == null)
363                                throw new ElementNotFoundException();
364
365                        return e;
366                }
367
368                protected String toStringHeader() {
369                        String header;
370
371                        switch (type) {
372                        case NODE:
373                                header = "cn";
374                                break;
375                        case EDGE:
376                                header = "ce";
377                                break;
378                        case GRAPH:
379                                header = "cg";
380                                break;
381                        default:
382                                header = "??";
383                                break;
384                        }
385
386                        return String.format("%s \"%s\"", header, elementId);
387                }
388
389                protected String toStringValue(Object o) {
390                        if (o == null)
391                                return "null";
392                        else if (o instanceof String)
393                                return "\"" + o.toString() + "\"";
394                        else if (o instanceof Number)
395                                return o.toString();
396                        else
397                                return o.toString();
398                }
399        }
400
401        protected class AttributeAdded extends ElementEvent {
402                String attrId;
403                Object value;
404
405                public AttributeAdded(ElementType type, String elementId,
406                                String attrId, Object value) {
407                        super(type, elementId);
408
409                        this.attrId = attrId;
410                        this.value = value;
411
412                        if (value != null && value.getClass().isArray()
413                                        && Array.getLength(value) > 0) {
414                                Object o = Array.newInstance(Array.get(value, 0).getClass(),
415                                                Array.getLength(value));
416
417                                for (int i = 0; i < Array.getLength(value); i++)
418                                        Array.set(o, i, Array.get(value, i));
419
420                                this.value = o;
421                        }
422                }
423
424                /*
425                 * (non-Javadoc)
426                 * 
427                 * @see
428                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
429                 * Graph)
430                 */
431                public void apply(String sourceId, long timeId, Sink g) {
432                        switch (type) {
433                        case NODE:
434                                g.nodeAttributeAdded(sourceId, timeId, elementId, attrId, value);
435                                break;
436                        case EDGE:
437                                g.edgeAttributeAdded(sourceId, timeId, elementId, attrId, value);
438                                break;
439                        case GRAPH:
440                                g.graphAttributeAdded(sourceId, timeId, attrId, value);
441                                break;
442                        }
443                }
444
445                /*
446                 * (non-Javadoc)
447                 * 
448                 * @see
449                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
450                 * .Graph)
451                 */
452                public void reverse(String sourceId, long timeId, Sink g) {
453                        switch (type) {
454                        case NODE:
455                                g.nodeAttributeRemoved(sourceId, timeId, elementId, attrId);
456                                break;
457                        case EDGE:
458                                g.edgeAttributeRemoved(sourceId, timeId, elementId, attrId);
459                                break;
460                        case GRAPH:
461                                g.graphAttributeRemoved(sourceId, timeId, attrId);
462                                break;
463                        }
464                }
465
466                /*
467                 * (non-Javadoc)
468                 * 
469                 * @see java.lang.Object#toString()
470                 */
471                @Override
472                public String toString() {
473                        return String.format("%s +\"%s\":%s", toStringHeader(), attrId,
474                                        toStringValue(value));
475                }
476        }
477
478        protected class AttributeChanged extends ElementEvent {
479                String attrId;
480                Object newValue;
481                Object oldValue;
482
483                public AttributeChanged(ElementType type, String elementId,
484                                String attrId, Object newValue, Object oldValue) {
485                        super(type, elementId);
486
487                        this.attrId = attrId;
488                        this.newValue = newValue;
489                        this.oldValue = oldValue;
490
491                        if (newValue != null && newValue.getClass().isArray()
492                                        && Array.getLength(newValue) > 0) {
493                                Object o = Array.newInstance(Array.get(newValue, 0).getClass(),
494                                                Array.getLength(newValue));
495
496                                for (int i = 0; i < Array.getLength(newValue); i++)
497                                        Array.set(o, i, Array.get(newValue, i));
498
499                                this.newValue = o;
500                        }
501
502                        if (oldValue != null && oldValue.getClass().isArray()
503                                        && Array.getLength(oldValue) > 0) {
504                                Object o = Array.newInstance(Array.get(oldValue, 0).getClass(),
505                                                Array.getLength(oldValue));
506
507                                for (int i = 0; i < Array.getLength(oldValue); i++)
508                                        Array.set(o, i, Array.get(oldValue, i));
509
510                                this.oldValue = o;
511                        }
512                }
513
514                /*
515                 * (non-Javadoc)
516                 * 
517                 * @see
518                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
519                 * Graph)
520                 */
521                public void apply(String sourceId, long timeId, Sink g) {
522                        switch (type) {
523                        case NODE:
524                                g.nodeAttributeChanged(sourceId, timeId, elementId, attrId,
525                                                oldValue, newValue);
526                                break;
527                        case EDGE:
528                                g.edgeAttributeChanged(sourceId, timeId, elementId, attrId,
529                                                oldValue, newValue);
530                                break;
531                        case GRAPH:
532                                g.graphAttributeChanged(sourceId, timeId, attrId, oldValue,
533                                                newValue);
534                                break;
535                        }
536                }
537
538                /*
539                 * (non-Javadoc)
540                 * 
541                 * @see
542                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
543                 * .Graph)
544                 */
545                public void reverse(String sourceId, long timeId, Sink g) {
546                        switch (type) {
547                        case NODE:
548                                g.nodeAttributeChanged(sourceId, timeId, elementId, attrId,
549                                                newValue, oldValue);
550                                break;
551                        case EDGE:
552                                g.edgeAttributeChanged(sourceId, timeId, elementId, attrId,
553                                                newValue, oldValue);
554                                break;
555                        case GRAPH:
556                                g.graphAttributeChanged(sourceId, timeId, attrId, newValue,
557                                                oldValue);
558                                break;
559                        }
560                }
561
562                /*
563                 * (non-Javadoc)
564                 * 
565                 * @see java.lang.Object#toString()
566                 */
567                @Override
568                public String toString() {
569                        return String.format("%s \"%s\":%s", toStringHeader(), attrId,
570                                        toStringValue(newValue));
571                }
572        }
573
574        protected class AttributeRemoved extends ElementEvent {
575                String attrId;
576                Object oldValue;
577
578                public AttributeRemoved(ElementType type, String elementId,
579                                String attrId, Object oldValue) {
580                        super(type, elementId);
581
582                        this.attrId = attrId;
583                        this.oldValue = oldValue;
584                }
585
586                /*
587                 * (non-Javadoc)
588                 * 
589                 * @see
590                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
591                 * Graph)
592                 */
593                public void apply(String sourceId, long timeId, Sink g) {
594                        switch (type) {
595                        case NODE:
596                                g.nodeAttributeRemoved(sourceId, timeId, elementId, attrId);
597                                break;
598                        case EDGE:
599                                g.edgeAttributeRemoved(sourceId, timeId, elementId, attrId);
600                                break;
601                        case GRAPH:
602                                g.graphAttributeRemoved(sourceId, timeId, attrId);
603                                break;
604                        }
605                }
606
607                /*
608                 * (non-Javadoc)
609                 * 
610                 * @see
611                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
612                 * .Graph)
613                 */
614                public void reverse(String sourceId, long timeId, Sink g) {
615                        switch (type) {
616                        case NODE:
617                                g.nodeAttributeAdded(sourceId, timeId, elementId, attrId,
618                                                oldValue);
619                                break;
620                        case EDGE:
621                                g.edgeAttributeAdded(sourceId, timeId, elementId, attrId,
622                                                oldValue);
623                                break;
624                        case GRAPH:
625                                g.graphAttributeAdded(sourceId, timeId, attrId, oldValue);
626                                break;
627                        }
628                }
629
630                /*
631                 * (non-Javadoc)
632                 * 
633                 * @see java.lang.Object#toString()
634                 */
635                @Override
636                public String toString() {
637                        return String.format("%s -\"%s\":%s", toStringHeader(), attrId,
638                                        toStringValue(oldValue));
639                }
640        }
641
642        protected class EdgeAdded extends Event {
643                String edgeId;
644                String source, target;
645                boolean directed;
646
647                public EdgeAdded(String edgeId, String source, String target,
648                                boolean directed) {
649                        this.edgeId = edgeId;
650                        this.source = source;
651                        this.target = target;
652                        this.directed = directed;
653                }
654
655                /*
656                 * (non-Javadoc)
657                 * 
658                 * @see
659                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
660                 * Graph)
661                 */
662                public void apply(String sourceId, long timeId, Sink g) {
663                        g.edgeAdded(sourceId, timeId, edgeId, source, target, directed);
664                }
665
666                /*
667                 * (non-Javadoc)
668                 * 
669                 * @see
670                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
671                 * .Graph)
672                 */
673                public void reverse(String sourceId, long timeId, Sink g) {
674                        g.edgeRemoved(sourceId, timeId, edgeId);
675                }
676
677                /*
678                 * (non-Javadoc)
679                 * 
680                 * @see java.lang.Object#toString()
681                 */
682                @Override
683                public String toString() {
684                        return String.format("ae \"%s\" \"%s\" %s \"%s\"", edgeId, source,
685                                        directed ? ">" : "--", target);
686                }
687        }
688
689        protected class EdgeRemoved extends EdgeAdded {
690                public EdgeRemoved(String edgeId, String source, String target,
691                                boolean directed) {
692                        super(edgeId, source, target, directed);
693                }
694
695                /*
696                 * (non-Javadoc)
697                 * 
698                 * @see
699                 * org.graphstream.util.GraphDiff.EdgeAdded#apply(org.graphstream.graph
700                 * .Graph)
701                 */
702                public void apply(String sourceId, long timeId, Sink g) {
703                        super.reverse(sourceId, timeId, g);
704                }
705
706                /*
707                 * (non-Javadoc)
708                 * 
709                 * @see
710                 * org.graphstream.util.GraphDiff.EdgeAdded#reverse(org.graphstream.
711                 * graph.Graph)
712                 */
713                public void reverse(String sourceId, long timeId, Sink g) {
714                        super.apply(sourceId, timeId, g);
715                }
716
717                /*
718                 * (non-Javadoc)
719                 * 
720                 * @see org.graphstream.util.GraphDiff.EdgeAdded#toString()
721                 */
722                @Override
723                public String toString() {
724                        return String.format("de \"%s\"", edgeId);
725                }
726        }
727
728        protected class StepBegins extends Event {
729                double newStep, oldStep;
730
731                public StepBegins(double oldStep, double newStep) {
732                        this.newStep = newStep;
733                        this.oldStep = oldStep;
734                }
735
736                /*
737                 * (non-Javadoc)
738                 * 
739                 * @see
740                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
741                 * Graph)
742                 */
743                public void apply(String sourceId, long timeId, Sink g) {
744                        g.stepBegins(sourceId, timeId, newStep);
745                }
746
747                /*
748                 * (non-Javadoc)
749                 * 
750                 * @see
751                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
752                 * .Graph)
753                 */
754                public void reverse(String sourceId, long timeId, Sink g) {
755                        g.stepBegins(sourceId, timeId, oldStep);
756                }
757
758                @Override
759                public String toString() {
760                        return String.format("st %f", newStep);
761                }
762        }
763
764        protected class GraphCleared extends Event {
765                byte[] data;
766
767                public GraphCleared(Graph g) {
768                        this.data = null;
769
770                        try {
771                                FileSinkDGS sink = new FileSinkDGS();
772                                ByteArrayOutputStream bytes = new ByteArrayOutputStream();
773                                GZIPOutputStream out = new GZIPOutputStream(bytes);
774
775                                sink.writeAll(g, out);
776                                out.flush();
777                                out.close();
778
779                                this.data = bytes.toByteArray();
780                        } catch (IOException e) {
781                                e.printStackTrace();
782                        }
783                }
784
785                /*
786                 * (non-Javadoc)
787                 * 
788                 * @see
789                 * org.graphstream.util.GraphDiff.Event#apply(org.graphstream.graph.
790                 * Graph)
791                 */
792                public void apply(String sourceId, long timeId, Sink g) {
793                        g.graphCleared(sourceId, timeId);
794                }
795
796                /*
797                 * (non-Javadoc)
798                 * 
799                 * @see
800                 * org.graphstream.util.GraphDiff.Event#reverse(org.graphstream.graph
801                 * .Graph)
802                 */
803                public void reverse(String sourceId, long timeId, Sink g) {
804                        try {
805                                ByteArrayInputStream bytes = new ByteArrayInputStream(this.data);
806                                GZIPInputStream in = new GZIPInputStream(bytes);
807                                FileSourceDGS dgs = new FileSourceDGS();
808
809                                dgs.addSink(g);
810                                dgs.readAll(in);
811                                dgs.removeSink(g);
812
813                                in.close();
814                        } catch (IOException e) {
815                                e.printStackTrace();
816                        }
817                }
818
819                /*
820                 * (non-Javadoc)
821                 * 
822                 * @see java.lang.Object#toString()
823                 */
824                @Override
825                public String toString() {
826                        return "cl";
827                }
828        }
829
830        private class Bridge implements Sink {
831                Graph g;
832
833                Bridge(Graph g) {
834
835                        this.g = g;
836                        g.addSink(this);
837                }
838
839                void end() {
840                        g.removeSink(this);
841                }
842
843                /*
844                 * (non-Javadoc)
845                 * 
846                 * @see
847                 * org.graphstream.stream.AttributeSink#graphAttributeAdded(java.lang
848                 * .String, long, java.lang.String, java.lang.Object)
849                 */
850                public void graphAttributeAdded(String sourceId, long timeId,
851                                String attribute, Object value) {
852                        Event e;
853                        e = new AttributeAdded(ElementType.GRAPH, null, attribute, value);
854                        events.add(e);
855                }
856
857                /*
858                 * (non-Javadoc)
859                 * 
860                 * @see
861                 * org.graphstream.stream.AttributeSink#graphAttributeChanged(java.lang
862                 * .String, long, java.lang.String, java.lang.Object, java.lang.Object)
863                 */
864                public void graphAttributeChanged(String sourceId, long timeId,
865                                String attribute, Object oldValue, Object newValue) {
866                        Event e;
867                        e = new AttributeChanged(ElementType.GRAPH, null, attribute,
868                                        newValue, g.getAttribute(attribute));
869                        events.add(e);
870                }
871
872                /*
873                 * (non-Javadoc)
874                 * 
875                 * @see
876                 * org.graphstream.stream.AttributeSink#graphAttributeRemoved(java.lang
877                 * .String, long, java.lang.String)
878                 */
879                public void graphAttributeRemoved(String sourceId, long timeId,
880                                String attribute) {
881                        Event e;
882                        e = new AttributeRemoved(ElementType.GRAPH, null, attribute,
883                                        g.getAttribute(attribute));
884                        events.add(e);
885                }
886
887                /*
888                 * (non-Javadoc)
889                 * 
890                 * @see
891                 * org.graphstream.stream.AttributeSink#nodeAttributeAdded(java.lang
892                 * .String, long, java.lang.String, java.lang.String, java.lang.Object)
893                 */
894                public void nodeAttributeAdded(String sourceId, long timeId,
895                                String nodeId, String attribute, Object value) {
896                        Event e;
897                        e = new AttributeAdded(ElementType.NODE, nodeId, attribute, value);
898                        events.add(e);
899                }
900
901                /*
902                 * (non-Javadoc)
903                 * 
904                 * @see
905                 * org.graphstream.stream.AttributeSink#nodeAttributeChanged(java.lang
906                 * .String, long, java.lang.String, java.lang.String, java.lang.Object,
907                 * java.lang.Object)
908                 */
909                public void nodeAttributeChanged(String sourceId, long timeId,
910                                String nodeId, String attribute, Object oldValue,
911                                Object newValue) {
912                        Event e;
913                        e = new AttributeChanged(ElementType.NODE, nodeId, attribute,
914                                        newValue, g.getNode(nodeId).getAttribute(attribute));
915                        events.add(e);
916                }
917
918                /*
919                 * (non-Javadoc)
920                 * 
921                 * @see
922                 * org.graphstream.stream.AttributeSink#nodeAttributeRemoved(java.lang
923                 * .String, long, java.lang.String, java.lang.String)
924                 */
925                public void nodeAttributeRemoved(String sourceId, long timeId,
926                                String nodeId, String attribute) {
927                        Event e;
928                        e = new AttributeRemoved(ElementType.NODE, nodeId, attribute, g
929                                        .getNode(nodeId).getAttribute(attribute));
930                        events.add(e);
931                }
932
933                /*
934                 * (non-Javadoc)
935                 * 
936                 * @see
937                 * org.graphstream.stream.AttributeSink#edgeAttributeAdded(java.lang
938                 * .String, long, java.lang.String, java.lang.String, java.lang.Object)
939                 */
940                public void edgeAttributeAdded(String sourceId, long timeId,
941                                String edgeId, String attribute, Object value) {
942                        Event e;
943                        e = new AttributeAdded(ElementType.EDGE, edgeId, attribute, value);
944                        events.add(e);
945                }
946
947                /*
948                 * (non-Javadoc)
949                 * 
950                 * @see
951                 * org.graphstream.stream.AttributeSink#edgeAttributeChanged(java.lang
952                 * .String, long, java.lang.String, java.lang.String, java.lang.Object,
953                 * java.lang.Object)
954                 */
955                public void edgeAttributeChanged(String sourceId, long timeId,
956                                String edgeId, String attribute, Object oldValue,
957                                Object newValue) {
958                        Event e;
959                        e = new AttributeChanged(ElementType.EDGE, edgeId, attribute,
960                                        newValue, g.getEdge(edgeId).getAttribute(attribute));
961                        events.add(e);
962                }
963
964                /*
965                 * (non-Javadoc)
966                 * 
967                 * @see
968                 * org.graphstream.stream.AttributeSink#edgeAttributeRemoved(java.lang
969                 * .String, long, java.lang.String, java.lang.String)
970                 */
971                public void edgeAttributeRemoved(String sourceId, long timeId,
972                                String edgeId, String attribute) {
973                        Event e;
974                        e = new AttributeRemoved(ElementType.EDGE, edgeId, attribute, g
975                                        .getEdge(edgeId).getAttribute(attribute));
976                        events.add(e);
977                }
978
979                /*
980                 * (non-Javadoc)
981                 * 
982                 * @see org.graphstream.stream.ElementSink#nodeAdded(java.lang.String,
983                 * long, java.lang.String)
984                 */
985                public void nodeAdded(String sourceId, long timeId, String nodeId) {
986                        Event e;
987                        e = new NodeAdded(nodeId);
988                        events.add(e);
989                }
990
991                /*
992                 * (non-Javadoc)
993                 * 
994                 * @see org.graphstream.stream.ElementSink#nodeRemoved(java.lang.String,
995                 * long, java.lang.String)
996                 */
997                public void nodeRemoved(String sourceId, long timeId, String nodeId) {
998                        Node n = g.getNode(nodeId);
999
1000                        for (String key : n.getAttributeKeySet())
1001                                nodeAttributeRemoved(sourceId, timeId, nodeId, key);
1002
1003                        Event e;
1004                        e = new NodeRemoved(nodeId);
1005                        events.add(e);
1006                }
1007
1008                /*
1009                 * (non-Javadoc)
1010                 * 
1011                 * @see org.graphstream.stream.ElementSink#edgeAdded(java.lang.String,
1012                 * long, java.lang.String, java.lang.String, java.lang.String, boolean)
1013                 */
1014                public void edgeAdded(String sourceId, long timeId, String edgeId,
1015                                String fromNodeId, String toNodeId, boolean directed) {
1016                        Event e;
1017                        e = new EdgeAdded(edgeId, fromNodeId, toNodeId, directed);
1018                        events.add(e);
1019                }
1020
1021                /*
1022                 * (non-Javadoc)
1023                 * 
1024                 * @see org.graphstream.stream.ElementSink#edgeRemoved(java.lang.String,
1025                 * long, java.lang.String)
1026                 */
1027                public void edgeRemoved(String sourceId, long timeId, String edgeId) {
1028                        Edge edge = g.getEdge(edgeId);
1029
1030                        for (String key : edge.getAttributeKeySet())
1031                                edgeAttributeRemoved(sourceId, timeId, edgeId, key);
1032
1033                        Event e;
1034                        e = new EdgeRemoved(edgeId, edge.getSourceNode().getId(), edge
1035                                        .getTargetNode().getId(), edge.isDirected());
1036                        events.add(e);
1037                }
1038
1039                /*
1040                 * (non-Javadoc)
1041                 * 
1042                 * @see
1043                 * org.graphstream.stream.ElementSink#graphCleared(java.lang.String,
1044                 * long)
1045                 */
1046                public void graphCleared(String sourceId, long timeId) {
1047                        Event e = new GraphCleared(g);
1048                        events.add(e);
1049                }
1050
1051                /*
1052                 * (non-Javadoc)
1053                 * 
1054                 * @see org.graphstream.stream.ElementSink#stepBegins(java.lang.String,
1055                 * long, double)
1056                 */
1057                public void stepBegins(String sourceId, long timeId, double step) {
1058                        Event e = new StepBegins(g.getStep(), step);
1059                        events.add(e);
1060                }
1061        }
1062
1063        public static void main(String... args) throws Exception {
1064                Graph g1 = new AdjacencyListGraph("g1");
1065                Graph g2 = new AdjacencyListGraph("g2");
1066
1067                Node a1 = g1.addNode("A");
1068                a1.addAttribute("attr1", "test");
1069                a1.addAttribute("attr2", 10.0);
1070                a1.addAttribute("attr3", 12);
1071
1072                Node a2 = g2.addNode("A");
1073                a2.addAttribute("attr1", "test1");
1074                a2.addAttribute("attr2", 10.0);
1075                g2.addNode("B");
1076                g2.addNode("C");
1077
1078                GraphDiff diff = new GraphDiff(g2, g1);
1079                System.out.println(diff);
1080        }
1081}