X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=Robust%2Fsrc%2FUtil%2FGraphNode.java;h=d765b2f2677369b2089e7d4146ee6091640f3493;hb=cdcf09c40af1419fa42932aae249cb79b69b5daf;hp=424dfc65de82c96a4a618886046a7a3ef00d67a7;hpb=888698c50499fab303d1ac0c41663523aff5a076;p=IRC.git

diff --git a/Robust/src/Util/GraphNode.java b/Robust/src/Util/GraphNode.java
deleted file mode 100755
index 424dfc65..00000000
--- a/Robust/src/Util/GraphNode.java
+++ /dev/null
@@ -1,537 +0,0 @@
-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 */
-
-    protected Vector edges = new Vector();
-    protected Vector inedges = new Vector();
-
-    NodeStatus status = UNVISITED;
-    String dotnodeparams = new String();
-    public boolean merge=false;
-
-    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<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();
-	}
-    }
-
-    public void setDotNodeParameters(String param) {
-        if (param == null) {
-            throw new NullPointerException();
-        }
-        if (dotnodeparams.length() > 0) {
-            dotnodeparams += "," + param;
-        } else {
-            dotnodeparams = param;
-        }
-    }
-
-    public void setStatus(NodeStatus status) {
-        if (status == null) {
-            throw new NullPointerException();
-        }
-        this.status = status;
-    }
-       
-    public String getLabel() {
-	return "";
-    }
-
-    public String getTextLabel() {
-	return "";
-    }
-    
-   	public String getName(){
-	   	return "";
-   	}
-
-    public NodeStatus getStatus() {
-        return this.status;
-    }
-
-    public int numedges() {
-	return edges.size();
-    }
-
-    public int numinedges() {
-	return inedges.size();
-    }
-
-    public Edge getedge(int i) {
-	return (Edge) edges.get(i);
-    }
-
-    public Edge getinedge(int i) {
-	return (Edge) inedges.get(i);
-    }
-
-    public Vector getEdgeVector() {
-	return edges;
-    }
-
-    public Vector getInedgeVector() {
-	return inedges;
-    }
-
-    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);
-    }
-
-    public void addEdge(Vector v) {
-	for (Iterator it = v.iterator(); it.hasNext();)
-	    addEdge((Edge)it.next());
-    }
-
-    public void removeEdge(Edge edge) {
-	edges.remove(edge);
-    }
-
-    public void removeInedge(Edge edge) {
-	inedges.remove(edge);
-    }
-
-    public void removeAllEdges() {
-	edges.removeAllElements();
-    }
-
-    public void removeAllInedges() {
-	inedges.removeAllElements();
-    }
-    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;
-	Vector namers;
-
-        private DOTVisitor(java.io.OutputStream output, Vector namers) {
-            tokennumber = 0;
-            color = 0;
-            this.output = new java.io.PrintWriter(output, true);
-	    this.namers=namers;
-        }
-
-        private String getNewID(String name) {
-            tokennumber = tokennumber + 1;
-            return new String (name+tokennumber);
-        }
-
-        Collection nodes;
-
-
-        public static void visit(java.io.OutputStream output, Collection nodes, Vector namers) {
-            DOTVisitor visitor = new DOTVisitor(output, namers);
-            visitor.nodes = nodes;
-            visitor.make();
-        }
-
-        public static void visit(java.io.OutputStream output, Collection nodes) {
-	    Vector v=new Vector();
-	    v.add(new Namer());
-            DOTVisitor visitor = new DOTVisitor(output, v);
-            visitor.nodes = nodes;
-            visitor.make();
-        }
-
-        private void make() {
-            output.println("digraph dotvisitor {");
-	    /*            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 it = nodes.iterator();
-            while (it.hasNext()) {
-                GraphNode gn = (GraphNode) it.next();
-                Iterator edges = gn.edges();
-                String label = "";
-		String dotnodeparams="";
-
-		for(int i=0;i<namers.size();i++) {
-		    Namer name=(Namer) namers.get(i);
-		    String newlabel=name.nodeLabel(gn);
-		    String newparams=name.nodeOption(gn);
-
-		    if (!newlabel.equals("") && !label.equals("")) {
-			label+=", ";
-		    }
-		    if (!newparams.equals("")) {
-			dotnodeparams+=", " + name.nodeOption(gn);
-		    }
-		    label+=name.nodeLabel(gn);
-		}
-
-		if (!gn.merge)
-                    output.println("\t" + gn.getLabel() + " [label=\"" + label + "\"" + dotnodeparams + "];");
-
-		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 = "";
-			    String edgedotnodeparams="";
-
-			    for(int i=0;i<namers.size();i++) {
-				Namer name=(Namer) namers.get(i);
-				String newlabel=name.edgeLabel(edge);
-				String newoption=name.edgeOption(edge);
-				if (!newlabel.equals("")&& ! edgelabel.equals(""))
-				    edgelabel+=", ";
-				edgelabel+=newlabel;
-				if (!newoption.equals(""))
-				    edgedotnodeparams+=", "+newoption;
-			    }
-			    
-			    output.println("\t" + gn.getLabel() + " -> " + node2.getLabel() + " [" + "label=\"" + edgelabel + "\"" + edgedotnodeparams + "];");
-			}
-		    }
-                }
-            }
-        }
-
-	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;i<scc.numSCC();i++) {
-	    if (scc.hasCycle(i))
-		cycleset.addAll(scc.getSCC(i));
-	}
-	return cycleset;
-    }
-
-    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;
-	}
-
-	/** 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();
-	}
-
-	/** 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;
-	}
-    }
-
-    /**
-     * DFS encapsulates the depth first search algorithm
-     */
-    public static class DFS {
-
-        int time = 0;
-	int sccindex = 0;
-        Collection nodes;
-	Vector finishingorder=null;
-	Vector finishingorder_edge = null; 
-	int edgetime = 0; 
-	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;
-            edgetime = 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();
-                edge.discover(edgetime++);
-                GraphNode node = edge.getTarget();
-				if (!nodes.contains(node)) /* Skip nodes which aren't in the set */ {
-					if(finishingorder_edge != null)
-				    	finishingorder_edge.add(edge);
-					edge.finish(edgetime++); 
-				    continue;
-				}
-                if (node.getStatus() == UNVISITED) {
-                    if (!dfs(node))
-                    	acyclic=false;
-                } else if (node.getStatus()==PROCESSING) {
-                		acyclic=false;
-                }
-                if(finishingorder_edge != null)
-    		    	finishingorder_edge.add(edge);
-    			edge.finish(edgetime++); 
-            }
-		    if (finishingorder!=null)
-			finishingorder.add(gn);  
-	        gn.finish(time++);
-		    return acyclic;
-        }
-
-        public static Vector topology(Collection nodes, Vector finishingorder_edge) {
-    	    if (nodes==null) {
-    		throw new NullPointerException();
-    	    }
-    	    DFS dfs=new DFS(nodes);
-    	    dfs.finishingorder=new Vector();
-    	    if(finishingorder_edge != null) {
-    	    	dfs.finishingorder_edge = new Vector();
-    	    }
-    	    boolean acyclic=dfs.go();
-    	    Vector topology = new Vector();
-    	    for(int i=dfs.finishingorder.size()-1;i>=0;i--) {
-    		GraphNode gn=(GraphNode)dfs.finishingorder.get(i);
-    		topology.add(gn);
-    	    }
-    	    if(finishingorder_edge != null) {
-	    	    for(int i=dfs.finishingorder_edge.size()-1;i>=0;i--) {
-	        		Edge gn=(Edge)dfs.finishingorder_edge.get(i);
-	        		finishingorder_edge.add(gn);
-	        	}
-    	    }
-    	    return topology;
-    	}
-    } /* end DFS */
-
-}