scripts/graph/traversal.py
author Sverre Rabbelier <srabbelier@gmail.com>
Thu, 27 Nov 2008 23:41:08 +0000
changeset 599 32a30f609530
parent 594 app/graph/traversal.py@06c2228e39cb
permissions -rw-r--r--
Moved check_includes and graph from app to scripts Patch by: Sverre Rabbelier
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
594
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     1
# Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     2
#
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     3
# Permission is hereby granted, free of charge, to any person
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     4
# obtaining a copy of this software and associated documentation
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     5
# files (the "Software"), to deal in the Software without
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     6
# restriction, including without limitation the rights to use,
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     7
# copy, modify, merge, publish, distribute, sublicense, and/or sell
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     8
# copies of the Software, and to permit persons to whom the
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
     9
# Software is furnished to do so, subject to the following
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    10
# conditions:
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    11
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    12
# The above copyright notice and this permission notice shall be
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    13
# included in all copies or substantial portions of the Software.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    14
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    15
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    16
# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    17
# OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    18
# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    19
# HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    20
# WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    21
# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    22
# OTHER DEALINGS IN THE SOFTWARE.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    23
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    24
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    25
"""
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    26
Traversal algorithms for python-graph.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    27
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    28
@sort: traversal
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    29
"""
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    30
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    31
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    32
# Minimal spanning tree
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    33
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    34
def traversal(graph, node, order):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    35
	"""
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    36
	Graph traversal iterator.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    37
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    38
	@type  node: node
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    39
	@param node: Node.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    40
	
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    41
	@type  order: string
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    42
	@param order: traversal ordering. Possible values are:
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    43
		2. 'pre' - Preordering (default)
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    44
		1. 'post' - Postordering
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    45
	
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    46
	@rtype:  iterator
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    47
	@return: Traversal iterator.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    48
	"""
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    49
	visited = {}
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    50
	if (order == 'pre'):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    51
		pre = 1
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    52
		post = 0
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    53
	elif (order == 'post'):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    54
		pre = 0
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    55
		post = 1
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    56
	
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    57
	for each in _dfs(graph, visited, node, pre, post):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    58
		yield each
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    59
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    60
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    61
def _dfs(graph, visited, node, pre, post):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    62
	"""
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    63
	Depht-first search subfunction for traversals.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    64
	
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    65
	@type  graph: graph
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    66
	@param graph: Graph.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    67
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    68
	@type  visited: dictionary
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    69
	@param visited: List of nodes (visited nodes are marked non-zero).
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    70
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    71
	@type  node: node
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    72
	@param node: Node to be explored by DFS.
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    73
	"""
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    74
	visited[node] = 1
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    75
	if (pre): yield node
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    76
	# Explore recursively the connected component
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    77
	for each in graph[node]:
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    78
		if (each not in visited):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    79
			for other in _dfs(graph, visited, each, pre, post):
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    80
				yield other
06c2228e39cb Added the python-graph module
Sverre Rabbelier <srabbelier@gmail.com>
parents:
diff changeset
    81
	if (post): yield node