Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/bipartite/basic.py: 21%
77 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2==========================
3Bipartite Graph Algorithms
4==========================
5"""
6import networkx as nx
7from networkx.algorithms.components import connected_components
8from networkx.exception import AmbiguousSolution
10__all__ = [
11 "is_bipartite",
12 "is_bipartite_node_set",
13 "color",
14 "sets",
15 "density",
16 "degrees",
17]
20@nx._dispatch
21def color(G):
22 """Returns a two-coloring of the graph.
24 Raises an exception if the graph is not bipartite.
26 Parameters
27 ----------
28 G : NetworkX graph
30 Returns
31 -------
32 color : dictionary
33 A dictionary keyed by node with a 1 or 0 as data for each node color.
35 Raises
36 ------
37 NetworkXError
38 If the graph is not two-colorable.
40 Examples
41 --------
42 >>> from networkx.algorithms import bipartite
43 >>> G = nx.path_graph(4)
44 >>> c = bipartite.color(G)
45 >>> print(c)
46 {0: 1, 1: 0, 2: 1, 3: 0}
48 You can use this to set a node attribute indicating the bipartite set:
50 >>> nx.set_node_attributes(G, c, "bipartite")
51 >>> print(G.nodes[0]["bipartite"])
52 1
53 >>> print(G.nodes[1]["bipartite"])
54 0
55 """
56 if G.is_directed():
57 import itertools
59 def neighbors(v):
60 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)])
62 else:
63 neighbors = G.neighbors
65 color = {}
66 for n in G: # handle disconnected graphs
67 if n in color or len(G[n]) == 0: # skip isolates
68 continue
69 queue = [n]
70 color[n] = 1 # nodes seen with color (1 or 0)
71 while queue:
72 v = queue.pop()
73 c = 1 - color[v] # opposite color of node v
74 for w in neighbors(v):
75 if w in color:
76 if color[w] == color[v]:
77 raise nx.NetworkXError("Graph is not bipartite.")
78 else:
79 color[w] = c
80 queue.append(w)
81 # color isolates with 0
82 color.update(dict.fromkeys(nx.isolates(G), 0))
83 return color
86@nx._dispatch
87def is_bipartite(G):
88 """Returns True if graph G is bipartite, False if not.
90 Parameters
91 ----------
92 G : NetworkX graph
94 Examples
95 --------
96 >>> from networkx.algorithms import bipartite
97 >>> G = nx.path_graph(4)
98 >>> print(bipartite.is_bipartite(G))
99 True
101 See Also
102 --------
103 color, is_bipartite_node_set
104 """
105 try:
106 color(G)
107 return True
108 except nx.NetworkXError:
109 return False
112@nx._dispatch
113def is_bipartite_node_set(G, nodes):
114 """Returns True if nodes and G/nodes are a bipartition of G.
116 Parameters
117 ----------
118 G : NetworkX graph
120 nodes: list or container
121 Check if nodes are a one of a bipartite set.
123 Examples
124 --------
125 >>> from networkx.algorithms import bipartite
126 >>> G = nx.path_graph(4)
127 >>> X = set([1, 3])
128 >>> bipartite.is_bipartite_node_set(G, X)
129 True
131 Notes
132 -----
133 An exception is raised if the input nodes are not distinct, because in this
134 case some bipartite algorithms will yield incorrect results.
135 For connected graphs the bipartite sets are unique. This function handles
136 disconnected graphs.
137 """
138 S = set(nodes)
140 if len(S) < len(nodes):
141 # this should maybe just return False?
142 raise AmbiguousSolution(
143 "The input node set contains duplicates.\n"
144 "This may lead to incorrect results when using it in bipartite algorithms.\n"
145 "Consider using set(nodes) as the input"
146 )
148 for CC in (G.subgraph(c).copy() for c in connected_components(G)):
149 X, Y = sets(CC)
150 if not (
151 (X.issubset(S) and Y.isdisjoint(S)) or (Y.issubset(S) and X.isdisjoint(S))
152 ):
153 return False
154 return True
157@nx._dispatch
158def sets(G, top_nodes=None):
159 """Returns bipartite node sets of graph G.
161 Raises an exception if the graph is not bipartite or if the input
162 graph is disconnected and thus more than one valid solution exists.
163 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
164 for further details on how bipartite graphs are handled in NetworkX.
166 Parameters
167 ----------
168 G : NetworkX graph
170 top_nodes : container, optional
171 Container with all nodes in one bipartite node set. If not supplied
172 it will be computed. But if more than one solution exists an exception
173 will be raised.
175 Returns
176 -------
177 X : set
178 Nodes from one side of the bipartite graph.
179 Y : set
180 Nodes from the other side.
182 Raises
183 ------
184 AmbiguousSolution
185 Raised if the input bipartite graph is disconnected and no container
186 with all nodes in one bipartite set is provided. When determining
187 the nodes in each bipartite set more than one valid solution is
188 possible if the input graph is disconnected.
189 NetworkXError
190 Raised if the input graph is not bipartite.
192 Examples
193 --------
194 >>> from networkx.algorithms import bipartite
195 >>> G = nx.path_graph(4)
196 >>> X, Y = bipartite.sets(G)
197 >>> list(X)
198 [0, 2]
199 >>> list(Y)
200 [1, 3]
202 See Also
203 --------
204 color
206 """
207 if G.is_directed():
208 is_connected = nx.is_weakly_connected
209 else:
210 is_connected = nx.is_connected
211 if top_nodes is not None:
212 X = set(top_nodes)
213 Y = set(G) - X
214 else:
215 if not is_connected(G):
216 msg = "Disconnected graph: Ambiguous solution for bipartite sets."
217 raise nx.AmbiguousSolution(msg)
218 c = color(G)
219 X = {n for n, is_top in c.items() if is_top}
220 Y = {n for n, is_top in c.items() if not is_top}
221 return (X, Y)
224@nx._dispatch(graphs="B")
225def density(B, nodes):
226 """Returns density of bipartite graph B.
228 Parameters
229 ----------
230 B : NetworkX graph
232 nodes: list or container
233 Nodes in one node set of the bipartite graph.
235 Returns
236 -------
237 d : float
238 The bipartite density
240 Examples
241 --------
242 >>> from networkx.algorithms import bipartite
243 >>> G = nx.complete_bipartite_graph(3, 2)
244 >>> X = set([0, 1, 2])
245 >>> bipartite.density(G, X)
246 1.0
247 >>> Y = set([3, 4])
248 >>> bipartite.density(G, Y)
249 1.0
251 Notes
252 -----
253 The container of nodes passed as argument must contain all nodes
254 in one of the two bipartite node sets to avoid ambiguity in the
255 case of disconnected graphs.
256 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
257 for further details on how bipartite graphs are handled in NetworkX.
259 See Also
260 --------
261 color
262 """
263 n = len(B)
264 m = nx.number_of_edges(B)
265 nb = len(nodes)
266 nt = n - nb
267 if m == 0: # includes cases n==0 and n==1
268 d = 0.0
269 else:
270 if B.is_directed():
271 d = m / (2 * nb * nt)
272 else:
273 d = m / (nb * nt)
274 return d
277@nx._dispatch(graphs="B", edge_attrs="weight")
278def degrees(B, nodes, weight=None):
279 """Returns the degrees of the two node sets in the bipartite graph B.
281 Parameters
282 ----------
283 B : NetworkX graph
285 nodes: list or container
286 Nodes in one node set of the bipartite graph.
288 weight : string or None, optional (default=None)
289 The edge attribute that holds the numerical value used as a weight.
290 If None, then each edge has weight 1.
291 The degree is the sum of the edge weights adjacent to the node.
293 Returns
294 -------
295 (degX,degY) : tuple of dictionaries
296 The degrees of the two bipartite sets as dictionaries keyed by node.
298 Examples
299 --------
300 >>> from networkx.algorithms import bipartite
301 >>> G = nx.complete_bipartite_graph(3, 2)
302 >>> Y = set([3, 4])
303 >>> degX, degY = bipartite.degrees(G, Y)
304 >>> dict(degX)
305 {0: 2, 1: 2, 2: 2}
307 Notes
308 -----
309 The container of nodes passed as argument must contain all nodes
310 in one of the two bipartite node sets to avoid ambiguity in the
311 case of disconnected graphs.
312 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
313 for further details on how bipartite graphs are handled in NetworkX.
315 See Also
316 --------
317 color, density
318 """
319 bottom = set(nodes)
320 top = set(B) - bottom
321 return (B.degree(top, weight), B.degree(bottom, weight))