# 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