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.graph.implementations;
033
034import java.io.IOException;
035import java.lang.reflect.Array;
036import java.util.ArrayList;
037import java.util.Collection;
038import java.util.HashMap;
039import java.util.Iterator;
040import java.util.LinkedList;
041import java.util.Map;
042import java.util.concurrent.locks.ReentrantLock;
043
044import org.graphstream.graph.Edge;
045import org.graphstream.graph.EdgeFactory;
046import org.graphstream.graph.EdgeRejectedException;
047import org.graphstream.graph.Element;
048import org.graphstream.graph.ElementNotFoundException;
049import org.graphstream.graph.Graph;
050import org.graphstream.graph.IdAlreadyInUseException;
051import org.graphstream.graph.Node;
052import org.graphstream.graph.NodeFactory;
053import org.graphstream.stream.AttributeSink;
054import org.graphstream.stream.ElementSink;
055import org.graphstream.stream.GraphParseException;
056import org.graphstream.stream.GraphReplay;
057import org.graphstream.stream.Sink;
058import org.graphstream.stream.file.FileSink;
059import org.graphstream.stream.file.FileSource;
060import org.graphstream.ui.swingViewer.Viewer;
061
062public class Graphs {
063
064        public static Graph unmutableGraph(Graph g) {
065                return null;
066        }
067
068        /**
069         * Synchronizes a graph. The returned graph can be accessed and modified by
070         * several threads. You lose genericity in methods returning edge or node
071         * because each element (graph, nodes and edges) is wrapped into a
072         * synchronized wrapper which breaks original elements class.
073         * 
074         * @param g
075         *            the graph to synchronize
076         * @return a synchronized wrapper for g
077         */
078        public static Graph synchronizedGraph(Graph g) {
079                return new SynchronizedGraph(g);
080        }
081
082        /**
083         * Merge several graphs in one. A new graph is created, that will contain
084         * the result. The method will try to create a graph of the same class that
085         * the first graph to merge (it needs to have a constructor with a String).
086         * Else, a MultiGraph is used.
087         * 
088         * @param graphs
089         *            graphs to merge
090         * @return merge result
091         */
092        public static Graph merge(Graph... graphs) {
093                if (graphs == null)
094                        return new DefaultGraph("void-merge");
095
096                String id = "merge";
097
098                for (Graph g : graphs)
099                        id += "-" + g.getId();
100
101                Graph result;
102
103                try {
104                        Class<? extends Graph> cls = graphs[0].getClass();
105                        result = cls.getConstructor(String.class).newInstance(id);
106                } catch (Exception e) {
107                        System.err.printf("*** WARNING *** can not create a graph of %s\n",
108                                        graphs[0].getClass().getName());
109
110                        result = new MultiGraph(id);
111                }
112
113                mergeIn(result, graphs);
114
115                return result;
116        }
117
118        /**
119         * Merge several graphs in one. The first parameter is the graph in which
120         * the other graphs will be merged.
121         * 
122         * @param result
123         *            destination graph.
124         * @param graphs
125         *            all graphs that will be merged in result.
126         */
127        public static void mergeIn(Graph result, Graph... graphs) {
128                boolean strict = result.isStrict();
129                GraphReplay replay = new GraphReplay(String.format("replay-%x",
130                                System.nanoTime()));
131
132                replay.addSink(result);
133                result.setStrict(false);
134
135                if (graphs != null)
136                        for (Graph g : graphs)
137                                replay.replay(g);
138
139                replay.removeSink(result);
140                result.setStrict(strict);
141        }
142
143        /**
144         * Clone a given graph with same node/edge structure and same attributes.
145         * 
146         * @param g
147         *            the graph to clone
148         * @return a copy of g
149         */
150        public static Graph clone(Graph g) {
151                Graph copy;
152
153                try {
154                        Class<? extends Graph> cls = g.getClass();
155                        copy = cls.getConstructor(String.class).newInstance(g.getId());
156                } catch (Exception e) {
157                        System.err.printf("*** WARNING *** can not create a graph of %s\n",
158                                        g.getClass().getName());
159
160                        copy = new AdjacencyListGraph(g.getId());
161                }
162
163                copyAttributes(g, copy);
164
165                for (int i = 0; i < g.getNodeCount(); i++) {
166                        Node source = g.getNode(i);
167                        Node target = copy.addNode(source.getId());
168
169                        copyAttributes(source, target);
170                }
171
172                for (int i = 0; i < g.getEdgeCount(); i++) {
173                        Edge source = g.getEdge(i);
174                        Edge target = copy.addEdge(source.getId(), source.getSourceNode()
175                                        .getId(), source.getTargetNode().getId(), source
176                                        .isDirected());
177
178                        copyAttributes(source, target);
179                }
180
181                return copy;
182        }
183
184        /**
185         * 
186         * @param source
187         * @param target
188         */
189        public static void copyAttributes(Element source, Element target) {
190                for (String key : source.getAttributeKeySet()) {
191                        Object value = source.getAttribute(key);
192                        value = checkedArrayOrCollectionCopy(value);
193
194                        target.setAttribute(key, value);
195                }
196        }
197
198        @SuppressWarnings({ "unchecked", "rawtypes" })
199        private static Object checkedArrayOrCollectionCopy(Object o) {
200                if (o == null)
201                        return null;
202
203                if (o.getClass().isArray()) {
204
205                        Object c = Array.newInstance(o.getClass().getComponentType(),
206                                        Array.getLength(o));
207
208                        for (int i = 0; i < Array.getLength(o); i++) {
209                                Object t = checkedArrayOrCollectionCopy(Array.get(o, i));
210                                Array.set(c, i, t);
211                        }
212
213                        return c;
214                }
215
216                if (Collection.class.isAssignableFrom(o.getClass())) {
217                        Collection<?> t;
218
219                        try {
220                                t = (Collection<?>) o.getClass().newInstance();
221                                t.addAll((Collection) o);
222
223                                return t;
224                        } catch (InstantiationException e) {
225                                e.printStackTrace();
226                        } catch (IllegalAccessException e) {
227                                e.printStackTrace();
228                        }
229                }
230
231                return o;
232        }
233
234        static class SynchronizedElement<U extends Element> implements Element {
235
236                private final ReentrantLock attributeLock;
237                protected final U wrappedElement;
238
239                SynchronizedElement(U e) {
240                        this.wrappedElement = e;
241                        this.attributeLock = new ReentrantLock();
242                }
243
244                public void addAttribute(String attribute, Object... values) {
245                        attributeLock.lock();
246                        wrappedElement.addAttribute(attribute, values);
247                        attributeLock.unlock();
248                }
249
250                public void addAttributes(Map<String, Object> attributes) {
251                        attributeLock.lock();
252                        wrappedElement.addAttributes(attributes);
253                        attributeLock.unlock();
254                }
255
256                public void changeAttribute(String attribute, Object... values) {
257                        attributeLock.lock();
258                        wrappedElement.changeAttribute(attribute, values);
259                        attributeLock.unlock();
260                }
261
262                public void clearAttributes() {
263                        attributeLock.lock();
264                        wrappedElement.clearAttributes();
265                        attributeLock.unlock();
266                }
267
268                public Object[] getArray(String key) {
269                        Object[] o;
270
271                        attributeLock.lock();
272                        o = wrappedElement.getArray(key);
273                        attributeLock.unlock();
274
275                        return o;
276                }
277
278                public <T> T getAttribute(String key) {
279                        T o;
280
281                        attributeLock.lock();
282                        o = wrappedElement.getAttribute(key);
283                        attributeLock.unlock();
284
285                        return o;
286                }
287
288                public <T> T getAttribute(String key, Class<T> clazz) {
289                        T o;
290
291                        attributeLock.lock();
292                        o = wrappedElement.getAttribute(key, clazz);
293                        attributeLock.unlock();
294
295                        return o;
296                }
297
298                public int getAttributeCount() {
299                        int c;
300
301                        attributeLock.lock();
302                        c = wrappedElement.getAttributeCount();
303                        attributeLock.unlock();
304
305                        return c;
306                }
307
308                public Iterator<String> getAttributeKeyIterator() {
309                        return getAttributeKeySet().iterator();
310                }
311
312                public Collection<String> getAttributeKeySet() {
313                        ArrayList<String> o;
314                        Iterator<String> it;
315
316                        attributeLock.lock();
317
318                        o = new ArrayList<String>(wrappedElement.getAttributeCount());
319                        it = wrappedElement.getAttributeKeyIterator();
320
321                        while (it.hasNext())
322                                o.add(it.next());
323
324                        attributeLock.unlock();
325
326                        return o;
327                }
328                
329                public Iterable<String> getEachAttributeKey() {
330                        return getAttributeKeySet();
331                }
332
333                public <T> T getFirstAttributeOf(String... keys) {
334                        T o;
335
336                        attributeLock.lock();
337                        o = wrappedElement.getFirstAttributeOf(keys);
338                        attributeLock.unlock();
339
340                        return o;
341                }
342
343                public <T> T getFirstAttributeOf(Class<T> clazz, String... keys) {
344                        T o;
345
346                        attributeLock.lock();
347                        o = wrappedElement.getFirstAttributeOf(clazz, keys);
348                        attributeLock.unlock();
349
350                        return o;
351                }
352
353                public HashMap<?, ?> getHash(String key) {
354                        HashMap<?, ?> o;
355
356                        attributeLock.lock();
357                        o = wrappedElement.getHash(key);
358                        attributeLock.unlock();
359
360                        return o;
361                }
362
363                public String getId() {
364                        return wrappedElement.getId();
365                }
366
367                public int getIndex() {
368                        return wrappedElement.getIndex();
369                }
370
371                public CharSequence getLabel(String key) {
372                        CharSequence o;
373
374                        attributeLock.lock();
375                        o = wrappedElement.getLabel(key);
376                        attributeLock.unlock();
377
378                        return o;
379                }
380
381                public double getNumber(String key) {
382                        double o;
383
384                        attributeLock.lock();
385                        o = wrappedElement.getNumber(key);
386                        attributeLock.unlock();
387
388                        return o;
389                }
390
391                public ArrayList<? extends Number> getVector(String key) {
392                        ArrayList<? extends Number> o;
393
394                        attributeLock.lock();
395                        o = wrappedElement.getVector(key);
396                        attributeLock.unlock();
397
398                        return o;
399                }
400
401                public boolean hasArray(String key) {
402                        boolean b;
403
404                        attributeLock.lock();
405                        b = wrappedElement.hasArray(key);
406                        attributeLock.unlock();
407
408                        return b;
409                }
410
411                public boolean hasAttribute(String key) {
412                        boolean b;
413
414                        attributeLock.lock();
415                        b = wrappedElement.hasAttribute(key);
416                        attributeLock.unlock();
417
418                        return b;
419                }
420
421                public boolean hasAttribute(String key, Class<?> clazz) {
422                        boolean b;
423
424                        attributeLock.lock();
425                        b = wrappedElement.hasAttribute(key, clazz);
426                        attributeLock.unlock();
427
428                        return b;
429                }
430
431                public boolean hasHash(String key) {
432                        boolean b;
433
434                        attributeLock.lock();
435                        b = wrappedElement.hasHash(key);
436                        attributeLock.unlock();
437
438                        return b;
439                }
440
441                public boolean hasLabel(String key) {
442                        boolean b;
443
444                        attributeLock.lock();
445                        b = wrappedElement.hasLabel(key);
446                        attributeLock.unlock();
447
448                        return b;
449                }
450
451                public boolean hasNumber(String key) {
452                        boolean b;
453
454                        attributeLock.lock();
455                        b = wrappedElement.hasNumber(key);
456                        attributeLock.unlock();
457
458                        return b;
459                }
460
461                public boolean hasVector(String key) {
462                        boolean b;
463
464                        attributeLock.lock();
465                        b = wrappedElement.hasVector(key);
466                        attributeLock.unlock();
467
468                        return b;
469                }
470
471                public void removeAttribute(String attribute) {
472                        attributeLock.lock();
473                        wrappedElement.removeAttribute(attribute);
474                        attributeLock.unlock();
475                }
476
477                public void setAttribute(String attribute, Object... values) {
478                        attributeLock.lock();
479                        wrappedElement.setAttribute(attribute, values);
480                        attributeLock.unlock();
481                }               
482        }
483
484        static class SynchronizedGraph extends SynchronizedElement<Graph> implements
485                        Graph {
486
487                final ReentrantLock elementLock;
488                final HashMap<String, Node> synchronizedNodes;
489                final HashMap<String, Edge> synchronizedEdges;
490
491                SynchronizedGraph(Graph g) {
492                        super(g);
493
494                        elementLock = new ReentrantLock();
495                        synchronizedNodes = new HashMap<String, Node>();
496                        synchronizedEdges = new HashMap<String, Edge>();
497
498                        for (Node n : g.getEachNode())
499                                synchronizedNodes.put(n.getId(), new SynchronizedNode(this, n));
500
501                        for (Edge e : g.getEachEdge())
502                                synchronizedEdges.put(e.getId(), new SynchronizedEdge(this, e));
503                }
504
505                @SuppressWarnings("unchecked")
506                public <T extends Edge> T addEdge(String id, String node1, String node2)
507                                throws IdAlreadyInUseException, ElementNotFoundException,
508                                EdgeRejectedException {
509                        T e;
510                        Edge se;
511
512                        elementLock.lock();
513
514                        e = wrappedElement.addEdge(id, node1, node2);
515                        se = new SynchronizedEdge(this, e);
516                        synchronizedEdges.put(id, se);
517
518                        elementLock.unlock();
519
520                        return (T) se;
521                }
522
523                @SuppressWarnings("unchecked")
524                public <T extends Edge> T addEdge(String id, String from, String to,
525                                boolean directed) throws IdAlreadyInUseException,
526                                ElementNotFoundException {
527                        T e;
528                        Edge se;
529
530                        elementLock.lock();
531
532                        e = wrappedElement.addEdge(id, from, to, directed);
533                        se = new SynchronizedEdge(this, e);
534                        synchronizedEdges.put(id, se);
535
536                        elementLock.unlock();
537
538                        return (T) se;
539                }
540
541                @SuppressWarnings("unchecked")
542                public <T extends Edge> T addEdge(String id, int index1, int index2) {
543                        T e;
544                        Edge se;
545
546                        elementLock.lock();
547
548                        e = wrappedElement.addEdge(id, index1, index2);
549                        se = new SynchronizedEdge(this, e);
550                        synchronizedEdges.put(id, se);
551
552                        elementLock.unlock();
553
554                        return (T) se;
555                }
556
557                @SuppressWarnings("unchecked")
558                public <T extends Edge> T addEdge(String id, int fromIndex,
559                                int toIndex, boolean directed) {
560                        T e;
561                        Edge se;
562
563                        elementLock.lock();
564
565                        e = wrappedElement.addEdge(id, fromIndex, toIndex, directed);
566                        se = new SynchronizedEdge(this, e);
567                        synchronizedEdges.put(id, se);
568
569                        elementLock.unlock();
570
571                        return (T) se;
572                }
573
574                @SuppressWarnings("unchecked")
575                public <T extends Edge> T addEdge(String id, Node node1, Node node2) {
576                        T e;
577                        Edge se;
578                        final Node unsyncNode1, unsyncNode2;
579
580                        unsyncNode1 = ((SynchronizedElement<Node>) node1).wrappedElement;
581                        unsyncNode2 = ((SynchronizedElement<Node>) node2).wrappedElement;
582
583                        elementLock.lock();
584
585                        e = wrappedElement.addEdge(id, unsyncNode1, unsyncNode2);
586                        se = new SynchronizedEdge(this, e);
587                        synchronizedEdges.put(id, se);
588
589                        elementLock.unlock();
590
591                        return (T) se;
592                }
593
594                @SuppressWarnings("unchecked")
595                public <T extends Edge> T addEdge(String id, Node from, Node to,
596                                boolean directed) {
597                        T e;
598                        Edge se;
599                        final Node unsyncFrom, unsyncTo;
600
601                        unsyncFrom = ((SynchronizedElement<Node>) from).wrappedElement;
602                        unsyncTo = ((SynchronizedElement<Node>) to).wrappedElement;
603
604                        elementLock.lock();
605
606                        e = wrappedElement.addEdge(id, unsyncFrom, unsyncTo, directed);
607                        se = new SynchronizedEdge(this, e);
608                        synchronizedEdges.put(id, se);
609
610                        elementLock.unlock();
611
612                        return (T) se;
613                }
614
615                @SuppressWarnings("unchecked")
616                public <T extends Node> T addNode(String id)
617                                throws IdAlreadyInUseException {
618                        T n;
619                        Node sn;
620
621                        elementLock.lock();
622
623                        n = wrappedElement.addNode(id);
624                        sn = new SynchronizedNode(this, n);
625                        synchronizedNodes.put(id, sn);
626
627                        elementLock.unlock();
628
629                        return (T) sn;
630                }
631
632                public Iterable<AttributeSink> attributeSinks() {
633                        LinkedList<AttributeSink> sinks = new LinkedList<AttributeSink>();
634
635                        elementLock.lock();
636
637                        for (AttributeSink as : wrappedElement.attributeSinks())
638                                sinks.add(as);
639
640                        elementLock.unlock();
641
642                        return sinks;
643                }
644
645                public void clear() {
646                        elementLock.lock();
647                        wrappedElement.clear();
648                        elementLock.unlock();
649                }
650
651                public Viewer display() {
652                        return wrappedElement.display();
653                }
654
655                public Viewer display(boolean autoLayout) {
656                        return wrappedElement.display(autoLayout);
657                }
658
659                public EdgeFactory<? extends Edge> edgeFactory() {
660                        return wrappedElement.edgeFactory();
661                }
662
663                public Iterable<ElementSink> elementSinks() {
664                        LinkedList<ElementSink> sinks = new LinkedList<ElementSink>();
665
666                        elementLock.lock();
667
668                        for (ElementSink es : wrappedElement.elementSinks())
669                                sinks.add(es);
670
671                        elementLock.unlock();
672
673                        return sinks;
674                }
675
676                public Iterable<Edge> getEachEdge() {
677                        LinkedList<Edge> edges;
678
679                        elementLock.lock();
680                        edges = new LinkedList<Edge>(synchronizedEdges.values());
681                        elementLock.unlock();
682
683                        return edges;
684                }
685
686                public Iterable<Node> getEachNode() {
687                        LinkedList<Node> nodes;
688
689                        elementLock.lock();
690                        nodes = new LinkedList<Node>(synchronizedNodes.values());
691                        elementLock.unlock();
692
693                        return nodes;
694                }
695
696                @SuppressWarnings("unchecked")
697                public <T extends Edge> T getEdge(String id) {
698                        T e;
699
700                        elementLock.lock();
701                        e = (T) synchronizedEdges.get(id);
702                        elementLock.unlock();
703
704                        return e;
705                }
706
707                public <T extends Edge> T getEdge(int index)
708                                throws IndexOutOfBoundsException {
709                        Edge e;
710
711                        elementLock.lock();
712                        e = wrappedElement.getEdge(index);
713                        elementLock.unlock();
714
715                        return e == null ? null : this.<T> getEdge(e.getId());
716                }
717
718                public int getEdgeCount() {
719                        int c;
720
721                        elementLock.lock();
722                        c = synchronizedEdges.size();
723                        elementLock.unlock();
724
725                        return c;
726                }
727
728                public Iterator<Edge> getEdgeIterator() {
729                        return getEdgeSet().iterator();
730                }
731
732                public Collection<Edge> getEdgeSet() {
733                        LinkedList<Edge> l;
734
735                        elementLock.lock();
736                        l = new LinkedList<Edge>(synchronizedEdges.values());
737                        elementLock.unlock();
738
739                        return l;
740                }
741
742                @SuppressWarnings("unchecked")
743                public <T extends Node> T getNode(String id) {
744                        T n;
745
746                        elementLock.lock();
747                        n = (T) synchronizedNodes.get(id);
748                        elementLock.unlock();
749
750                        return n;
751                }
752
753                public <T extends Node> T getNode(int index)
754                                throws IndexOutOfBoundsException {
755                        Node n;
756
757                        elementLock.lock();
758                        n = wrappedElement.getNode(index);
759                        elementLock.unlock();
760
761                        return n == null ? null : this.<T> getNode(n.getId());
762                }
763
764                public int getNodeCount() {
765                        int c;
766
767                        elementLock.lock();
768                        c = synchronizedNodes.size();
769                        elementLock.unlock();
770
771                        return c;
772                }
773
774                public Iterator<Node> getNodeIterator() {
775                        return getNodeSet().iterator();
776                }
777
778                public Collection<Node> getNodeSet() {
779                        LinkedList<Node> l;
780
781                        elementLock.lock();
782                        l = new LinkedList<Node>(synchronizedNodes.values());
783                        elementLock.unlock();
784
785                        return l;
786                }
787
788                public double getStep() {
789                        double s;
790
791                        elementLock.lock();
792                        s = wrappedElement.getStep();
793                        elementLock.unlock();
794
795                        return s;
796                }
797
798                public boolean isAutoCreationEnabled() {
799                        return wrappedElement.isAutoCreationEnabled();
800                }
801
802                public boolean isStrict() {
803                        return wrappedElement.isStrict();
804                }
805
806                public NodeFactory<? extends Node> nodeFactory() {
807                        return wrappedElement.nodeFactory();
808                }
809
810                public boolean nullAttributesAreErrors() {
811                        return wrappedElement.nullAttributesAreErrors();
812                }
813
814                public void read(String filename) throws IOException,
815                                GraphParseException, ElementNotFoundException {
816                        elementLock.lock();
817                        wrappedElement.read(filename);
818                        elementLock.unlock();
819                }
820
821                public void read(FileSource input, String filename) throws IOException,
822                                GraphParseException {
823                        elementLock.lock();
824                        wrappedElement.read(input, filename);
825                        elementLock.unlock();
826                }
827
828                @SuppressWarnings("unchecked")
829                public <T extends Edge> T removeEdge(String from, String to)
830                                throws ElementNotFoundException {
831                        T e;
832                        Edge se;
833
834                        elementLock.lock();
835                        e = wrappedElement.removeEdge(from, to);
836                        se = synchronizedEdges.remove(e.getId());
837                        elementLock.unlock();
838
839                        return (T) se;
840                }
841
842                @SuppressWarnings("unchecked")
843                public <T extends Edge> T removeEdge(String id)
844                                throws ElementNotFoundException {
845                        T e;
846                        Edge se;
847
848                        elementLock.lock();
849                        e = wrappedElement.removeEdge(id);
850                        se = synchronizedEdges.remove(e.getId());
851                        elementLock.unlock();
852
853                        return (T) se;
854                }
855
856                @SuppressWarnings("unchecked")
857                public <T extends Edge> T removeEdge(int index) {
858                        T e;
859                        Edge se;
860
861                        elementLock.lock();
862                        e = wrappedElement.removeEdge(index);
863                        se = synchronizedEdges.remove(e.getId());
864                        elementLock.unlock();
865
866                        return (T) se;
867                }
868
869                @SuppressWarnings("unchecked")
870                public <T extends Edge> T removeEdge(int fromIndex, int toIndex) {
871                        T e;
872                        Edge se;
873
874                        elementLock.lock();
875                        e = wrappedElement.removeEdge(fromIndex, toIndex);
876                        se = synchronizedEdges.remove(e.getId());
877                        elementLock.unlock();
878
879                        return (T) se;
880                }
881
882                @SuppressWarnings("unchecked")
883                public <T extends Edge> T removeEdge(Node node1, Node node2) {
884                        T e;
885                        Edge se;
886
887                        if (node1 instanceof SynchronizedNode)
888                                node1 = ((SynchronizedNode) node1).wrappedElement;
889
890                        if (node2 instanceof SynchronizedNode)
891                                node2 = ((SynchronizedNode) node1).wrappedElement;
892
893                        elementLock.lock();
894                        e = wrappedElement.removeEdge(node1, node2);
895                        se = synchronizedEdges.remove(e.getId());
896                        elementLock.unlock();
897
898                        return (T) se;
899                }
900
901                @SuppressWarnings("unchecked")
902                public <T extends Edge> T removeEdge(Edge edge) {
903                        T e;
904                        Edge se;
905
906                        if (edge instanceof SynchronizedEdge)
907                                edge = ((SynchronizedEdge) edge).wrappedElement;
908
909                        elementLock.lock();
910                        e = wrappedElement.removeEdge(edge);
911                        se = synchronizedEdges.remove(e.getId());
912                        elementLock.unlock();
913
914                        return (T) se;
915                }
916
917                @SuppressWarnings("unchecked")
918                public <T extends Node> T removeNode(String id)
919                                throws ElementNotFoundException {
920                        T n;
921                        Node sn;
922
923                        elementLock.lock();
924                        n = wrappedElement.removeNode(id);
925                        sn = synchronizedNodes.remove(n.getId());
926                        elementLock.unlock();
927
928                        return (T) sn;
929                }
930
931                @SuppressWarnings("unchecked")
932                public <T extends Node> T removeNode(int index) {
933                        T n;
934                        Node sn;
935
936                        elementLock.lock();
937                        n = wrappedElement.removeNode(index);
938                        sn = synchronizedNodes.remove(n.getId());
939                        elementLock.unlock();
940
941                        return (T) sn;
942                }
943
944                @SuppressWarnings("unchecked")
945                public <T extends Node> T removeNode(Node node) {
946                        T n;
947                        Node sn;
948
949                        if (node instanceof SynchronizedNode)
950                                node = ((SynchronizedNode) node).wrappedElement;
951
952                        elementLock.lock();
953                        n = wrappedElement.removeNode(node);
954                        sn = synchronizedNodes.remove(n.getId());
955                        elementLock.unlock();
956
957                        return (T) sn;
958                }
959
960                public void setAutoCreate(boolean on) {
961                        elementLock.lock();
962                        wrappedElement.setAutoCreate(on);
963                        elementLock.unlock();
964                }
965
966                public void setEdgeFactory(EdgeFactory<? extends Edge> ef) {
967                        elementLock.lock();
968                        wrappedElement.setEdgeFactory(ef);
969                        elementLock.unlock();
970                }
971
972                public void setNodeFactory(NodeFactory<? extends Node> nf) {
973                        elementLock.lock();
974                        wrappedElement.setNodeFactory(nf);
975                        elementLock.unlock();
976                }
977
978                public void setNullAttributesAreErrors(boolean on) {
979                        elementLock.lock();
980                        wrappedElement.setNullAttributesAreErrors(on);
981                        elementLock.unlock();
982                }
983
984                public void setStrict(boolean on) {
985                        elementLock.lock();
986                        wrappedElement.setStrict(on);
987                        elementLock.unlock();
988                }
989
990                public void stepBegins(double time) {
991                        elementLock.lock();
992                        wrappedElement.stepBegins(time);
993                        elementLock.unlock();
994                }
995
996                public void write(String filename) throws IOException {
997                        elementLock.lock();
998                        wrappedElement.write(filename);
999                        elementLock.unlock();
1000                }
1001
1002                public void write(FileSink output, String filename) throws IOException {
1003                        elementLock.lock();
1004                        wrappedElement.write(output, filename);
1005                        elementLock.unlock();
1006                }
1007
1008                public void addAttributeSink(AttributeSink sink) {
1009                        elementLock.lock();
1010                        wrappedElement.addAttributeSink(sink);
1011                        elementLock.unlock();
1012                }
1013
1014                public void addElementSink(ElementSink sink) {
1015                        elementLock.lock();
1016                        wrappedElement.addElementSink(sink);
1017                        elementLock.unlock();
1018                }
1019
1020                public void addSink(Sink sink) {
1021                        elementLock.lock();
1022                        wrappedElement.addSink(sink);
1023                        elementLock.unlock();
1024                }
1025
1026                public void clearAttributeSinks() {
1027                        elementLock.lock();
1028                        wrappedElement.clearAttributeSinks();
1029                        elementLock.unlock();
1030                }
1031
1032                public void clearElementSinks() {
1033                        elementLock.lock();
1034                        wrappedElement.clearElementSinks();
1035                        elementLock.unlock();
1036                }
1037
1038                public void clearSinks() {
1039                        elementLock.lock();
1040                        wrappedElement.clearSinks();
1041                        elementLock.unlock();
1042                }
1043
1044                public void removeAttributeSink(AttributeSink sink) {
1045                        elementLock.lock();
1046                        wrappedElement.removeAttributeSink(sink);
1047                        elementLock.unlock();
1048                }
1049
1050                public void removeElementSink(ElementSink sink) {
1051                        elementLock.lock();
1052                        wrappedElement.removeElementSink(sink);
1053                        elementLock.unlock();
1054                }
1055
1056                public void removeSink(Sink sink) {
1057                        elementLock.lock();
1058                        wrappedElement.removeSink(sink);
1059                        elementLock.unlock();
1060                }
1061
1062                public void edgeAttributeAdded(String sourceId, long timeId,
1063                                String edgeId, String attribute, Object value) {
1064                        wrappedElement.edgeAttributeAdded(sourceId, timeId, edgeId,
1065                                        attribute, value);
1066                }
1067
1068                public void edgeAttributeChanged(String sourceId, long timeId,
1069                                String edgeId, String attribute, Object oldValue,
1070                                Object newValue) {
1071                        wrappedElement.edgeAttributeChanged(sourceId, timeId, edgeId,
1072                                        attribute, oldValue, newValue);
1073                }
1074
1075                public void edgeAttributeRemoved(String sourceId, long timeId,
1076                                String edgeId, String attribute) {
1077                        wrappedElement.edgeAttributeRemoved(sourceId, timeId, edgeId,
1078                                        attribute);
1079                }
1080
1081                public void graphAttributeAdded(String sourceId, long timeId,
1082                                String attribute, Object value) {
1083                        wrappedElement.graphAttributeAdded(sourceId, timeId, attribute,
1084                                        value);
1085                }
1086
1087                public void graphAttributeChanged(String sourceId, long timeId,
1088                                String attribute, Object oldValue, Object newValue) {
1089                        wrappedElement.graphAttributeChanged(sourceId, timeId, attribute,
1090                                        oldValue, newValue);
1091                }
1092
1093                public void graphAttributeRemoved(String sourceId, long timeId,
1094                                String attribute) {
1095                        wrappedElement.graphAttributeRemoved(sourceId, timeId, attribute);
1096                }
1097
1098                public void nodeAttributeAdded(String sourceId, long timeId,
1099                                String nodeId, String attribute, Object value) {
1100                        wrappedElement.nodeAttributeAdded(sourceId, timeId, nodeId,
1101                                        attribute, value);
1102                }
1103
1104                public void nodeAttributeChanged(String sourceId, long timeId,
1105                                String nodeId, String attribute, Object oldValue,
1106                                Object newValue) {
1107                        wrappedElement.nodeAttributeChanged(sourceId, timeId, nodeId,
1108                                        attribute, oldValue, newValue);
1109                }
1110
1111                public void nodeAttributeRemoved(String sourceId, long timeId,
1112                                String nodeId, String attribute) {
1113                        wrappedElement.nodeAttributeRemoved(sourceId, timeId, nodeId,
1114                                        attribute);
1115                }
1116
1117                public void edgeAdded(String sourceId, long timeId, String edgeId,
1118                                String fromNodeId, String toNodeId, boolean directed) {
1119                        wrappedElement.edgeAdded(sourceId, timeId, edgeId, fromNodeId,
1120                                        toNodeId, directed);
1121                }
1122
1123                public void edgeRemoved(String sourceId, long timeId, String edgeId) {
1124                        wrappedElement.edgeRemoved(sourceId, timeId, edgeId);
1125                }
1126
1127                public void graphCleared(String sourceId, long timeId) {
1128                        wrappedElement.graphCleared(sourceId, timeId);
1129                }
1130
1131                public void nodeAdded(String sourceId, long timeId, String nodeId) {
1132                        wrappedElement.nodeAdded(sourceId, timeId, nodeId);
1133                }
1134
1135                public void nodeRemoved(String sourceId, long timeId, String nodeId) {
1136                        wrappedElement.nodeRemoved(sourceId, timeId, nodeId);
1137                }
1138
1139                public void stepBegins(String sourceId, long timeId, double step) {
1140                        wrappedElement.stepBegins(sourceId, timeId, step);
1141                }
1142
1143                public Iterator<Node> iterator() {
1144                        return getEachNode().iterator();
1145                }
1146        }
1147
1148        static class SynchronizedNode extends SynchronizedElement<Node> implements
1149                        Node {
1150
1151                private final SynchronizedGraph sg;
1152                private final ReentrantLock elementLock;
1153
1154                SynchronizedNode(SynchronizedGraph sg, Node n) {
1155                        super(n);
1156
1157                        this.sg = sg;
1158                        this.elementLock = new ReentrantLock();
1159                }
1160
1161                public Iterator<Node> getBreadthFirstIterator() {
1162                        return getBreadthFirstIterator(false);
1163                }
1164
1165                public Iterator<Node> getBreadthFirstIterator(boolean directed) {
1166                        LinkedList<Node> l = new LinkedList<Node>();
1167                        Iterator<Node> it;
1168
1169                        elementLock.lock();
1170                        sg.elementLock.lock();
1171
1172                        it = wrappedElement.getBreadthFirstIterator(directed);
1173
1174                        while (it.hasNext())
1175                                l.add(sg.getNode(it.next().getIndex()));
1176
1177                        sg.elementLock.unlock();
1178                        elementLock.unlock();
1179
1180                        return l.iterator();
1181                }
1182
1183                public int getDegree() {
1184                        int d;
1185
1186                        elementLock.lock();
1187                        d = wrappedElement.getDegree();
1188                        elementLock.unlock();
1189
1190                        return d;
1191                }
1192
1193                public Iterator<Node> getDepthFirstIterator() {
1194                        return getDepthFirstIterator(false);
1195                }
1196
1197                public Iterator<Node> getDepthFirstIterator(boolean directed) {
1198                        LinkedList<Node> l = new LinkedList<Node>();
1199                        Iterator<Node> it;
1200
1201                        elementLock.lock();
1202                        sg.elementLock.lock();
1203
1204                        it = wrappedElement.getDepthFirstIterator();
1205
1206                        while (it.hasNext())
1207                                l.add(sg.getNode(it.next().getIndex()));
1208
1209                        sg.elementLock.unlock();
1210                        elementLock.unlock();
1211
1212                        return l.iterator();
1213                }
1214
1215                public Iterable<Edge> getEachEdge() {
1216                        return getEdgeSet();
1217                }
1218
1219                public Iterable<Edge> getEachEnteringEdge() {
1220                        return getEnteringEdgeSet();
1221                }
1222
1223                public Iterable<Edge> getEachLeavingEdge() {
1224                        return getLeavingEdgeSet();
1225                }
1226
1227                public <T extends Edge> T getEdge(int i) {
1228                        T e;
1229
1230                        elementLock.lock();
1231                        e = sg.getEdge(wrappedElement.getEdge(i).getIndex());
1232                        elementLock.unlock();
1233
1234                        return e;
1235                }
1236
1237                public <T extends Edge> T getEnteringEdge(int i) {
1238                        T e;
1239
1240                        elementLock.lock();
1241                        e = sg.getEdge(wrappedElement.getEnteringEdge(i).getIndex());
1242                        elementLock.unlock();
1243
1244                        return e;
1245                }
1246
1247                public <T extends Edge> T getLeavingEdge(int i) {
1248                        T e;
1249
1250                        elementLock.lock();
1251                        e = sg.getEdge(wrappedElement.getLeavingEdge(i).getIndex());
1252                        elementLock.unlock();
1253
1254                        return e;
1255                }
1256
1257                public <T extends Edge> T getEdgeBetween(String id) {
1258                        T e;
1259
1260                        elementLock.lock();
1261                        e = sg.getEdge(wrappedElement.getEdgeBetween(id).getIndex());
1262                        elementLock.unlock();
1263
1264                        return e;
1265                }
1266
1267                public <T extends Edge> T getEdgeBetween(Node n) {
1268                        T e;
1269
1270                        elementLock.lock();
1271                        e = sg.getEdge(wrappedElement.getEdgeBetween(n).getIndex());
1272                        elementLock.unlock();
1273
1274                        return e;
1275                }
1276
1277                public <T extends Edge> T getEdgeBetween(int index) {
1278                        T e;
1279
1280                        elementLock.lock();
1281                        e = sg.getEdge(wrappedElement.getEdgeBetween(index).getIndex());
1282                        elementLock.unlock();
1283
1284                        return e;
1285                }
1286
1287                public <T extends Edge> T getEdgeFrom(String id) {
1288                        T e;
1289
1290                        elementLock.lock();
1291                        e = sg.getEdge(wrappedElement.getEdgeFrom(id).getIndex());
1292                        elementLock.unlock();
1293
1294                        return e;
1295                }
1296
1297                public <T extends Edge> T getEdgeFrom(Node n) {
1298                        T e;
1299
1300                        elementLock.lock();
1301                        e = sg.getEdge(wrappedElement.getEdgeFrom(n).getIndex());
1302                        elementLock.unlock();
1303
1304                        return e;
1305                }
1306
1307                public <T extends Edge> T getEdgeFrom(int index) {
1308                        T e;
1309
1310                        elementLock.lock();
1311                        e = sg.getEdge(wrappedElement.getEdgeFrom(index).getIndex());
1312                        elementLock.unlock();
1313
1314                        return e;
1315                }
1316
1317                public Iterator<Edge> getEdgeIterator() {
1318                        return getEdgeSet().iterator();
1319                }
1320
1321                public Collection<Edge> getEdgeSet() {
1322                        ArrayList<Edge> l;
1323                        Iterator<Edge> it;
1324
1325                        elementLock.lock();
1326
1327                        l = new ArrayList<Edge>(wrappedElement.getDegree());
1328                        it = wrappedElement.getEachEdge().iterator();
1329
1330                        while (it.hasNext())
1331                                l.add(sg.getEdge(it.next().getIndex()));
1332
1333                        elementLock.unlock();
1334
1335                        return l;
1336                }
1337
1338                public <T extends Edge> T getEdgeToward(String id) {
1339                        T e;
1340
1341                        elementLock.lock();
1342                        e = sg.getEdge(wrappedElement.getEdgeToward(id).getIndex());
1343                        elementLock.unlock();
1344
1345                        return e;
1346                }
1347
1348                public <T extends Edge> T getEdgeToward(Node n) {
1349                        T e;
1350
1351                        elementLock.lock();
1352                        e = sg.getEdge(wrappedElement.getEdgeToward(n).getIndex());
1353                        elementLock.unlock();
1354
1355                        return e;
1356                }
1357
1358                public <T extends Edge> T getEdgeToward(int index) {
1359                        T e;
1360
1361                        elementLock.lock();
1362                        e = sg.getEdge(wrappedElement.getEdgeToward(index).getIndex());
1363                        elementLock.unlock();
1364
1365                        return e;
1366                }
1367
1368                public Iterator<Edge> getEnteringEdgeIterator() {
1369                        return getEnteringEdgeSet().iterator();
1370                }
1371
1372                public Collection<Edge> getEnteringEdgeSet() {
1373                        ArrayList<Edge> l;
1374                        Iterator<Edge> it;
1375
1376                        elementLock.lock();
1377                        sg.elementLock.lock();
1378
1379                        l = new ArrayList<Edge>(wrappedElement.getInDegree());
1380                        it = wrappedElement.getEachEnteringEdge().iterator();
1381
1382                        while (it.hasNext())
1383                                l.add(sg.getEdge(it.next().getIndex()));
1384
1385                        sg.elementLock.unlock();
1386                        elementLock.unlock();
1387
1388                        return l;
1389                }
1390
1391                public Graph getGraph() {
1392                        return sg;
1393                }
1394
1395                public int getInDegree() {
1396                        int d;
1397
1398                        elementLock.lock();
1399                        d = wrappedElement.getInDegree();
1400                        elementLock.unlock();
1401
1402                        return d;
1403                }
1404
1405                public Iterator<Edge> getLeavingEdgeIterator() {
1406                        return getLeavingEdgeSet().iterator();
1407                }
1408
1409                public Collection<Edge> getLeavingEdgeSet() {
1410                        ArrayList<Edge> l;
1411                        Iterator<Edge> it;
1412
1413                        elementLock.lock();
1414                        sg.elementLock.lock();
1415
1416                        l = new ArrayList<Edge>(wrappedElement.getOutDegree());
1417                        it = wrappedElement.<Edge> getEachLeavingEdge().iterator();
1418
1419                        while (it.hasNext())
1420                                l.add(sg.getEdge(it.next().getIndex()));
1421
1422                        sg.elementLock.unlock();
1423                        elementLock.unlock();
1424
1425                        return l;
1426                }
1427
1428                public Iterator<Node> getNeighborNodeIterator() {
1429                        ArrayList<Node> l;
1430                        Iterator<Node> it;
1431
1432                        elementLock.lock();
1433                        sg.elementLock.lock();
1434
1435                        l = new ArrayList<Node>(wrappedElement.getDegree());
1436                        it = wrappedElement.getNeighborNodeIterator();
1437
1438                        while (it.hasNext())
1439                                l.add(sg.getNode(it.next().getIndex()));
1440
1441                        sg.elementLock.unlock();
1442                        elementLock.unlock();
1443
1444                        return l.iterator();
1445                }
1446
1447                public int getOutDegree() {
1448                        int d;
1449
1450                        elementLock.lock();
1451                        d = wrappedElement.getOutDegree();
1452                        elementLock.unlock();
1453
1454                        return d;
1455                }
1456
1457                public boolean hasEdgeBetween(String id) {
1458                        boolean b;
1459
1460                        elementLock.lock();
1461                        b = wrappedElement.hasEdgeBetween(id);
1462                        elementLock.unlock();
1463
1464                        return b;
1465                }
1466
1467                public boolean hasEdgeBetween(Node node) {
1468                        boolean b;
1469
1470                        elementLock.lock();
1471                        b = wrappedElement.hasEdgeBetween(node);
1472                        elementLock.unlock();
1473
1474                        return b;
1475                }
1476
1477                public boolean hasEdgeBetween(int index) {
1478                        boolean b;
1479
1480                        elementLock.lock();
1481                        b = wrappedElement.hasEdgeBetween(index);
1482                        elementLock.unlock();
1483
1484                        return b;
1485                }
1486
1487                public boolean hasEdgeFrom(String id) {
1488                        boolean b;
1489
1490                        elementLock.lock();
1491                        b = wrappedElement.hasEdgeFrom(id);
1492                        elementLock.unlock();
1493
1494                        return b;
1495                }
1496
1497                public boolean hasEdgeFrom(Node node) {
1498                        boolean b;
1499
1500                        elementLock.lock();
1501                        b = wrappedElement.hasEdgeFrom(node);
1502                        elementLock.unlock();
1503
1504                        return b;
1505                }
1506
1507                public boolean hasEdgeFrom(int index) {
1508                        boolean b;
1509
1510                        elementLock.lock();
1511                        b = wrappedElement.hasEdgeFrom(index);
1512                        elementLock.unlock();
1513
1514                        return b;
1515                }
1516
1517                public boolean hasEdgeToward(String id) {
1518                        boolean b;
1519
1520                        elementLock.lock();
1521                        b = wrappedElement.hasEdgeToward(id);
1522                        elementLock.unlock();
1523
1524                        return b;
1525                }
1526
1527                public boolean hasEdgeToward(Node node) {
1528                        boolean b;
1529
1530                        elementLock.lock();
1531                        b = wrappedElement.hasEdgeToward(node);
1532                        elementLock.unlock();
1533
1534                        return b;
1535                }
1536
1537                public boolean hasEdgeToward(int index) {
1538                        boolean b;
1539
1540                        elementLock.lock();
1541                        b = wrappedElement.hasEdgeToward(index);
1542                        elementLock.unlock();
1543
1544                        return b;
1545                }
1546
1547                public Iterator<Edge> iterator() {
1548                        return getEdgeSet().iterator();
1549                }
1550        }
1551
1552        static class SynchronizedEdge extends SynchronizedElement<Edge> implements
1553                        Edge {
1554
1555                final SynchronizedGraph sg;
1556
1557                SynchronizedEdge(SynchronizedGraph sg, Edge e) {
1558                        super(e);
1559                        this.sg = sg;
1560                }
1561
1562                public <T extends Node> T getNode0() {
1563                        T n;
1564
1565                        sg.elementLock.lock();
1566                        n = sg.getNode(wrappedElement.getNode0().getIndex());
1567                        sg.elementLock.unlock();
1568
1569                        return n;
1570                }
1571
1572                public <T extends Node> T getNode1() {
1573                        T n;
1574
1575                        sg.elementLock.lock();
1576                        n = sg.getNode(wrappedElement.getNode1().getIndex());
1577                        sg.elementLock.unlock();
1578
1579                        return n;
1580                }
1581
1582                public <T extends Node> T getOpposite(Node node) {
1583                        T n;
1584
1585                        if (node instanceof SynchronizedNode)
1586                                node = ((SynchronizedNode) node).wrappedElement;
1587
1588                        sg.elementLock.lock();
1589                        n = sg.getNode(wrappedElement.getOpposite(node).getIndex());
1590                        sg.elementLock.unlock();
1591
1592                        return n;
1593                }
1594
1595                public <T extends Node> T getSourceNode() {
1596                        T n;
1597
1598                        sg.elementLock.lock();
1599                        n = sg.getNode(wrappedElement.getSourceNode().getIndex());
1600                        sg.elementLock.unlock();
1601
1602                        return n;
1603                }
1604
1605                public <T extends Node> T getTargetNode() {
1606                        T n;
1607
1608                        sg.elementLock.lock();
1609                        n = sg.getNode(wrappedElement.getTargetNode().getIndex());
1610                        sg.elementLock.unlock();
1611
1612                        return n;
1613                }
1614
1615                public boolean isDirected() {
1616                        return wrappedElement.isDirected();
1617                }
1618
1619                public boolean isLoop() {
1620                        return wrappedElement.isLoop();
1621                }
1622        }
1623}