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