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 String getName(){
 103                 return "";
 104         }
 105
 106     public NodeStatus getStatus() {
 107         return this.status;
 108     }
 109
 110     public int numedges() {
 111         return edges.size();
 112     }
 113
 114     public int numinedges() {
 115         return inedges.size();
 116     }
 117
 118     public Edge getedge(int i) {
 119         return (Edge) edges.get(i);
 120     }
 121
 122     public Edge getinedge(int i) {
 123         return (Edge) inedges.get(i);
 124     }
 125
 126     public Iterator edges() {
 127         return edges.iterator();
 128     }
 129
 130     public Iterator inedges() {
 131         return inedges.iterator();
 132     }
 133
 134     public void addEdge(Edge newedge) {
 135         newedge.setSource(this);
 136         edges.addElement(newedge);
 137         GraphNode tonode=newedge.getTarget();
 138         tonode.inedges.addElement(newedge);
 139     }
 140
 141     void reset() {
 142             discoverytime = -1;
 143             finishingtime = -1;
 144             status = UNVISITED;
 145     }
 146
 147     void resetscc() {
 148         status = UNVISITED;
 149     }
 150
 151     void discover(int time) {
 152         discoverytime = time;
 153         status = PROCESSING;
 154     }
 155
 156     void finish(int time) {
 157         assert status == PROCESSING;
 158         finishingtime = time;
 159         status = FINISHED;
 160     }
 161
 162     /** Returns finishing time for dfs */
 163
 164     public int getFinishingTime() {
 165         return finishingtime;
 166     }
 167
 168
 169     public static class DOTVisitor {
 170
 171         java.io.PrintWriter output;
 172         int tokennumber;
 173         int color;
 174         Vector namers;
 175
 176         private DOTVisitor(java.io.OutputStream output, Vector namers) {
 177             tokennumber = 0;
 178             color = 0;
 179             this.output = new java.io.PrintWriter(output, true);
 180             this.namers=namers;
 181         }
 182
 183         private String getNewID(String name) {
 184             tokennumber = tokennumber + 1;
 185             return new String (name+tokennumber);
 186         }
 187
 188         Collection nodes;
 189
 190
 191         public static void visit(java.io.OutputStream output, Collection nodes, Vector namers) {
 192             DOTVisitor visitor = new DOTVisitor(output, namers);
 193             visitor.nodes = nodes;
 194             visitor.make();
 195         }
 196
 197         public static void visit(java.io.OutputStream output, Collection nodes) {
 198             Vector v=new Vector();
 199             v.add(new Namer());
 200             DOTVisitor visitor = new DOTVisitor(output, v);
 201             visitor.nodes = nodes;
 202             visitor.make();
 203         }
 204
 205         private void make() {
 206             output.println("digraph dotvisitor {");
 207             /*            output.println("\tpage=\"8.5,11\";");
 208                           output.println("\tnslimit=1000.0;");
 209                           output.println("\tnslimit1=1000.0;");
 210                           output.println("\tmclimit=1000.0;");
 211                           output.println("\tremincross=true;");*/
 212             output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];");
 213             output.println("\tedge [fontsize=6];");
 214             traverse();
 215             output.println("}\n");
 216         }
 217
 218         private void traverse() {
 219             Set cycleset=GraphNode.findcycles(nodes);
 220
 221             Iterator it = nodes.iterator();
 222             while (it.hasNext()) {
 223                 GraphNode gn = (GraphNode) it.next();
 224                 Iterator edges = gn.edges();
 225                 String label = "";
 226                 String dotnodeparams="";
 227
 228                 for(int i=0;i<namers.size();i++) {
 229                     Namer name=(Namer) namers.get(i);
 230                     String newlabel=name.nodeLabel(gn);
 231                     String newparams=name.nodeOption(gn);
 232
 233                     if (!newlabel.equals("") && !label.equals("")) {
 234                         label+=", ";
 235                     }
 236                     if (!newparams.equals("")) {
 237                         dotnodeparams+=", " + name.nodeOption(gn);
 238                     }
 239                     label+=name.nodeLabel(gn);
 240                 }
 241
 242                 if (!gn.merge)
 243                     output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
 244
 245                 if (!gn.merge)
 246                 while (edges.hasNext()) {
 247                     Edge edge = (Edge) edges.next();
 248                     GraphNode node = edge.getTarget();
 249                     if (nodes.contains(node)) {
 250                         for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
 251                             GraphNode node2=(GraphNode)nodeit.next();
 252                             String edgelabel = "";
 253                             String edgedotnodeparams="";
 254
 255                             for(int i=0;i<namers.size();i++) {
 256                                 Namer name=(Namer) namers.get(i);
 257                                 String newlabel=name.edgeLabel(edge);
 258                                 String newoption=name.edgeOption(edge);
 259                                 if (!newlabel.equals("")&& ! edgelabel.equals(""))
 260                                     edgelabel+=", ";
 261                                 edgelabel+=newlabel;
 262                                 if (!newoption.equals(""))
 263                                     edgedotnodeparams+=", "+newoption;
 264                             }
 265
 266                             output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
 267                         }
 268                     }
 269                 }
 270             }
 271         }
 272
 273         Set nonmerge(GraphNode gn) {
 274             HashSet newset=new HashSet();
 275             HashSet toprocess=new HashSet();
 276             toprocess.add(gn);
 277             while(!toprocess.isEmpty()) {
 278                 GraphNode gn2=(GraphNode)toprocess.iterator().next();
 279                 toprocess.remove(gn2);
 280                 if (!gn2.merge)
 281                     newset.add(gn2);
 282                 else {
 283                     Iterator edges = gn2.edges();
 284                     while (edges.hasNext()) {
 285                         Edge edge = (Edge) edges.next();
 286                         GraphNode node = edge.getTarget();
 287                         if (!newset.contains(node)&&nodes.contains(node))
 288                             toprocess.add(node);
 289                     }
 290                 }
 291             }
 292             return newset;
 293         }
 294
 295     }
 296
 297     /** This function returns the set of nodes involved in cycles.
 298      *  It only considers cycles containing nodes in the set 'nodes'.
 299     */
 300     public static Set findcycles(Collection nodes) {
 301         HashSet cycleset=new HashSet();
 302         SCC scc=DFS.computeSCC(nodes);
 303         if (!scc.hasCycles())
 304             return cycleset;
 305         for(int i=0;i<scc.numSCC();i++) {
 306             if (scc.hasCycle(i))
 307                 cycleset.addAll(scc.getSCC(i));
 308         }
 309         return cycleset;
 310     }
 311
 312     public static class SCC {
 313         boolean acyclic;
 314         HashMap map,revmap;
 315         int numscc;
 316         public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
 317             this.acyclic=acyclic;
 318             this.map=map;
 319             this.revmap=revmap;
 320             this.numscc=numscc;
 321         }
 322
 323         /** Returns whether the graph has any cycles */
 324         public boolean hasCycles() {
 325             return !acyclic;
 326         }
 327
 328         /** Returns the number of Strongly Connected Components */
 329         public int numSCC() {
 330             return numscc;
 331         }
 332
 333         /** Returns the strongly connected component number for the GraphNode gn*/
 334         public int getComponent(GraphNode gn) {
 335             return ((Integer)revmap.get(gn)).intValue();
 336         }
 337
 338         /** Returns the set of nodes in the strongly connected component i*/
 339         public Set getSCC(int i) {
 340             Integer scc=new Integer(i);
 341             return (Set)map.get(scc);
 342         }
 343
 344         /** Returns whether the strongly connected component i contains a cycle */
 345         boolean hasCycle(int i) {
 346             Integer scc=new Integer(i);
 347             Set s=(Set)map.get(scc);
 348             if (s.size()>1)
 349                 return true;
 350             Object [] array=s.toArray();
 351             GraphNode gn=(GraphNode)array[0];
 352             for(Iterator it=gn.edges();it.hasNext();) {
 353                 Edge e=(Edge)it.next();
 354                 if (e.getTarget()==gn)
 355                     return true; /* Self Cycle */
 356             }
 357             return false;
 358         }
 359     }
 360
 361     /**
 362      * DFS encapsulates the depth first search algorithm
 363      */
 364     public static class DFS {
 365
 366         int time = 0;
 367         int sccindex = 0;
 368         Collection nodes;
 369         Vector finishingorder=null;
 370         HashMap sccmap;
 371         HashMap sccmaprev;
 372
 373         private DFS(Collection nodes) {
 374             this.nodes = nodes;
 375         }
 376         /** Calculates the strong connected components for the graph composed
 377          *  of the set of nodes 'nodes'*/
 378         public static SCC computeSCC(Collection nodes) {
 379             if (nodes==null) {
 380                 throw new NullPointerException();
 381             }
 382             DFS dfs=new DFS(nodes);
 383             dfs.sccmap=new HashMap();
 384             dfs.sccmaprev=new HashMap();
 385             dfs.finishingorder=new Vector();
 386             boolean acyclic=dfs.go();
 387             for (Iterator it = nodes.iterator();it.hasNext();) {
 388                 GraphNode gn = (GraphNode) it.next();
 389                 gn.resetscc();
 390             }
 391             for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
 392                 GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
 393                 if (gn.getStatus() == UNVISITED) {
 394                     dfs.dfsprev(gn);
 395                     dfs.sccindex++; /* Increment scc index */
 396                 }
 397             }
 398             return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex);
 399         }
 400
 401         void dfsprev(GraphNode gn) {
 402             if (gn.getStatus()==FINISHED||!nodes.contains(gn))
 403                 return;
 404             gn.setStatus(FINISHED);
 405             Integer i=new Integer(sccindex);
 406             if (!sccmap.containsKey(i))
 407                 sccmap.put(i,new HashSet());
 408             ((Set)sccmap.get(i)).add(gn);
 409             sccmaprev.put(gn,i);
 410             for(Iterator edgeit=gn.inedges();edgeit.hasNext();) {
 411                 Edge e=(Edge)edgeit.next();
 412                 GraphNode gn2=e.getSource();
 413                 dfsprev(gn2);
 414             }
 415         }
 416
 417         public static boolean depthFirstSearch(Collection nodes) {
 418             if (nodes == null) {
 419                 throw new NullPointerException();
 420             }
 421
 422             DFS dfs = new DFS(nodes);
 423             return dfs.go();
 424         }
 425
 426         private boolean go() {
 427             Iterator i;
 428             time = 0;
 429             boolean acyclic=true;
 430             i = nodes.iterator();
 431             while (i.hasNext()) {
 432                 GraphNode gn = (GraphNode) i.next();
 433                 gn.reset();
 434             }
 435
 436             i = nodes.iterator();
 437             while (i.hasNext()) {
 438                 GraphNode gn = (GraphNode) i.next();
 439                 assert gn.getStatus() != PROCESSING;
 440                 if (gn.getStatus() == UNVISITED) {
 441                     if (!dfs(gn))
 442                         acyclic=false;
 443                 }
 444             }
 445             return acyclic;
 446         }
 447
 448         private boolean dfs(GraphNode gn) {
 449             boolean acyclic=true;
 450             gn.discover(time++);
 451             Iterator edges = gn.edges();
 452
 453             while (edges.hasNext()) {
 454                 Edge edge = (Edge) edges.next();
 455                 GraphNode node = edge.getTarget();
 456                 if (!nodes.contains(node)) /* Skip nodes which aren't in the set */
 457                     continue;
 458                 if (node.getStatus() == UNVISITED) {
 459                     if (!dfs(node))
 460                         acyclic=false;
 461                 } else if (node.getStatus()==PROCESSING) {
 462                     acyclic=false;
 463                 }
 464             }
 465             if (finishingorder!=null)
 466                 finishingorder.add(gn);
 467             gn.finish(time++);
 468             return acyclic;
 469         }
 470
 471     } /* end DFS */
 472
 473 }