--- a/app/graph/minmax.py Thu Nov 27 23:40:30 2008 +0000
+++ /dev/null Thu Jan 01 00:00:00 1970 +0000
@@ -1,168 +0,0 @@
-# Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com>
-# Rhys Ulerich <rhys.ulerich@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.
-
-
-"""
-Minimization and maximization algorithms for python-graph.
-
-@sort: minimal_spanning_tree, shortest_path, _first_unvisited, _lightest_edge
-"""
-
-
-# Minimal spanning tree
-
-def minimal_spanning_tree(graph, root=None):
- """
- Minimal spanning tree.
-
- @attention: Minimal spanning tree meaningful only for weighted graphs.
-
- @type graph: graph
- @param graph: Graph.
-
- @type root: node
- @param root: Optional root node (will explore only root's connected component)
-
- @rtype: dictionary
- @return: Generated spanning tree.
- """
- visited = [] # List for marking visited and non-visited nodes
- spanning_tree = {} # MInimal Spanning tree
-
- # Initialization
- if (root is not None):
- visited.append(root)
- nroot = root
- spanning_tree[root] = None
- else:
- nroot = 1
-
- # Algorithm loop
- while (nroot is not None):
- ledge = _lightest_edge(graph, visited)
- if (ledge == (-1, -1)):
- if (root is not None):
- break
- nroot = _first_unvisited(graph, visited)
- if (nroot is not None):
- spanning_tree[nroot] = None
- visited.append(nroot)
- else:
- spanning_tree[ledge[1]] = ledge[0]
- visited.append(ledge[1])
-
- return spanning_tree
-
-
-def _first_unvisited(graph, visited):
- """
- Return first unvisited node.
-
- @type graph: graph
- @param graph: Graph.
-
- @type visited: list
- @param visited: List of nodes.
-
- @rtype: node
- @return: First unvisited node.
- """
- for each in graph:
- if (each not in visited):
- return each
- return None
-
-
-def _lightest_edge(graph, visited):
- """
- Return the lightest edge in graph going from a visited node to an unvisited one.
-
- @type graph: graph
- @param graph: Graph.
-
- @type visited: list
- @param visited: List of nodes.
-
- @rtype: tuple
- @return: Lightest edge in graph going from a visited node to an unvisited one.
- """
- lightest_edge = (-1, -1)
- weight = -1
- for each in visited:
- for other in graph[each]:
- if (other not in visited):
- w = graph.get_edge_weight(each, other)
- if (w < weight or weight < 0):
- lightest_edge = (each, other)
- weight = w
- return lightest_edge
-
-
-# Shortest Path
-# Code donated by Rhys Ulerich
-
-def shortest_path(graph, source):
- """
- Return the shortest path distance between source and all other nodes using Dijkstra's algorithm.
-
- @attention: All weights must be nonnegative.
-
- @type graph: graph
- @param graph: Graph.
-
- @type source: node
- @param source: Node from which to start the search.
-
- @rtype: tuple
- @return: A tuple containing two dictionaries, each keyed by target nodes.
- 1. Shortest path spanning tree
- 2. Shortest distance from given source to each target node
- Inaccessible target nodes do not appear in either dictionary.
- """
- # Initialization
- dist = { source: 0 }
- previous = { source: None}
- q = graph.nodes()
-
- # Algorithm loop
- while q:
- # examine_min process performed using O(nodes) pass here.
- # May be improved using another examine_min data structure.
- u = q[0]
- for node in q[1:]:
- if ((not dist.has_key(u))
- or (dist.has_key(node) and dist[node] < dist[u])):
- u = node
- q.remove(u)
-
- # Process reachable, remaining nodes from u
- if (dist.has_key(u)):
- for v in graph[u]:
- if v in q:
- alt = dist[u] + graph.get_edge_weight(u, v)
- if (not dist.has_key(v)) or (alt < dist[v]):
- dist[v] = alt
- previous[v] = u
-
- return previous, dist