Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/hybrid.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 Provides functions for finding and testing for locally `(k, l)`-connected | |
3 graphs. | |
4 | |
5 """ | |
6 import copy | |
7 import networkx as nx | |
8 | |
9 __all__ = ["kl_connected_subgraph", "is_kl_connected"] | |
10 | |
11 | |
12 def kl_connected_subgraph(G, k, l, low_memory=False, same_as_graph=False): | |
13 """Returns the maximum locally `(k, l)`-connected subgraph of `G`. | |
14 | |
15 A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the | |
16 graph there are at least `l` edge-disjoint paths of length at most `k` | |
17 joining `u` to `v`. | |
18 | |
19 Parameters | |
20 ---------- | |
21 G : NetworkX graph | |
22 The graph in which to find a maximum locally `(k, l)`-connected | |
23 subgraph. | |
24 | |
25 k : integer | |
26 The maximum length of paths to consider. A higher number means a looser | |
27 connectivity requirement. | |
28 | |
29 l : integer | |
30 The number of edge-disjoint paths. A higher number means a stricter | |
31 connectivity requirement. | |
32 | |
33 low_memory : bool | |
34 If this is True, this function uses an algorithm that uses slightly | |
35 more time but less memory. | |
36 | |
37 same_as_graph : bool | |
38 If True then return a tuple of the form `(H, is_same)`, | |
39 where `H` is the maximum locally `(k, l)`-connected subgraph and | |
40 `is_same` is a Boolean representing whether `G` is locally `(k, | |
41 l)`-connected (and hence, whether `H` is simply a copy of the input | |
42 graph `G`). | |
43 | |
44 Returns | |
45 ------- | |
46 NetworkX graph or two-tuple | |
47 If `same_as_graph` is True, then this function returns a | |
48 two-tuple as described above. Otherwise, it returns only the maximum | |
49 locally `(k, l)`-connected subgraph. | |
50 | |
51 See also | |
52 -------- | |
53 is_kl_connected | |
54 | |
55 References | |
56 ---------- | |
57 .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid | |
58 Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg, | |
59 2004. 89--104. | |
60 | |
61 """ | |
62 H = copy.deepcopy(G) # subgraph we construct by removing from G | |
63 | |
64 graphOK = True | |
65 deleted_some = True # hack to start off the while loop | |
66 while deleted_some: | |
67 deleted_some = False | |
68 # We use `for edge in list(H.edges()):` instead of | |
69 # `for edge in H.edges():` because we edit the graph `H` in | |
70 # the loop. Hence using an iterator will result in | |
71 # `RuntimeError: dictionary changed size during iteration` | |
72 for edge in list(H.edges()): | |
73 (u, v) = edge | |
74 # Get copy of graph needed for this search | |
75 if low_memory: | |
76 verts = {u, v} | |
77 for i in range(k): | |
78 for w in verts.copy(): | |
79 verts.update(G[w]) | |
80 G2 = G.subgraph(verts).copy() | |
81 else: | |
82 G2 = copy.deepcopy(G) | |
83 ### | |
84 path = [u, v] | |
85 cnt = 0 | |
86 accept = 0 | |
87 while path: | |
88 cnt += 1 # Found a path | |
89 if cnt >= l: | |
90 accept = 1 | |
91 break | |
92 # record edges along this graph | |
93 prev = u | |
94 for w in path: | |
95 if prev != w: | |
96 G2.remove_edge(prev, w) | |
97 prev = w | |
98 # path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1? | |
99 try: | |
100 path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1? | |
101 except nx.NetworkXNoPath: | |
102 path = False | |
103 # No Other Paths | |
104 if accept == 0: | |
105 H.remove_edge(u, v) | |
106 deleted_some = True | |
107 if graphOK: | |
108 graphOK = False | |
109 # We looked through all edges and removed none of them. | |
110 # So, H is the maximal (k,l)-connected subgraph of G | |
111 if same_as_graph: | |
112 return (H, graphOK) | |
113 return H | |
114 | |
115 | |
116 def is_kl_connected(G, k, l, low_memory=False): | |
117 """Returns True if and only if `G` is locally `(k, l)`-connected. | |
118 | |
119 A graph is locally `(k, l)`-connected if for each edge `(u, v)` in the | |
120 graph there are at least `l` edge-disjoint paths of length at most `k` | |
121 joining `u` to `v`. | |
122 | |
123 Parameters | |
124 ---------- | |
125 G : NetworkX graph | |
126 The graph to test for local `(k, l)`-connectedness. | |
127 | |
128 k : integer | |
129 The maximum length of paths to consider. A higher number means a looser | |
130 connectivity requirement. | |
131 | |
132 l : integer | |
133 The number of edge-disjoint paths. A higher number means a stricter | |
134 connectivity requirement. | |
135 | |
136 low_memory : bool | |
137 If this is True, this function uses an algorithm that uses slightly | |
138 more time but less memory. | |
139 | |
140 Returns | |
141 ------- | |
142 bool | |
143 Whether the graph is locally `(k, l)`-connected subgraph. | |
144 | |
145 See also | |
146 -------- | |
147 kl_connected_subgraph | |
148 | |
149 References | |
150 ---------- | |
151 .. [1]: Chung, Fan and Linyuan Lu. "The Small World Phenomenon in Hybrid | |
152 Power Law Graphs." *Complex Networks*. Springer Berlin Heidelberg, | |
153 2004. 89--104. | |
154 | |
155 """ | |
156 graphOK = True | |
157 for edge in G.edges(): | |
158 (u, v) = edge | |
159 # Get copy of graph needed for this search | |
160 if low_memory: | |
161 verts = {u, v} | |
162 for i in range(k): | |
163 [verts.update(G.neighbors(w)) for w in verts.copy()] | |
164 G2 = G.subgraph(verts) | |
165 else: | |
166 G2 = copy.deepcopy(G) | |
167 ### | |
168 path = [u, v] | |
169 cnt = 0 | |
170 accept = 0 | |
171 while path: | |
172 cnt += 1 # Found a path | |
173 if cnt >= l: | |
174 accept = 1 | |
175 break | |
176 # record edges along this graph | |
177 prev = u | |
178 for w in path: | |
179 if w != prev: | |
180 G2.remove_edge(prev, w) | |
181 prev = w | |
182 # path = shortest_path(G2, u, v, k) # ??? should "Cutoff" be k+1? | |
183 try: | |
184 path = nx.shortest_path(G2, u, v) # ??? should "Cutoff" be k+1? | |
185 except nx.NetworkXNoPath: | |
186 path = False | |
187 # No Other Paths | |
188 if accept == 0: | |
189 graphOK = False | |
190 break | |
191 # return status | |
192 return graphOK |