--- a/app/graph/searching.py	Thu Nov 27 23:40:30 2008 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,167 +0,0 @@
-# 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