1 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com> |
|
2 # Rhys Ulerich <rhys.ulerich@gmail.com> |
|
3 # |
|
4 # Permission is hereby granted, free of charge, to any person |
|
5 # obtaining a copy of this software and associated documentation |
|
6 # files (the "Software"), to deal in the Software without |
|
7 # restriction, including without limitation the rights to use, |
|
8 # copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
9 # copies of the Software, and to permit persons to whom the |
|
10 # Software is furnished to do so, subject to the following |
|
11 # conditions: |
|
12 |
|
13 # The above copyright notice and this permission notice shall be |
|
14 # included in all copies or substantial portions of the Software. |
|
15 |
|
16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
17 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
|
18 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
|
19 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
|
20 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|
21 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
|
22 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
23 # OTHER DEALINGS IN THE SOFTWARE. |
|
24 |
|
25 |
|
26 """ |
|
27 Minimization and maximization algorithms for python-graph. |
|
28 |
|
29 @sort: minimal_spanning_tree, shortest_path, _first_unvisited, _lightest_edge |
|
30 """ |
|
31 |
|
32 |
|
33 # Minimal spanning tree |
|
34 |
|
35 def minimal_spanning_tree(graph, root=None): |
|
36 """ |
|
37 Minimal spanning tree. |
|
38 |
|
39 @attention: Minimal spanning tree meaningful only for weighted graphs. |
|
40 |
|
41 @type graph: graph |
|
42 @param graph: Graph. |
|
43 |
|
44 @type root: node |
|
45 @param root: Optional root node (will explore only root's connected component) |
|
46 |
|
47 @rtype: dictionary |
|
48 @return: Generated spanning tree. |
|
49 """ |
|
50 visited = [] # List for marking visited and non-visited nodes |
|
51 spanning_tree = {} # MInimal Spanning tree |
|
52 |
|
53 # Initialization |
|
54 if (root is not None): |
|
55 visited.append(root) |
|
56 nroot = root |
|
57 spanning_tree[root] = None |
|
58 else: |
|
59 nroot = 1 |
|
60 |
|
61 # Algorithm loop |
|
62 while (nroot is not None): |
|
63 ledge = _lightest_edge(graph, visited) |
|
64 if (ledge == (-1, -1)): |
|
65 if (root is not None): |
|
66 break |
|
67 nroot = _first_unvisited(graph, visited) |
|
68 if (nroot is not None): |
|
69 spanning_tree[nroot] = None |
|
70 visited.append(nroot) |
|
71 else: |
|
72 spanning_tree[ledge[1]] = ledge[0] |
|
73 visited.append(ledge[1]) |
|
74 |
|
75 return spanning_tree |
|
76 |
|
77 |
|
78 def _first_unvisited(graph, visited): |
|
79 """ |
|
80 Return first unvisited node. |
|
81 |
|
82 @type graph: graph |
|
83 @param graph: Graph. |
|
84 |
|
85 @type visited: list |
|
86 @param visited: List of nodes. |
|
87 |
|
88 @rtype: node |
|
89 @return: First unvisited node. |
|
90 """ |
|
91 for each in graph: |
|
92 if (each not in visited): |
|
93 return each |
|
94 return None |
|
95 |
|
96 |
|
97 def _lightest_edge(graph, visited): |
|
98 """ |
|
99 Return the lightest edge in graph going from a visited node to an unvisited one. |
|
100 |
|
101 @type graph: graph |
|
102 @param graph: Graph. |
|
103 |
|
104 @type visited: list |
|
105 @param visited: List of nodes. |
|
106 |
|
107 @rtype: tuple |
|
108 @return: Lightest edge in graph going from a visited node to an unvisited one. |
|
109 """ |
|
110 lightest_edge = (-1, -1) |
|
111 weight = -1 |
|
112 for each in visited: |
|
113 for other in graph[each]: |
|
114 if (other not in visited): |
|
115 w = graph.get_edge_weight(each, other) |
|
116 if (w < weight or weight < 0): |
|
117 lightest_edge = (each, other) |
|
118 weight = w |
|
119 return lightest_edge |
|
120 |
|
121 |
|
122 # Shortest Path |
|
123 # Code donated by Rhys Ulerich |
|
124 |
|
125 def shortest_path(graph, source): |
|
126 """ |
|
127 Return the shortest path distance between source and all other nodes using Dijkstra's algorithm. |
|
128 |
|
129 @attention: All weights must be nonnegative. |
|
130 |
|
131 @type graph: graph |
|
132 @param graph: Graph. |
|
133 |
|
134 @type source: node |
|
135 @param source: Node from which to start the search. |
|
136 |
|
137 @rtype: tuple |
|
138 @return: A tuple containing two dictionaries, each keyed by target nodes. |
|
139 1. Shortest path spanning tree |
|
140 2. Shortest distance from given source to each target node |
|
141 Inaccessible target nodes do not appear in either dictionary. |
|
142 """ |
|
143 # Initialization |
|
144 dist = { source: 0 } |
|
145 previous = { source: None} |
|
146 q = graph.nodes() |
|
147 |
|
148 # Algorithm loop |
|
149 while q: |
|
150 # examine_min process performed using O(nodes) pass here. |
|
151 # May be improved using another examine_min data structure. |
|
152 u = q[0] |
|
153 for node in q[1:]: |
|
154 if ((not dist.has_key(u)) |
|
155 or (dist.has_key(node) and dist[node] < dist[u])): |
|
156 u = node |
|
157 q.remove(u) |
|
158 |
|
159 # Process reachable, remaining nodes from u |
|
160 if (dist.has_key(u)): |
|
161 for v in graph[u]: |
|
162 if v in q: |
|
163 alt = dist[u] + graph.get_edge_weight(u, v) |
|
164 if (not dist.has_key(v)) or (alt < dist[v]): |
|
165 dist[v] = alt |
|
166 previous[v] = u |
|
167 |
|
168 return previous, dist |
|