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 GraphNode source;
29 private String dotnodeparams = new String();
31 public Edge(String label, GraphNode target) {
36 public String getLabel() {
40 public void setSource(GraphNode s) {
44 public GraphNode getSource() {
48 public GraphNode getTarget() {
52 public void setDotNodeParameters(String param) {
54 throw new NullPointerException();
56 if (param.length() > 0) {
57 dotnodeparams = "," + param;
59 dotnodeparams = new String();
65 int discoverytime = -1;
66 int finishingtime = -1; /* used for searches */
68 Vector edges = new Vector();
69 Vector inedges = new Vector();
72 NodeStatus status = UNVISITED;
73 String dotnodeparams = new String();
78 public void setOption(String option) {
79 this.nodeoption=option;
82 public void setMerge() {
86 public GraphNode(String label) {
87 this.nodelabel = label;
88 this.textlabel = label;
91 public GraphNode(String label, Object owner) {
92 this.nodelabel = label;
93 this.textlabel = label;
97 public GraphNode(String label, String textlabel, Object owner) {
98 this.nodelabel = label;
99 this.textlabel = textlabel;
103 public Object getOwner() {
107 public static void computeclosure(Collection nodes, Collection removed) {
108 Stack tovisit=new Stack();
109 tovisit.addAll(nodes);
110 while(!tovisit.isEmpty()) {
111 GraphNode gn=(GraphNode)tovisit.pop();
112 for(Iterator it=gn.edges();it.hasNext();) {
113 Edge edge=(Edge)it.next();
114 GraphNode target=edge.getTarget();
115 if (!nodes.contains(target)) {
116 if ((removed==null)||
117 (!removed.contains(target))) {
119 tovisit.push(target);
126 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
127 Stack tovisit=new Stack();
128 Stack newvisit=new Stack();
129 tovisit.addAll(nodes);
130 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
131 while(!tovisit.isEmpty()) {
132 GraphNode gn=(GraphNode)tovisit.pop();
133 for(Iterator it=gn.edges();it.hasNext();) {
134 Edge edge=(Edge)it.next();
135 GraphNode target=edge.getTarget();
136 if (!nodes.contains(target)) {
137 if ((removed==null)||
138 (!removed.contains(target))) {
140 newvisit.push(target);
146 newvisit=new Stack();
150 public void setDotNodeParameters(String param) {
152 throw new NullPointerException();
154 if (param.length() > 0) {
155 dotnodeparams = "," + param;
157 dotnodeparams = new String();
161 public void setStatus(NodeStatus status) {
162 if (status == null) {
163 throw new NullPointerException();
165 this.status = status;
168 public String getLabel() {
172 public String getTextLabel() {
176 public NodeStatus getStatus() {
180 public Iterator edges() {
181 return edges.iterator();
184 public Iterator inedges() {
185 return inedges.iterator();
188 public void addEdge(Edge newedge) {
189 newedge.setSource(this);
190 edges.addElement(newedge);
191 GraphNode tonode=newedge.getTarget();
192 tonode.inedges.addElement(newedge);
205 void discover(int time) {
206 discoverytime = time;
210 void finish(int time) {
211 assert status == PROCESSING;
212 finishingtime = time;
216 /** Returns finishing time for dfs */
218 public int getFinishingTime() {
219 return finishingtime;
223 public static class DOTVisitor {
225 java.io.PrintWriter output;
229 private DOTVisitor(java.io.OutputStream output) {
232 this.output = new java.io.PrintWriter(output, true);
235 private String getNewID(String name) {
236 tokennumber = tokennumber + 1;
237 return new String (name+tokennumber);
243 public static void visit(java.io.OutputStream output, Collection nodes) {
244 visit(output,nodes,null);
247 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
248 DOTVisitor visitor = new DOTVisitor(output);
249 visitor.special=special;
250 visitor.nodes = nodes;
254 private void make() {
255 output.println("digraph dotvisitor {");
256 output.println("\trotate=90;");
257 /* output.println("\tpage=\"8.5,11\";");
258 output.println("\tnslimit=1000.0;");
259 output.println("\tnslimit1=1000.0;");
260 output.println("\tmclimit=1000.0;");
261 output.println("\tremincross=true;");*/
262 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
263 output.println("\tedge [fontsize=6];");
265 output.println("}\n");
268 private void traverse() {
269 Set cycleset=GraphNode.findcycles(nodes);
271 Iterator i = nodes.iterator();
272 while (i.hasNext()) {
273 GraphNode gn = (GraphNode) i.next();
274 Iterator edges = gn.edges();
275 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
276 String option=gn.nodeoption;
277 if (special!=null&&special.contains(gn))
278 option+=",shape=box";
280 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
283 while (edges.hasNext()) {
284 Edge edge = (Edge) edges.next();
285 GraphNode node = edge.getTarget();
286 if (nodes.contains(node)) {
287 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
288 GraphNode node2=(GraphNode)nodeit.next();
289 String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
290 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
297 Set nonmerge(GraphNode gn) {
298 HashSet newset=new HashSet();
299 HashSet toprocess=new HashSet();
301 while(!toprocess.isEmpty()) {
302 GraphNode gn2=(GraphNode)toprocess.iterator().next();
303 toprocess.remove(gn2);
307 Iterator edges = gn2.edges();
308 while (edges.hasNext()) {
309 Edge edge = (Edge) edges.next();
310 GraphNode node = edge.getTarget();
311 if (!newset.contains(node)&&nodes.contains(node))
321 /** This function returns the set of nodes involved in cycles.
322 * It only considers cycles containing nodes in the set 'nodes'.
324 public static Set findcycles(Collection nodes) {
325 HashSet cycleset=new HashSet();
326 SCC scc=DFS.computeSCC(nodes);
327 if (!scc.hasCycles())
329 for(int i=0;i<scc.numSCC();i++) {
331 cycleset.addAll(scc.getSCC(i));
336 public static class SCC {
340 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
341 this.acyclic=acyclic;
347 /** Returns whether the graph has any cycles */
348 public boolean hasCycles() {
352 /** Returns the number of Strongly Connected Components */
353 public int numSCC() {
357 /** Returns the strongly connected component number for the GraphNode gn*/
358 public int getComponent(GraphNode gn) {
359 return ((Integer)revmap.get(gn)).intValue();
362 /** Returns the set of nodes in the strongly connected component i*/
363 public Set getSCC(int i) {
364 Integer scc=new Integer(i);
365 return (Set)map.get(scc);
368 /** Returns whether the strongly connected component i contains a cycle */
369 boolean hasCycle(int i) {
370 Integer scc=new Integer(i);
371 Set s=(Set)map.get(scc);
374 Object [] array=s.toArray();
375 GraphNode gn=(GraphNode)array[0];
376 for(Iterator it=gn.edges();it.hasNext();) {
377 Edge e=(Edge)it.next();
378 if (e.getTarget()==gn)
379 return true; /* Self Cycle */
386 * DFS encapsulates the depth first search algorithm
388 public static class DFS {
393 Vector finishingorder=null;
397 private DFS(Collection nodes) {
400 /** Calculates the strong connected components for the graph composed
401 * of the set of nodes 'nodes'*/
402 public static SCC computeSCC(Collection nodes) {
404 throw new NullPointerException();
406 DFS dfs=new DFS(nodes);
407 dfs.sccmap=new HashMap();
408 dfs.sccmaprev=new HashMap();
409 dfs.finishingorder=new Vector();
410 boolean acyclic=dfs.go();
411 for (Iterator it = nodes.iterator();it.hasNext();) {
412 GraphNode gn = (GraphNode) it.next();
415 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
416 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
417 if (gn.getStatus() == UNVISITED) {
419 dfs.sccindex++; /* Increment scc index */
422 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
425 void dfsprev(GraphNode gn) {
426 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
428 gn.setStatus(FINISHED);
429 Integer i=new Integer(sccindex);
430 if (!sccmap.containsKey(i))
431 sccmap.put(i,new HashSet());
432 ((Set)sccmap.get(i)).add(gn);
434 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
435 Edge e=(Edge)edgeit.next();
436 GraphNode gn2=e.getSource();
441 public static boolean depthFirstSearch(Collection nodes) {
443 throw new NullPointerException();
446 DFS dfs = new DFS(nodes);
450 private boolean go() {
453 boolean acyclic=true;
454 i = nodes.iterator();
455 while (i.hasNext()) {
456 GraphNode gn = (GraphNode) i.next();
460 i = nodes.iterator();
461 while (i.hasNext()) {
462 GraphNode gn = (GraphNode) i.next();
463 assert gn.getStatus() != PROCESSING;
464 if (gn.getStatus() == UNVISITED) {
472 private boolean dfs(GraphNode gn) {
473 boolean acyclic=true;
475 Iterator edges = gn.edges();
477 while (edges.hasNext()) {
478 Edge edge = (Edge) edges.next();
479 GraphNode node = edge.getTarget();
480 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
482 if (node.getStatus() == UNVISITED) {
485 } else if (node.getStatus()==PROCESSING) {
489 if (finishingorder!=null)
490 finishingorder.add(gn);