From: bdemsky Date: Thu, 1 Apr 2004 18:45:12 +0000 (+0000) Subject: Replaced findcycles method with something more efficient based on SCC computation. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=repair.git;a=commitdiff_plain;h=83e11f87b6627ff592f1b14ab1117abd38050732 Replaced findcycles method with something more efficient based on SCC computation. --- diff --git a/Repair/RepairCompiler/MCC/IR/GraphNode.java b/Repair/RepairCompiler/MCC/IR/GraphNode.java index de8fe32..13500ea 100755 --- a/Repair/RepairCompiler/MCC/IR/GraphNode.java +++ b/Repair/RepairCompiler/MCC/IR/GraphNode.java @@ -64,7 +64,6 @@ public class GraphNode { int discoverytime = -1; int finishingtime = -1; /* used for searches */ - int scc = -1; Vector edges = new Vector(); Vector inedges = new Vector(); @@ -167,15 +166,6 @@ public class GraphNode { void resetscc() { status = UNVISITED; - scc = -1; - } - - public int getSCC() { - return scc; - } - - void setSCC(int s) { - scc=s; } void discover(int time) { @@ -261,73 +251,55 @@ public class GraphNode { } } - /* XXXXXXXX Should use SCC algorithm here - will change */ + /** This function returns the set of nodes involved in cycles. + * It only considers cycles containing nodes in the set 'nodes'. + */ public static Set findcycles(Collection nodes) { - Stack st=new Stack(); - HashSet acyclic=new HashSet(); - HashSet cycles=new HashSet(); - for(Iterator it=nodes.iterator();it.hasNext();) { - GraphNode node=(GraphNode)it.next(); - if (acyclic.contains(node)) - continue; - if (cycles.contains(node)) - continue; - findcycles(cycles, acyclic, st,node,nodes); + HashSet cycleset=new HashSet(); + SCC scc=DFS.computeSCC(nodes); + if (!scc.hasCycles()) + return cycleset; + for(int i=0;i1) @@ -353,19 +325,22 @@ public class GraphNode { Collection nodes; Vector finishingorder=null; HashMap sccmap; + HashMap sccmaprev; private DFS(Collection nodes) { this.nodes = nodes; } - + /** Calculates the strong connected components for the graph composed + * of the set of nodes 'nodes'*/ public static SCC computeSCC(Collection nodes) { if (nodes==null) { throw new NullPointerException(); } DFS dfs=new DFS(nodes); dfs.sccmap=new HashMap(); + dfs.sccmaprev=new HashMap(); dfs.finishingorder=new Vector(); - boolean hascycles=dfs.go(); + boolean acyclic=dfs.go(); for (Iterator it = nodes.iterator();it.hasNext();) { GraphNode gn = (GraphNode) it.next(); gn.resetscc(); @@ -377,18 +352,18 @@ public class GraphNode { dfs.sccindex++; /* Increment scc index */ } } - return new SCC(hascycles,dfs.sccmap,dfs.sccindex); + return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex); } void dfsprev(GraphNode gn) { if (gn.getStatus()==FINISHED||!nodes.contains(gn)) return; gn.setStatus(FINISHED); - gn.setSCC(sccindex); Integer i=new Integer(sccindex); if (!sccmap.containsKey(i)) sccmap.put(i,new HashSet()); ((Set)sccmap.get(i)).add(gn); + sccmaprev.put(gn,i); for(Iterator edgeit=gn.inedges();edgeit.hasNext();) { Edge e=(Edge)edgeit.next(); GraphNode gn2=e.getSource();