ioftools / networkxMiCe / networkxmaster / networkx / algorithms / bipartite / __init__.py @ 5cef0f13
History  View  Annotate  Download (3.71 KB)
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.

5 

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:

8 

9 
>>> import networkx as nx

10 
>>> from networkx.algorithms import bipartite

11 

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. This convention is not enforced in

18 
the source code of bipartite functions, it's only a recommendation.

19 

20 
For example:

21 

22 
>>> B = nx.Graph()

23 
>>> # Add nodes with the node attribute "bipartite"

24 
>>> B.add_nodes_from([1, 2, 3, 4], bipartite=0)

25 
>>> B.add_nodes_from(['a', 'b', 'c'], bipartite=1)

26 
>>> # Add edges only between nodes of opposite node sets

27 
>>> B.add_edges_from([(1, 'a'), (1, 'b'), (2, 'b'), (2, 'c'), (3, 'c'), (4, 'a')])

28 

29 
Many algorithms of the bipartite module of NetworkX require, as an argument, a

30 
container with all the nodes that belong to one set, in addition to the bipartite

31 
graph `B`. The functions in the bipartite package do not check that the node set

32 
is actually correct nor that the input graph is actually bipartite.

33 
If `B` is connected, you can find the two node sets using a twocoloring

34 
algorithm:

35 

36 
>>> nx.is_connected(B)

37 
True

38 
>>> bottom_nodes, top_nodes = bipartite.sets(B)

39 

40 
However, if the input graph is not connected, there are more than one possible

41 
colorations. This is the reason why we require the user to pass a container

42 
with all nodes of one bipartite node set as an argument to most bipartite

43 
functions. In the face of ambiguity, we refuse the temptation to guess and

44 
raise an :exc:`AmbiguousSolution <networkx.AmbiguousSolution>`

45 
Exception if the input graph for

46 
:func:`bipartite.sets <networkx.algorithms.bipartite.basic.sets>`

47 
is disconnected.

48 

49 
Using the `bipartite` node attribute, you can easily get the two node sets:

50 

51 
>>> top_nodes = {n for n, d in B.nodes(data=True) if d['bipartite']==0}

52 
>>> bottom_nodes = set(B)  top_nodes

53 

54 
So you can easily use the bipartite algorithms that require, as an argument, a

55 
container with all nodes that belong to one node set:

56 

57 
>>> print(round(bipartite.density(B, bottom_nodes), 2))

58 
0.5

59 
>>> G = bipartite.projected_graph(B, top_nodes)

60 

61 
All bipartite graph generators in NetworkX build bipartite graphs with the

62 
`bipartite` node attribute. Thus, you can use the same approach:

63 

64 
>>> RB = bipartite.random_graph(5, 7, 0.2)

65 
>>> RB_top = {n for n, d in RB.nodes(data=True) if d['bipartite']==0}

66 
>>> RB_bottom = set(RB)  RB_top

67 
>>> list(RB_top)

68 
[0, 1, 2, 3, 4]

69 
>>> list(RB_bottom)

70 
[5, 6, 7, 8, 9, 10, 11]

71 

72 
For other bipartite graph generators see

73 
:mod:`Generators <networkx.algorithms.bipartite.generators>`.

74 

75 
"""

76  
77 
from networkx.algorithms.bipartite.basic import * 
78 
from networkx.algorithms.bipartite.centrality import * 
79 
from networkx.algorithms.bipartite.cluster import * 
80 
from networkx.algorithms.bipartite.covering import * 
81 
from networkx.algorithms.bipartite.edgelist import * 
82 
from networkx.algorithms.bipartite.matching import * 
83 
from networkx.algorithms.bipartite.matrix import * 
84 
from networkx.algorithms.bipartite.projection import * 
85 
from networkx.algorithms.bipartite.redundancy import * 
86 
from networkx.algorithms.bipartite.spectral import * 
87 
from networkx.algorithms.bipartite.generators import * 