Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2==========================
3Bipartite Graph Algorithms
4==========================
5"""
7import networkx as nx
8from networkx.algorithms.components import connected_components
9from networkx.exception import AmbiguousSolution
11__all__ = [
12 "is_bipartite",
13 "is_bipartite_node_set",
14 "color",
15 "sets",
16 "density",
17 "degrees",
18]
21@nx._dispatchable
22def color(G):
23 """Returns a two-coloring of the graph.
25 Raises an exception if the graph is not bipartite.
27 Parameters
28 ----------
29 G : NetworkX graph
31 Returns
32 -------
33 color : dictionary
34 A dictionary keyed by node with a 1 or 0 as data for each node color.
36 Raises
37 ------
38 NetworkXError
39 If the graph is not two-colorable.
41 Examples
42 --------
43 >>> G = nx.path_graph(4)
44 >>> c = nx.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, name="bipartite")
51 >>> G.nodes[0]["bipartite"]
52 1
53 >>> 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._dispatchable
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 >>> G = nx.path_graph(4)
97 >>> nx.is_bipartite(G)
98 True
99 >>> G = nx.cycle_graph(7)
100 >>> nx.is_bipartite(G)
101 False
103 See Also
104 --------
105 color, is_bipartite_node_set
106 """
107 try:
108 color(G)
109 return True
110 except nx.NetworkXError:
111 return False
114@nx._dispatchable
115def is_bipartite_node_set(G, nodes):
116 """Returns True if nodes and G/nodes are a bipartition of G.
118 Parameters
119 ----------
120 G : NetworkX graph
122 nodes: list or container
123 Check if nodes are a one of a bipartite set.
125 Examples
126 --------
127 >>> G = nx.path_graph(4)
128 >>> X = set([1, 3])
129 >>> nx.bipartite.is_bipartite_node_set(G, X)
130 True
132 Notes
133 -----
134 An exception is raised if the input nodes are not distinct, because in this
135 case some bipartite algorithms will yield incorrect results.
136 For connected graphs the bipartite sets are unique. This function handles
137 disconnected graphs.
138 """
139 S = set(nodes)
141 if len(S) < len(nodes):
142 # this should maybe just return False?
143 raise AmbiguousSolution(
144 "The input node set contains duplicates.\n"
145 "This may lead to incorrect results when using it in bipartite algorithms.\n"
146 "Consider using set(nodes) as the input"
147 )
149 for CC in (G.subgraph(c).copy() for c in connected_components(G)):
150 X, Y = sets(CC)
151 if not (
152 (X.issubset(S) and Y.isdisjoint(S)) or (Y.issubset(S) and X.isdisjoint(S))
153 ):
154 return False
155 return True
158@nx._dispatchable
159def sets(G, top_nodes=None):
160 """Returns bipartite node sets of graph G.
162 Raises an exception if the graph is not bipartite or if the input
163 graph is disconnected and thus more than one valid solution exists.
164 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
165 for further details on how bipartite graphs are handled in NetworkX.
167 Parameters
168 ----------
169 G : NetworkX graph
171 top_nodes : container, optional
172 Container with all nodes in one bipartite node set. If not supplied
173 it will be computed. But if more than one solution exists an exception
174 will be raised.
176 Returns
177 -------
178 X : set
179 Nodes from one side of the bipartite graph.
180 Y : set
181 Nodes from the other side.
183 Raises
184 ------
185 AmbiguousSolution
186 Raised if the input bipartite graph is disconnected and no container
187 with all nodes in one bipartite set is provided. When determining
188 the nodes in each bipartite set more than one valid solution is
189 possible if the input graph is disconnected.
190 NetworkXError
191 Raised if the input graph is not bipartite.
193 Examples
194 --------
195 >>> G = nx.path_graph(4)
196 >>> X, Y = nx.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._dispatchable(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 >>> G = nx.complete_bipartite_graph(3, 2)
243 >>> nx.bipartite.density(G, nodes={0, 1, 2})
244 1.0
245 >>> nx.bipartite.density(G, nodes={3, 4})
246 1.0
248 Notes
249 -----
250 The container of nodes passed as argument must contain all nodes
251 in one of the two bipartite node sets to avoid ambiguity in the
252 case of disconnected graphs.
253 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
254 for further details on how bipartite graphs are handled in NetworkX.
256 See Also
257 --------
258 color
259 """
260 n = len(B)
261 m = nx.number_of_edges(B)
262 nb = len(nodes)
263 nt = n - nb
264 if m == 0: # includes cases n==0 and n==1
265 d = 0.0
266 else:
267 if B.is_directed():
268 d = m / (2 * nb * nt)
269 else:
270 d = m / (nb * nt)
271 return d
274@nx._dispatchable(graphs="B", edge_attrs="weight")
275def degrees(B, nodes, weight=None):
276 """Returns the degrees of the two node sets in the bipartite graph B.
278 Parameters
279 ----------
280 B : NetworkX graph
282 nodes: list or container
283 Nodes in one node set of the bipartite graph.
285 weight : string or None, optional (default=None)
286 The edge attribute that holds the numerical value used as a weight.
287 If None, then each edge has weight 1.
288 The degree is the sum of the edge weights adjacent to the node.
290 Returns
291 -------
292 (degX,degY) : tuple of dictionaries
293 The degrees of the two bipartite sets as dictionaries keyed by node.
295 Examples
296 --------
297 >>> G = nx.complete_bipartite_graph(3, 2)
298 >>> degX, degY = nx.bipartite.degrees(G, nodes={3, 4})
299 >>> dict(degX)
300 {0: 2, 1: 2, 2: 2}
302 Notes
303 -----
304 The container of nodes passed as argument must contain all nodes
305 in one of the two bipartite node sets to avoid ambiguity in the
306 case of disconnected graphs.
307 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
308 for further details on how bipartite graphs are handled in NetworkX.
310 See Also
311 --------
312 color, density
313 """
314 bottom = set(nodes)
315 top = set(B) - bottom
316 return (B.degree(top, weight), B.degree(bottom, weight))