Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/hybrid.py @ 1:56ad4e20f292 draft

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