Changeset 2589

Timestamp:

10/24/08 11:14:08 (3 months ago)

Author:

leo

Message:

[ADD] GraphHelper?

Location:

XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph

Files:

• BreadthFirstSearch.java (modified) (13 diffs)
• DepthFirstSearch.java (modified) (1 diff)
• GraphHelper.java (added)

XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/BreadthFirstSearch.java

@@ -31 +31 @@
  * @author leo
  * 
- * @param <NodeType>
- * @param <EdgeType>
+ * @param <NodeLabel>
+ * @param <EdgeLabel>
  */
-public abstract class BreadthFirstSearch<NodeType, EdgeType>
+public abstract class BreadthFirstSearch<NodeLabel, EdgeLabel>
 {
     enum NodeColor {
@@ -40 +40 @@
     }
 
-    private Graph<NodeType, EdgeType> _graph;
-    private HashMap<NodeType, NodeColor> _nodeColor = new HashMap<NodeType, NodeColor>();
-    private HashMap<NodeType, NodeType> _predecessor = new HashMap<NodeType, NodeType>();
+    private Graph<NodeLabel, EdgeLabel> _graph;
+    private HashMap<NodeLabel, NodeColor> _nodeColor = new HashMap<NodeLabel, NodeColor>();
+    private HashMap<NodeLabel, NodeLabel> _predecessor = new HashMap<NodeLabel, NodeLabel>();
     private int _time;
-    private HashMap<NodeType, Integer> _depth = new HashMap<NodeType, Integer>();
+    private HashMap<NodeLabel, Integer> _depth = new HashMap<NodeLabel, Integer>();
     //private HashMap<NodeType, Integer> _finishTime = new HashMap<NodeType, Integer>();
-    private Stack<NodeType> nodeStack = new Stack<NodeType>();
-
-    public void run(Graph<NodeType, EdgeType> graph)
+    private Stack<NodeLabel> nodeStack = new Stack<NodeLabel>();
+
+    public void run(Graph<NodeLabel, EdgeLabel> graph)
     {
         run(graph, null);
     }
 
-    public void run(Graph<NodeType, EdgeType> graph, NodeType startNode)
+    public void run(Graph<NodeLabel, EdgeLabel> graph, NodeLabel startNode)
     {
         this._graph = graph;
         nodeStack.clear();
 
-        for (NodeType eachNode : _graph.getNodeLabelSet())
+        for (NodeLabel eachNode : _graph.getNodeLabelSet())
         {
             initializeNode(eachNode);
@@ -69 +69 @@
             searchStart(startNode);
         }
-        for (NodeType node : _graph.getNodeLabelSet())
+        for (NodeLabel node : _graph.getNodeLabelSet())
         {
             searchStart(node);
@@ -76 +76 @@
     }
 
-    private void searchStart(NodeType node)
+    private void searchStart(NodeLabel node)
     {
         NodeColor color = _nodeColor.get(node);
@@ -89 +89 @@
     }
 
-    private void bfsVisit(NodeType node)
+    private void bfsVisit(NodeLabel node)
     {
         nodeStack.add(node);
@@ -98 +98 @@
         while (!nodeStack.isEmpty())
         {
-            NodeType cursorNode = nodeStack.pop();
+            NodeLabel cursorNode = nodeStack.pop();
             this.examineNode(cursorNode);
 
@@ -105 +105 @@
                 this.examineEdge(edge);
 
-                NodeType nextNode = _graph.getNodeLabel(edge.getDestNodeID());
+                NodeLabel nextNode = _graph.getNodeLabel(edge.getDestNodeID());
                 NodeColor nextNodeColor = _nodeColor.get(nextNode);
                 assert (nextNodeColor != null);
@@ -136 +136 @@
     }
 
+    protected final Graph<NodeLabel, EdgeLabel> getGraph()
+    {
+        return _graph;
+    }
+
+    // utilty methods
+    protected NodeLabel getPredecessor(NodeLabel node)
+    {
+        return _predecessor.get(node);
+    }
+
+    protected int getSearchDepth(NodeLabel node)
+    {
+        return _depth.get(node);
+    }
+
+    protected EdgeLabel getEdgeLabel(Edge edge)
+    {
+        return _graph.getEdgeLabel(edge);
+    }
+
+    protected NodeLabel getSourceNodeLabel(Edge edge)
+    {
+        return GraphHelper.getSourceNodeLabel(_graph, edge);
+    }
+
+    protected NodeLabel getDestNodeLabel(Edge edge)
+    {
+        return GraphHelper.getDestNodeLabel(_graph, edge);
+    }
+
+    protected String toString(Edge edge)
+    {
+        return GraphHelper.toString(_graph, edge);
+    }
+
     /**
      * Invoked before the search starts
@@ -141 +177 @@
      * @param node
      */
-    protected abstract void initializeNode(NodeType node);
+    protected abstract void initializeNode(NodeLabel node);
 
     /**
@@ -148 +184 @@
      * @param node
      */
-    protected abstract void startNode(NodeType node);
+    protected abstract void startNode(NodeLabel node);
 
     /**
@@ -155 +191 @@
      * @param node
      */
-    protected abstract void discoverNode(NodeType node);
+    protected abstract void discoverNode(NodeLabel node);
 
     /**
@@ -162 +198 @@
      * @param node
      */
-    protected abstract void examineNode(NodeType node);
+    protected abstract void examineNode(NodeLabel node);
 
     /**
@@ -183 +219 @@
      * @param node
      */
-    protected abstract void finishNode(NodeType node);
+    protected abstract void finishNode(NodeLabel node);
 
     /**

XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/DepthFirstSearch.java

@@ -163 +163 @@
     }
 
-    protected NodeLabel getSourceNode(Edge edge)
-    {
-        return _graph.getNodeLabel(edge.getSourceNodeID());
-    }
-
-    protected NodeLabel getDestNode(Edge edge)
-    {
-        return _graph.getNodeLabel(edge.getDestNodeID());
-    }
-
-    public String toString(Edge edge)
-    {
-        return String.format("(%s,%s)", getGraph().getNodeLabel(edge.getSourceNodeID()).toString(), getGraph()
-                .getNodeLabel(edge.getDestNodeID()).toString());
+    protected NodeLabel getSourceNodeLabel(Edge edge)
+    {
+        return GraphHelper.getSourceNodeLabel(_graph, edge);
+    }
+
+    protected NodeLabel getDestNodeLabel(Edge edge)
+    {
+        return GraphHelper.getDestNodeLabel(_graph, edge);
+    }
+
+    protected String toString(Edge edge)
+    {
+        return GraphHelper.toString(_graph, edge);
     }