+++ /dev/null
-/*--------------------------------------------------------------------------\r
- * Copyright 2008 Taro L. Saito\r
- *\r
- * Licensed under the Apache License, Version 2.0 (the "License");\r
- * you may not use this file except in compliance with the License.\r
- * You may obtain a copy of the License at\r
- *\r
- * http://www.apache.org/licenses/LICENSE-2.0\r
- *\r
- * Unless required by applicable law or agreed to in writing, software\r
- * distributed under the License is distributed on an "AS IS" BASIS,\r
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
- * See the License for the specific language governing permissions and\r
- * limitations under the License.\r
- *--------------------------------------------------------------------------*/\r
-//--------------------------------------\r
-// XerialJ\r
-//\r
-// BreadthFirstSearch.java\r
-// Since: Oct 17, 2008 5:01:43 PM\r
-//\r
-// $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/BreadthFirstSearch.java $\r
-// $Author: leo $\r
-//--------------------------------------\r
-package org.xerial.util.graph;\r
-\r
-import java.util.HashMap;\r
-import java.util.Stack;\r
-\r
-/**\r
- * @author leo\r
- * \r
- * @param <NodeLabel>\r
- * @param <EdgeLabel>\r
- */\r
-public abstract class BreadthFirstSearch<NodeLabel, EdgeLabel>\r
-{\r
- enum NodeColor {\r
- WHITE, GRAY, BLACK\r
- }\r
-\r
- private Graph<NodeLabel, EdgeLabel> _graph;\r
- private HashMap<NodeLabel, NodeColor> _nodeColor = new HashMap<NodeLabel, NodeColor>();\r
- private HashMap<NodeLabel, NodeLabel> _predecessor = new HashMap<NodeLabel, NodeLabel>();\r
- private int _time;\r
- private HashMap<NodeLabel, Integer> _depth = new HashMap<NodeLabel, Integer>();\r
- //private HashMap<NodeType, Integer> _finishTime = new HashMap<NodeType, Integer>();\r
- private Stack<NodeLabel> nodeStack = new Stack<NodeLabel>();\r
-\r
- public void run(Graph<NodeLabel, EdgeLabel> graph)\r
- {\r
- run(graph, null);\r
- }\r
-\r
- public void run(Graph<NodeLabel, EdgeLabel> graph, NodeLabel startNode)\r
- {\r
- this._graph = graph;\r
- nodeStack.clear();\r
-\r
- for (NodeLabel eachNode : _graph.getNodeLabelSet())\r
- {\r
- initializeNode(eachNode);\r
- _nodeColor.put(eachNode, NodeColor.WHITE);\r
- _predecessor.put(eachNode, eachNode);\r
- }\r
- _time = 0;\r
- if (startNode != null)\r
- {\r
- searchStart(startNode);\r
- }\r
- for (NodeLabel node : _graph.getNodeLabelSet())\r
- {\r
- searchStart(node);\r
- }\r
-\r
- }\r
-\r
- private void searchStart(NodeLabel node)\r
- {\r
- NodeColor color = _nodeColor.get(node);\r
- assert (color != null);\r
-\r
- // skip already traversed nodes\r
- if (color != NodeColor.WHITE)\r
- return;\r
-\r
- this.startNode(node);\r
- bfsVisit(node);\r
- }\r
-\r
- private void bfsVisit(NodeLabel node)\r
- {\r
- nodeStack.add(node);\r
- this.discoverNode(node);\r
- _nodeColor.put(node, NodeColor.GRAY);\r
- _depth.put(node, 0);\r
-\r
- while (!nodeStack.isEmpty())\r
- {\r
- NodeLabel cursorNode = nodeStack.pop();\r
- this.examineNode(cursorNode);\r
-\r
- for (Edge edge : _graph.getOutEdgeSet(cursorNode))\r
- {\r
- this.examineEdge(edge);\r
-\r
- NodeLabel nextNode = _graph.getNodeLabel(edge.getDestNodeID());\r
- NodeColor nextNodeColor = _nodeColor.get(nextNode);\r
- assert (nextNodeColor != null);\r
-\r
- switch (nextNodeColor)\r
- {\r
- case WHITE:\r
- this.treeEdge(edge);\r
- _nodeColor.put(nextNode, NodeColor.GRAY);\r
- _depth.put(nextNode, _depth.get(cursorNode) + 1);\r
- _predecessor.put(nextNode, cursorNode);\r
-\r
- nodeStack.add(nextNode);\r
- this.discoverNode(nextNode);\r
- break;\r
- case GRAY:\r
- this.backEdge(edge);\r
- break;\r
- case BLACK:\r
- this.forwardOrCrossEdge(edge);\r
- break;\r
- }\r
-\r
- }\r
- this.finishNode(cursorNode);\r
- _nodeColor.put(cursorNode, NodeColor.BLACK);\r
-\r
- }\r
-\r
- }\r
-\r
- protected final Graph<NodeLabel, EdgeLabel> getGraph()\r
- {\r
- return _graph;\r
- }\r
-\r
- // utilty methods\r
- protected NodeLabel getPredecessor(NodeLabel node)\r
- {\r
- return _predecessor.get(node);\r
- }\r
-\r
- protected int getSearchDepth(NodeLabel node)\r
- {\r
- return _depth.get(node);\r
- }\r
-\r
- protected EdgeLabel getEdgeLabel(Edge edge)\r
- {\r
- return _graph.getEdgeLabel(edge);\r
- }\r
-\r
- protected NodeLabel getSourceNodeLabel(Edge edge)\r
- {\r
- return GraphHelper.getSourceNodeLabel(_graph, edge);\r
- }\r
-\r
- protected NodeLabel getDestNodeLabel(Edge edge)\r
- {\r
- return GraphHelper.getDestNodeLabel(_graph, edge);\r
- }\r
-\r
- protected String toString(Edge edge)\r
- {\r
- return GraphHelper.toString(_graph, edge);\r
- }\r
-\r
- /**\r
- * Invoked before the search starts\r
- * \r
- * @param node\r
- */\r
- protected abstract void initializeNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when the search starts from this node\r
- * \r
- * @param node\r
- */\r
- protected abstract void startNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when this node is discovered.\r
- * \r
- * @param node\r
- */\r
- protected abstract void discoverNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when the node becomes the travasal target\r
- * \r
- * @param node\r
- */\r
- protected abstract void examineNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when the edge is examined\r
- * \r
- * @param edge\r
- */\r
- protected abstract void examineEdge(Edge edge);\r
-\r
- /**\r
- * Invoked when a new edge is found\r
- * \r
- * @param edge\r
- */\r
- protected abstract void treeEdge(Edge edge);\r
-\r
- /**\r
- * Invoked when all edges beginning from this node are examined.\r
- * \r
- * @param node\r
- */\r
- protected abstract void finishNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when a node whose DFS search is in-progress (GRAY) is found.\r
- * \r
- * @param edge\r
- */\r
- protected abstract void backEdge(Edge edge);\r
-\r
- /**\r
- * Invoked when an already finished node (BLACK) is found\r
- * \r
- * @param edge\r
- */\r
- protected abstract void forwardOrCrossEdge(Edge edge);\r
-\r
-}\r
OSDN Git Service
