Programming Languages Research Group: Git - IRC.git/blob

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