From 0a1378fe326f6f343dc3b197185f97bd077bb1e2 Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 18 May 2007 04:23:23 +0000 Subject: [PATCH] Migrate GraphNode functionality into its own class and we inherit from this class... --- .../src/Analysis/TaskStateAnalysis/Edge.java | 64 --- .../src/Analysis/TaskStateAnalysis/FEdge.java | 38 ++ .../Analysis/TaskStateAnalysis/FlagState.java | 415 +---------------- .../TaskStateAnalysis/TaskAnalysis.java | 4 +- Robust/src/Util/Edge.java | 40 ++ Robust/src/Util/GraphNode.java | 427 ++++++++++++++++++ 6 files changed, 513 insertions(+), 475 deletions(-) delete mode 100644 Robust/src/Analysis/TaskStateAnalysis/Edge.java create mode 100644 Robust/src/Analysis/TaskStateAnalysis/FEdge.java create mode 100644 Robust/src/Util/Edge.java create mode 100755 Robust/src/Util/GraphNode.java diff --git a/Robust/src/Analysis/TaskStateAnalysis/Edge.java b/Robust/src/Analysis/TaskStateAnalysis/Edge.java deleted file mode 100644 index 097f22f4..00000000 --- a/Robust/src/Analysis/TaskStateAnalysis/Edge.java +++ /dev/null @@ -1,64 +0,0 @@ -package Analysis.TaskStateAnalysis; -import IR.*; -import Analysis.TaskStateAnalysis.*; -import IR.Tree.*; -import IR.Flat.*; -import java.util.*; - - -/* Edge *****************/ - -public class Edge { - - private String label; - private FlagState target; - private FlagState source; - protected String dotnodeparams = new String(); - - public Edge(FlagState target, String label) { - this.label = label; - this.target = target; - } - - public String getLabel() { - return label; - } - - public void setSource(FlagState s) { - this.source=s; - } - - public FlagState getSource() { - return source; - } - - public FlagState getTarget() { - return target; - } - - public int hashCode(){ - return target.hashCode()^label.hashCode(); - } - - public void setDotNodeParameters(String param) { - if (param == null) { - throw new NullPointerException(); - } - if (param.length() > 0) { - dotnodeparams = "," + param; - } else { - dotnodeparams = new String(); - } - } - public boolean equals(Object o) { - if (o instanceof Edge) { - Edge e=(Edge)o; - if (e.label.compareTo(label)!=0) - return false; - return e.target.equals(target); - } - return false; - } - - -} diff --git a/Robust/src/Analysis/TaskStateAnalysis/FEdge.java b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java new file mode 100644 index 00000000..02a6c489 --- /dev/null +++ b/Robust/src/Analysis/TaskStateAnalysis/FEdge.java @@ -0,0 +1,38 @@ +package Analysis.TaskStateAnalysis; +import IR.*; +import Analysis.TaskStateAnalysis.*; +import IR.Tree.*; +import IR.Flat.*; +import java.util.*; +import Util.Edge; + +/* Edge *****************/ + +public class FEdge extends Edge { + + private String label; + + public FEdge(FlagState target, String label) { + super(target); + this.label = label; + } + + public String getLabel() { + return label; + } + + public int hashCode(){ + return target.hashCode()^label.hashCode(); + } + + public boolean equals(Object o) { + if (o instanceof FEdge) { + FEdge e=(FEdge)o; + return e.label.equals(label)&& + e.target.equals(target); + } + return false; + } + + +} diff --git a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java index bc07cade..e66231c8 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/FlagState.java +++ b/Robust/src/Analysis/TaskStateAnalysis/FlagState.java @@ -5,40 +5,16 @@ import IR.Tree.*; import IR.Flat.*; import java.util.*; import java.io.*; +import Util.GraphNode; /** This class is used to hold the flag states that a class in the Bristlecone * program can exist in, during runtime. */ -public class FlagState { - /* NodeStatus enumeration pattern ***********/ - - public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED"); - public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING"); - public static final NodeStatus FINISHED = new NodeStatus("FINISHED"); +public class FlagState extends GraphNode { public static final int ONETAG=1; public static final int NOTAGS=0; public static final int MULTITAGS=-1; - - - - public static class NodeStatus { - private static String name; - private NodeStatus(String name) { this.name = name; } - public String toString() { return name; } - } - - - int discoverytime = -1; - int finishingtime = -1; /* used for searches */ - - //Hashtable tags=new Hashtable(); - Vector edges = new Vector(); - Vector inedges = new Vector(); - NodeStatus status = UNVISITED; - protected String dotnodeparams = new String(); - boolean merge=false; - String nodeoption=""; private int uid; private static int nodeid=0; @@ -53,6 +29,7 @@ public class FlagState { public void setMerge() { merge=true; } + /** Class constructor * Creates a new flagstate with all flags set to false. * @param cd ClassDescriptor @@ -120,6 +97,7 @@ public class FlagState { return new FlagState(newset,cd,newtags); } + public int getTagCount(String tagtype){ for (Enumeration en=getTags();en.hasMoreElements();){ TagDescriptor td=(TagDescriptor)en.nextElement(); @@ -130,8 +108,6 @@ public class FlagState { } - - public FlagState[] clearTag(TagDescriptor tag){ FlagState[] retstates; @@ -189,9 +165,9 @@ public class FlagState { * @return returns the classdescriptor of the flagstate. */ - public ClassDescriptor getClassDescriptor(){ + public ClassDescriptor getClassDescriptor(){ return cd; - } + } /** Sets the status of a specific flag in a flagstate after cloning it. * @param fd FlagDescriptor of the flag whose status is being set. @@ -228,67 +204,6 @@ public class FlagState { return cd.hashCode()^flagstate.hashCode()^tags.hashCode(); } - public static void computeclosure(Collection nodes, Collection removed) { - Stack tovisit=new Stack(); - tovisit.addAll(nodes); - while(!tovisit.isEmpty()) { - FlagState gn=(FlagState)tovisit.pop(); - for(Iterator it=gn.edges();it.hasNext();) { - Edge edge=(Edge)it.next(); - FlagState target=edge.getTarget(); - if (!nodes.contains(target)) { - if ((removed==null)|| - (!removed.contains(target))) { - nodes.add(target); - tovisit.push(target); - } - } - } - } - } - - public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) { - Stack tovisit=new Stack(); - Stack newvisit=new Stack(); - tovisit.addAll(nodes); - for(int i=0;i 0) { - dotnodeparams = "," + param; - } else { - dotnodeparams = new String(); - } - } - - public void setStatus(NodeStatus status) { - if (status == null) { - throw new NullPointerException(); - } - this.status = status; - } - public String getLabel() { return "N"+uid; } @@ -320,323 +235,5 @@ public class FlagState { public Enumeration getTags(){ return tags.keys(); - } - - public NodeStatus getStatus() { - return this.status; - } - - public Iterator edges() { - return edges.iterator(); - } - - public Iterator inedges() { - return inedges.iterator(); - } - - public void addEdge(Edge newedge) { - newedge.setSource(this); - edges.addElement(newedge); - FlagState tonode=newedge.getTarget(); - tonode.inedges.addElement(newedge); - } - - void reset() { - discoverytime = -1; - finishingtime = -1; - status = UNVISITED; - } - - void resetscc() { - status = UNVISITED; - } - - void discover(int time) { - discoverytime = time; - status = PROCESSING; - } - - void finish(int time) { - assert status == PROCESSING; - finishingtime = time; - status = FINISHED; - } - - /** Returns finishing time for dfs */ - - public int getFinishingTime() { - return finishingtime; - } - - - public static class DOTVisitor { - - java.io.PrintWriter output; - int tokennumber; - int color; - - private DOTVisitor(java.io.OutputStream output) { - tokennumber = 0; - color = 0; - this.output = new java.io.PrintWriter(output, true); - } - - private String getNewID(String name) { - tokennumber = tokennumber + 1; - return new String (name+tokennumber); - } - - Collection nodes; - Collection special; - - public static void visit(java.io.OutputStream output, Collection nodes) { - visit(output,nodes,null); - } - - public static void visit(java.io.OutputStream output, Collection nodes, Collection special) { - DOTVisitor visitor = new DOTVisitor(output); - visitor.special=special; - visitor.nodes = nodes; - visitor.make(); - } - - private void make() { - output.println("digraph dotvisitor {"); - output.println("\trotate=90;"); - /* output.println("\tpage=\"8.5,11\";"); - output.println("\tnslimit=1000.0;"); - output.println("\tnslimit1=1000.0;"); - output.println("\tmclimit=1000.0;"); - output.println("\tremincross=true;");*/ - output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];"); - output.println("\tedge [fontsize=6];"); - traverse(); - output.println("}\n"); - } - - private void traverse() { - Iterator i = nodes.iterator(); - while (i.hasNext()) { - FlagState gn = (FlagState) i.next(); - Iterator edges = gn.edges(); - String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];"; - String option=gn.nodeoption; - if (special!=null&&special.contains(gn)) - option+=",shape=box"; - if (!gn.merge) - output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];"); - if (!gn.merge) - while (edges.hasNext()) { - Edge edge = (Edge) edges.next(); - FlagState node = edge.getTarget(); - if (nodes.contains(node)) { - for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) { - FlagState node2=(FlagState)nodeit.next(); - String edgelabel = "label=\"" + edge.getLabel() + "\""; - output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];"); - } - } - } - } - } - - - Set nonmerge(FlagState gn) { - HashSet newset=new HashSet(); - HashSet toprocess=new HashSet(); - toprocess.add(gn); - while(!toprocess.isEmpty()) { - FlagState gn2=(FlagState)toprocess.iterator().next(); - toprocess.remove(gn2); - if (!gn2.merge) - newset.add(gn2); - else { - Iterator edges = gn2.edges(); - while (edges.hasNext()) { - Edge edge = (Edge) edges.next(); - FlagState node = edge.getTarget(); - if (!newset.contains(node)&&nodes.contains(node)) - toprocess.add(node); - } - } - } - return newset; - } - - } - - /** 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) { - HashSet cycleset=new HashSet(); - SCC scc=DFS.computeSCC(nodes); - if (!scc.hasCycles()) - return cycleset; - for(int i=0;i1) - return true; - Object [] array=s.toArray(); - FlagState gn=(FlagState)array[0]; - for(Iterator it=gn.edges();it.hasNext();) { - Edge e=(Edge)it.next(); - if (e.getTarget()==gn) - return true; /* Self Cycle */ - } - return false; - } } - - /** - * DFS encapsulates the depth first search algorithm - */ - public static class DFS { - - int time = 0; - int sccindex = 0; - 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 acyclic=dfs.go(); - for (Iterator it = nodes.iterator();it.hasNext();) { - FlagState gn = (FlagState) it.next(); - gn.resetscc(); - } - for(int i=dfs.finishingorder.size()-1;i>=0;i--) { - FlagState gn=(FlagState)dfs.finishingorder.get(i); - if (gn.getStatus() == UNVISITED) { - dfs.dfsprev(gn); - dfs.sccindex++; /* Increment scc index */ - } - } - return new SCC(acyclic,dfs.sccmap,dfs.sccmaprev,dfs.sccindex); - } - - void dfsprev(FlagState gn) { - if (gn.getStatus()==FINISHED||!nodes.contains(gn)) - return; - gn.setStatus(FINISHED); - 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(); - FlagState gn2=e.getSource(); - dfsprev(gn2); - } - } - - public static boolean depthFirstSearch(Collection nodes) { - if (nodes == null) { - throw new NullPointerException(); - } - - DFS dfs = new DFS(nodes); - return dfs.go(); - } - - private boolean go() { - Iterator i; - time = 0; - boolean acyclic=true; - i = nodes.iterator(); - while (i.hasNext()) { - FlagState gn = (FlagState) i.next(); - gn.reset(); - } - - i = nodes.iterator(); - while (i.hasNext()) { - FlagState gn = (FlagState) i.next(); - assert gn.getStatus() != PROCESSING; - if (gn.getStatus() == UNVISITED) { - if (!dfs(gn)) - acyclic=false; - } - } - return acyclic; - } - - private boolean dfs(FlagState gn) { - boolean acyclic=true; - gn.discover(time++); - Iterator edges = gn.edges(); - - while (edges.hasNext()) { - Edge edge = (Edge) edges.next(); - FlagState node = edge.getTarget(); - if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ - continue; - if (node.getStatus() == UNVISITED) { - if (!dfs(node)) - acyclic=false; - } else if (node.getStatus()==PROCESSING) { - acyclic=false; - } - } - if (finishingorder!=null) - finishingorder.add(gn); - gn.finish(time++); - return acyclic; - } - } /* end DFS */ } diff --git a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java index 4e786816..6469560e 100644 --- a/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java +++ b/Robust/src/Analysis/TaskStateAnalysis/TaskAnalysis.java @@ -228,7 +228,7 @@ public class TaskAnalysis { } //seen this node already fs_taskexit=canonicalizeFlagState(sourcenodes,fs_taskexit); - Edge newedge=new Edge(fs_taskexit,taskname); + FEdge newedge=new FEdge(fs_taskexit,taskname); fs.addEdge(newedge); } } @@ -424,7 +424,7 @@ private boolean isTaskTrigger_tag(TagExpressionList tel, FlagState fs){ toprocess.add(fstemp); fstemp=canonicalizeFlagState(sourcenodes,fstemp); - fs.addEdge(new Edge(fstemp,"Runtime")); + fs.addEdge(new FEdge(fstemp,"Runtime")); } } } diff --git a/Robust/src/Util/Edge.java b/Robust/src/Util/Edge.java new file mode 100644 index 00000000..20e93d9b --- /dev/null +++ b/Robust/src/Util/Edge.java @@ -0,0 +1,40 @@ +package Util; + +/* Edge *****************/ + +public class Edge { + protected GraphNode target; + protected GraphNode source; + protected String dotnodeparams = new String(); + + public Edge(GraphNode target) { + this.target = target; + } + + public String getLabel() { + return ""; + } + + public void setSource(GraphNode s) { + this.source=s; + } + + public GraphNode getSource() { + return source; + } + + public GraphNode getTarget() { + return target; + } + + public void setDotNodeParameters(String param) { + if (param == null) { + throw new NullPointerException(); + } + if (param.length() > 0) { + dotnodeparams = "," + param; + } else { + dotnodeparams = new String(); + } + } +} diff --git a/Robust/src/Util/GraphNode.java b/Robust/src/Util/GraphNode.java new file mode 100755 index 00000000..931a4844 --- /dev/null +++ b/Robust/src/Util/GraphNode.java @@ -0,0 +1,427 @@ +package Util; + +import java.util.*; +import java.io.*; + +public class GraphNode { + /* NodeStatus enumeration pattern ***********/ + + public static final NodeStatus UNVISITED = new NodeStatus("UNVISITED"); + public static final NodeStatus PROCESSING = new NodeStatus("PROCESSING"); + public static final NodeStatus FINISHED = new NodeStatus("FINISHED"); + + public static class NodeStatus { + private static String name; + private NodeStatus(String name) { this.name = name; } + public String toString() { return name; } + } + + int discoverytime = -1; + int finishingtime = -1; /* used for searches */ + + Vector edges = new Vector(); + Vector inedges = new Vector(); + NodeStatus status = UNVISITED; + String dotnodeparams = new String(); + public boolean merge=false; + public String nodeoption=""; + + public void setOption(String option) { + this.nodeoption=","+option; + } + + public void setMerge() { + merge=true; + } + + public static void computeclosure(Collection nodes, Collection removed) { + Stack tovisit=new Stack(); + tovisit.addAll(nodes); + while(!tovisit.isEmpty()) { + GraphNode gn=(GraphNode)tovisit.pop(); + for(Iterator it=gn.edges();it.hasNext();) { + Edge edge=(Edge)it.next(); + GraphNode target=edge.getTarget(); + if (!nodes.contains(target)) { + if ((removed==null)|| + (!removed.contains(target))) { + nodes.add(target); + tovisit.push(target); + } + } + } + } + } + + public static void boundedcomputeclosure(Collection nodes, Collection removed,int depth) { + Stack tovisit=new Stack(); + Stack newvisit=new Stack(); + tovisit.addAll(nodes); + for(int i=0;i 0) { + dotnodeparams = "," + param; + } else { + dotnodeparams = new String(); + } + } + + public void setStatus(NodeStatus status) { + if (status == null) { + throw new NullPointerException(); + } + this.status = status; + } + + public String getLabel() { + return ""; + } + + public String getTextLabel() { + return ""; + } + + public NodeStatus getStatus() { + return this.status; + } + + public Iterator edges() { + return edges.iterator(); + } + + public Iterator inedges() { + return inedges.iterator(); + } + + public void addEdge(Edge newedge) { + newedge.setSource(this); + edges.addElement(newedge); + GraphNode tonode=newedge.getTarget(); + tonode.inedges.addElement(newedge); + } + + void reset() { + discoverytime = -1; + finishingtime = -1; + status = UNVISITED; + } + + void resetscc() { + status = UNVISITED; + } + + void discover(int time) { + discoverytime = time; + status = PROCESSING; + } + + void finish(int time) { + assert status == PROCESSING; + finishingtime = time; + status = FINISHED; + } + + /** Returns finishing time for dfs */ + + public int getFinishingTime() { + return finishingtime; + } + + + public static class DOTVisitor { + + java.io.PrintWriter output; + int tokennumber; + int color; + + private DOTVisitor(java.io.OutputStream output) { + tokennumber = 0; + color = 0; + this.output = new java.io.PrintWriter(output, true); + } + + private String getNewID(String name) { + tokennumber = tokennumber + 1; + return new String (name+tokennumber); + } + + Collection nodes; + Collection special; + + public static void visit(java.io.OutputStream output, Collection nodes) { + visit(output,nodes,null); + } + + public static void visit(java.io.OutputStream output, Collection nodes, Collection special) { + DOTVisitor visitor = new DOTVisitor(output); + visitor.special=special; + visitor.nodes = nodes; + visitor.make(); + } + + private void make() { + output.println("digraph dotvisitor {"); + output.println("\trotate=90;"); + /* output.println("\tpage=\"8.5,11\";"); + output.println("\tnslimit=1000.0;"); + output.println("\tnslimit1=1000.0;"); + output.println("\tmclimit=1000.0;"); + output.println("\tremincross=true;");*/ + output.println("\tnode [fontsize=10,height=\"0.1\", width=\"0.1\"];"); + output.println("\tedge [fontsize=6];"); + traverse(); + output.println("}\n"); + } + + private void traverse() { + Set cycleset=GraphNode.findcycles(nodes); + + Iterator i = nodes.iterator(); + while (i.hasNext()) { + GraphNode gn = (GraphNode) i.next(); + Iterator edges = gn.edges(); + String label = gn.getTextLabel(); + String option=gn.nodeoption; + if (special!=null&&special.contains(gn)) + option+=",shape=box"; + if (!gn.merge) + output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];"); + + if (!gn.merge) + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + GraphNode node = edge.getTarget(); + if (nodes.contains(node)) { + for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) { + GraphNode node2=(GraphNode)nodeit.next(); + String edgelabel = "label=\"" + edge.getLabel() + "\"" ; + output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];"); + } + } + } + } + } + + Set nonmerge(GraphNode gn) { + HashSet newset=new HashSet(); + HashSet toprocess=new HashSet(); + toprocess.add(gn); + while(!toprocess.isEmpty()) { + GraphNode gn2=(GraphNode)toprocess.iterator().next(); + toprocess.remove(gn2); + if (!gn2.merge) + newset.add(gn2); + else { + Iterator edges = gn2.edges(); + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + GraphNode node = edge.getTarget(); + if (!newset.contains(node)&&nodes.contains(node)) + toprocess.add(node); + } + } + } + return newset; + } + + } + + /** 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) { + HashSet cycleset=new HashSet(); + SCC scc=DFS.computeSCC(nodes); + if (!scc.hasCycles()) + return cycleset; + for(int i=0;i1) + return true; + Object [] array=s.toArray(); + GraphNode gn=(GraphNode)array[0]; + for(Iterator it=gn.edges();it.hasNext();) { + Edge e=(Edge)it.next(); + if (e.getTarget()==gn) + return true; /* Self Cycle */ + } + return false; + } + } + + /** + * DFS encapsulates the depth first search algorithm + */ + public static class DFS { + + int time = 0; + int sccindex = 0; + 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 acyclic=dfs.go(); + for (Iterator it = nodes.iterator();it.hasNext();) { + GraphNode gn = (GraphNode) it.next(); + gn.resetscc(); + } + for(int i=dfs.finishingorder.size()-1;i>=0;i--) { + GraphNode gn=(GraphNode)dfs.finishingorder.get(i); + if (gn.getStatus() == UNVISITED) { + dfs.dfsprev(gn); + dfs.sccindex++; /* Increment scc index */ + } + } + 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); + 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(); + dfsprev(gn2); + } + } + + public static boolean depthFirstSearch(Collection nodes) { + if (nodes == null) { + throw new NullPointerException(); + } + + DFS dfs = new DFS(nodes); + return dfs.go(); + } + + private boolean go() { + Iterator i; + time = 0; + boolean acyclic=true; + i = nodes.iterator(); + while (i.hasNext()) { + GraphNode gn = (GraphNode) i.next(); + gn.reset(); + } + + i = nodes.iterator(); + while (i.hasNext()) { + GraphNode gn = (GraphNode) i.next(); + assert gn.getStatus() != PROCESSING; + if (gn.getStatus() == UNVISITED) { + if (!dfs(gn)) + acyclic=false; + } + } + return acyclic; + } + + private boolean dfs(GraphNode gn) { + boolean acyclic=true; + gn.discover(time++); + Iterator edges = gn.edges(); + + while (edges.hasNext()) { + Edge edge = (Edge) edges.next(); + GraphNode node = edge.getTarget(); + if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ + continue; + if (node.getStatus() == UNVISITED) { + if (!dfs(node)) + acyclic=false; + } else if (node.getStatus()==PROCESSING) { + acyclic=false; + } + } + if (finishingorder!=null) + finishingorder.add(gn); + gn.finish(time++); + return acyclic; + } + + } /* end DFS */ + +} -- 2.34.1