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 >>> from networkx.algorithms import bipartite
44 >>> G = nx.path_graph(4)
45 >>> c = bipartite.color(G)
46 >>> print(c)
47 {0: 1, 1: 0, 2: 1, 3: 0}
49 You can use this to set a node attribute indicating the bipartite set:
51 >>> nx.set_node_attributes(G, c, "bipartite")
52 >>> print(G.nodes[0]["bipartite"])
53 1
54 >>> print(G.nodes[1]["bipartite"])
55 0
56 """
57 if G.is_directed():
58 import itertools
60 def neighbors(v):
61 return itertools.chain.from_iterable([G.predecessors(v), G.successors(v)])
63 else:
64 neighbors = G.neighbors
66 color = {}
67 for n in G: # handle disconnected graphs
68 if n in color or len(G[n]) == 0: # skip isolates
69 continue
70 queue = [n]
71 color[n] = 1 # nodes seen with color (1 or 0)
72 while queue:
73 v = queue.pop()
74 c = 1 - color[v] # opposite color of node v
75 for w in neighbors(v):
76 if w in color:
77 if color[w] == color[v]:
78 raise nx.NetworkXError("Graph is not bipartite.")
79 else:
80 color[w] = c
81 queue.append(w)
82 # color isolates with 0
83 color.update(dict.fromkeys(nx.isolates(G), 0))
84 return color
87@nx._dispatchable
88def is_bipartite(G):
89 """Returns True if graph G is bipartite, False if not.
91 Parameters
92 ----------
93 G : NetworkX graph
95 Examples
96 --------
97 >>> from networkx.algorithms import bipartite
98 >>> G = nx.path_graph(4)
99 >>> print(bipartite.is_bipartite(G))
100 True
102 See Also
103 --------
104 color, is_bipartite_node_set
105 """
106 try:
107 color(G)
108 return True
109 except nx.NetworkXError:
110 return False
113@nx._dispatchable
114def is_bipartite_node_set(G, nodes):
115 """Returns True if nodes and G/nodes are a bipartition of G.
117 Parameters
118 ----------
119 G : NetworkX graph
121 nodes: list or container
122 Check if nodes are a one of a bipartite set.
124 Examples
125 --------
126 >>> from networkx.algorithms import bipartite
127 >>> G = nx.path_graph(4)
128 >>> X = set([1, 3])
129 >>> 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 >>> from networkx.algorithms import bipartite
196 >>> G = nx.path_graph(4)
197 >>> X, Y = bipartite.sets(G)
198 >>> list(X)
199 [0, 2]
200 >>> list(Y)
201 [1, 3]
203 See Also
204 --------
205 color
207 """
208 if G.is_directed():
209 is_connected = nx.is_weakly_connected
210 else:
211 is_connected = nx.is_connected
212 if top_nodes is not None:
213 X = set(top_nodes)
214 Y = set(G) - X
215 else:
216 if not is_connected(G):
217 msg = "Disconnected graph: Ambiguous solution for bipartite sets."
218 raise nx.AmbiguousSolution(msg)
219 c = color(G)
220 X = {n for n, is_top in c.items() if is_top}
221 Y = {n for n, is_top in c.items() if not is_top}
222 return (X, Y)
225@nx._dispatchable(graphs="B")
226def density(B, nodes):
227 """Returns density of bipartite graph B.
229 Parameters
230 ----------
231 B : NetworkX graph
233 nodes: list or container
234 Nodes in one node set of the bipartite graph.
236 Returns
237 -------
238 d : float
239 The bipartite density
241 Examples
242 --------
243 >>> from networkx.algorithms import bipartite
244 >>> G = nx.complete_bipartite_graph(3, 2)
245 >>> X = set([0, 1, 2])
246 >>> bipartite.density(G, X)
247 1.0
248 >>> Y = set([3, 4])
249 >>> bipartite.density(G, Y)
250 1.0
252 Notes
253 -----
254 The container of nodes passed as argument must contain all nodes
255 in one of the two bipartite node sets to avoid ambiguity in the
256 case of disconnected graphs.
257 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
258 for further details on how bipartite graphs are handled in NetworkX.
260 See Also
261 --------
262 color
263 """
264 n = len(B)
265 m = nx.number_of_edges(B)
266 nb = len(nodes)
267 nt = n - nb
268 if m == 0: # includes cases n==0 and n==1
269 d = 0.0
270 else:
271 if B.is_directed():
272 d = m / (2 * nb * nt)
273 else:
274 d = m / (nb * nt)
275 return d
278@nx._dispatchable(graphs="B", edge_attrs="weight")
279def degrees(B, nodes, weight=None):
280 """Returns the degrees of the two node sets in the bipartite graph B.
282 Parameters
283 ----------
284 B : NetworkX graph
286 nodes: list or container
287 Nodes in one node set of the bipartite graph.
289 weight : string or None, optional (default=None)
290 The edge attribute that holds the numerical value used as a weight.
291 If None, then each edge has weight 1.
292 The degree is the sum of the edge weights adjacent to the node.
294 Returns
295 -------
296 (degX,degY) : tuple of dictionaries
297 The degrees of the two bipartite sets as dictionaries keyed by node.
299 Examples
300 --------
301 >>> from networkx.algorithms import bipartite
302 >>> G = nx.complete_bipartite_graph(3, 2)
303 >>> Y = set([3, 4])
304 >>> degX, degY = bipartite.degrees(G, Y)
305 >>> dict(degX)
306 {0: 2, 1: 2, 2: 2}
308 Notes
309 -----
310 The container of nodes passed as argument must contain all nodes
311 in one of the two bipartite node sets to avoid ambiguity in the
312 case of disconnected graphs.
313 See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
314 for further details on how bipartite graphs are handled in NetworkX.
316 See Also
317 --------
318 color, density
319 """
320 bottom = set(nodes)
321 top = set(B) - bottom
322 return (B.degree(top, weight), B.degree(bottom, weight))