1
r""" This module provides functions and operations for bipartite
2
graphs. Bipartite graphs `B = (U, V, E)` have two node sets `U,V` and edges in
3
`E` that only connect nodes from opposite sets. It is common in the literature
4
to use an spatial analogy referring to the two node sets as top and bottom nodes.
6
The bipartite algorithms are not imported into the networkx namespace
7
at the top level so the easiest way to use them is with:
9
>>> import networkx as nx
10
>>> from networkx.algorithms import bipartite
12
NetworkX does not have a custom bipartite graph class but the Graph()
13
or DiGraph() classes can be used to represent bipartite graphs. However,
14
you have to keep track of which set each node belongs to, and make
15
sure that there is no edge between nodes of the same set. The convention used
16
in NetworkX is to use a node attribute named "bipartite" with values 0 or 1 to
17
identify the sets each node belongs to.
22
>>> B.add_nodes_from([1,2,3,4], bipartite=0) # Add the node attribute "bipartite"
23
>>> B.add_nodes_from(['a','b','c'], bipartite=1)
24
>>> B.add_edges_from([(1,'a'), (1,'b'), (2,'b'), (2,'c'), (3,'c'), (4,'a')])
26
Many algorithms of the bipartite module of NetworkX require, as an argument, a
27
container with all the nodes that belong to one set, in addition to the bipartite
28
graph `B`. If `B` is connected, you can find the node sets using a two-coloring
31
>>> nx.is_connected(B)
33
>>> bottom_nodes, top_nodes = bipartite.sets(B)
36
>>> list(bottom_nodes)
39
However, if the input graph is not connected, there are more than one possible
40
colorations. Thus, the following result is correct:
42
>>> B.remove_edge(2,'c')
43
>>> nx.is_connected(B)
45
>>> bottom_nodes, top_nodes = bipartite.sets(B)
48
>>> list(bottom_nodes)
51
Using the "bipartite" node attribute, you can easily get the two node sets:
53
>>> top_nodes = set(n for n,d in B.nodes(data=True) if d['bipartite']==0)
54
>>> bottom_nodes = set(B) - top_nodes
57
>>> list(bottom_nodes)
60
So you can easily use the bipartite algorithms that require, as an argument, a
61
container with all nodes that belong to one node set:
63
>>> print(round(bipartite.density(B, bottom_nodes),2))
65
>>> G = bipartite.projected_graph(B, top_nodes)
69
All bipartite graph generators in NetworkX build bipartite graphs with the
70
"bipartite" node attribute. Thus, you can use the same approach:
72
>>> RB = nx.bipartite_random_graph(5, 7, 0.2)
73
>>> nx.is_connected(RB)
75
>>> RB_top = set(n for n,d in RB.nodes(data=True) if d['bipartite']==0)
76
>>> RB_bottom = set(RB) - RB_top
80
[5, 6, 7, 8, 9, 10, 11]
82
For other bipartite graph generators see the bipartite section of
87
from networkx.algorithms.bipartite.basic import *
88
from networkx.algorithms.bipartite.centrality import *
89
from networkx.algorithms.bipartite.cluster import *
90
from networkx.algorithms.bipartite.projection import *
91
from networkx.algorithms.bipartite.redundancy import *
92
from networkx.algorithms.bipartite.spectral import *
added
removed
networkx/algorithms/bipartite/__init__.py
