Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/connectivity/utils.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Utilities for connectivity package | |
3 """ | |
4 import networkx as nx | |
5 | |
6 __all__ = ["build_auxiliary_node_connectivity", "build_auxiliary_edge_connectivity"] | |
7 | |
8 | |
9 def build_auxiliary_node_connectivity(G): | |
10 r"""Creates a directed graph D from an undirected graph G to compute flow | |
11 based node connectivity. | |
12 | |
13 For an undirected graph G having `n` nodes and `m` edges we derive a | |
14 directed graph D with `2n` nodes and `2m+n` arcs by replacing each | |
15 original node `v` with two nodes `vA`, `vB` linked by an (internal) | |
16 arc in D. Then for each edge (`u`, `v`) in G we add two arcs (`uB`, `vA`) | |
17 and (`vB`, `uA`) in D. Finally we set the attribute capacity = 1 for each | |
18 arc in D [1]_. | |
19 | |
20 For a directed graph having `n` nodes and `m` arcs we derive a | |
21 directed graph D with `2n` nodes and `m+n` arcs by replacing each | |
22 original node `v` with two nodes `vA`, `vB` linked by an (internal) | |
23 arc (`vA`, `vB`) in D. Then for each arc (`u`, `v`) in G we add one | |
24 arc (`uB`, `vA`) in D. Finally we set the attribute capacity = 1 for | |
25 each arc in D. | |
26 | |
27 A dictionary with a mapping between nodes in the original graph and the | |
28 auxiliary digraph is stored as a graph attribute: H.graph['mapping']. | |
29 | |
30 References | |
31 ---------- | |
32 .. [1] Kammer, Frank and Hanjo Taubig. Graph Connectivity. in Brandes and | |
33 Erlebach, 'Network Analysis: Methodological Foundations', Lecture | |
34 Notes in Computer Science, Volume 3418, Springer-Verlag, 2005. | |
35 http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf | |
36 | |
37 """ | |
38 directed = G.is_directed() | |
39 | |
40 mapping = {} | |
41 H = nx.DiGraph() | |
42 | |
43 for i, node in enumerate(G): | |
44 mapping[node] = i | |
45 H.add_node(f"{i}A", id=node) | |
46 H.add_node(f"{i}B", id=node) | |
47 H.add_edge(f"{i}A", f"{i}B", capacity=1) | |
48 | |
49 edges = [] | |
50 for (source, target) in G.edges(): | |
51 edges.append((f"{mapping[source]}B", f"{mapping[target]}A")) | |
52 if not directed: | |
53 edges.append((f"{mapping[target]}B", f"{mapping[source]}A")) | |
54 H.add_edges_from(edges, capacity=1) | |
55 | |
56 # Store mapping as graph attribute | |
57 H.graph["mapping"] = mapping | |
58 return H | |
59 | |
60 | |
61 def build_auxiliary_edge_connectivity(G): | |
62 """Auxiliary digraph for computing flow based edge connectivity | |
63 | |
64 If the input graph is undirected, we replace each edge (`u`,`v`) with | |
65 two reciprocal arcs (`u`, `v`) and (`v`, `u`) and then we set the attribute | |
66 'capacity' for each arc to 1. If the input graph is directed we simply | |
67 add the 'capacity' attribute. Part of algorithm 1 in [1]_ . | |
68 | |
69 References | |
70 ---------- | |
71 .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. (this is a | |
72 chapter, look for the reference of the book). | |
73 http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf | |
74 """ | |
75 if G.is_directed(): | |
76 H = nx.DiGraph() | |
77 H.add_nodes_from(G.nodes()) | |
78 H.add_edges_from(G.edges(), capacity=1) | |
79 return H | |
80 else: | |
81 H = nx.DiGraph() | |
82 H.add_nodes_from(G.nodes()) | |
83 for (source, target) in G.edges(): | |
84 H.add_edges_from([(source, target), (target, source)], capacity=1) | |
85 return H |