001: /* Copyright (C) 2004 - 2007 db4objects Inc. http://www.db4o.com
002:
003: This file is part of the db4o open source object database.
004:
005: db4o is free software; you can redistribute it and/or modify it under
006: the terms of version 2 of the GNU General Public License as published
007: by the Free Software Foundation and as clarified by db4objects' GPL
008: interpretation policy, available at
009: http://www.db4o.com/about/company/legalpolicies/gplinterpretation/
010: Alternatively you can write to db4objects, Inc., 1900 S Norfolk Street,
011: Suite 350, San Mateo, CA 94403, USA.
012:
013: db4o is distributed in the hope that it will be useful, but WITHOUT ANY
014: WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: for more details.
017:
018: You should have received a copy of the GNU General Public License along
019: with this program; if not, write to the Free Software Foundation, Inc.,
020: 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
021: package EDU.purdue.cs.bloat.util;
022:
023: import java.util.*;
024:
025: /**
026: * Graph represents a graph of nodes with directed edges between them.
027: * GraphNodes are created and are added to the Graph before the edges can be
028: * constructed. Each GraphNode as a unique key associated with it. For instance,
029: * if a Graph represents a control flow graph, each GraphNode would be
030: * associated with a basic block.
031: *
032: * @see #addNode
033: * @see #addEdge
034: *
035: * @see GraphNode
036: * @see EDU.purdue.cs.bloat.cfg.FlowGraph
037: */
038: public class Graph {
039: private NodeMap nodes; // The nodes in this Graph
040:
041: private NodeList preOrder; //
042:
043: private NodeList postOrder;
044:
045: private Collection roots; // The root nodes of this Graph (no
046: // predacessors)
047:
048: private Collection revRoots; // Reverse root nodes of this Graph (no
049: // successors)
050:
051: // These counts are used to determine when certain actions (such as updating
052: // the
053: // roots Collection) should or should not be performed.
054: protected int rootEdgeModCount = 0;
055:
056: protected int revRootEdgeModCount = 0;
057:
058: protected int nodeModCount = 0; // Number of nodes that have been modified
059:
060: protected int edgeModCount = 0; // Number of edges that have been modified
061:
062: protected int removingNode = 0;
063:
064: protected int removingEdge = 0;
065:
066: /**
067: * Constructor.
068: */
069: public Graph() {
070: nodes = new NodeMap();
071: preOrder = null;
072: postOrder = null;
073: roots = null;
074: revRoots = null;
075: }
076:
077: /**
078: * @return The roots of this Graph. That is, the nodes with no predacessors.
079: */
080: public Collection roots() {
081: if ((roots == null) || (rootEdgeModCount != edgeModCount)) {
082: rootEdgeModCount = edgeModCount;
083: roots = new ArrayList();
084: buildRootList(roots, false);
085: }
086:
087: return roots;
088: }
089:
090: /**
091: * @return The reverse roots of this Graph. That is, the nodes with no
092: * successors.
093: */
094: public Collection reverseRoots() {
095: if ((roots == null) || (revRootEdgeModCount != edgeModCount)) {
096: revRootEdgeModCount = edgeModCount;
097: revRoots = new ArrayList();
098: buildRootList(revRoots, true);
099: }
100:
101: return revRoots;
102: }
103:
104: /**
105: * Compile a collection of root nodes in this Graph. If reverse is true, the
106: * collection will contain those nodes with no predacessor nodes. If reverse
107: * is false, the collection will contain those nodes with no sucessor nodes.
108: *
109: * @param c
110: * A Collection that will contain the roots in the graph.
111: * @param reverse
112: * Do we make a reverse traversal of the graph?
113: */
114: private void buildRootList(final Collection c, final boolean reverse) {
115: final HashSet visited = new HashSet(nodes.size() * 2);
116: final ArrayList stack = new ArrayList();
117:
118: final Iterator iter = nodes.values().iterator();
119:
120: while (iter.hasNext()) {
121: final GraphNode node = (GraphNode) iter.next();
122:
123: if (!visited.contains(node)) {
124: visited.add(node);
125: stack.add(node);
126:
127: while (!stack.isEmpty()) {
128: final GraphNode v = (GraphNode) stack.remove(stack
129: .size() - 1);
130: boolean pushed = false;
131:
132: final Iterator preds = reverse ? v.succs.iterator()
133: : v.preds.iterator();
134:
135: while (preds.hasNext()) {
136: final GraphNode w = (GraphNode) preds.next();
137:
138: if (!visited.contains(w)) {
139: visited.add(w);
140: stack.add(w);
141: pushed = true;
142: }
143: }
144:
145: if (!pushed) {
146: c.add(v);
147: }
148: }
149: }
150: }
151: }
152:
153: /**
154: * Return the successors of a given node.
155: */
156: public Collection succs(final GraphNode v) {
157: return new EdgeSet(v, v.succs);
158: }
159:
160: /**
161: * Returns the predacessors of a given node.
162: */
163: public Collection preds(final GraphNode v) {
164: return new EdgeSet(v, v.preds);
165: }
166:
167: /**
168: * Determines whether or not a node v is an ancestor (has a lower pre-order
169: * index and a higher post-order index) of a node w.
170: *
171: * @param v
172: * Candidate ancestor node.
173: * @param w
174: * Candidate descendent node.
175: *
176: * @return True, if v is an ancestor of w.
177: */
178: public boolean isAncestorToDescendent(final GraphNode v,
179: final GraphNode w) {
180: return (preOrderIndex(v) <= preOrderIndex(w))
181: && (postOrderIndex(w) <= postOrderIndex(v));
182: }
183:
184: /**
185: * Returns the index of a given node in a pre-order ordering of this Graph.
186: */
187: public int preOrderIndex(final GraphNode node) {
188: if ((preOrder == null)
189: || (edgeModCount != preOrder.edgeModCount)) {
190: buildLists();
191: }
192:
193: return node.preOrderIndex();
194: }
195:
196: /**
197: * Returns the index of a given node in a post-order ordering of this Graph.
198: */
199: public int postOrderIndex(final GraphNode node) {
200: if ((postOrder == null)
201: || (edgeModCount != postOrder.edgeModCount)) {
202: buildLists();
203: }
204:
205: return node.postOrderIndex();
206: }
207:
208: /**
209: * Returns the nodes in this Graph ordered by their pre-order index.
210: */
211: public List preOrder() {
212: if ((preOrder == null)
213: || (edgeModCount != preOrder.edgeModCount)) {
214: buildLists();
215: }
216:
217: return preOrder;
218: }
219:
220: /**
221: * Return the nodes in this Graph ordered by their post-order index.
222: */
223: public List postOrder() {
224: if ((postOrder == null)
225: || (edgeModCount != postOrder.edgeModCount)) {
226: buildLists();
227: }
228:
229: return postOrder;
230: }
231:
232: /**
233: * Constructs lists of nodes in both pre-order and post-order order.
234: */
235: private void buildLists() {
236: Iterator iter = roots().iterator();
237:
238: preOrder = new NodeList();
239: postOrder = new NodeList();
240:
241: final Set visited = new HashSet();
242:
243: // Calculate the indices of the nodes.
244: while (iter.hasNext()) {
245: final GraphNode root = (GraphNode) iter.next();
246:
247: Assert.isTrue(nodes.containsValue(root),
248: "Graph does not contain " + root);
249:
250: number(root, visited);
251: }
252:
253: // Mark all nodes that were not numbered as having an index of -1. This
254: // information is used when removing unreachable nodes.
255: iter = nodes.values().iterator();
256:
257: while (iter.hasNext()) {
258: final GraphNode node = (GraphNode) iter.next();
259:
260: if (!visited.contains(node)) {
261: node.setPreOrderIndex(-1);
262: node.setPostOrderIndex(-1);
263: } else {
264: Assert.isTrue(node.preOrderIndex() >= 0);
265: Assert.isTrue(node.postOrderIndex() >= 0);
266: }
267: }
268: }
269:
270: /**
271: * Removes all nodes from this Graph that cannot be reached in a pre-order
272: * traversal of the Graph. These nodes have a pre-order index of -1.
273: */
274: public void removeUnreachable() {
275: if ((preOrder == null)
276: || (edgeModCount != preOrder.edgeModCount)) {
277: buildLists();
278: }
279:
280: final Iterator iter = nodes.entrySet().iterator();
281:
282: while (iter.hasNext()) {
283: final Map.Entry e = (Map.Entry) iter.next();
284:
285: final GraphNode v = (GraphNode) e.getValue();
286:
287: if (v.preOrderIndex() == -1) {
288: iter.remove();
289: }
290: }
291: }
292:
293: /**
294: * Sets the pre-order and post-order indices of a node.
295: *
296: * @param node
297: * The node to number.
298: * @param visited
299: * The nodes that have been visited already.
300: */
301: private void number(final GraphNode node, final Set visited) {
302: visited.add(node);
303:
304: // Visit in pre-order
305: node.setPreOrderIndex(preOrder.size());
306: preOrder.addNode(node);
307:
308: final Iterator iter = succs(node).iterator();
309:
310: while (iter.hasNext()) {
311: final GraphNode succ = (GraphNode) iter.next();
312: if (!visited.contains(succ)) {
313: number(succ, visited);
314: }
315: }
316:
317: // Visit in post-order
318: node.setPostOrderIndex(postOrder.size());
319: postOrder.addNode(node);
320: }
321:
322: /**
323: * Insertes a node (and its associated key) into this Graph.
324: *
325: * @param key
326: * A unique value associated with this node. For instance, if
327: * this Graph represented a control flow graph, the key would be
328: * a basic block.
329: * @param node
330: * The node to be added.
331: */
332: // This method is NOT guaranteed to be called whenever a node is added.
333: public void addNode(final Object key, final GraphNode node) {
334: Assert.isTrue(nodes.get(key) == null);
335: nodes.putNodeInMap(key, node);
336: preOrder = null;
337: postOrder = null;
338: nodeModCount++;
339: edgeModCount++;
340: }
341:
342: /**
343: * Returns the node in this Graph with a given key.
344: */
345: public GraphNode getNode(final Object key) {
346: return (GraphNode) nodes.get(key);
347: }
348:
349: /**
350: * Returns a Set of the keys used to uniquely identify the nodes in this
351: * Graph.
352: */
353: public Set keySet() {
354: return nodes.keySet();
355: }
356:
357: /**
358: * Removes a node with a given key from the Graph.
359: *
360: * @param key
361: * The key associated with the node to remove.
362: */
363: // This method is guaranteed to be called whenever a node is deleted.
364: // If removingNode != 0, the node is NOT deleted when this method returns.
365: // It is the callers responsibility to delete the node AFTER this method
366: // is called. An exception will be thrown if the node is not present
367: // in the graph.
368: public void removeNode(final Object key) {
369: final GraphNode node = getNode(key);
370: Assert.isTrue(node != null, "No node for " + key);
371:
372: succs(node).clear();
373: preds(node).clear();
374:
375: if (removingNode == 0) {
376: nodes.removeNodeFromMap(key);
377: } else if (removingNode != 1) {
378: throw new RuntimeException();
379: }
380:
381: // Removing a node invalidates the orderings
382: preOrder = null;
383: postOrder = null;
384:
385: nodeModCount++;
386: edgeModCount++;
387: }
388:
389: /**
390: * Adds a directed edge from node v to node w.
391: *
392: * @param v
393: * Source node.
394: * @param w
395: * Destination node.
396: */
397: // This method is NOT guaranteed to be called whenever an edge is added.
398: public void addEdge(final GraphNode v, final GraphNode w) {
399: Assert.isTrue(nodes.containsValue(v), "Graph does not contain "
400: + v);
401: Assert.isTrue(nodes.containsValue(w), "Graph does not contain "
402: + w);
403:
404: succs(v).add(w);
405: edgeModCount++;
406: }
407:
408: // This method is guaranteed to be called whenever an edge is deleted.
409: // If removingEdge != 0, the edge is NOT deleted when this method returns.
410: // It is the callers responsibility to delete the edge AFTER this method
411: // is called. An exception will be thrown if the edge is not present
412: // in the graph.
413: public void removeEdge(final GraphNode v, final GraphNode w) {
414: Assert.isTrue(nodes.containsValue(v), "Graph does not contain "
415: + v);
416: Assert.isTrue(nodes.containsValue(w), "Graph does not contain "
417: + w);
418: Assert.isTrue(v.succs().contains(w));
419:
420: if (removingEdge == 0) {
421: succs(v).remove(w);
422: } else if (removingEdge != 1) {
423: throw new RuntimeException();
424: }
425:
426: edgeModCount++;
427: }
428:
429: public String toString() {
430: String s = "";
431:
432: final Iterator iter = nodes.values().iterator();
433:
434: while (iter.hasNext()) {
435: final GraphNode node = (GraphNode) iter.next();
436: s += "[" + node;
437: s += " succs = " + node.succs();
438: s += " preds = " + node.preds();
439: s += "]\n";
440: }
441:
442: return s;
443: }
444:
445: /**
446: * Searchs this Graph for a given GraphNode.
447: *
448: * @param v
449: * GraphNode to search for.
450: *
451: * @return True, if this Graphs contains v.
452: */
453: public boolean hasNode(final GraphNode v) {
454: return nodes.containsValue(v);
455: }
456:
457: /**
458: * Searches this Graph for an (directed) edge between two GraphNodes.
459: *
460: * @param v
461: * Source node of desired edge.
462: * @param w
463: * Destination node of desired edge.
464: *
465: * @return True, if an edge exists between nodes v and w.
466: */
467: public boolean hasEdge(final GraphNode v, final GraphNode w) {
468: Assert.isTrue(nodes.containsValue(v), "Graph does not contain "
469: + v);
470: Assert.isTrue(nodes.containsValue(w), "Graph does not contain "
471: + w);
472: return succs(v).contains(w);
473: }
474:
475: /**
476: * Returns all the nodes in this Graph.
477: */
478: public Collection nodes() {
479: return nodes.values();
480: }
481:
482: /**
483: * Returns the number of nodes in this Graph.
484: */
485: public int size() {
486: return nodes.size();
487: }
488:
489: /**
490: * A NodeMap that stores nodes. I guess we use this data structure to make
491: * it easier to ensure that there are not duplicate nodes in the Graph. A
492: * HashMap is used as the underlying stored mechanism.
493: */
494: class NodeMap extends AbstractMap {
495: HashMap map = new HashMap();
496:
497: void removeNodeFromMap(final Object key) {
498: map.remove(key);
499: }
500:
501: void putNodeInMap(final Object key, final Object value) {
502: map.put(key, value);
503: }
504:
505: public Object remove(final Object key) {
506: final GraphNode v = (GraphNode) map.get(key);
507:
508: if (v != null) {
509: Graph.this .removeNode(v);
510: }
511:
512: return v;
513: }
514:
515: public Object put(final Object key, final Object value) {
516: final GraphNode v = (GraphNode) remove(key);
517: Graph.this .addNode(key, (GraphNode) value);
518: return v;
519: }
520:
521: public void clear() {
522: final Iterator iter = entrySet().iterator();
523:
524: while (iter.hasNext()) {
525: final Map.Entry e = (Map.Entry) iter.next();
526: removingNode++;
527: Graph.this .removeNode(e.getKey());
528: removingNode--;
529: iter.remove();
530: }
531: }
532:
533: public Set entrySet() /* Modified for final JDK1.2 API */
534: {
535: final Collection entries = map.entrySet();
536:
537: return new AbstractSet() {
538: public int size() {
539: return entries.size();
540: }
541:
542: public boolean contains(final Object a) {
543: return entries.contains(a);
544: }
545:
546: public boolean remove(final Object a) {
547: final Map.Entry e = (Map.Entry) a;
548:
549: removingNode++;
550: Graph.this .removeNode(e.getKey());
551: removingNode--;
552:
553: return entries.remove(a);
554: }
555:
556: public void clear() {
557: final Iterator iter = entries.iterator();
558:
559: while (iter.hasNext()) {
560: final Map.Entry e = (Map.Entry) iter.next();
561: removingNode++;
562: Graph.this .removeNode(e.getKey());
563: removingNode--;
564: iter.remove();
565: }
566: }
567:
568: public Iterator iterator() {
569: final Iterator iter = entries.iterator();
570:
571: return new Iterator() {
572: int nodeModCount = Graph.this .nodeModCount;
573:
574: Map.Entry last;
575:
576: public boolean hasNext() {
577: if (nodeModCount != Graph.this .nodeModCount) {
578: throw new ConcurrentModificationException();
579: }
580:
581: return iter.hasNext();
582: }
583:
584: public Object next() {
585: if (nodeModCount != Graph.this .nodeModCount) {
586: throw new ConcurrentModificationException();
587: }
588:
589: last = (Map.Entry) iter.next();
590: return last;
591: }
592:
593: public void remove() {
594: if (nodeModCount != Graph.this .nodeModCount) {
595: throw new ConcurrentModificationException();
596: }
597:
598: removingNode++;
599: Graph.this .removeNode(last.getKey());
600: removingNode--;
601: iter.remove();
602:
603: nodeModCount = Graph.this .nodeModCount;
604: }
605: };
606: }
607: };
608: }
609: }
610:
611: /**
612: * NodeList represents a list of nodes. Special provisions must be made for
613: * methods such as indexOf() and iterator(). A NodeList is used to store the
614: * pre-order and post-order travsersals of the Graph.
615: */
616: class NodeList extends ArrayList implements List {
617: int edgeModCount;
618:
619: NodeList() {
620: super (Graph.this .size());
621: edgeModCount = Graph.this .edgeModCount;
622: }
623:
624: boolean addNode(final GraphNode a) {
625: return super .add(a);
626: }
627:
628: public void clear() {
629: throw new UnsupportedOperationException();
630: }
631:
632: public boolean add(final Object a) {
633: throw new UnsupportedOperationException();
634: }
635:
636: public boolean remove(final Object a) {
637: throw new UnsupportedOperationException();
638: }
639:
640: // This works only if each node is in the list at most once.
641: public int indexOf(final Object a) {
642: if (edgeModCount != Graph.this .edgeModCount) {
643: throw new ConcurrentModificationException();
644: }
645:
646: final GraphNode v = (GraphNode) a;
647:
648: if (this == Graph.this .preOrder) {
649: return v.preOrderIndex();
650: }
651:
652: if (this == Graph.this .postOrder) {
653: return v.postOrderIndex();
654: }
655:
656: return super .indexOf(a);
657: }
658:
659: // This works only if each node is in the list at most once.
660: public int indexOf(final Object a, final int index) {
661: final int i = indexOf(a);
662:
663: if (i >= index) {
664: return i;
665: }
666:
667: return -1;
668: }
669:
670: // This works only if each node is in the list at most once.
671: public int lastIndexOf(final Object a) {
672: if (edgeModCount != Graph.this .edgeModCount) {
673: throw new ConcurrentModificationException();
674: }
675:
676: final GraphNode v = (GraphNode) a;
677:
678: if (this == Graph.this .preOrder) {
679: return v.preOrderIndex();
680: }
681:
682: if (this == Graph.this .postOrder) {
683: return v.postOrderIndex();
684: }
685:
686: return super .lastIndexOf(a);
687: }
688:
689: // This works only if each node is in the list at most once.
690: public int lastIndexOf(final Object a, final int index) {
691: final int i = indexOf(a);
692:
693: if (i <= index) {
694: return i;
695: }
696:
697: return -1;
698: }
699:
700: public Iterator iterator() {
701: if (Graph.this .edgeModCount != edgeModCount) {
702: throw new ConcurrentModificationException();
703: }
704:
705: final Iterator iter = super .iterator();
706:
707: return new Iterator() {
708: int edgeModCount = NodeList.this .edgeModCount;
709:
710: Object last;
711:
712: public boolean hasNext() {
713: if (Graph.this .edgeModCount != edgeModCount) {
714: throw new ConcurrentModificationException();
715: }
716:
717: return iter.hasNext();
718: }
719:
720: public Object next() {
721: if (Graph.this .edgeModCount != edgeModCount) {
722: throw new ConcurrentModificationException();
723: }
724:
725: last = iter.next();
726: return last;
727: }
728:
729: public void remove() {
730: throw new UnsupportedOperationException();
731: }
732: };
733: }
734: }
735:
736: /**
737: * A set of edges. Recall that a Set cannot contain duplicate entries.
738: */
739: class EdgeSet extends AbstractSet {
740: GraphNode node;
741:
742: Set set;
743:
744: int nodeModCount;
745:
746: /**
747: *
748: */
749: public EdgeSet(final GraphNode node, final Set set) {
750: this .node = node;
751: this .set = set;
752: this .nodeModCount = Graph.this .nodeModCount;
753: }
754:
755: public int size() {
756: if (nodeModCount != Graph.this .nodeModCount) {
757: throw new ConcurrentModificationException();
758: }
759:
760: return set.size();
761: }
762:
763: /**
764: * Removes all nodes in this set except for those found in collection.
765: *
766: * @param c
767: * Nodes that are to be retained.
768: */
769: public boolean retainAll(final Collection c) {
770: return super .retainAll(new ArrayList(c));
771: }
772:
773: /**
774: * Removes all of the nodes in this set that are specified in a given
775: * Collection.
776: *
777: * @param c
778: * The nodes to remove.
779: */
780: public boolean removeAll(final Collection c) {
781: return super .removeAll(new ArrayList(c));
782: }
783:
784: /**
785: * Adds all of the nodes in a Collection to this set.
786: */
787: public boolean addAll(final Collection c) {
788: return super .addAll(new ArrayList(c));
789: }
790:
791: public boolean add(final Object a) {
792: if (nodeModCount != Graph.this .nodeModCount) {
793: throw new ConcurrentModificationException();
794: }
795:
796: Assert.isTrue(nodes.containsValue(a));
797: Assert.isTrue(nodes.containsValue(node));
798:
799: final GraphNode v = (GraphNode) a;
800:
801: if (set.add(v)) {
802: Graph.this .edgeModCount++;
803:
804: if (set == node.succs) {
805: v.preds.add(node);
806: } else {
807: v.succs.add(node);
808: }
809:
810: return true;
811: }
812:
813: return false;
814: }
815:
816: public boolean remove(final Object a) {
817: if (nodeModCount != Graph.this .nodeModCount) {
818: throw new ConcurrentModificationException();
819: }
820:
821: final GraphNode v = (GraphNode) a;
822:
823: if (set.contains(v)) {
824: Graph.this .edgeModCount++;
825:
826: if (set == node.succs) {
827: removingEdge++;
828: Graph.this .removeEdge(node, v);
829: removingEdge--;
830: v.preds.remove(node);
831: } else {
832: removingEdge++;
833: Graph.this .removeEdge(v, node);
834: removingEdge--;
835: v.succs.remove(node);
836: }
837:
838: set.remove(v);
839:
840: return true;
841: }
842:
843: return false;
844: }
845:
846: public boolean contains(final Object a) {
847: if (nodeModCount != Graph.this .nodeModCount) {
848: throw new ConcurrentModificationException();
849: }
850:
851: Assert.isTrue(nodes.containsValue(a));
852: Assert.isTrue(nodes.containsValue(node));
853:
854: if (a instanceof GraphNode) {
855: return set.contains(a);
856: }
857:
858: return false;
859: }
860:
861: public void clear() {
862: if (nodeModCount != Graph.this .nodeModCount) {
863: throw new ConcurrentModificationException();
864: }
865:
866: final Iterator iter = set.iterator();
867:
868: while (iter.hasNext()) {
869: final GraphNode v = (GraphNode) iter.next();
870:
871: if (set == node.succs) {
872: removingEdge++;
873: Graph.this .removeEdge(node, v);
874: removingEdge--;
875: v.preds.remove(node);
876: } else {
877: removingEdge++;
878: Graph.this .removeEdge(v, node);
879: removingEdge--;
880: v.succs.remove(node);
881: }
882: }
883:
884: Graph.this .edgeModCount++;
885:
886: set.clear();
887: }
888:
889: public Iterator iterator() {
890: if (nodeModCount != Graph.this .nodeModCount) {
891: throw new ConcurrentModificationException();
892: }
893:
894: final Iterator iter = set.iterator();
895:
896: return new Iterator() {
897: GraphNode last;
898:
899: int edgeModCount = Graph.this .edgeModCount;
900:
901: int nodeModCount = EdgeSet.this .nodeModCount;
902:
903: public boolean hasNext() {
904: if (nodeModCount != Graph.this .nodeModCount) {
905: throw new ConcurrentModificationException();
906: }
907: if (edgeModCount != Graph.this .edgeModCount) {
908: throw new ConcurrentModificationException();
909: }
910:
911: return iter.hasNext();
912: }
913:
914: public Object next() {
915: if (nodeModCount != Graph.this .nodeModCount) {
916: throw new ConcurrentModificationException();
917: }
918: if (edgeModCount != Graph.this .edgeModCount) {
919: throw new ConcurrentModificationException();
920: }
921:
922: last = (GraphNode) iter.next();
923:
924: Assert.isTrue(nodes.containsValue(last), last
925: + " not found in graph");
926: Assert.isTrue(nodes.containsValue(node), node
927: + " not found in graph");
928:
929: return last;
930: }
931:
932: public void remove() {
933: if (nodeModCount != Graph.this .nodeModCount) {
934: throw new ConcurrentModificationException();
935: }
936: if (edgeModCount != Graph.this .edgeModCount) {
937: throw new ConcurrentModificationException();
938: }
939:
940: if (set == node.succs) {
941: removingEdge++;
942: Graph.this.removeEdge(node, last);
943: removingEdge--;
944: last.preds.remove(node);
945: } else {
946: removingEdge++;
947: Graph.this.removeEdge(last, node);
948: removingEdge--;
949: last.succs.remove(node);
950: }
951:
952: Graph.this.edgeModCount++;
953: edgeModCount = Graph.this.edgeModCount;
954:
955: iter.remove();
956: }
957: };
958: }
959: }
960: }
|