separate out naming functionality
[IRC.git] / Robust / src / Util / GraphNode.java
1 package Util;
2
3 import java.util.*;
4 import java.io.*;
5
6 public class GraphNode {
7     /* NodeStatus enumeration pattern ***********/
8
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");
12
13     public static class NodeStatus {
14         private static String name;
15         private NodeStatus(String name) { this.name = name; }
16         public String toString() { return name; }
17     }
18
19     int discoverytime = -1;
20     int finishingtime = -1; /* used for searches */
21
22     protected Vector edges = new Vector();
23     protected Vector inedges = new Vector();
24
25     NodeStatus status = UNVISITED;
26     String dotnodeparams = new String();
27     public boolean merge=false;
28
29     public void setMerge() {
30         merge=true;
31     }
32
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)) {
42                     if ((removed==null)||
43                         (!removed.contains(target))) {
44                         nodes.add(target);
45                         tovisit.push(target);
46                     }
47                 }
48             }
49         }
50     }
51
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)) {
63                         if ((removed==null)||
64                             (!removed.contains(target))) {
65                             nodes.add(target);
66                             newvisit.push(target);
67                         }
68                     }
69                 }
70             }
71             tovisit=newvisit;
72             newvisit=new Stack();
73         }
74     }
75
76     public void setDotNodeParameters(String param) {
77         if (param == null) {
78             throw new NullPointerException();
79         }
80         if (param.length() > 0) {
81             dotnodeparams = "," + param;
82         } else {
83             dotnodeparams = new String();
84         }
85     }
86
87     public void setStatus(NodeStatus status) {
88         if (status == null) {
89             throw new NullPointerException();
90         }
91         this.status = status;
92     }
93
94     public String getLabel() {
95         return "";
96     }
97
98     public String getTextLabel() {
99         return "";
100     }
101
102     public NodeStatus getStatus() {
103         return this.status;
104     }
105
106     public Iterator edges() {
107         return edges.iterator();
108     }
109
110     public Iterator inedges() {
111         return inedges.iterator();
112     }
113
114     public void addEdge(Edge newedge) {
115         newedge.setSource(this);
116         edges.addElement(newedge);
117         GraphNode tonode=newedge.getTarget();
118         tonode.inedges.addElement(newedge);
119     }
120
121     void reset() {
122             discoverytime = -1;
123             finishingtime = -1;
124             status = UNVISITED;
125     }
126
127     void resetscc() {
128         status = UNVISITED;
129     }
130
131     void discover(int time) {
132         discoverytime = time;
133         status = PROCESSING;
134     }
135
136     void finish(int time) {
137         assert status == PROCESSING;
138         finishingtime = time;
139         status = FINISHED;
140     }
141
142     /** Returns finishing time for dfs */
143
144     public int getFinishingTime() {
145         return finishingtime;
146     }
147
148
149     public static class DOTVisitor {
150
151         java.io.PrintWriter output;
152         int tokennumber;
153         int color;
154         Vector namers;
155
156         private DOTVisitor(java.io.OutputStream output, Vector namers) {
157             tokennumber = 0;
158             color = 0;
159             this.output = new java.io.PrintWriter(output, true);
160             this.namers=namers;
161         }
162
163         private String getNewID(String name) {
164             tokennumber = tokennumber + 1;
165             return new String (name+tokennumber);
166         }
167
168         Collection nodes;
169
170
171         public static void visit(java.io.OutputStream output, Collection nodes, Vector namers) {
172             DOTVisitor visitor = new DOTVisitor(output, namers);
173             visitor.nodes = nodes;
174             visitor.make();
175         }
176
177         public static void visit(java.io.OutputStream output, Collection nodes) {
178             Vector v=new Vector();
179             v.add(new Namer());
180             DOTVisitor visitor = new DOTVisitor(output, v);
181             visitor.nodes = nodes;
182             visitor.make();
183         }
184
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];");
195             traverse();
196             output.println("}\n");
197         }
198
199         private void traverse() {
200             Set cycleset=GraphNode.findcycles(nodes);
201
202             Iterator it = nodes.iterator();
203             while (it.hasNext()) {
204                 GraphNode gn = (GraphNode) it.next();
205                 Iterator edges = gn.edges();
206                 String label = "";
207                 String dotnodeparams="";
208
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);
213
214                     if (!newlabel.equals("") && !label.equals("")) {
215                         label+=", ";
216                     }
217                     if (!newparams.equals("")) {
218                         dotnodeparams+=", " + name.nodeOption(gn);
219                     }
220                     label+=name.nodeLabel(gn);
221                 }
222
223                 if (!gn.merge)
224                     output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
225
226                 if (!gn.merge)
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="";
235
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(""))
241                                     edgelabel+=", ";
242                                 edgelabel+=newlabel;
243                                 if (!newoption.equals(""))
244                                     edgedotnodeparams+=", "+newoption;
245                             }
246                             
247                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
248                         }
249                     }
250                 }
251             }
252         }
253
254         Set nonmerge(GraphNode gn) {
255             HashSet newset=new HashSet();
256             HashSet toprocess=new HashSet();
257             toprocess.add(gn);
258             while(!toprocess.isEmpty()) {
259                 GraphNode gn2=(GraphNode)toprocess.iterator().next();
260                 toprocess.remove(gn2);
261                 if (!gn2.merge)
262                     newset.add(gn2);
263                 else {
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))
269                             toprocess.add(node);
270                     }
271                 }
272             }
273             return newset;
274         }
275
276     }
277
278     /** This function returns the set of nodes involved in cycles.
279      *  It only considers cycles containing nodes in the set 'nodes'.
280     */
281     public static Set findcycles(Collection nodes) {
282         HashSet cycleset=new HashSet();
283         SCC scc=DFS.computeSCC(nodes);
284         if (!scc.hasCycles())
285             return cycleset;
286         for(int i=0;i<scc.numSCC();i++) {
287             if (scc.hasCycle(i))
288                 cycleset.addAll(scc.getSCC(i));
289         }
290         return cycleset;
291     }
292
293     public static class SCC {
294         boolean acyclic;
295         HashMap map,revmap;
296         int numscc;
297         public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
298             this.acyclic=acyclic;
299             this.map=map;
300             this.revmap=revmap;
301             this.numscc=numscc;
302         }
303
304         /** Returns whether the graph has any cycles */
305         public boolean hasCycles() {
306             return !acyclic;
307         }
308
309         /** Returns the number of Strongly Connected Components */
310         public int numSCC() {
311             return numscc;
312         }
313
314         /** Returns the strongly connected component number for the GraphNode gn*/
315         public int getComponent(GraphNode gn) {
316             return ((Integer)revmap.get(gn)).intValue();
317         }
318
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);
323         }
324
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);
329             if (s.size()>1)
330                 return true;
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 */
337             }
338             return false;
339         }
340     }
341
342     /**
343      * DFS encapsulates the depth first search algorithm
344      */
345     public static class DFS {
346
347         int time = 0;
348         int sccindex = 0;
349         Collection nodes;
350         Vector finishingorder=null;
351         HashMap sccmap;
352         HashMap sccmaprev;
353
354         private DFS(Collection nodes) {
355             this.nodes = nodes;
356         }
357         /** Calculates the strong connected components for the graph composed
358          *  of the set of nodes 'nodes'*/
359         public static SCC computeSCC(Collection nodes) {
360             if (nodes==null) {
361                 throw new NullPointerException();
362             }
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();
370                 gn.resetscc();
371             }
372             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
373                 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
374                 if (gn.getStatus() == UNVISITED) {
375                     dfs.dfsprev(gn);
376                     dfs.sccindex++; /* Increment scc index */
377                 }
378             }
379             return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
380         }
381
382         void dfsprev(GraphNode gn) {
383             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
384                 return;
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);
390             sccmaprev.put(gn,i);
391             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
392                 Edge e=(Edge)edgeit.next();
393                 GraphNode gn2=e.getSource();
394                 dfsprev(gn2);
395             }
396         }
397
398         public static boolean depthFirstSearch(Collection nodes) {
399             if (nodes == null) {
400                 throw new NullPointerException();
401             }
402
403             DFS dfs = new DFS(nodes);
404             return dfs.go();
405         }
406
407         private boolean go() {
408             Iterator i;
409             time = 0;
410             boolean acyclic=true;
411             i = nodes.iterator();
412             while (i.hasNext()) {
413                 GraphNode gn = (GraphNode) i.next();
414                 gn.reset();
415             }
416
417             i = nodes.iterator();
418             while (i.hasNext()) {
419                 GraphNode gn = (GraphNode) i.next();
420                 assert gn.getStatus() != PROCESSING;
421                 if (gn.getStatus() == UNVISITED) {
422                     if (!dfs(gn))
423                         acyclic=false;
424                 }
425             }
426             return acyclic;
427         }
428
429         private boolean dfs(GraphNode gn) {
430             boolean acyclic=true;
431             gn.discover(time++);
432             Iterator edges = gn.edges();
433
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 */
438                     continue;
439                 if (node.getStatus() == UNVISITED) {
440                     if (!dfs(node))
441                         acyclic=false;
442                 } else if (node.getStatus()==PROCESSING) {
443                     acyclic=false;
444                 }
445             }
446             if (finishingorder!=null)
447                 finishingorder.add(gn);
448             gn.finish(time++);
449             return acyclic;
450         }
451
452     } /* end DFS */
453
454 }