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) {
  16       this.name = name;
  17     }
  18     public String toString() {
  19       return name;
  20     }
  21   }
  22
  23   int discoverytime = -1;
  24   int finishingtime = -1;   /* used for searches */
  25
  26   protected Vector edges = new Vector();
  27   protected Vector inedges = new Vector();
  28
  29   NodeStatus status = UNVISITED;
  30   String dotnodeparams = new String();
  31   public boolean merge=false;
  32
  33   public void setMerge() {
  34     merge=true;
  35   }
  36
  37   public static void computeclosure(Collection nodes, Collection removed) {
  38     Stack tovisit=new Stack();
  39     tovisit.addAll(nodes);
  40     while(!tovisit.isEmpty()) {
  41       GraphNode gn=(GraphNode)tovisit.pop();
  42       for(Iterator it=gn.edges(); it.hasNext();) {
  43         Edge edge=(Edge)it.next();
  44         GraphNode target=edge.getTarget();
  45         if (!nodes.contains(target)) {
  46           if ((removed==null)||
  47               (!removed.contains(target))) {
  48             nodes.add(target);
  49             tovisit.push(target);
  50           }
  51         }
  52       }
  53     }
  54   }
  55
  56   public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) {
  57     Stack tovisit=new Stack();
  58     Stack newvisit=new Stack();
  59     tovisit.addAll(nodes);
  60     for(int i=0; i<depth&&!tovisit.isEmpty(); i++) {
  61       while(!tovisit.isEmpty()) {
  62         GraphNode gn=(GraphNode)tovisit.pop();
  63         for(Iterator it=gn.edges(); it.hasNext();) {
  64           Edge edge=(Edge)it.next();
  65           GraphNode target=edge.getTarget();
  66           if (!nodes.contains(target)) {
  67             if ((removed==null)||
  68                 (!removed.contains(target))) {
  69               nodes.add(target);
  70               newvisit.push(target);
  71             }
  72           }
  73         }
  74       }
  75       tovisit=newvisit;
  76       newvisit=new Stack();
  77     }
  78   }
  79
  80   public void setDotNodeParameters(String param) {
  81     if (param == null) {
  82       throw new NullPointerException();
  83     }
  84     if (dotnodeparams.length() > 0) {
  85       dotnodeparams += "," + param;
  86     } else {
  87       dotnodeparams = param;
  88     }
  89   }
  90
  91   public void setStatus(NodeStatus status) {
  92     if (status == null) {
  93       throw new NullPointerException();
  94     }
  95     this.status = status;
  96   }
  97
  98   public String getLabel() {
  99     return "";
 100   }
 101
 102   public String getTextLabel() {
 103     return "";
 104   }
 105
 106   public String getName() {
 107     return "";
 108   }
 109
 110   public NodeStatus getStatus() {
 111     return this.status;
 112   }
 113
 114   public int numedges() {
 115     return edges.size();
 116   }
 117
 118   public int numinedges() {
 119     return inedges.size();
 120   }
 121
 122   public Edge getedge(int i) {
 123     return (Edge) edges.get(i);
 124   }
 125
 126   public Edge getinedge(int i) {
 127     return (Edge) inedges.get(i);
 128   }
 129
 130   public Vector getEdgeVector() {
 131     return edges;
 132   }
 133
 134   public Vector getInedgeVector() {
 135     return inedges;
 136   }
 137
 138   public Iterator edges() {
 139     return edges.iterator();
 140   }
 141
 142   public Iterator inedges() {
 143     return inedges.iterator();
 144   }
 145
 146   public void addEdge(Edge newedge) {
 147     newedge.setSource(this);
 148     edges.addElement(newedge);
 149     GraphNode tonode=newedge.getTarget();
 150     tonode.inedges.addElement(newedge);
 151   }
 152
 153   public boolean containsEdge(Edge e) {
 154     return edges.contains(e);
 155   }
 156
 157   public void addEdge(Vector v) {
 158     for (Iterator it = v.iterator(); it.hasNext();)
 159       addEdge((Edge)it.next());
 160   }
 161
 162   public void removeEdge(Edge edge) {
 163     edges.remove(edge);
 164   }
 165
 166   public void removeInedge(Edge edge) {
 167     inedges.remove(edge);
 168   }
 169
 170   public void removeAllEdges() {
 171     edges.removeAllElements();
 172   }
 173
 174   public void removeAllInedges() {
 175     inedges.removeAllElements();
 176   }
 177   void reset() {
 178     discoverytime = -1;
 179     finishingtime = -1;
 180     status = UNVISITED;
 181   }
 182
 183   void resetscc() {
 184     status = UNVISITED;
 185   }
 186
 187   void discover(int time) {
 188     discoverytime = time;
 189     status = PROCESSING;
 190   }
 191
 192   void finish(int time) {
 193     assert status == PROCESSING;
 194     finishingtime = time;
 195     status = FINISHED;
 196   }
 197
 198   /** Returns finishing time for dfs */
 199
 200   public int getFinishingTime() {
 201     return finishingtime;
 202   }
 203
 204
 205   public static class DOTVisitor {
 206
 207     java.io.PrintWriter output;
 208     int tokennumber;
 209     int color;
 210     Vector namers;
 211
 212     private DOTVisitor(java.io.OutputStream output, Vector namers) {
 213       tokennumber = 0;
 214       color = 0;
 215       this.output = new java.io.PrintWriter(output, true);
 216       this.namers=namers;
 217     }
 218
 219     private String getNewID(String name) {
 220       tokennumber = tokennumber + 1;
 221       return new String(name+tokennumber);
 222     }
 223
 224     Collection nodes;
 225
 226
 227     public static void visit(java.io.OutputStream output, Collection nodes, Vector namers) {
 228       DOTVisitor visitor = new DOTVisitor(output, namers);
 229       visitor.nodes = nodes;
 230       visitor.make();
 231     }
 232
 233     public static void visit(java.io.OutputStream output, Collection nodes) {
 234       Vector v=new Vector();
 235       v.add(new Namer());
 236       DOTVisitor visitor = new DOTVisitor(output, v);
 237       visitor.nodes = nodes;
 238       visitor.make();
 239     }
 240
 241     private void make() {
 242       output.println("digraph dotvisitor {");
 243       /*            output.println("\tpage=\"8.5,11\";");
 244                     output.println("\tnslimit=1000.0;");
 245                     output.println("\tnslimit1=1000.0;");
 246                     output.println("\tmclimit=1000.0;");
 247                     output.println("\tremincross=true;");*/
 248       output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 249       output.println("\tedge [fontsize=6];");
 250       traverse();
 251       output.println("}\n");
 252     }
 253
 254
 255
 256     private void traverse() {
 257       Set cycleset=GraphNode.findcycles(nodes);
 258
 259       Iterator it = nodes.iterator();
 260       while (it.hasNext()) {
 261         GraphNode gn = (GraphNode) it.next();
 262         Iterator edges = gn.edges();
 263         String label = "";
 264         String dotnodeparams="";
 265
 266         for(int i=0; i<namers.size(); i++) {
 267           Namer name=(Namer) namers.get(i);
 268           String newlabel=name.nodeLabel(gn);
 269           String newparams=name.nodeOption(gn);
 270
 271           if (!newlabel.equals("") && !label.equals("")) {
 272             label+=", ";
 273           }
 274           if (!newparams.equals("")) {
 275             dotnodeparams+=", " + name.nodeOption(gn);
 276           }
 277           label+=name.nodeLabel(gn);
 278         }
 279
 280         if (!gn.merge)
 281           output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
 282
 283         if (!gn.merge)
 284           while (edges.hasNext()) {
 285             Edge edge = (Edge) edges.next();
 286             GraphNode node = edge.getTarget();
 287             if (nodes.contains(node)) {
 288               for(Iterator nodeit=nonmerge(node).iterator(); nodeit.hasNext();) {
 289                 GraphNode node2=(GraphNode)nodeit.next();
 290                 String edgelabel = "";
 291                 String edgedotnodeparams="";
 292
 293                 for(int i=0; i<namers.size(); i++) {
 294                   Namer name=(Namer) namers.get(i);
 295                   String newlabel=name.edgeLabel(edge);
 296                   String newoption=name.edgeOption(edge);
 297                   if (!newlabel.equals("")&& !edgelabel.equals(""))
 298                     edgelabel+=", ";
 299                   edgelabel+=newlabel;
 300                   if (!newoption.equals(""))
 301                     edgedotnodeparams+=", "+newoption;
 302                 }
 303
 304                 output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 305               }
 306             }
 307           }
 308       }
 309     }
 310
 311     Set nonmerge(GraphNode gn) {
 312       HashSet newset=new HashSet();
 313       HashSet toprocess=new HashSet();
 314       toprocess.add(gn);
 315       while(!toprocess.isEmpty()) {
 316         GraphNode gn2=(GraphNode)toprocess.iterator().next();
 317         toprocess.remove(gn2);
 318         if (!gn2.merge)
 319           newset.add(gn2);
 320         else {
 321           Iterator edges = gn2.edges();
 322           while (edges.hasNext()) {
 323             Edge edge = (Edge) edges.next();
 324             GraphNode node = edge.getTarget();
 325             if (!newset.contains(node)&&nodes.contains(node))
 326               toprocess.add(node);
 327           }
 328         }
 329       }
 330       return newset;
 331     }
 332
 333   }
 334
 335   /** This function returns the set of nodes involved in cycles.
 336    *    It only considers cycles containing nodes in the set 'nodes'.
 337    */
 338   public static Set findcycles(Collection nodes) {
 339     HashSet cycleset=new HashSet();
 340     SCC scc=DFS.computeSCC(nodes);
 341     if (!scc.hasCycles())
 342       return cycleset;
 343     for(int i=0; i<scc.numSCC(); i++) {
 344       if (scc.hasCycle(i))
 345         cycleset.addAll(scc.getSCC(i));
 346     }
 347     return cycleset;
 348   }
 349
 350   public static class SCC {
 351     boolean acyclic;
 352     HashMap map,revmap;
 353     int numscc;
 354     public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
 355       this.acyclic=acyclic;
 356       this.map=map;
 357       this.revmap=revmap;
 358       this.numscc=numscc;
 359     }
 360
 361     /** Returns whether the graph has any cycles */
 362     public boolean hasCycles() {
 363       return !acyclic;
 364     }
 365
 366     /** Returns the number of Strongly Connected Components */
 367     public int numSCC() {
 368       return numscc;
 369     }
 370
 371     /** Returns the strongly connected component number for the GraphNode gn*/
 372     public int getComponent(GraphNode gn) {
 373       return ((Integer)revmap.get(gn)).intValue();
 374     }
 375
 376     /** Returns the set of nodes in the strongly connected component i*/
 377     public Set getSCC(int i) {
 378       Integer scc=new Integer(i);
 379       return (Set)map.get(scc);
 380     }
 381
 382     /** Returns whether the strongly connected component i contains a cycle */
 383     boolean hasCycle(int i) {
 384       Integer scc=new Integer(i);
 385       Set s=(Set)map.get(scc);
 386       if (s.size()>1)
 387         return true;
 388       Object [] array=s.toArray();
 389       GraphNode gn=(GraphNode)array[0];
 390       for(Iterator it=gn.edges(); it.hasNext();) {
 391         Edge e=(Edge)it.next();
 392         if (e.getTarget()==gn)
 393           return true;           /* Self Cycle */
 394       }
 395       return false;
 396     }
 397   }
 398
 399   /**
 400    * DFS encapsulates the depth first search algorithm
 401    */
 402   public static class DFS {
 403
 404     int time = 0;
 405     int sccindex = 0;
 406     Collection nodes;
 407     Vector finishingorder=null;
 408     Vector finishingorder_edge = null;
 409     int edgetime = 0;
 410     HashMap sccmap;
 411     HashMap sccmaprev;
 412
 413     private DFS(Collection nodes) {
 414       this.nodes = nodes;
 415     }
 416     /** Calculates the strong connected components for the graph composed
 417      *  of the set of nodes 'nodes'*/
 418     public static SCC computeSCC(Collection nodes) {
 419       if (nodes==null) {
 420         throw new NullPointerException();
 421       }
 422       DFS dfs=new DFS(nodes);
 423       dfs.sccmap=new HashMap();
 424       dfs.sccmaprev=new HashMap();
 425       dfs.finishingorder=new Vector();
 426       boolean acyclic=dfs.go();
 427       for (Iterator it = nodes.iterator(); it.hasNext();) {
 428         GraphNode gn = (GraphNode) it.next();
 429         gn.resetscc();
 430       }
 431       for(int i=dfs.finishingorder.size()-1; i>=0; i--) {
 432         GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
 433         if (gn.getStatus() == UNVISITED) {
 434           dfs.dfsprev(gn);
 435           dfs.sccindex++;           /* Increment scc index */
 436         }
 437       }
 438       return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
 439     }
 440
 441     void dfsprev(GraphNode gn) {
 442       if (gn.getStatus()==FINISHED||!nodes.contains(gn))
 443         return;
 444       gn.setStatus(FINISHED);
 445       Integer i=new Integer(sccindex);
 446       if (!sccmap.containsKey(i))
 447         sccmap.put(i,new HashSet());
 448       ((Set)sccmap.get(i)).add(gn);
 449       sccmaprev.put(gn,i);
 450       for(Iterator edgeit=gn.inedges(); edgeit.hasNext();) {
 451         Edge e=(Edge)edgeit.next();
 452         GraphNode gn2=e.getSource();
 453         dfsprev(gn2);
 454       }
 455     }
 456
 457     public static boolean depthFirstSearch(Collection nodes) {
 458       if (nodes == null) {
 459         throw new NullPointerException();
 460       }
 461
 462       DFS dfs = new DFS(nodes);
 463       return dfs.go();
 464     }
 465
 466     private boolean go() {
 467       Iterator i;
 468       time = 0;
 469       edgetime = 0;
 470       boolean acyclic=true;
 471       i = nodes.iterator();
 472       while (i.hasNext()) {
 473         GraphNode gn = (GraphNode) i.next();
 474         gn.reset();
 475       }
 476
 477       i = nodes.iterator();
 478       while (i.hasNext()) {
 479         GraphNode gn = (GraphNode) i.next();
 480         assert gn.getStatus() != PROCESSING;
 481         if (gn.getStatus() == UNVISITED) {
 482           if (!dfs(gn))
 483             acyclic=false;
 484         }
 485       }
 486       return acyclic;
 487     }
 488
 489     private boolean dfs(GraphNode gn) {
 490       boolean acyclic=true;
 491       gn.discover(time++);
 492       Iterator edges = gn.edges();
 493
 494       while (edges.hasNext()) {
 495         Edge edge = (Edge) edges.next();
 496         edge.discover(edgetime++);
 497         GraphNode node = edge.getTarget();
 498         if (!nodes.contains(node)) {                       /* Skip nodes which aren't in the set */
 499           if(finishingorder_edge != null)
 500             finishingorder_edge.add(edge);
 501           edge.finish(edgetime++);
 502           continue;
 503         }
 504         if (node.getStatus() == UNVISITED) {
 505           if (!dfs(node))
 506             acyclic=false;
 507         } else if (node.getStatus()==PROCESSING) {
 508           acyclic=false;
 509         }
 510         if(finishingorder_edge != null)
 511           finishingorder_edge.add(edge);
 512         edge.finish(edgetime++);
 513       }
 514       if (finishingorder!=null)
 515         finishingorder.add(gn);
 516       gn.finish(time++);
 517       return acyclic;
 518     }
 519
 520     public static Vector topology(Collection nodes, Vector finishingorder_edge) {
 521       if (nodes==null) {
 522         throw new NullPointerException();
 523       }
 524       DFS dfs=new DFS(nodes);
 525       dfs.finishingorder=new Vector();
 526       if(finishingorder_edge != null) {
 527         dfs.finishingorder_edge = new Vector();
 528       }
 529       boolean acyclic=dfs.go();
 530       Vector topology = new Vector();
 531       for(int i=dfs.finishingorder.size()-1; i>=0; i--) {
 532         GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
 533         topology.add(gn);
 534       }
 535       if(finishingorder_edge != null) {
 536         for(int i=dfs.finishingorder_edge.size()-1; i>=0; i--) {
 537           Edge gn=(Edge)dfs.finishingorder_edge.get(i);
 538           finishingorder_edge.add(gn);
 539         }
 540       }
 541       return topology;
 542     }
 543   }   /* end DFS */
 544
 545 }