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();
76 public GraphNode(String label) {
77 this.nodelabel = label;
78 this.textlabel = label;
81 public GraphNode(String label, Object owner) {
82 this.nodelabel = label;
83 this.textlabel = label;
87 public GraphNode(String label, String textlabel, Object owner) {
88 this.nodelabel = label;
89 this.textlabel = textlabel;
93 public Object getOwner() {
97 public static void computeclosure(Collection nodes, Collection removed) {
98 Stack tovisit=new Stack();
99 tovisit.addAll(nodes);
100 while(!tovisit.isEmpty()) {
101 GraphNode gn=(GraphNode)tovisit.pop();
102 for(Iterator it=gn.edges();it.hasNext();) {
103 Edge edge=(Edge)it.next();
104 GraphNode target=edge.getTarget();
105 if (!nodes.contains(target)) {
106 if ((removed==null)||
107 (!removed.contains(target))) {
109 tovisit.push(target);
116 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
117 Stack tovisit=new Stack();
118 Stack newvisit=new Stack();
119 tovisit.addAll(nodes);
120 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
121 while(!tovisit.isEmpty()) {
122 GraphNode gn=(GraphNode)tovisit.pop();
123 for(Iterator it=gn.edges();it.hasNext();) {
124 Edge edge=(Edge)it.next();
125 GraphNode target=edge.getTarget();
126 if (!nodes.contains(target)) {
127 if ((removed==null)||
128 (!removed.contains(target))) {
130 newvisit.push(target);
136 newvisit=new Stack();
140 public void setDotNodeParameters(String param) {
142 throw new NullPointerException();
144 if (param.length() > 0) {
145 dotnodeparams = "," + param;
147 dotnodeparams = new String();
151 public void setStatus(NodeStatus status) {
152 if (status == null) {
153 throw new NullPointerException();
155 this.status = status;
158 public String getLabel() {
162 public String getTextLabel() {
166 public NodeStatus getStatus() {
170 public Iterator edges() {
171 return edges.iterator();
174 public Iterator inedges() {
175 return inedges.iterator();
178 public void addEdge(Edge newedge) {
179 newedge.setSource(this);
180 edges.addElement(newedge);
181 GraphNode tonode=newedge.getTarget();
182 tonode.inedges.addElement(newedge);
195 void discover(int time) {
196 discoverytime = time;
200 void finish(int time) {
201 assert status == PROCESSING;
202 finishingtime = time;
206 /** Returns finishing time for dfs */
208 public int getFinishingTime() {
209 return finishingtime;
213 public static class DOTVisitor {
215 java.io.PrintWriter output;
219 private DOTVisitor(java.io.OutputStream output) {
222 this.output = new java.io.PrintWriter(output, true);
225 private String getNewID(String name) {
226 tokennumber = tokennumber + 1;
227 return new String (name+tokennumber);
233 public static void visit(java.io.OutputStream output, Collection nodes) {
234 visit(output,nodes,null);
237 public static void visit(java.io.OutputStream output, Collection nodes, Collection special) {
238 DOTVisitor visitor = new DOTVisitor(output);
239 visitor.special=special;
240 visitor.nodes = nodes;
244 private void make() {
245 output.println("digraph dotvisitor {");
246 output.println("\trotate=90;");
247 /* output.println("\tpage=\"8.5,11\";");
248 output.println("\tnslimit=1000.0;");
249 output.println("\tnslimit1=1000.0;");
250 output.println("\tmclimit=1000.0;");
251 output.println("\tremincross=true;");*/
252 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
253 output.println("\tedge [fontsize=6];");
255 output.println("}\n");
258 private void traverse() {
259 Set cycleset=GraphNode.findcycles(nodes);
261 Iterator i = nodes.iterator();
262 while (i.hasNext()) {
263 GraphNode gn = (GraphNode) i.next();
264 Iterator edges = gn.edges();
265 String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
267 if (cycleset.contains(gn))
268 option=",style=bold";
269 if (special!=null&&special.contains(gn))
270 option+=",shape=box";
271 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
273 while (edges.hasNext()) {
274 Edge edge = (Edge) edges.next();
275 GraphNode node = edge.getTarget();
276 if (nodes.contains(node)) {
277 String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
278 output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
285 /** This function returns the set of nodes involved in cycles.
286 * It only considers cycles containing nodes in the set 'nodes'.
288 public static Set findcycles(Collection nodes) {
289 HashSet cycleset=new HashSet();
290 SCC scc=DFS.computeSCC(nodes);
291 if (!scc.hasCycles())
293 for(int i=0;i<scc.numSCC();i++) {
295 cycleset.addAll(scc.getSCC(i));
300 public static class SCC {
304 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
305 this.acyclic=acyclic;
311 /** Returns whether the graph has any cycles */
312 public boolean hasCycles() {
316 /** Returns the number of Strongly Connected Components */
317 public int numSCC() {
321 /** Returns the strongly connected component number for the GraphNode gn*/
322 public int getComponent(GraphNode gn) {
323 return ((Integer)revmap.get(gn)).intValue();
326 /** Returns the set of nodes in the strongly connected component i*/
327 public Set getSCC(int i) {
328 Integer scc=new Integer(i);
329 return (Set)map.get(scc);
332 /** Returns whether the strongly connected component i contains a cycle */
333 boolean hasCycle(int i) {
334 Integer scc=new Integer(i);
335 Set s=(Set)map.get(scc);
338 Object [] array=s.toArray();
339 GraphNode gn=(GraphNode)array[0];
340 for(Iterator it=gn.edges();it.hasNext();) {
341 Edge e=(Edge)it.next();
342 if (e.getTarget()==gn)
343 return true; /* Self Cycle */
350 * DFS encapsulates the depth first search algorithm
352 public static class DFS {
357 Vector finishingorder=null;
361 private DFS(Collection nodes) {
364 /** Calculates the strong connected components for the graph composed
365 * of the set of nodes 'nodes'*/
366 public static SCC computeSCC(Collection nodes) {
368 throw new NullPointerException();
370 DFS dfs=new DFS(nodes);
371 dfs.sccmap=new HashMap();
372 dfs.sccmaprev=new HashMap();
373 dfs.finishingorder=new Vector();
374 boolean acyclic=dfs.go();
375 for (Iterator it = nodes.iterator();it.hasNext();) {
376 GraphNode gn = (GraphNode) it.next();
379 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
380 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
381 if (gn.getStatus() == UNVISITED) {
383 dfs.sccindex++; /* Increment scc index */
386 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
389 void dfsprev(GraphNode gn) {
390 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
392 gn.setStatus(FINISHED);
393 Integer i=new Integer(sccindex);
394 if (!sccmap.containsKey(i))
395 sccmap.put(i,new HashSet());
396 ((Set)sccmap.get(i)).add(gn);
398 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
399 Edge e=(Edge)edgeit.next();
400 GraphNode gn2=e.getSource();
405 public static boolean depthFirstSearch(Collection nodes) {
407 throw new NullPointerException();
410 DFS dfs = new DFS(nodes);
414 private boolean go() {
417 boolean acyclic=true;
418 i = nodes.iterator();
419 while (i.hasNext()) {
420 GraphNode gn = (GraphNode) i.next();
424 i = nodes.iterator();
425 while (i.hasNext()) {
426 GraphNode gn = (GraphNode) i.next();
427 assert gn.getStatus() != PROCESSING;
428 if (gn.getStatus() == UNVISITED) {
436 private boolean dfs(GraphNode gn) {
437 boolean acyclic=true;
439 Iterator edges = gn.edges();
441 while (edges.hasNext()) {
442 Edge edge = (Edge) edges.next();
443 GraphNode node = edge.getTarget();
444 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
446 if (node.getStatus() == UNVISITED) {
449 } else if (node.getStatus()==PROCESSING) {
453 if (finishingorder!=null)
454 finishingorder.add(gn);