--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/app/graph/searching.py Wed Nov 26 23:56:19 2008 +0000
@@ -0,0 +1,167 @@
+# Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>
+#
+# Permission is hereby granted, free of charge, to any person
+# obtaining a copy of this software and associated documentation
+# files (the "Software"), to deal in the Software without
+# restriction, including without limitation the rights to use,
+# copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the
+# Software is furnished to do so, subject to the following
+# conditions:
+
+# The above copyright notice and this permission notice shall be
+# included in all copies or substantial portions of the Software.
+
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+# OTHER DEALINGS IN THE SOFTWARE.
+
+
+"""
+Search algorithms for python-graph.
+
+@sort: breadth_first_search, depth_first_search, _bfs, _dfs
+"""
+
+
+# Depth-first search
+
+def depth_first_search(graph, root=None):
+ """
+ Depth-first search.
+
+ @type graph: graph
+ @param graph: Graph.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @rtype: tuple
+ @return: A tupple containing a dictionary and two lists:
+ 1. Generated spanning tree
+ 2. Graph's preordering
+ 3. Graph's postordering
+ """
+ visited = {} # List for marking visited and non-visited nodes
+ spanning_tree = {} # Spanning tree
+ pre = [] # Graph's preordering
+ post = [] # Graph's postordering
+
+ # DFS from one node only
+ if (root is not None):
+ spanning_tree[root] = None
+ _dfs(graph, visited, spanning_tree, pre, post, root)
+ return spanning_tree, pre, post
+
+ # Algorithm loop
+ for each in graph:
+ # Select a non-visited node
+ if (each not in visited):
+ spanning_tree[each] = None
+ # Explore node's connected component
+ _dfs(graph, visited, spanning_tree, pre, post, each)
+
+ return spanning_tree, pre, post
+
+
+def _dfs(graph, visited, spanning_tree, pre, post, node):
+ """
+ Depht-first search subfunction.
+
+ @type graph: graph
+ @param graph: Graph.
+
+ @type visited: dictionary
+ @param visited: List of nodes (visited nodes are marked non-zero).
+
+ @type spanning_tree: dictionary
+ @param spanning_tree: Spanning tree being built for the graph by DFS.
+
+ @type pre: list
+ @param pre: Graph's preordering.
+
+ @type post: list
+ @param post: Graph's postordering.
+
+ @type node: node
+ @param node: Node to be explored by DFS.
+ """
+ visited[node] = 1
+ pre.append(node)
+ # Explore recursively the connected component
+ for each in graph[node]:
+ if (each not in visited):
+ spanning_tree[each] = node
+ _dfs(graph, visited, spanning_tree, pre, post, each)
+ post.append(node)
+
+
+# Breadth-first search
+
+def breadth_first_search(graph, root=None):
+ """
+ Breadth-first search.
+
+ @type graph: graph
+ @param graph: Graph.
+
+ @type root: node
+ @param root: Optional root node (will explore only root's connected component)
+
+ @rtype: tuple
+ @return: A tuple containing a dictionary and a list.
+ 1. Generated spanning tree
+ 2. Graph's level-based ordering
+ """
+ queue = [] # Visiting queue
+ spanning_tree = {} # Spanning tree
+ ordering = []
+
+ # BFS from one node only
+ if (root is not None):
+ queue.append(root)
+ ordering.append(root)
+ spanning_tree[root] = None
+ _bfs(graph, queue, spanning_tree, ordering)
+ return spanning_tree, ordering
+
+ # Algorithm
+ for each in graph:
+ if (each not in spanning_tree):
+ queue.append(each)
+ ordering.append(root)
+ spanning_tree[each] = None
+ _bfs(graph, queue, spanning_tree, ordering)
+
+ return spanning_tree, ordering[1:]
+
+
+def _bfs(graph, queue, spanning_tree, ordering):
+ """
+ Breadth-first search subfunction.
+
+ @type graph: graph
+ @param graph: Graph.
+
+ @type spanning_tree: dictionary
+ @param spanning_tree: Spanning tree being built for the graph by DFS.
+
+ @type ordering: list
+ @param ordering: Graph's level-based ordering.
+
+ @type queue: list
+ @param queue: Nodes to be visited (ordered).
+ """
+ while (queue != []):
+ node = queue.pop(0)
+
+ for other in graph[node]:
+ if (other not in spanning_tree):
+ queue.append(other)
+ ordering.append(other)
+ spanning_tree[other] = node