--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/thirdparty/python-graph/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