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 }