1 cananian 1.1a // AbstractGraph.java, created Sun May 4 11:29:53 2003 by cananian
2 cananian 1.1a // Copyright (C) 2003 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1a // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Util.Collections;
5 cananian 1.1a
6 cananian 1.2 import net.cscott.jutil.AggregateSetFactory;
7 cananian 1.2 import net.cscott.jutil.SetFactory;
8 cananian 1.1a
9 cananian 1.1a import java.util.AbstractSet;
10 cananian 1.1a import java.util.Collection;
11 cananian 1.1a import java.util.Collections;
12 cananian 1.1a import java.util.Iterator;
13 cananian 1.4a import java.util.LinkedHashSet;
14 cananian 1.1a import java.util.Map;
15 cananian 1.1a import java.util.Set;
16 cananian 1.1a
17 cananian 1.1a /**
18 cananian 1.1a * An <code>AbstractGraph</code> provides a basic implementation
19 cananian 1.1a * of the <code>Graph</code> interface.
20 cananian 1.1a *
21 cananian 1.1a * @author C. Scott Ananian <cananian@alumni.princeton.edu>
22 cananian 1.3 * @version $Id: AbstractGraph.java,v 1.3 2004/02/08 03:21:44 cananian Exp $
23 cananian 1.1a */
24 cananian 1.2 public abstract class AbstractGraph<N extends AbstractGraph.Node<N,E>,E extends Graph.Edge<N,E>> implements MutableGraph<N,E> {
25 cananian 1.1a final SetFactory<E> edgeSetFactory = new AggregateSetFactory<E>();
26 cananian 1.4a final Set<N> nodes = new LinkedHashSet<N>();
27 cananian 1.4a final Set<N> nodesRO = Collections.unmodifiableSet(nodes);
28 cananian 1.4a public Set<N> nodes() { return nodesRO; }
29 cananian 1.4a
30 cananian 1.1a public void summarize(Collection<N> nodesToRemove) {
31 cananian 1.1a for (Iterator<N> it=nodesToRemove.iterator(); it.hasNext(); )
32 cananian 1.1a summarize(it.next());
33 cananian 1.1a }
34 cananian 1.1a public void summarize(N nodeToRemove) {
35 cananian 1.1a if (!nodes.contains(nodeToRemove)) return; // done already!
36 cananian 1.1a // remove self-loops.
37 cananian 1.3 for (E edge : nodeToRemove.predC()) {
38 cananian 1.1a assert edge.to()==nodeToRemove;
39 cananian 1.1a if (edge.from()==nodeToRemove)
40 cananian 1.1a removeEdge(edge);
41 cananian 1.1a }
42 cananian 1.1a // A->n->B becomes A->B
43 cananian 1.4a for (Iterator<E> it=nodeToRemove.predC().iterator(); it.hasNext(); ) {
44 cananian 1.1a N pred = it.next().from();
45 cananian 1.1a assert pred!=nodeToRemove;
46 cananian 1.1a // extend this edge to all successors.
47 cananian 1.4a for (Iterator<E> it2=nodeToRemove.succC().iterator();
48 cananian 1.1a it2.hasNext(); ) {
49 cananian 1.1a N succ = it2.next().to();
50 cananian 1.1a assert succ!=nodeToRemove;
51 cananian 1.1a addEdge(pred, succ);
52 cananian 1.1a }
53 cananian 1.1a }
54 cananian 1.1a // remove original edges
55 cananian 1.4a for (Iterator<E> it=nodeToRemove.predC().iterator(); it.hasNext(); )
56 cananian 1.1a removeEdge(it.next());
57 cananian 1.4a for (Iterator<E> it=nodeToRemove.succC().iterator(); it.hasNext(); )
58 cananian 1.1a removeEdge(it.next());
59 cananian 1.1a // finally, remove the node.
60 cananian 1.4a boolean changed = nodes.remove(nodeToRemove);
61 cananian 1.4a assert changed;
62 cananian 1.1a assert !nodes.contains(nodeToRemove);
63 cananian 1.4a assert nodeToRemove.predC().size()==0;
64 cananian 1.4a assert nodeToRemove.succC().size()==0;
65 cananian 1.1a }
66 cananian 1.1a public abstract E addEdge(N from, N to);
67 cananian 1.1a
68 cananian 1.4a public void addNode(N n) {
69 cananian 1.4a assert !nodes.contains(n);
70 cananian 1.4a nodes.add(n);
71 cananian 1.1a }
72 cananian 1.1a protected void addEdge(E e) {
73 cananian 1.1a e.from().succ.add(e);
74 cananian 1.1a e.to().pred.add(e);
75 cananian 1.1a }
76 cananian 1.1a public void removeEdge(E e) {
77 cananian 1.1a e.from().succ.remove(e);
78 cananian 1.1a e.to().pred.remove(e);
79 cananian 1.1a }
80 cananian 1.1a
81 cananian 1.1a protected AbstractGraph() { }
82 cananian 1.1a
83 cananian 1.3a /**
84 cananian 1.3a * <code>AbstractGraph.Node</code> provides a basic implementation of
85 cananian 1.3a * the <code>Graph.Node</code> interface.
86 cananian 1.3a *
87 cananian 1.3a * @author C. Scott Ananian <cananian@alumni.princeton.edu>
88 cananian 1.3 * @version $Id: AbstractGraph.java,v 1.3 2004/02/08 03:21:44 cananian Exp $
89 cananian 1.3a */
90 cananian 1.4a public static class Node<N extends Node<N,E>,E extends Graph.Edge<N,E>> implements Graph.Node<N,E> {
91 cananian 1.1a final Set<E> pred, succ, predRO, succRO;
92 cananian 1.4a public Node(AbstractGraph<N,E> parent) {
93 cananian 1.1a this.pred = parent.edgeSetFactory.makeSet();
94 cananian 1.1a this.succ = parent.edgeSetFactory.makeSet();
95 cananian 1.1a this.predRO = Collections.unmodifiableSet(this.pred);
96 cananian 1.1a this.succRO = Collections.unmodifiableSet(this.succ);
97 cananian 1.1a }
98 cananian 1.4a public Set<E> predC() { return predRO; }
99 cananian 1.4a public Set<E> succC() { return succRO; }
100 cananian 1.1a public boolean isSucc(N n) {
101 cananian 1.1a for (Iterator<E> it=succ.iterator(); it.hasNext(); )
102 cananian 1.1a if (it.next().to().equals(n)) return true;
103 cananian 1.1a return false;
104 cananian 1.1a }
105 cananian 1.1a public boolean isPred(N n) {
106 cananian 1.1a for (Iterator<E> it=pred.iterator(); it.hasNext(); )
107 cananian 1.1a if (it.next().from().equals(n)) return true;
108 cananian 1.1a return false;
109 cananian 1.1a }
110 cananian 1.1a }
111 cananian 1.3a /**
112 cananian 1.3a * <code>AbstractGraph.Edge</code> provides a basic implementation of
113 cananian 1.3a * the <code>Graph.Edge</code> interface. This is a simple pair
114 cananian 1.3a * of "from" and "to" nodes; you don't have to extend this
115 cananian 1.3a * class when implementing <code>AbstractGraph</code> if you
116 cananian 1.3a * prefer to use your own <code>Graph.Edge</code> implementation.
117 cananian 1.3a *
118 cananian 1.3a * @author C. Scott Ananian <cananian@alumni.princeton.edu>
119 cananian 1.3 * @version $Id: AbstractGraph.java,v 1.3 2004/02/08 03:21:44 cananian Exp $
120 cananian 1.3a */
121 cananian 1.4a public static class Edge<N extends Node<N,E>,E extends Edge<N,E>> implements Graph.Edge<N,E> {
122 cananian 1.1a final N from;
123 cananian 1.1a final N to;
124 cananian 1.1a public Edge(N from, N to) { this.from=from; this.to=to; }
125 cananian 1.1a public N from() { return from; }
126 cananian 1.1a public N to() { return to; }
127 cananian 1.1a }
128 cananian 1.1a }