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 (param.length() > 0) {
81 dotnodeparams = "," + param;
83 dotnodeparams = new String();
87 public void setStatus(NodeStatus status) {
89 throw new NullPointerException();
94 public String getLabel() {
98 public String getTextLabel() {
102 public NodeStatus getStatus() {
106 public Iterator edges() {
107 return edges.iterator();
110 public Iterator inedges() {
111 return inedges.iterator();
114 public void addEdge(Edge newedge) {
115 newedge.setSource(this);
116 edges.addElement(newedge);
117 GraphNode tonode=newedge.getTarget();
118 tonode.inedges.addElement(newedge);
131 void discover(int time) {
132 discoverytime = time;
136 void finish(int time) {
137 assert status == PROCESSING;
138 finishingtime = time;
142 /** Returns finishing time for dfs */
144 public int getFinishingTime() {
145 return finishingtime;
149 public static class DOTVisitor {
151 java.io.PrintWriter output;
156 private DOTVisitor(java.io.OutputStream output, Vector namers) {
159 this.output = new java.io.PrintWriter(output, true);
163 private String getNewID(String name) {
164 tokennumber = tokennumber + 1;
165 return new String (name+tokennumber);
171 public static void visit(java.io.OutputStream output, Collection nodes, Vector namers) {
172 DOTVisitor visitor = new DOTVisitor(output, namers);
173 visitor.nodes = nodes;
177 public static void visit(java.io.OutputStream output, Collection nodes) {
178 Vector v=new Vector();
180 DOTVisitor visitor = new DOTVisitor(output, v);
181 visitor.nodes = nodes;
185 private void make() {
186 output.println("digraph dotvisitor {");
187 output.println("\trotate=90;");
188 /* output.println("\tpage=\"8.5,11\";");
189 output.println("\tnslimit=1000.0;");
190 output.println("\tnslimit1=1000.0;");
191 output.println("\tmclimit=1000.0;");
192 output.println("\tremincross=true;");*/
193 output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
194 output.println("\tedge [fontsize=6];");
196 output.println("}\n");
199 private void traverse() {
200 Set cycleset=GraphNode.findcycles(nodes);
202 Iterator it = nodes.iterator();
203 while (it.hasNext()) {
204 GraphNode gn = (GraphNode) it.next();
205 Iterator edges = gn.edges();
207 String dotnodeparams="";
209 for(int i=0;i<namers.size();i++) {
210 Namer name=(Namer) namers.get(i);
211 String newlabel=name.nodeLabel(gn);
212 String newparams=name.nodeOption(gn);
214 if (!newlabel.equals("") && !label.equals("")) {
217 if (!newparams.equals("")) {
218 dotnodeparams+=", " + name.nodeOption(gn);
220 label+=name.nodeLabel(gn);
224 output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
227 while (edges.hasNext()) {
228 Edge edge = (Edge) edges.next();
229 GraphNode node = edge.getTarget();
230 if (nodes.contains(node)) {
231 for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
232 GraphNode node2=(GraphNode)nodeit.next();
233 String edgelabel = "";
234 String edgedotnodeparams="";
236 for(int i=0;i<namers.size();i++) {
237 Namer name=(Namer) namers.get(i);
238 String newlabel=name.edgeLabel(gn, edge);
239 String newoption=name.edgeOption(gn, edge);
240 if (!newlabel.equals("")&& ! edgelabel.equals(""))
243 if (!newoption.equals(""))
244 edgedotnodeparams+=", "+newoption;
247 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
254 Set nonmerge(GraphNode gn) {
255 HashSet newset=new HashSet();
256 HashSet toprocess=new HashSet();
258 while(!toprocess.isEmpty()) {
259 GraphNode gn2=(GraphNode)toprocess.iterator().next();
260 toprocess.remove(gn2);
264 Iterator edges = gn2.edges();
265 while (edges.hasNext()) {
266 Edge edge = (Edge) edges.next();
267 GraphNode node = edge.getTarget();
268 if (!newset.contains(node)&&nodes.contains(node))
278 /** This function returns the set of nodes involved in cycles.
279 * It only considers cycles containing nodes in the set 'nodes'.
281 public static Set findcycles(Collection nodes) {
282 HashSet cycleset=new HashSet();
283 SCC scc=DFS.computeSCC(nodes);
284 if (!scc.hasCycles())
286 for(int i=0;i<scc.numSCC();i++) {
288 cycleset.addAll(scc.getSCC(i));
293 public static class SCC {
297 public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
298 this.acyclic=acyclic;
304 /** Returns whether the graph has any cycles */
305 public boolean hasCycles() {
309 /** Returns the number of Strongly Connected Components */
310 public int numSCC() {
314 /** Returns the strongly connected component number for the GraphNode gn*/
315 public int getComponent(GraphNode gn) {
316 return ((Integer)revmap.get(gn)).intValue();
319 /** Returns the set of nodes in the strongly connected component i*/
320 public Set getSCC(int i) {
321 Integer scc=new Integer(i);
322 return (Set)map.get(scc);
325 /** Returns whether the strongly connected component i contains a cycle */
326 boolean hasCycle(int i) {
327 Integer scc=new Integer(i);
328 Set s=(Set)map.get(scc);
331 Object [] array=s.toArray();
332 GraphNode gn=(GraphNode)array[0];
333 for(Iterator it=gn.edges();it.hasNext();) {
334 Edge e=(Edge)it.next();
335 if (e.getTarget()==gn)
336 return true; /* Self Cycle */
343 * DFS encapsulates the depth first search algorithm
345 public static class DFS {
350 Vector finishingorder=null;
354 private DFS(Collection nodes) {
357 /** Calculates the strong connected components for the graph composed
358 * of the set of nodes 'nodes'*/
359 public static SCC computeSCC(Collection nodes) {
361 throw new NullPointerException();
363 DFS dfs=new DFS(nodes);
364 dfs.sccmap=new HashMap();
365 dfs.sccmaprev=new HashMap();
366 dfs.finishingorder=new Vector();
367 boolean acyclic=dfs.go();
368 for (Iterator it = nodes.iterator();it.hasNext();) {
369 GraphNode gn = (GraphNode) it.next();
372 for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
373 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
374 if (gn.getStatus() == UNVISITED) {
376 dfs.sccindex++; /* Increment scc index */
379 return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
382 void dfsprev(GraphNode gn) {
383 if (gn.getStatus()==FINISHED||!nodes.contains(gn))
385 gn.setStatus(FINISHED);
386 Integer i=new Integer(sccindex);
387 if (!sccmap.containsKey(i))
388 sccmap.put(i,new HashSet());
389 ((Set)sccmap.get(i)).add(gn);
391 for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
392 Edge e=(Edge)edgeit.next();
393 GraphNode gn2=e.getSource();
398 public static boolean depthFirstSearch(Collection nodes) {
400 throw new NullPointerException();
403 DFS dfs = new DFS(nodes);
407 private boolean go() {
410 boolean acyclic=true;
411 i = nodes.iterator();
412 while (i.hasNext()) {
413 GraphNode gn = (GraphNode) i.next();
417 i = nodes.iterator();
418 while (i.hasNext()) {
419 GraphNode gn = (GraphNode) i.next();
420 assert gn.getStatus() != PROCESSING;
421 if (gn.getStatus() == UNVISITED) {
429 private boolean dfs(GraphNode gn) {
430 boolean acyclic=true;
432 Iterator edges = gn.edges();
434 while (edges.hasNext()) {
435 Edge edge = (Edge) edges.next();
436 GraphNode node = edge.getTarget();
437 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
439 if (node.getStatus() == UNVISITED) {
442 } else if (node.getStatus()==PROCESSING) {
446 if (finishingorder!=null)
447 finishingorder.add(gn);