+++ /dev/null
-/*--------------------------------------------------------------------------\r
- * Copyright 2007 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 Project\r
-//\r
-// DFSVisitor.java\r
-// Since: 2007/05/14\r
-//\r
-// $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/DepthFirstSearch.java $ \r
-// $Author: leo $\r
-//--------------------------------------\r
-package org.xerial.util.graph;\r
-\r
-import java.util.HashMap;\r
-\r
-/**\r
- * Depth First Search Algorithm of the graph.\r
- * \r
- * Reference:\r
- * http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/DFSVisitor.html\r
- * \r
- * <ol>\r
- * <li>initializeNode each node is colored WHITE\r
- * <li>startNode\r
- * <li>discoverNode the node is colored GRAY\r
- * <li>examinEdge\r
- * <li>treeEdge | backEdge | forwardOrCrossEdge (if the edge is a tree edge,\r
- * traverse to the edge)\r
- * <li>finishNode the node is colored BLACK\r
- * \r
- * </ol>\r
- * \r
- * \r
- * @author leo\r
- * \r
- */\r
-public abstract class DepthFirstSearch<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> _discoveryTime = new HashMap<NodeLabel, Integer>();\r
- private HashMap<NodeLabel, Integer> _finishTime = new HashMap<NodeLabel, Integer>();\r
-\r
- public DepthFirstSearch()\r
- {\r
-\r
- }\r
-\r
- public void run(Graph<NodeLabel, EdgeLabel> graph)\r
- {\r
- // start from the fist entry in the node collection of the graph\r
- run(graph, null);\r
- }\r
-\r
- public void run(Graph<NodeLabel, EdgeLabel> graph, NodeLabel startNode)\r
- {\r
- this._graph = graph;\r
-\r
- // initialize each node \r
- for (NodeLabel eachNode : _graph.getNodeLabelSet())\r
- {\r
- this.initializeNode(eachNode);\r
-\r
- _nodeColor.put(eachNode, NodeColor.WHITE);\r
- _predecessor.put(eachNode, eachNode);\r
- }\r
- _time = 0;\r
- if (startNode != null)\r
- {\r
- this.startNode(startNode);\r
- dfsVisit(startNode);\r
- }\r
- for (NodeLabel node : _graph.getNodeLabelSet())\r
- {\r
- NodeColor color = _nodeColor.get(node);\r
- assert (color != null);\r
- if (color == NodeColor.WHITE)\r
- {\r
- this.startNode(node);\r
- dfsVisit(node);\r
- }\r
- }\r
- }\r
-\r
- private void dfsVisit(NodeLabel node)\r
- {\r
- this.discoverNode(node);\r
- _nodeColor.put(node, NodeColor.GRAY);\r
- _discoveryTime.put(node, _time++);\r
- for (Edge edge : _graph.getOutEdgeSet(node))\r
- {\r
- this.examineEdge(edge);\r
-\r
- NodeLabel adjacentNode = _graph.getNodeLabel(edge.getDestNodeID());\r
- NodeColor color = _nodeColor.get(adjacentNode);\r
- assert (color != null);\r
- if (color == NodeColor.WHITE)\r
- {\r
- this.treeEdge(edge);\r
-\r
- _predecessor.put(adjacentNode, node);\r
- dfsVisit(adjacentNode);\r
- }\r
- else if (color == NodeColor.GRAY)\r
- {\r
- this.backEdge(edge);\r
- }\r
- else if (color == NodeColor.BLACK)\r
- {\r
- this.forwardOrCrossEdge(edge);\r
- }\r
- }\r
-\r
- this.finishNode(node);\r
- _nodeColor.put(node, NodeColor.BLACK);\r
-\r
- _finishTime.put(node, _time++);\r
- }\r
-\r
- // utilty methods\r
- protected NodeLabel getPredecessor(NodeLabel node)\r
- {\r
- return _predecessor.get(node);\r
- }\r
-\r
- protected int getDiscoveryTime(NodeLabel node)\r
- {\r
- return _discoveryTime.get(node);\r
- }\r
-\r
- protected int getFinishTime(NodeLabel node)\r
- {\r
- return _finishTime.get(node);\r
- }\r
-\r
- protected final Graph<NodeLabel, EdgeLabel> getGraph()\r
- {\r
- return _graph;\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
- * This method is invoked only once before the search starts.\r
- * \r
- * @param node\r
- */\r
- protected abstract void initializeNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when the DFS search from this node begins.\r
- * \r
- * @param node\r
- */\r
- protected abstract void startNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when a new node is found\r
- * \r
- * @param node\r
- */\r
- protected abstract void discoverNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when the depth first search beginning from this node\r
- * \r
- * @param node\r
- */\r
- protected abstract void finishNode(NodeLabel node);\r
-\r
- /**\r
- * Invoked when searching for edges to traverse\r
- * \r
- * @param edge\r
- */\r
- protected abstract void examineEdge(Edge edge);\r
-\r
- /**\r
- * Invoked when traversing to a newly found node (WHITE)\r
- * \r
- * @param edge\r
- */\r
- protected abstract void treeEdge(Edge edge);\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
