1 # Copyright (c) 2007-2008 Pedro Matiello <pmatiello@gmail.com> |
|
2 # |
|
3 # Permission is hereby granted, free of charge, to any person |
|
4 # obtaining a copy of this software and associated documentation |
|
5 # files (the "Software"), to deal in the Software without |
|
6 # restriction, including without limitation the rights to use, |
|
7 # copy, modify, merge, publish, distribute, sublicense, and/or sell |
|
8 # copies of the Software, and to permit persons to whom the |
|
9 # Software is furnished to do so, subject to the following |
|
10 # conditions: |
|
11 |
|
12 # The above copyright notice and this permission notice shall be |
|
13 # included in all copies or substantial portions of the Software. |
|
14 |
|
15 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
|
16 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
|
17 # OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
|
18 # NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT |
|
19 # HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, |
|
20 # WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
|
21 # FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
|
22 # OTHER DEALINGS IN THE SOFTWARE. |
|
23 |
|
24 |
|
25 """ |
|
26 Accessibility algorithms for python-graph. |
|
27 |
|
28 @sort: accessibility, connected_components, cut_edges, cut_nodes, mutual_accessibility |
|
29 """ |
|
30 |
|
31 |
|
32 # Transitive-closure |
|
33 |
|
34 def accessibility(graph): |
|
35 """ |
|
36 Accessibility matrix (transitive closure). |
|
37 |
|
38 @type graph: graph |
|
39 @param graph: Graph. |
|
40 |
|
41 @rtype: dictionary |
|
42 @return: Accessibility information for each node. |
|
43 """ |
|
44 accessibility = {} # Accessibility matrix |
|
45 |
|
46 # For each node i, mark each node j if that exists a path from i to j. |
|
47 for each in graph: |
|
48 access = {} |
|
49 # Perform DFS to explore all reachable nodes |
|
50 _dfs(graph, access, 1, each) |
|
51 accessibility[each] = access.keys() |
|
52 return accessibility |
|
53 |
|
54 |
|
55 # Strongly connected components |
|
56 |
|
57 def mutual_accessibility(graph): |
|
58 """ |
|
59 Mutual-accessibility matrix (strongly connected components). |
|
60 |
|
61 @type graph: graph |
|
62 @param graph: Graph. |
|
63 |
|
64 @rtype: dictionary |
|
65 @return: Mutual-accessibility information for each node. |
|
66 """ |
|
67 mutual_access = {} |
|
68 access = graph.accessibility() |
|
69 |
|
70 for i in graph: |
|
71 mutual_access[i] = [] |
|
72 for j in graph: |
|
73 if (i in access[j] and j in access[i]): |
|
74 mutual_access[i].append(j) |
|
75 |
|
76 return mutual_access |
|
77 |
|
78 |
|
79 # Connected components |
|
80 |
|
81 def connected_components(graph): |
|
82 """ |
|
83 Connected components. |
|
84 |
|
85 @attention: Indentification of connected components is meaningful only for non-directed graphs. |
|
86 |
|
87 @type graph: graph |
|
88 @param graph: Graph. |
|
89 |
|
90 @rtype: dictionary |
|
91 @return: Pairing that associates each node to its connected component. |
|
92 """ |
|
93 visited = {} |
|
94 count = 1 |
|
95 |
|
96 # For 'each' node not found to belong to a connected component, find its connected component. |
|
97 for each in graph: |
|
98 if (each not in visited): |
|
99 _dfs(graph, visited, count, each) |
|
100 count = count + 1 |
|
101 |
|
102 return visited |
|
103 |
|
104 |
|
105 # Limited DFS implementations used by algorithms here |
|
106 |
|
107 def _dfs(graph, visited, count, node): |
|
108 """ |
|
109 Depht-first search subfunction adapted for accessibility algorithms. |
|
110 |
|
111 @type graph: graph |
|
112 @param graph: Graph. |
|
113 |
|
114 @type visited: dictionary |
|
115 @param visited: List of nodes (visited nodes are marked non-zero). |
|
116 |
|
117 @type count: number |
|
118 @param count: Counter of connected components. |
|
119 |
|
120 @type node: number |
|
121 @param node: Node to be explored by DFS. |
|
122 """ |
|
123 visited[node] = count |
|
124 # Explore recursively the connected component |
|
125 for each in graph[node]: |
|
126 if (each not in visited): |
|
127 _dfs(graph, visited, count, each) |
|
128 |
|
129 |
|
130 # Cut-Edge and Cut-Vertex identification |
|
131 |
|
132 def cut_edges(graph): |
|
133 """ |
|
134 Return the cut-edges of the given graph. |
|
135 |
|
136 @rtype: list |
|
137 @return: List of cut-edges. |
|
138 """ |
|
139 pre = {} |
|
140 low = {} |
|
141 spanning_tree = {} |
|
142 reply = [] |
|
143 pre[None] = 0 |
|
144 |
|
145 for each in graph: |
|
146 if (not pre.has_key(each)): |
|
147 spanning_tree[each] = None |
|
148 _cut_dfs(graph, spanning_tree, pre, low, reply, each) |
|
149 return reply |
|
150 |
|
151 |
|
152 def cut_nodes(graph): |
|
153 """ |
|
154 Return the cut-nodes of the given graph. |
|
155 |
|
156 @rtype: list |
|
157 @return: List of cut-nodes. |
|
158 """ |
|
159 pre = {} # Pre-ordering |
|
160 low = {} # Lowest pre[] reachable from this node going down the spanning tree + one backedge |
|
161 reply = {} |
|
162 spanning_tree = {} |
|
163 pre[None] = 0 |
|
164 |
|
165 # Create spanning trees, calculate pre[], low[] |
|
166 for each in graph: |
|
167 if (not pre.has_key(each)): |
|
168 spanning_tree[each] = None |
|
169 _cut_dfs(graph, spanning_tree, pre, low, [], each) |
|
170 |
|
171 # Find cuts |
|
172 for each in graph: |
|
173 # If node is not a root |
|
174 if (spanning_tree[each] is not None): |
|
175 for other in graph[each]: |
|
176 # If there is no back-edge from descendent to a ancestral of each |
|
177 if (low[other] >= pre[each] and spanning_tree[other] == each): |
|
178 reply[each] = 1 |
|
179 # If node is a root |
|
180 else: |
|
181 children = 0 |
|
182 for other in graph: |
|
183 if (spanning_tree[other] == each): |
|
184 children = children + 1 |
|
185 # root is cut-vertex iff it has two or more children |
|
186 if (children >= 2): |
|
187 reply[each] = 1 |
|
188 |
|
189 return reply.keys() |
|
190 |
|
191 |
|
192 def _cut_dfs(graph, spanning_tree, pre, low, reply, node): |
|
193 """ |
|
194 Depth first search adapted for identification of cut-edges and cut-nodes. |
|
195 |
|
196 @type graph: graph |
|
197 @param graph: Graph |
|
198 |
|
199 @type spanning_tree: dictionary |
|
200 @param spanning_tree: Spanning tree being built for the graph by DFS. |
|
201 |
|
202 @type pre: dictionary |
|
203 @param pre: Graph's preordering. |
|
204 |
|
205 @type low: dictionary |
|
206 @param low: Associates to each node, the preordering index of the node of lowest preordering |
|
207 accessible from the given node. |
|
208 |
|
209 @type reply: list |
|
210 @param reply: List of cut-edges. |
|
211 |
|
212 @type node: node |
|
213 @param node: Node to be explored by DFS. |
|
214 """ |
|
215 pre[node] = pre[None] |
|
216 low[node] = pre[None] |
|
217 pre[None] = pre[None] + 1 |
|
218 |
|
219 for each in graph[node]: |
|
220 if (not pre.has_key(each)): |
|
221 spanning_tree[each] = node |
|
222 _cut_dfs(graph, spanning_tree, pre, low, reply, each) |
|
223 if (low[node] > low[each]): |
|
224 low[node] = low[each] |
|
225 if (low[each] == pre[each]): |
|
226 reply.append((node, each)) |
|
227 elif (low[node] > pre[each] and spanning_tree[node] != each): |
|
228 low[node] = pre[each] |
|