1 pnkfelix 1.1.2.1 // AbstractGraph.java, created Tue Jul 25 15:52:49 2000 by pnkfelix
2 cananian 1.1.2.4 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis.GraphColoring;
5 pnkfelix 1.1.2.1
6 cananian 1.4 import net.cscott.jutil.UnmodifiableIterator;
7 cananian 1.4 import net.cscott.jutil.Default;
8 cananian 1.4 import net.cscott.jutil.FilterIterator;
9 pnkfelix 1.1.2.1
10 pnkfelix 1.1.2.1 import java.util.Iterator;
11 pnkfelix 1.1.2.1 import java.util.Collection;
12 pnkfelix 1.1.2.1 import java.util.AbstractCollection;
13 pnkfelix 1.1.2.1 import java.util.Set;
14 pnkfelix 1.1.2.1 import java.util.AbstractSet;
15 pnkfelix 1.1.2.1 import java.util.HashSet;
16 pnkfelix 1.1.2.1 import java.util.List;
17 pnkfelix 1.1.2.1
18 pnkfelix 1.1.2.1 /**
19 pnkfelix 1.1.2.1 * <code>AbstractGraph</code> is a skeletal implementation of the
20 pnkfelix 1.1.2.1 * <code>Graph</code> interface, to minimize the effort required to
21 pnkfelix 1.1.2.1 * implement this interface.
22 pnkfelix 1.1.2.1 *
23 pnkfelix 1.1.2.1 * To implement an unmodifiable graph, the programmer needs only to
24 pnkfelix 1.1.2.1 * extend this class and provide implementations for the
25 pnkfelix 1.1.2.1 * <code>nodeSet</code> and <code>neighborsOf</code> methods.
26 pnkfelix 1.1.2.1 *
27 pnkfelix 1.1.2.1 * To implement a modifiable graph, the programmer must additionally
28 pnkfelix 1.1.2.1 * override this class's <code>addNode</code> and <code>addEdge</code>
29 pnkfelix 1.1.2.1 * methods (which otherwise throws UnsupportedOperationException).
30 pnkfelix 1.1.2.1 *
31 cananian 1.1.2.4 * @author Felix S. Klock II <pnkfelix@mit.edu>
32 cananian 1.4 * @version $Id: AbstractGraph.java,v 1.4 2004/02/08 01:52:03 cananian Exp $
33 pnkfelix 1.1.2.1 */
34 pnkfelix 1.1.2.1 public abstract class AbstractGraph implements Graph {
35 pnkfelix 1.1.2.1
36 pnkfelix 1.1.2.1 /** Creates a <code>AbstractGraph</code>. */
37 pnkfelix 1.1.2.1 public AbstractGraph() { }
38 pnkfelix 1.1.2.1 public abstract Set nodeSet();
39 pnkfelix 1.1.2.1 public abstract Collection neighborsOf(Object n);
40 pnkfelix 1.1.2.1
41 pnkfelix 1.1.2.1
42 pnkfelix 1.1.2.1 public boolean addNode(Object n) {
43 pnkfelix 1.1.2.1 throw new UnsupportedOperationException();
44 pnkfelix 1.1.2.1 }
45 pnkfelix 1.1.2.1 public boolean addEdge(Object m, Object n) {
46 pnkfelix 1.1.2.1 throw new UnsupportedOperationException();
47 pnkfelix 1.1.2.1 }
48 pnkfelix 1.1.2.1 public int getDegree(Object n) {
49 pnkfelix 1.1.2.1 return neighborsOf(n).size();
50 pnkfelix 1.1.2.1 }
51 pnkfelix 1.1.2.1 public Collection edgesFor(final Object n) {
52 pnkfelix 1.1.2.1 final FilterIterator.Filter filter = new FilterIterator.Filter(){
53 pnkfelix 1.1.2.1 public Object map(Object o) { return Default.pair(n, o); }
54 pnkfelix 1.1.2.1 };
55 pnkfelix 1.1.2.1 return new AbstractCollection() {
56 pnkfelix 1.1.2.1 public int size() { return neighborsOf(n).size(); }
57 pnkfelix 1.1.2.1 public Iterator iterator() {
58 pnkfelix 1.1.2.1 return new FilterIterator(neighborsOf(n).iterator(),
59 pnkfelix 1.1.2.1 filter);
60 pnkfelix 1.1.2.1 }
61 pnkfelix 1.1.2.1 };
62 pnkfelix 1.1.2.1 }
63 pnkfelix 1.1.2.1
64 pnkfelix 1.1.2.1 public Collection edges() {
65 pnkfelix 1.1.2.1 return new AbstractCollection() {
66 pnkfelix 1.1.2.1 public int size() {
67 pnkfelix 1.1.2.1 int d = 0;
68 pnkfelix 1.1.2.1 for(Iterator nodes=nodeSet().iterator();nodes.hasNext();){
69 pnkfelix 1.1.2.1 Object n = nodes.next();
70 pnkfelix 1.1.2.1 d += neighborsOf(n).size();
71 pnkfelix 1.1.2.1 }
72 pnkfelix 1.1.2.1 return d/2;
73 pnkfelix 1.1.2.1 }
74 pnkfelix 1.1.2.1 public Iterator iterator() {
75 pnkfelix 1.1.2.1 final Iterator nodes = nodeSet().iterator();
76 pnkfelix 1.1.2.1
77 pnkfelix 1.1.2.2 // visited holds all previous values for curr in
78 pnkfelix 1.1.2.2 // returned Iterator
79 pnkfelix 1.1.2.1 final Set visited = new HashSet();
80 pnkfelix 1.1.2.1
81 pnkfelix 1.1.2.1 final Object first;
82 pnkfelix 1.1.2.1 if (nodes.hasNext()) {
83 pnkfelix 1.1.2.1 first = nodes.next();
84 pnkfelix 1.1.2.1 } else {
85 pnkfelix 1.1.2.1 first = null;
86 pnkfelix 1.1.2.1 }
87 pnkfelix 1.1.2.1 final Iterator firstNeighbors;
88 pnkfelix 1.1.2.1 if (first != null) {
89 pnkfelix 1.1.2.1 firstNeighbors = neighborsOf(first).iterator();
90 pnkfelix 1.1.2.1 } else {
91 pnkfelix 1.1.2.1 firstNeighbors = Default.nullIterator;
92 pnkfelix 1.1.2.1 }
93 pnkfelix 1.1.2.1
94 pnkfelix 1.1.2.1 return new UnmodifiableIterator(){
95 pnkfelix 1.1.2.3 // (nbor != null) ==> next edge is <curr, nbor>
96 pnkfelix 1.1.2.1 Object curr = first, nbor = null;
97 pnkfelix 1.1.2.1
98 pnkfelix 1.1.2.3 // (curr == null) ==> !niter.hasNext()
99 pnkfelix 1.1.2.1 // niter.hasNext() ==> niter.next() is next
100 pnkfelix 1.1.2.1 // potential nbor
101 pnkfelix 1.1.2.1 Iterator niter = firstNeighbors;
102 pnkfelix 1.1.2.1
103 pnkfelix 1.1.2.3 // (nbor == null) ==> push up to next nbor val
104 pnkfelix 1.1.2.1 public boolean hasNext() {
105 pnkfelix 1.1.2.1 if(nbor!=null) {
106 pnkfelix 1.1.2.1 return true;
107 pnkfelix 1.1.2.1 } else {
108 pnkfelix 1.1.2.1 // loop until
109 pnkfelix 1.1.2.1 // <curr, nbor> is a valid new edge
110 pnkfelix 1.1.2.1 // or (!niter.hasNext() /\ !nodes.hasNext())
111 pnkfelix 1.1.2.1 while(true) {
112 pnkfelix 1.1.2.1 while(niter.hasNext()) {
113 pnkfelix 1.1.2.1 nbor = niter.next();
114 pnkfelix 1.1.2.1 if(!visited.contains(nbor))
115 pnkfelix 1.1.2.1 return true;
116 pnkfelix 1.1.2.1 }
117 pnkfelix 1.1.2.1
118 pnkfelix 1.1.2.1 // finished with neighbors for curr
119 pnkfelix 1.1.2.1 nbor = null;
120 pnkfelix 1.1.2.1
121 pnkfelix 1.1.2.1 if(nodes.hasNext()) {
122 pnkfelix 1.1.2.1 visited.add(curr);
123 pnkfelix 1.1.2.2 curr = nodes.next();
124 pnkfelix 1.1.2.1 niter = neighborsOf(curr).iterator();
125 pnkfelix 1.1.2.1 } else {
126 pnkfelix 1.1.2.1 return false;
127 pnkfelix 1.1.2.1 }
128 pnkfelix 1.1.2.1 }
129 pnkfelix 1.1.2.1 }
130 pnkfelix 1.1.2.1 }
131 pnkfelix 1.1.2.1 public Object next() {
132 pnkfelix 1.1.2.1 if(hasNext()){
133 pnkfelix 1.1.2.1 List edge = Default.pair(curr, nbor);
134 pnkfelix 1.1.2.1 nbor = null;
135 pnkfelix 1.1.2.1 return edge;
136 pnkfelix 1.1.2.1 } else {
137 pnkfelix 1.1.2.1 throw new java.util.NoSuchElementException();
138 pnkfelix 1.1.2.1 }
139 pnkfelix 1.1.2.1 }
140 pnkfelix 1.1.2.1 };
141 pnkfelix 1.1.2.1 }
142 pnkfelix 1.1.2.1 };
143 pnkfelix 1.1.2.1 }
144 cananian 1.2 }