6 public class GraphNode {
7 /* NodeStatus enumeration pattern ***********/
9 public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED");
10 public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING");
11 public static final NodeStatus FINISHED = new NodeStatus("FINISHED");
13 public static class NodeStatus {
14 private static String name;
15 private NodeStatus(String name) { this.name = name; }
16 public String toString() { return name; }
19 int discoverytime = -1;
20 int finishingtime = -1; /* used for searches */
22 Vector edges = new Vector();
23 Vector inedges = new Vector();
24 NodeStatus status = UNVISITED;
25 String dotnodeparams = new String();
26 public boolean merge=false;
27 public String nodeoption="";
29 public void setOption(String option) {
30 this.nodeoption=","+option;
33 public void setMerge() {
37 public static void computeclosure(Collection nodes, Collection removed) {
38 Stack tovisit=new Stack();
39 tovisit.addAll(nodes);
40 while(!tovisit.isEmpty()) {
41 GraphNode gn=(GraphNode)tovisit.pop();
42 for(Iterator it=gn.edges();it.hasNext();) {
43 Edge edge=(Edge)it.next();
44 GraphNode target=edge.getTarget();
45 if (!nodes.contains(target)) {
47 (!removed.contains(target))) {
56 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
57 Stack tovisit=new Stack();
58 Stack newvisit=new Stack();
59 tovisit.addAll(nodes);
60 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
61 while(!tovisit.isEmpty()) {
62 GraphNode gn=(GraphNode)tovisit.pop();
63 for(Iterator it=gn.edges();it.hasNext();) {
64 Edge edge=(Edge)it.next();
65 GraphNode target=edge.getTarget();
66 if (!nodes.contains(target)) {
68 (!removed.contains(target))) {
70 newvisit.push(target);
80 public void setDotNodeParameters(String param) {
82 throw new NullPointerException();
84 if (param.length() > 0) {
85 dotnodeparams = "," + param;
87 dotnodeparams = new String();
91 public void setStatus(NodeStatus status) {
93 throw new NullPointerException();
98 public String getLabel() {
102 public String getTextLabel() {
106 public NodeStatus getStatus() {
110 public Iterator edges() {
111 return edges.iterator();
114 public Iterator inedges() {
115 return inedges.iterator();
118 public void addEdge(Edge newedge) {
119 newedge.setSource(this);
120 edges.addElement(newedge);
121 GraphNode tonode=newedge.getTarget();
122 tonode.inedges.addElement(newedge);
135 void discover(int time) {
136 discoverytime = time;
140 void finish(int time) {
141 assert status == PROCESSING;
142 finishingtime = time;
146 /** Returns finishing time for dfs */
148 public int getFinishingTime() {
149 return finishingtime;
153 public static class DOTVisitor {
155 java.io.PrintWriter output;
159 private DOTVisitor(java.io.OutputStream output) {
162 this.output = new java.io.PrintWriter(output, true);
165 private String getNewID(String name) {
166 tokennumber = tokennumber + 1;
167 return new String (name+tokennumber);
173 public static void visit(java.io.OutputStream output, Collection nodes) {
174 visit(output,nodes,null);
177 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
178 DOTVisitor visitor = new DOTVisitor(output);
179 visitor.special=special;
180 visitor.nodes = nodes;
184 private void make() {
185 output.println("digraph dotvisitor {");
186 output.println("\trotate=90;");
187 /* output.println("\tpage=\"8.5,11\";");
188 output.println("\tnslimit=1000.0;");
189 output.println("\tnslimit1=1000.0;");
190 output.println("\tmclimit=1000.0;");
191 output.println("\tremincross=true;");*/
192 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
193 output.println("\tedge [fontsize=6];");
195 output.println("}\n");
198 private void traverse() {
199 Set cycleset=GraphNode.findcycles(nodes);
201 Iterator i = nodes.iterator();
202 while (i.hasNext()) {
203 GraphNode gn = (GraphNode) i.next();
204 Iterator edges = gn.edges();
205 String label = gn.getTextLabel();
206 String option=gn.nodeoption;
207 if (special!=null&&special.contains(gn))
208 option+=",shape=box";
210 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
213 while (edges.hasNext()) {
214 Edge edge = (Edge) edges.next();
215 GraphNode node = edge.getTarget();
216 if (nodes.contains(node)) {
217 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
218 GraphNode node2=(GraphNode)nodeit.next();
219 String edgelabel = "label=\"" + edge.getLabel() + "\"" ;
220 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
227 Set nonmerge(GraphNode gn) {
228 HashSet newset=new HashSet();
229 HashSet toprocess=new HashSet();
231 while(!toprocess.isEmpty()) {
232 GraphNode gn2=(GraphNode)toprocess.iterator().next();
233 toprocess.remove(gn2);
237 Iterator edges = gn2.edges();
238 while (edges.hasNext()) {
239 Edge edge = (Edge) edges.next();
240 GraphNode node = edge.getTarget();
241 if (!newset.contains(node)&&nodes.contains(node))
251 /** This function returns the set of nodes involved in cycles.
252 * It only considers cycles containing nodes in the set 'nodes'.
254 public static Set findcycles(Collection nodes) {
255 HashSet cycleset=new HashSet();
256 SCC scc=DFS.computeSCC(nodes);
257 if (!scc.hasCycles())
259 for(int i=0;i<scc.numSCC();i++) {
261 cycleset.addAll(scc.getSCC(i));
266 public static class SCC {
270 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
271 this.acyclic=acyclic;
277 /** Returns whether the graph has any cycles */
278 public boolean hasCycles() {
282 /** Returns the number of Strongly Connected Components */
283 public int numSCC() {
287 /** Returns the strongly connected component number for the GraphNode gn*/
288 public int getComponent(GraphNode gn) {
289 return ((Integer)revmap.get(gn)).intValue();
292 /** Returns the set of nodes in the strongly connected component i*/
293 public Set getSCC(int i) {
294 Integer scc=new Integer(i);
295 return (Set)map.get(scc);
298 /** Returns whether the strongly connected component i contains a cycle */
299 boolean hasCycle(int i) {
300 Integer scc=new Integer(i);
301 Set s=(Set)map.get(scc);
304 Object [] array=s.toArray();
305 GraphNode gn=(GraphNode)array[0];
306 for(Iterator it=gn.edges();it.hasNext();) {
307 Edge e=(Edge)it.next();
308 if (e.getTarget()==gn)
309 return true; /* Self Cycle */
316 * DFS encapsulates the depth first search algorithm
318 public static class DFS {
323 Vector finishingorder=null;
327 private DFS(Collection nodes) {
330 /** Calculates the strong connected components for the graph composed
331 * of the set of nodes 'nodes'*/
332 public static SCC computeSCC(Collection nodes) {
334 throw new NullPointerException();
336 DFS dfs=new DFS(nodes);
337 dfs.sccmap=new HashMap();
338 dfs.sccmaprev=new HashMap();
339 dfs.finishingorder=new Vector();
340 boolean acyclic=dfs.go();
341 for (Iterator it = nodes.iterator();it.hasNext();) {
342 GraphNode gn = (GraphNode) it.next();
345 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
346 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
347 if (gn.getStatus() == UNVISITED) {
349 dfs.sccindex++; /* Increment scc index */
352 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
355 void dfsprev(GraphNode gn) {
356 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
358 gn.setStatus(FINISHED);
359 Integer i=new Integer(sccindex);
360 if (!sccmap.containsKey(i))
361 sccmap.put(i,new HashSet());
362 ((Set)sccmap.get(i)).add(gn);
364 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
365 Edge e=(Edge)edgeit.next();
366 GraphNode gn2=e.getSource();
371 public static boolean depthFirstSearch(Collection nodes) {
373 throw new NullPointerException();
376 DFS dfs = new DFS(nodes);
380 private boolean go() {
383 boolean acyclic=true;
384 i = nodes.iterator();
385 while (i.hasNext()) {
386 GraphNode gn = (GraphNode) i.next();
390 i = nodes.iterator();
391 while (i.hasNext()) {
392 GraphNode gn = (GraphNode) i.next();
393 assert gn.getStatus() != PROCESSING;
394 if (gn.getStatus() == UNVISITED) {
402 private boolean dfs(GraphNode gn) {
403 boolean acyclic=true;
405 Iterator edges = gn.edges();
407 while (edges.hasNext()) {
408 Edge edge = (Edge) edges.next();
409 GraphNode node = edge.getTarget();
410 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
412 if (node.getStatus() == UNVISITED) {
415 } else if (node.getStatus()==PROCESSING) {
419 if (finishingorder!=null)
420 finishingorder.add(gn);