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 protected Vector edges = new Vector();
23 protected Vector inedges = new Vector();
25 NodeStatus status = UNVISITED;
26 String dotnodeparams = new String();
27 public boolean merge=false;
29 public void setMerge() {
33 public static void computeclosure(Collection nodes, Collection removed) {
34 Stack tovisit=new Stack();
35 tovisit.addAll(nodes);
36 while(!tovisit.isEmpty()) {
37 GraphNode gn=(GraphNode)tovisit.pop();
38 for(Iterator it=gn.edges();it.hasNext();) {
39 Edge edge=(Edge)it.next();
40 GraphNode target=edge.getTarget();
41 if (!nodes.contains(target)) {
43 (!removed.contains(target))) {
52 public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
53 Stack tovisit=new Stack();
54 Stack newvisit=new Stack();
55 tovisit.addAll(nodes);
56 for(int i=0;i<depth&&!tovisit.isEmpty();i++) {
57 while(!tovisit.isEmpty()) {
58 GraphNode gn=(GraphNode)tovisit.pop();
59 for(Iterator it=gn.edges();it.hasNext();) {
60 Edge edge=(Edge)it.next();
61 GraphNode target=edge.getTarget();
62 if (!nodes.contains(target)) {
64 (!removed.contains(target))) {
66 newvisit.push(target);
76 public void setDotNodeParameters(String param) {
78 throw new NullPointerException();
80 if (dotnodeparams.length() > 0) {
81 dotnodeparams += "," + param;
83 dotnodeparams = param;
87 public void setStatus(NodeStatus status) {
89 throw new NullPointerException();
94 public String getLabel() {
98 public String getTextLabel() {
102 public String getName(){
106 public NodeStatus getStatus() {
110 public int numedges() {
114 public int numinedges() {
115 return inedges.size();
118 public Edge getedge(int i) {
119 return (Edge) edges.get(i);
122 public Edge getinedge(int i) {
123 return (Edge) inedges.get(i);
126 public Vector getEdgeVector() {
130 public Vector getInedgeVector() {
134 public Iterator edges() {
135 return edges.iterator();
138 public Iterator inedges() {
139 return inedges.iterator();
142 public void addEdge(Edge newedge) {
143 newedge.setSource(this);
144 edges.addElement(newedge);
145 GraphNode tonode=newedge.getTarget();
146 tonode.inedges.addElement(newedge);
149 public boolean containsEdge(Edge e) {
150 return edges.contains(e);
153 public void addEdge(Vector v) {
154 for (Iterator it = v.iterator(); it.hasNext();)
155 addEdge((Edge)it.next());
158 public void removeEdge(Edge edge) {
162 public void removeInedge(Edge edge) {
163 inedges.remove(edge);
166 public void removeAllEdges() {
167 edges.removeAllElements();
170 public void removeAllInedges() {
171 inedges.removeAllElements();
183 void discover(int time) {
184 discoverytime = time;
188 void finish(int time) {
189 assert status == PROCESSING;
190 finishingtime = time;
194 /** Returns finishing time for dfs */
196 public int getFinishingTime() {
197 return finishingtime;
201 public static class DOTVisitor {
203 java.io.PrintWriter output;
208 private DOTVisitor(java.io.OutputStream output, Vector namers) {
211 this.output = new java.io.PrintWriter(output, true);
215 private String getNewID(String name) {
216 tokennumber = tokennumber + 1;
217 return new String (name+tokennumber);
223 public static void visit(java.io.OutputStream output, Collection nodes, Vector namers) {
224 DOTVisitor visitor = new DOTVisitor(output, namers);
225 visitor.nodes = nodes;
229 public static void visit(java.io.OutputStream output, Collection nodes) {
230 Vector v=new Vector();
232 DOTVisitor visitor = new DOTVisitor(output, v);
233 visitor.nodes = nodes;
237 private void make() {
238 output.println("digraph dotvisitor {");
239 /* output.println("\tpage=\"8.5,11\";");
240 output.println("\tnslimit=1000.0;");
241 output.println("\tnslimit1=1000.0;");
242 output.println("\tmclimit=1000.0;");
243 output.println("\tremincross=true;");*/
244 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
245 output.println("\tedge [fontsize=6];");
247 output.println("}\n");
252 private void traverse() {
253 Set cycleset=GraphNode.findcycles(nodes);
255 Iterator it = nodes.iterator();
256 while (it.hasNext()) {
257 GraphNode gn = (GraphNode) it.next();
258 Iterator edges = gn.edges();
260 String dotnodeparams="";
262 for(int i=0;i<namers.size();i++) {
263 Namer name=(Namer) namers.get(i);
264 String newlabel=name.nodeLabel(gn);
265 String newparams=name.nodeOption(gn);
267 if (!newlabel.equals("") && !label.equals("")) {
270 if (!newparams.equals("")) {
271 dotnodeparams+=", " + name.nodeOption(gn);
273 label+=name.nodeLabel(gn);
277 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
280 while (edges.hasNext()) {
281 Edge edge = (Edge) edges.next();
282 GraphNode node = edge.getTarget();
283 if (nodes.contains(node)) {
284 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
285 GraphNode node2=(GraphNode)nodeit.next();
286 String edgelabel = "";
287 String edgedotnodeparams="";
289 for(int i=0;i<namers.size();i++) {
290 Namer name=(Namer) namers.get(i);
291 String newlabel=name.edgeLabel(edge);
292 String newoption=name.edgeOption(edge);
293 if (!newlabel.equals("")&& ! edgelabel.equals(""))
296 if (!newoption.equals(""))
297 edgedotnodeparams+=", "+newoption;
300 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
307 Set nonmerge(GraphNode gn) {
308 HashSet newset=new HashSet();
309 HashSet toprocess=new HashSet();
311 while(!toprocess.isEmpty()) {
312 GraphNode gn2=(GraphNode)toprocess.iterator().next();
313 toprocess.remove(gn2);
317 Iterator edges = gn2.edges();
318 while (edges.hasNext()) {
319 Edge edge = (Edge) edges.next();
320 GraphNode node = edge.getTarget();
321 if (!newset.contains(node)&&nodes.contains(node))
331 /** This function returns the set of nodes involved in cycles.
332 * It only considers cycles containing nodes in the set 'nodes'.
334 public static Set findcycles(Collection nodes) {
335 HashSet cycleset=new HashSet();
336 SCC scc=DFS.computeSCC(nodes);
337 if (!scc.hasCycles())
339 for(int i=0;i<scc.numSCC();i++) {
341 cycleset.addAll(scc.getSCC(i));
346 public static class SCC {
350 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
351 this.acyclic=acyclic;
357 /** Returns whether the graph has any cycles */
358 public boolean hasCycles() {
362 /** Returns the number of Strongly Connected Components */
363 public int numSCC() {
367 /** Returns the strongly connected component number for the GraphNode gn*/
368 public int getComponent(GraphNode gn) {
369 return ((Integer)revmap.get(gn)).intValue();
372 /** Returns the set of nodes in the strongly connected component i*/
373 public Set getSCC(int i) {
374 Integer scc=new Integer(i);
375 return (Set)map.get(scc);
378 /** Returns whether the strongly connected component i contains a cycle */
379 boolean hasCycle(int i) {
380 Integer scc=new Integer(i);
381 Set s=(Set)map.get(scc);
384 Object [] array=s.toArray();
385 GraphNode gn=(GraphNode)array[0];
386 for(Iterator it=gn.edges();it.hasNext();) {
387 Edge e=(Edge)it.next();
388 if (e.getTarget()==gn)
389 return true; /* Self Cycle */
396 * DFS encapsulates the depth first search algorithm
398 public static class DFS {
403 Vector finishingorder=null;
404 Vector finishingorder_edge = null;
409 private DFS(Collection nodes) {
412 /** Calculates the strong connected components for the graph composed
413 * of the set of nodes 'nodes'*/
414 public static SCC computeSCC(Collection nodes) {
416 throw new NullPointerException();
418 DFS dfs=new DFS(nodes);
419 dfs.sccmap=new HashMap();
420 dfs.sccmaprev=new HashMap();
421 dfs.finishingorder=new Vector();
422 boolean acyclic=dfs.go();
423 for (Iterator it = nodes.iterator();it.hasNext();) {
424 GraphNode gn = (GraphNode) it.next();
427 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
428 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
429 if (gn.getStatus() == UNVISITED) {
431 dfs.sccindex++; /* Increment scc index */
434 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
437 void dfsprev(GraphNode gn) {
438 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
440 gn.setStatus(FINISHED);
441 Integer i=new Integer(sccindex);
442 if (!sccmap.containsKey(i))
443 sccmap.put(i,new HashSet());
444 ((Set)sccmap.get(i)).add(gn);
446 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
447 Edge e=(Edge)edgeit.next();
448 GraphNode gn2=e.getSource();
453 public static boolean depthFirstSearch(Collection nodes) {
455 throw new NullPointerException();
458 DFS dfs = new DFS(nodes);
462 private boolean go() {
466 boolean acyclic=true;
467 i = nodes.iterator();
468 while (i.hasNext()) {
469 GraphNode gn = (GraphNode) i.next();
473 i = nodes.iterator();
474 while (i.hasNext()) {
475 GraphNode gn = (GraphNode) i.next();
476 assert gn.getStatus() != PROCESSING;
477 if (gn.getStatus() == UNVISITED) {
485 private boolean dfs(GraphNode gn) {
486 boolean acyclic=true;
488 Iterator edges = gn.edges();
490 while (edges.hasNext()) {
491 Edge edge = (Edge) edges.next();
492 edge.discover(edgetime++);
493 GraphNode node = edge.getTarget();
494 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ {
495 if(finishingorder_edge != null)
496 finishingorder_edge.add(edge);
497 edge.finish(edgetime++);
500 if (node.getStatus() == UNVISITED) {
503 } else if (node.getStatus()==PROCESSING) {
506 if(finishingorder_edge != null)
507 finishingorder_edge.add(edge);
508 edge.finish(edgetime++);
510 if (finishingorder!=null)
511 finishingorder.add(gn);
516 public static Vector topology(Collection nodes, Vector finishingorder_edge) {
518 throw new NullPointerException();
520 DFS dfs=new DFS(nodes);
521 dfs.finishingorder=new Vector();
522 if(finishingorder_edge != null) {
523 dfs.finishingorder_edge = new Vector();
525 boolean acyclic=dfs.go();
526 Vector topology = new Vector();
527 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
528 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
531 if(finishingorder_edge != null) {
532 for(int i=dfs.finishingorder_edge.size()-1;i>=0;i--) {
533 Edge gn=(Edge)dfs.finishingorder_edge.get(i);
534 finishingorder_edge.add(gn);