Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/basic.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 ========================== | |
3 Bipartite Graph Algorithms | |
4 ========================== | |
5 """ | |
6 import networkx as nx | |
7 from networkx.algorithms.components import connected_components | |
8 | |
9 __all__ = [ | |
10 "is_bipartite", | |
11 "is_bipartite_node_set", | |
12 "color", | |
13 "sets", | |
14 "density", | |
15 "degrees", | |
16 ] | |
17 | |
18 | |
19 def color(G): | |
20 """Returns a two-coloring of the graph. | |
21 | |
22 Raises an exception if the graph is not bipartite. | |
23 | |
24 Parameters | |
25 ---------- | |
26 G : NetworkX graph | |
27 | |
28 Returns | |
29 ------- | |
30 color : dictionary | |
31 A dictionary keyed by node with a 1 or 0 as data for each node color. | |
32 | |
33 Raises | |
34 ------ | |
35 NetworkXError | |
36 If the graph is not two-colorable. | |
37 | |
38 Examples | |
39 -------- | |
40 >>> from networkx.algorithms import bipartite | |
41 >>> G = nx.path_graph(4) | |
42 >>> c = bipartite.color(G) | |
43 >>> print(c) | |
44 {0: 1, 1: 0, 2: 1, 3: 0} | |
45 | |
46 You can use this to set a node attribute indicating the biparite set: | |
47 | |
48 >>> nx.set_node_attributes(G, c, "bipartite") | |
49 >>> print(G.nodes[0]["bipartite"]) | |
50 1 | |
51 >>> print(G.nodes[1]["bipartite"]) | |
52 0 | |
53 """ | |
54 if G.is_directed(): | |
55 import itertools | |
56 | |
57 def neighbors(v): | |
58 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)]) | |
59 | |
60 else: | |
61 neighbors = G.neighbors | |
62 | |
63 color = {} | |
64 for n in G: # handle disconnected graphs | |
65 if n in color or len(G[n]) == 0: # skip isolates | |
66 continue | |
67 queue = [n] | |
68 color[n] = 1 # nodes seen with color (1 or 0) | |
69 while queue: | |
70 v = queue.pop() | |
71 c = 1 - color[v] # opposite color of node v | |
72 for w in neighbors(v): | |
73 if w in color: | |
74 if color[w] == color[v]: | |
75 raise nx.NetworkXError("Graph is not bipartite.") | |
76 else: | |
77 color[w] = c | |
78 queue.append(w) | |
79 # color isolates with 0 | |
80 color.update(dict.fromkeys(nx.isolates(G), 0)) | |
81 return color | |
82 | |
83 | |
84 def is_bipartite(G): | |
85 """ Returns True if graph G is bipartite, False if not. | |
86 | |
87 Parameters | |
88 ---------- | |
89 G : NetworkX graph | |
90 | |
91 Examples | |
92 -------- | |
93 >>> from networkx.algorithms import bipartite | |
94 >>> G = nx.path_graph(4) | |
95 >>> print(bipartite.is_bipartite(G)) | |
96 True | |
97 | |
98 See Also | |
99 -------- | |
100 color, is_bipartite_node_set | |
101 """ | |
102 try: | |
103 color(G) | |
104 return True | |
105 except nx.NetworkXError: | |
106 return False | |
107 | |
108 | |
109 def is_bipartite_node_set(G, nodes): | |
110 """Returns True if nodes and G/nodes are a bipartition of G. | |
111 | |
112 Parameters | |
113 ---------- | |
114 G : NetworkX graph | |
115 | |
116 nodes: list or container | |
117 Check if nodes are a one of a bipartite set. | |
118 | |
119 Examples | |
120 -------- | |
121 >>> from networkx.algorithms import bipartite | |
122 >>> G = nx.path_graph(4) | |
123 >>> X = set([1, 3]) | |
124 >>> bipartite.is_bipartite_node_set(G, X) | |
125 True | |
126 | |
127 Notes | |
128 ----- | |
129 For connected graphs the bipartite sets are unique. This function handles | |
130 disconnected graphs. | |
131 """ | |
132 S = set(nodes) | |
133 for CC in (G.subgraph(c).copy() for c in connected_components(G)): | |
134 X, Y = sets(CC) | |
135 if not ( | |
136 (X.issubset(S) and Y.isdisjoint(S)) or (Y.issubset(S) and X.isdisjoint(S)) | |
137 ): | |
138 return False | |
139 return True | |
140 | |
141 | |
142 def sets(G, top_nodes=None): | |
143 """Returns bipartite node sets of graph G. | |
144 | |
145 Raises an exception if the graph is not bipartite or if the input | |
146 graph is disconnected and thus more than one valid solution exists. | |
147 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
148 for further details on how bipartite graphs are handled in NetworkX. | |
149 | |
150 Parameters | |
151 ---------- | |
152 G : NetworkX graph | |
153 | |
154 top_nodes : container, optional | |
155 Container with all nodes in one bipartite node set. If not supplied | |
156 it will be computed. But if more than one solution exists an exception | |
157 will be raised. | |
158 | |
159 Returns | |
160 ------- | |
161 X : set | |
162 Nodes from one side of the bipartite graph. | |
163 Y : set | |
164 Nodes from the other side. | |
165 | |
166 Raises | |
167 ------ | |
168 AmbiguousSolution | |
169 Raised if the input bipartite graph is disconnected and no container | |
170 with all nodes in one bipartite set is provided. When determining | |
171 the nodes in each bipartite set more than one valid solution is | |
172 possible if the input graph is disconnected. | |
173 NetworkXError | |
174 Raised if the input graph is not bipartite. | |
175 | |
176 Examples | |
177 -------- | |
178 >>> from networkx.algorithms import bipartite | |
179 >>> G = nx.path_graph(4) | |
180 >>> X, Y = bipartite.sets(G) | |
181 >>> list(X) | |
182 [0, 2] | |
183 >>> list(Y) | |
184 [1, 3] | |
185 | |
186 See Also | |
187 -------- | |
188 color | |
189 | |
190 """ | |
191 if G.is_directed(): | |
192 is_connected = nx.is_weakly_connected | |
193 else: | |
194 is_connected = nx.is_connected | |
195 if top_nodes is not None: | |
196 X = set(top_nodes) | |
197 Y = set(G) - X | |
198 else: | |
199 if not is_connected(G): | |
200 msg = "Disconnected graph: Ambiguous solution for bipartite sets." | |
201 raise nx.AmbiguousSolution(msg) | |
202 c = color(G) | |
203 X = {n for n, is_top in c.items() if is_top} | |
204 Y = {n for n, is_top in c.items() if not is_top} | |
205 return (X, Y) | |
206 | |
207 | |
208 def density(B, nodes): | |
209 """Returns density of bipartite graph B. | |
210 | |
211 Parameters | |
212 ---------- | |
213 G : NetworkX graph | |
214 | |
215 nodes: list or container | |
216 Nodes in one node set of the bipartite graph. | |
217 | |
218 Returns | |
219 ------- | |
220 d : float | |
221 The bipartite density | |
222 | |
223 Examples | |
224 -------- | |
225 >>> from networkx.algorithms import bipartite | |
226 >>> G = nx.complete_bipartite_graph(3, 2) | |
227 >>> X = set([0, 1, 2]) | |
228 >>> bipartite.density(G, X) | |
229 1.0 | |
230 >>> Y = set([3, 4]) | |
231 >>> bipartite.density(G, Y) | |
232 1.0 | |
233 | |
234 Notes | |
235 ----- | |
236 The container of nodes passed as argument must contain all nodes | |
237 in one of the two bipartite node sets to avoid ambiguity in the | |
238 case of disconnected graphs. | |
239 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
240 for further details on how bipartite graphs are handled in NetworkX. | |
241 | |
242 See Also | |
243 -------- | |
244 color | |
245 """ | |
246 n = len(B) | |
247 m = nx.number_of_edges(B) | |
248 nb = len(nodes) | |
249 nt = n - nb | |
250 if m == 0: # includes cases n==0 and n==1 | |
251 d = 0.0 | |
252 else: | |
253 if B.is_directed(): | |
254 d = m / (2.0 * float(nb * nt)) | |
255 else: | |
256 d = m / float(nb * nt) | |
257 return d | |
258 | |
259 | |
260 def degrees(B, nodes, weight=None): | |
261 """Returns the degrees of the two node sets in the bipartite graph B. | |
262 | |
263 Parameters | |
264 ---------- | |
265 G : NetworkX graph | |
266 | |
267 nodes: list or container | |
268 Nodes in one node set of the bipartite graph. | |
269 | |
270 weight : string or None, optional (default=None) | |
271 The edge attribute that holds the numerical value used as a weight. | |
272 If None, then each edge has weight 1. | |
273 The degree is the sum of the edge weights adjacent to the node. | |
274 | |
275 Returns | |
276 ------- | |
277 (degX,degY) : tuple of dictionaries | |
278 The degrees of the two bipartite sets as dictionaries keyed by node. | |
279 | |
280 Examples | |
281 -------- | |
282 >>> from networkx.algorithms import bipartite | |
283 >>> G = nx.complete_bipartite_graph(3, 2) | |
284 >>> Y = set([3, 4]) | |
285 >>> degX, degY = bipartite.degrees(G, Y) | |
286 >>> dict(degX) | |
287 {0: 2, 1: 2, 2: 2} | |
288 | |
289 Notes | |
290 ----- | |
291 The container of nodes passed as argument must contain all nodes | |
292 in one of the two bipartite node sets to avoid ambiguity in the | |
293 case of disconnected graphs. | |
294 See :mod:`bipartite documentation <networkx.algorithms.bipartite>` | |
295 for further details on how bipartite graphs are handled in NetworkX. | |
296 | |
297 See Also | |
298 -------- | |
299 color, density | |
300 """ | |
301 bottom = set(nodes) | |
302 top = set(B) - bottom | |
303 return (B.degree(top, weight), B.degree(bottom, weight)) |