Mercurial > repos > shellac > sam_consensus_v3

comparison env/lib/python3.9/site-packages/networkx/algorithms/hybrid.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"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