diff -r 342bebadd075 -r 88c486951f10 thirdparty/python-graph/graph/accessibility.py --- a/thirdparty/python-graph/graph/accessibility.py Sun Nov 30 16:39:18 2008 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,228 +0,0 @@ -# Copyright (c) 2007-2008 Pedro Matiello -# -# 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. - - -""" -Accessibility algorithms for python-graph. - -@sort: accessibility, connected_components, cut_edges, cut_nodes, mutual_accessibility -""" - - -# Transitive-closure - -def accessibility(graph): - """ - Accessibility matrix (transitive closure). - - @type graph: graph - @param graph: Graph. - - @rtype: dictionary - @return: Accessibility information for each node. - """ - accessibility = {} # Accessibility matrix - - # For each node i, mark each node j if that exists a path from i to j. - for each in graph: - access = {} - # Perform DFS to explore all reachable nodes - _dfs(graph, access, 1, each) - accessibility[each] = access.keys() - return accessibility - - -# Strongly connected components - -def mutual_accessibility(graph): - """ - Mutual-accessibility matrix (strongly connected components). - - @type graph: graph - @param graph: Graph. - - @rtype: dictionary - @return: Mutual-accessibility information for each node. - """ - mutual_access = {} - access = graph.accessibility() - - for i in graph: - mutual_access[i] = [] - for j in graph: - if (i in access[j] and j in access[i]): - mutual_access[i].append(j) - - return mutual_access - - -# Connected components - -def connected_components(graph): - """ - Connected components. - - @attention: Indentification of connected components is meaningful only for non-directed graphs. - - @type graph: graph - @param graph: Graph. - - @rtype: dictionary - @return: Pairing that associates each node to its connected component. - """ - visited = {} - count = 1 - - # For 'each' node not found to belong to a connected component, find its connected component. - for each in graph: - if (each not in visited): - _dfs(graph, visited, count, each) - count = count + 1 - - return visited - - -# Limited DFS implementations used by algorithms here - -def _dfs(graph, visited, count, node): - """ - Depht-first search subfunction adapted for accessibility algorithms. - - @type graph: graph - @param graph: Graph. - - @type visited: dictionary - @param visited: List of nodes (visited nodes are marked non-zero). - - @type count: number - @param count: Counter of connected components. - - @type node: number - @param node: Node to be explored by DFS. - """ - visited[node] = count - # Explore recursively the connected component - for each in graph[node]: - if (each not in visited): - _dfs(graph, visited, count, each) - - -# Cut-Edge and Cut-Vertex identification - -def cut_edges(graph): - """ - Return the cut-edges of the given graph. - - @rtype: list - @return: List of cut-edges. - """ - pre = {} - low = {} - spanning_tree = {} - reply = [] - pre[None] = 0 - - for each in graph: - if (not pre.has_key(each)): - spanning_tree[each] = None - _cut_dfs(graph, spanning_tree, pre, low, reply, each) - return reply - - -def cut_nodes(graph): - """ - Return the cut-nodes of the given graph. - - @rtype: list - @return: List of cut-nodes. - """ - pre = {} # Pre-ordering - low = {} # Lowest pre[] reachable from this node going down the spanning tree + one backedge - reply = {} - spanning_tree = {} - pre[None] = 0 - - # Create spanning trees, calculate pre[], low[] - for each in graph: - if (not pre.has_key(each)): - spanning_tree[each] = None - _cut_dfs(graph, spanning_tree, pre, low, [], each) - - # Find cuts - for each in graph: - # If node is not a root - if (spanning_tree[each] is not None): - for other in graph[each]: - # If there is no back-edge from descendent to a ancestral of each - if (low[other] >= pre[each] and spanning_tree[other] == each): - reply[each] = 1 - # If node is a root - else: - children = 0 - for other in graph: - if (spanning_tree[other] == each): - children = children + 1 - # root is cut-vertex iff it has two or more children - if (children >= 2): - reply[each] = 1 - - return reply.keys() - - -def _cut_dfs(graph, spanning_tree, pre, low, reply, node): - """ - Depth first search adapted for identification of cut-edges and cut-nodes. - - @type graph: graph - @param graph: Graph - - @type spanning_tree: dictionary - @param spanning_tree: Spanning tree being built for the graph by DFS. - - @type pre: dictionary - @param pre: Graph's preordering. - - @type low: dictionary - @param low: Associates to each node, the preordering index of the node of lowest preordering - accessible from the given node. - - @type reply: list - @param reply: List of cut-edges. - - @type node: node - @param node: Node to be explored by DFS. - """ - pre[node] = pre[None] - low[node] = pre[None] - pre[None] = pre[None] + 1 - - for each in graph[node]: - if (not pre.has_key(each)): - spanning_tree[each] = node - _cut_dfs(graph, spanning_tree, pre, low, reply, each) - if (low[node] > low[each]): - low[node] = low[each] - if (low[each] == pre[each]): - reply.append((node, each)) - elif (low[node] > pre[each] and spanning_tree[node] != each): - low[node] = pre[each]