7 public class GraphNode {
9 /* NodeStatus enumeration pattern ***********/
11 public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
12 public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
13 public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
15 public static class NodeStatus {
16 private static String name;
17 private NodeStatus(String name) { this.name = name; }
18 public String toString() { return name; }
21 /* Edge *****************/
23 public static class Edge {
26 private GraphNode target;
27 private GraphNode source;
28 private String dotnodeparams = new String();
30 public Edge(String label, GraphNode target) {
35 public String getLabel() {
39 public void setSource(GraphNode s) {
43 public GraphNode getSource() {
47 public GraphNode getTarget() {
51 public void setDotNodeParameters(String param) {
53 throw new NullPointerException();
55 if (param.length() > 0) {
56 dotnodeparams = "," + param;
58 dotnodeparams = new String();
64 int discoverytime = -1;
65 int finishingtime = -1; /* used for searches */
67 Vector edges = new Vector();
68 Vector inedges = new Vector();
71 NodeStatus status = UNVISITED;
72 String dotnodeparams = new String();
77 public void setOption(String option) {
78 this.nodeoption=","+option;
81 public void setMerge() {
85 public GraphNode(String label) {
86 this.nodelabel = label;
87 this.textlabel = label;
90 public GraphNode(String label, Object owner) {
91 this.nodelabel = label;
92 this.textlabel = label;
96 public GraphNode(String label, String textlabel, Object owner) {
97 this.nodelabel = label;
98 this.textlabel = textlabel;
102 public Object getOwner() {
106 public static void computeclosure(Collection nodes, Collection removed) {
107 Stack tovisit=new Stack();
108 tovisit.addAll(nodes);
109 while(!tovisit.isEmpty()) {
110 GraphNode gn=(GraphNode)tovisit.pop();
111 for(Iterator it=gn.edges();it.hasNext();) {
112 Edge edge=(Edge)it.next();
113 GraphNode target=edge.getTarget();
114 if (!nodes.contains(target)) {
115 if ((removed==null)||
116 (!removed.contains(target))) {
118 tovisit.push(target);
125 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
126 Stack tovisit=new Stack();
127 Stack newvisit=new Stack();
128 tovisit.addAll(nodes);
129 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
130 while(!tovisit.isEmpty()) {
131 GraphNode gn=(GraphNode)tovisit.pop();
132 for(Iterator it=gn.edges();it.hasNext();) {
133 Edge edge=(Edge)it.next();
134 GraphNode target=edge.getTarget();
135 if (!nodes.contains(target)) {
136 if ((removed==null)||
137 (!removed.contains(target))) {
139 newvisit.push(target);
145 newvisit=new Stack();
149 public void setDotNodeParameters(String param) {
151 throw new NullPointerException();
153 if (param.length() > 0) {
154 dotnodeparams = "," + param;
156 dotnodeparams = new String();
160 public void setStatus(NodeStatus status) {
161 if (status == null) {
162 throw new NullPointerException();
164 this.status = status;
167 public String getLabel() {
171 public String getTextLabel() {
175 public NodeStatus getStatus() {
179 public Iterator edges() {
180 return edges.iterator();
183 public Iterator inedges() {
184 return inedges.iterator();
187 public void addEdge(Edge newedge) {
188 newedge.setSource(this);
189 edges.addElement(newedge);
190 GraphNode tonode=newedge.getTarget();
191 tonode.inedges.addElement(newedge);
204 void discover(int time) {
205 discoverytime = time;
209 void finish(int time) {
210 assert status == PROCESSING;
211 finishingtime = time;
215 /** Returns finishing time for dfs */
217 public int getFinishingTime() {
218 return finishingtime;
222 public static class DOTVisitor {
224 java.io.PrintWriter output;
228 private DOTVisitor(java.io.OutputStream output) {
231 this.output = new java.io.PrintWriter(output, true);
234 private String getNewID(String name) {
235 tokennumber = tokennumber + 1;
236 return new String (name+tokennumber);
242 public static void visit(java.io.OutputStream output, Collection nodes) {
243 visit(output,nodes,null);
246 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
247 DOTVisitor visitor = new DOTVisitor(output);
248 visitor.special=special;
249 visitor.nodes = nodes;
253 private void make() {
254 output.println("digraph dotvisitor {");
255 output.println("\trotate=90;");
256 /* output.println("\tpage=\"8.5,11\";");
257 output.println("\tnslimit=1000.0;");
258 output.println("\tnslimit1=1000.0;");
259 output.println("\tmclimit=1000.0;");
260 output.println("\tremincross=true;");*/
261 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
262 output.println("\tedge [fontsize=6];");
264 output.println("}\n");
267 private void traverse() {
268 Set cycleset=GraphNode.findcycles(nodes);
270 Iterator i = nodes.iterator();
271 while (i.hasNext()) {
272 GraphNode gn = (GraphNode) i.next();
273 Iterator edges = gn.edges();
274 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
275 String option=gn.nodeoption;
276 if (special!=null&&special.contains(gn))
277 option+=",shape=box";
279 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
282 while (edges.hasNext()) {
283 Edge edge = (Edge) edges.next();
284 GraphNode node = edge.getTarget();
285 if (nodes.contains(node)) {
286 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
287 GraphNode node2=(GraphNode)nodeit.next();
288 String edgelabel = Compiler.DEBUGGRAPH ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
289 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
296 Set nonmerge(GraphNode gn) {
297 HashSet newset=new HashSet();
298 HashSet toprocess=new HashSet();
300 while(!toprocess.isEmpty()) {
301 GraphNode gn2=(GraphNode)toprocess.iterator().next();
302 toprocess.remove(gn2);
306 Iterator edges = gn2.edges();
307 while (edges.hasNext()) {
308 Edge edge = (Edge) edges.next();
309 GraphNode node = edge.getTarget();
310 if (!newset.contains(node)&&nodes.contains(node))
320 /** This function returns the set of nodes involved in cycles.
321 * It only considers cycles containing nodes in the set 'nodes'.
323 public static Set findcycles(Collection nodes) {
324 HashSet cycleset=new HashSet();
325 SCC scc=DFS.computeSCC(nodes);
326 if (!scc.hasCycles())
328 for(int i=0;i<scc.numSCC();i++) {
330 cycleset.addAll(scc.getSCC(i));
335 public static class SCC {
339 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
340 this.acyclic=acyclic;
346 /** Returns whether the graph has any cycles */
347 public boolean hasCycles() {
351 /** Returns the number of Strongly Connected Components */
352 public int numSCC() {
356 /** Returns the strongly connected component number for the GraphNode gn*/
357 public int getComponent(GraphNode gn) {
358 return ((Integer)revmap.get(gn)).intValue();
361 /** Returns the set of nodes in the strongly connected component i*/
362 public Set getSCC(int i) {
363 Integer scc=new Integer(i);
364 return (Set)map.get(scc);
367 /** Returns whether the strongly connected component i contains a cycle */
368 boolean hasCycle(int i) {
369 Integer scc=new Integer(i);
370 Set s=(Set)map.get(scc);
373 Object [] array=s.toArray();
374 GraphNode gn=(GraphNode)array[0];
375 for(Iterator it=gn.edges();it.hasNext();) {
376 Edge e=(Edge)it.next();
377 if (e.getTarget()==gn)
378 return true; /* Self Cycle */
385 * DFS encapsulates the depth first search algorithm
387 public static class DFS {
392 Vector finishingorder=null;
396 private DFS(Collection nodes) {
399 /** Calculates the strong connected components for the graph composed
400 * of the set of nodes 'nodes'*/
401 public static SCC computeSCC(Collection nodes) {
403 throw new NullPointerException();
405 DFS dfs=new DFS(nodes);
406 dfs.sccmap=new HashMap();
407 dfs.sccmaprev=new HashMap();
408 dfs.finishingorder=new Vector();
409 boolean acyclic=dfs.go();
410 for (Iterator it = nodes.iterator();it.hasNext();) {
411 GraphNode gn = (GraphNode) it.next();
414 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
415 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
416 if (gn.getStatus() == UNVISITED) {
418 dfs.sccindex++; /* Increment scc index */
421 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
424 void dfsprev(GraphNode gn) {
425 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
427 gn.setStatus(FINISHED);
428 Integer i=new Integer(sccindex);
429 if (!sccmap.containsKey(i))
430 sccmap.put(i,new HashSet());
431 ((Set)sccmap.get(i)).add(gn);
433 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
434 Edge e=(Edge)edgeit.next();
435 GraphNode gn2=e.getSource();
440 public static boolean depthFirstSearch(Collection nodes) {
442 throw new NullPointerException();
445 DFS dfs = new DFS(nodes);
449 private boolean go() {
452 boolean acyclic=true;
453 i = nodes.iterator();
454 while (i.hasNext()) {
455 GraphNode gn = (GraphNode) i.next();
459 i = nodes.iterator();
460 while (i.hasNext()) {
461 GraphNode gn = (GraphNode) i.next();
462 assert gn.getStatus() != PROCESSING;
463 if (gn.getStatus() == UNVISITED) {
471 private boolean dfs(GraphNode gn) {
472 boolean acyclic=true;
474 Iterator edges = gn.edges();
476 while (edges.hasNext()) {
477 Edge edge = (Edge) edges.next();
478 GraphNode node = edge.getTarget();
479 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
481 if (node.getStatus() == UNVISITED) {
484 } else if (node.getStatus()==PROCESSING) {
488 if (finishingorder!=null)
489 finishingorder.add(gn);