6 public class GraphNode {
8 public static boolean useEdgeLabels;
10 /* NodeStatus enumeration pattern ***********/
12 public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
13 public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
14 public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
16 public static class NodeStatus {
17 private static String name;
18 private NodeStatus(String name) { this.name = name; }
19 public String toString() { return name; }
22 /* Edge *****************/
24 public static class Edge {
27 private GraphNode target;
28 private String dotnodeparams = new String();
30 public Edge(String label, GraphNode target) {
35 public String getLabel() {
39 public GraphNode getTarget() {
43 public void setDotNodeParameters(String param) {
45 throw new NullPointerException();
47 if (param.length() > 0) {
48 dotnodeparams = "," + param;
50 dotnodeparams = new String();
56 int discoverytime = -1;
57 int finishingtime = -1; /* used for searches */
58 Vector edges = new Vector();
61 NodeStatus status = UNVISITED;
62 String dotnodeparams = new String();
65 public GraphNode(String label) {
66 this.nodelabel = label;
67 this.textlabel = label;
70 public GraphNode(String label, Object owner) {
71 this.nodelabel = label;
72 this.textlabel = label;
76 public GraphNode(String label, String textlabel, Object owner) {
77 this.nodelabel = label;
78 this.textlabel = textlabel;
82 public Object getOwner() {
86 public static void computeclosure(Set nodes, Set removed) {
87 Stack tovisit=new Stack();
88 tovisit.addAll(nodes);
89 while(!tovisit.isEmpty()) {
90 GraphNode gn=(GraphNode)tovisit.pop();
91 for(Iterator it=gn.edges();it.hasNext();) {
92 Edge edge=(Edge)it.next();
93 GraphNode target=edge.getTarget();
94 if (!nodes.contains(target)) {
96 (!removed.contains(target))) {
105 public void setDotNodeParameters(String param) {
107 throw new NullPointerException();
109 if (param.length() > 0) {
110 dotnodeparams = "," + param;
112 dotnodeparams = new String();
116 public void setStatus(NodeStatus status) {
117 if (status == null) {
118 throw new NullPointerException();
120 this.status = status;
123 public String getLabel() {
127 public String getTextLabel() {
131 public NodeStatus getStatus() {
135 public Iterator edges() {
136 return edges.iterator();
139 public void addEdge(Edge newedge) {
140 edges.addElement(newedge);
143 public void reset() {
149 public void discover(int time) {
150 discoverytime = time;
154 public void finish(int time) {
155 assert status == PROCESSING;
156 finishingtime = time;
160 public int getFinishingTime() {
161 return finishingtime;
165 public static class DOTVisitor {
167 java.io.PrintWriter output;
171 private DOTVisitor(java.io.OutputStream output) {
174 this.output = new java.io.PrintWriter(output, true);
177 private String getNewID(String name) {
178 tokennumber = tokennumber + 1;
179 return new String (name+tokennumber);
184 public static void visit(java.io.OutputStream output, Collection nodes) {
185 DOTVisitor visitor = new DOTVisitor(output);
186 visitor.nodes = nodes;
191 private void make() {
192 output.println("digraph dotvisitor {");
193 output.println("\trotate=90;");
194 /* output.println("\tpage=\"8.5,11\";");
195 output.println("\tnslimit=1000.0;");
196 output.println("\tnslimit1=1000.0;");
197 output.println("\tmclimit=1000.0;");
198 output.println("\tremincross=true;");*/
199 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
200 output.println("\tedge [fontsize=6];");
202 output.println("}\n");
205 private void traverse() {
206 Set cycleset=GraphNode.findcycles(nodes);
208 Iterator i = nodes.iterator();
209 while (i.hasNext()) {
210 GraphNode gn = (GraphNode) i.next();
211 Iterator edges = gn.edges();
212 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
214 if (cycleset.contains(gn))
215 option=",style=bold";
216 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
218 while (edges.hasNext()) {
219 Edge edge = (Edge) edges.next();
220 GraphNode node = edge.getTarget();
221 if (nodes.contains(node)) {
222 String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
223 output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
230 /* XXXXXXXX Should use SCC algorithm here - will change */
231 public static Set findcycles(Collection nodes) {
232 Stack st=new Stack();
233 HashSet acyclic=new HashSet();
234 HashSet cycles=new HashSet();
235 for(Iterator it=nodes.iterator();it.hasNext();) {
236 GraphNode node=(GraphNode)it.next();
237 if (acyclic.contains(node))
239 if (cycles.contains(node))
241 findcycles(cycles, acyclic, st,node,nodes);
246 private static boolean findcycles(Set cycles, Set acyclic, Stack visited, GraphNode gn, Collection nodes) {
247 if (visited.contains(gn)) {/* Found cycle */
248 cycles.addAll(visited.subList(visited.indexOf(gn),visited.size())); /* Add this cycle */
251 boolean acyclicflag=true;
253 for(Iterator it=gn.edges();it.hasNext();) {
254 Edge e=(Edge) it.next();
255 GraphNode node = e.getTarget();
256 if (!nodes.contains(node))
257 continue; /* Don't visit stuff outside set */
258 if (acyclic.contains(node))
260 if (findcycles(cycles,acyclic,visited,node,nodes)) {
267 acyclic.add(gn); /* no cycles through gn */
270 return true; /* found cycle */
274 * DFS encapsulates the depth first search algorithm
276 public static class DFS {
281 private DFS(Collection nodes) {
285 public static boolean depthFirstSearch(Collection nodes) {
287 throw new NullPointerException();
290 DFS dfs = new DFS(nodes);
294 private boolean go() {
297 boolean acyclic=true;
298 i = nodes.iterator();
299 while (i.hasNext()) {
300 GraphNode gn = (GraphNode) i.next();
304 i = nodes.iterator();
305 while (i.hasNext()) {
306 GraphNode gn = (GraphNode) i.next();
307 assert gn.getStatus() != PROCESSING;
308 if (gn.getStatus() == UNVISITED) {
316 private boolean dfs(GraphNode gn) {
317 boolean acyclic=true;
319 Iterator edges = gn.edges();
321 while (edges.hasNext()) {
322 Edge edge = (Edge) edges.next();
323 GraphNode node = edge.getTarget();
324 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
326 if (node.getStatus() == UNVISITED) {
329 } else if (node.getStatus()==PROCESSING) {