private String label;
private GraphNode target;
+ private GraphNode source;
private String dotnodeparams = new String();
public Edge(String label, GraphNode target) {
return label;
}
+ public void setSource(GraphNode s) {
+ this.source=s;
+ }
+
+ public GraphNode getSource() {
+ return source;
+ }
+
public GraphNode getTarget() {
return target;
}
int discoverytime = -1;
int finishingtime = -1; /* used for searches */
+
Vector edges = new Vector();
+ Vector inedges = new Vector();
String nodelabel;
String textlabel;
NodeStatus status = UNVISITED;
String dotnodeparams = new String();
Object owner = null;
+ boolean merge=false;
+ String nodeoption="";
+
+ public void setOption(String option) {
+ this.nodeoption=option;
+ }
+
+ public void setMerge() {
+ merge=true;
+ }
public GraphNode(String label) {
this.nodelabel = label;
return owner;
}
- public static void computeclosure(Set nodes) {
+ public static void computeclosure(Collection nodes, Collection removed) {
Stack tovisit=new Stack();
tovisit.addAll(nodes);
while(!tovisit.isEmpty()) {
Edge edge=(Edge)it.next();
GraphNode target=edge.getTarget();
if (!nodes.contains(target)) {
- nodes.add(target);
- tovisit.push(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<depth&&!tovisit.isEmpty();i++) {
+ 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);
+ newvisit.push(target);
+ }
+ }
}
}
+ tovisit=newvisit;
+ newvisit=new Stack();
}
}
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;
}
- public void reset() {
- discoverytime = -1;
- finishingtime = -1;
- status = UNVISITED;
+ void resetscc() {
+ status = UNVISITED;
}
- public void discover(int time) {
- discoverytime = time;
- status = PROCESSING;
+ void discover(int time) {
+ discoverytime = time;
+ status = PROCESSING;
}
- public void finish(int time) {
+ void finish(int time) {
assert status == PROCESSING;
- finishingtime = time;
+ finishingtime = time;
status = FINISHED;
}
+ /** Returns finishing time for dfs */
+
public int getFinishingTime() {
- return finishingtime;
+ return finishingtime;
}
}
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() {
GraphNode gn = (GraphNode) i.next();
Iterator edges = gn.edges();
String label = gn.getTextLabel(); // + " [" + gn.discoverytime + "," + gn.finishingtime + "];";
- String option="";
- if (cycleset.contains(gn))
- option=",style=bold";
- output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + gn.dotnodeparams + option+"];");
+ 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)) {
- String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
- output.println("\t" + gn.getLabel() + " -> " + node.getLabel() + " [" + edgelabel + edge.dotnodeparams + "];");
+ for(Iterator nodeit=nonmerge(node).iterator();nodeit.hasNext();) {
+ GraphNode node2=(GraphNode)nodeit.next();
+ String edgelabel = useEdgeLabels ? "label=\"" + edge.getLabel() + "\"" : "label=\"\"";
+ 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;
+ }
+
}
- /* 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;i<scc.numSCC();i++) {
+ if (scc.hasCycle(i))
+ cycleset.addAll(scc.getSCC(i));
}
- return cycles;
+ return cycleset;
}
- private static boolean findcycles(Set cycles, Set acyclic, Stack visited, GraphNode gn, Collection nodes) {
- if (visited.contains(gn)) {/* Found cycle */
- cycles.addAll(visited.subList(visited.indexOf(gn),visited.size())); /* Add this cycle */
- return true;
+ public static class SCC {
+ boolean acyclic;
+ HashMap map,revmap;
+ int numscc;
+ public SCC(boolean acyclic, HashMap map,HashMap revmap,int numscc) {
+ this.acyclic=acyclic;
+ this.map=map;
+ this.revmap=revmap;
+ this.numscc=numscc;
}
- boolean acyclicflag=true;
- visited.push(gn);
- for(Iterator it=gn.edges();it.hasNext();) {
- Edge e=(Edge) it.next();
- GraphNode node = e.getTarget();
- if (!nodes.contains(node))
- continue; /* Don't visit stuff outside set */
- if (acyclic.contains(node))
- continue;
- if (findcycles(cycles,acyclic,visited,node,nodes)) {
- /* Found cycle */
- acyclicflag=false;
- }
+
+ /** Returns whether the graph has any cycles */
+ public boolean hasCycles() {
+ return !acyclic;
+ }
+
+ /** Returns the number of Strongly Connected Components */
+ public int numSCC() {
+ return numscc;
+ }
+
+ /** Returns the strongly connected component number for the GraphNode gn*/
+ public int getComponent(GraphNode gn) {
+ return ((Integer)revmap.get(gn)).intValue();
}
- visited.pop();
- if (acyclicflag) {
- acyclic.add(gn); /* no cycles through gn */
+
+ /** Returns the set of nodes in the strongly connected component i*/
+ public Set getSCC(int i) {
+ Integer scc=new Integer(i);
+ return (Set)map.get(scc);
+ }
+
+ /** Returns whether the strongly connected component i contains a cycle */
+ boolean hasCycle(int i) {
+ Integer scc=new Integer(i);
+ Set s=(Set)map.get(scc);
+ if (s.size()>1)
+ 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;
- } else
- return true; /* found cycle */
+ }
}
-
+
/**
* 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) {
i = nodes.iterator();
while (i.hasNext()) {
GraphNode gn = (GraphNode) i.next();
- assert gn.getStatus() != PROCESSING;
+ assert gn.getStatus() != PROCESSING;
if (gn.getStatus() == UNVISITED) {
if (!dfs(gn))
acyclic=false;
private boolean dfs(GraphNode gn) {
boolean acyclic=true;
- gn.discover(time++);
+ 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;
acyclic=false;
}
}
-
+ if (finishingorder!=null)
+ finishingorder.add(gn);
gn.finish(time++);
return acyclic;
}
projects / repair.git / blobdiff