3 public class DirectedEdgeGraph
5 protected class EdgeGraphNode
8 protected final boolean hasInNeighbor(EdgeGraphNode n) {
9 return inEdges.containsKey(n);
12 protected boolean addInEdge(EdgeGraphNode n, GraphEdge e) {
13 if(hasInNeighbor(n)) {
21 protected boolean removeInEdge(EdgeGraphNode n) {
22 if(!hasInNeighbor(n)) {
30 protected GraphEdge getInEdge(EdgeGraphNode n) {
31 return (GraphEdge)inEdges.get(n);
34 protected Collection getInEdges() {
35 return inEdges.values();
38 protected final Collection getInNeighbors() {
39 return inEdges.keySet();
42 protected final Collection getInNeighborsCopy() {
43 return new ArrayList(inEdges.keySet());
46 protected final boolean hasOutNeighbor(EdgeGraphNode n) {
47 return outEdges.containsKey(n);
50 protected boolean addOutEdge(EdgeGraphNode n, GraphEdge e) {
51 if(hasOutNeighbor(n)) {
59 protected boolean removeOutEdge(EdgeGraphNode n) {
60 if(!hasOutNeighbor(n)) {
68 protected GraphEdge getOutEdge(EdgeGraphNode n) {
69 return (GraphEdge)outEdges.get(n);
72 protected Collection getOutEdges() {
73 return outEdges.values();
76 protected final Collection getOutNeighbors() {
77 return outEdges.keySet();
80 protected final Collection getOutNeighborsCopy() {
81 return new ArrayList(outEdges.keySet());
84 public Object getData() {
85 return getNodeData(this);
88 public Object setData(Object n) {
89 return setNodeData(this, n);
92 protected Map inEdges;
93 protected Map outEdges;
94 protected Object data;
95 final DirectedEdgeGraph this$0;
99 this$0 = DirectedEdgeGraph.this;
102 EdgeGraphNode(Object d) {
104 this$0 = DirectedEdgeGraph.this;
105 inEdges = new HashMap();
106 outEdges = new HashMap();
111 protected class GraphEdge
114 protected final EdgeGraphNode getOpposite(EdgeGraphNode n) {
115 return n != src ? src : dest;
118 protected final EdgeGraphNode getSrc() {
122 protected final EdgeGraphNode getDest() {
126 public Object getData() {
127 return getEdgeData(this);
130 public Object setData(Object e) {
131 return setEdgeData(this, e);
134 protected EdgeGraphNode src;
135 protected EdgeGraphNode dest;
137 final DirectedEdgeGraph this$0;
139 public GraphEdge(Object d) {
141 this$0 = DirectedEdgeGraph.this;
145 public GraphEdge(EdgeGraphNode src, EdgeGraphNode dest, Object d) {
153 public DirectedEdgeGraph() {
154 nodes = Collections.synchronizedSet(new HashSet());
157 public boolean addEdge(Edge e) {
158 GraphEdge ge = (GraphEdge)e;
159 EdgeGraphNode src = ge.getSrc();
160 EdgeGraphNode dest = ge.getDest();
161 return src.addOutEdge(dest, ge) ? dest.addInEdge(src, ge) : false;
164 public Edge createEdge(Node src, Node dest, Object e) {
165 return new GraphEdge((EdgeGraphNode)src, (EdgeGraphNode)dest, e);
168 public Node getDest(Edge e) {
169 return ((GraphEdge)e).getDest();
172 public Edge getEdge(Node src, Node dest) {
173 return ((EdgeGraphNode)src).getOutEdge((EdgeGraphNode)dest);
176 public Collection getInEdges(Node n) {
177 return ((EdgeGraphNode)n).getInEdges();
180 public Collection getOutEdges(Node n) {
181 return ((EdgeGraphNode)n).getOutEdges();
184 public Node getSource(Edge e) {
185 return ((GraphEdge)e).src;
188 public boolean hasEdge(Edge e) {
189 GraphEdge ge = (GraphEdge)e;
190 return ge.getSrc().hasOutNeighbor(ge.getDest());
193 public boolean removeEdge(Edge e) {
194 GraphEdge ge = (GraphEdge)e;
195 EdgeGraphNode src = ge.getSrc();
196 EdgeGraphNode dest = ge.getDest();
197 return src.removeOutEdge(dest) ? dest.removeInEdge(src) : false;
200 public boolean addNeighbor(Node src, Node dest) {
201 throw new UnsupportedOperationException("addNeighbor not supported in EdgeGraphs. Use createEdge/addEdge instead");
204 public Node createNode(Object n) {
205 return new EdgeGraphNode(n);
208 public Collection getInNeighbors(Node src) {
209 return ((EdgeGraphNode)src).getInNeighbors();
212 public Collection getOutNeighbors(Node src) {
213 return ((EdgeGraphNode)src).getOutNeighbors();
216 public boolean removeNeighbor(Node src, Node dest) {
217 EdgeGraphNode gsrc = (EdgeGraphNode)src;
218 EdgeGraphNode gdest = (EdgeGraphNode)dest;
219 return gsrc.removeOutEdge(gdest) ? gdest.removeInEdge(gsrc) : false;
222 public Object getEdgeData(Edge e) {
223 return ((GraphEdge)e).d;
226 public Object setEdgeData(Edge e, Object d) {
227 GraphEdge ge = (GraphEdge)e;
228 Object retval = ge.d;
233 public Iterator iterator() {
234 return nodes.iterator();
237 public boolean addNode(Node n) {
238 return nodes.add((EdgeGraphNode)n);
241 public boolean containsNode(Node n) {
242 return nodes.contains(n);
245 public Object getNodeData(Node n) {
246 EdgeGraphNode egn = (EdgeGraphNode)n;
250 public int getNumNodes() {
254 public Node getRandom() {
255 return (Node)Sets.getAny(nodes);
258 public boolean hasNeighbor(Node src, Node dest) {
259 EdgeGraphNode esrc = (EdgeGraphNode)src;
260 EdgeGraphNode edest = (EdgeGraphNode)dest;
261 return esrc.hasOutNeighbor(edest);
264 public boolean removeNode(Node n) {
265 removeConnectingEdges((EdgeGraphNode)n);
266 return nodes.remove(n);
269 protected void removeConnectingEdges(EdgeGraphNode n) {
270 Collection outNeighbors = n.getOutNeighborsCopy();
272 for(Iterator iterator1 = outNeighbors.iterator(); iterator1.hasNext(); removeNeighbor(n, g))
273 g = (EdgeGraphNode)iterator1.next();
275 Collection inNeighbors = n.getInNeighborsCopy();
276 for(Iterator iterator2 = inNeighbors.iterator(); iterator2.hasNext(); removeNeighbor(g, n))
277 g = (EdgeGraphNode)iterator2.next();
281 public Object setNodeData(Node n, Object d) {
282 EdgeGraphNode egn = (EdgeGraphNode)n;
283 Object retval = egn.data;
288 public boolean isDirected() {