Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/bipartite/__init__.py: 100%

1r""" This module provides functions and operations for bipartite 

2graphs. 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 

4to use an spatial analogy referring to the two node sets as top and bottom nodes. 

5 

6The bipartite algorithms are not imported into the networkx namespace 

7at the top level so the easiest way to use them is with: 

8 

9>>> from networkx.algorithms import bipartite 

10 

11NetworkX does not have a custom bipartite graph class but the Graph() 

12or DiGraph() classes can be used to represent bipartite graphs. However, 

13you have to keep track of which set each node belongs to, and make 

14sure that there is no edge between nodes of the same set. The convention used 

15in NetworkX is to use a node attribute named `bipartite` with values 0 or 1 to 

16identify the sets each node belongs to. This convention is not enforced in 

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

18 

19For example: 

20 

21>>> B = nx.Graph() 

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

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

24>>> B.add_nodes_from(["a", "b", "c"], bipartite=1) 

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

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

27 

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

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

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

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

32If `B` is connected, you can find the two node sets using a two-coloring 

33algorithm: 

34 

35>>> nx.is_connected(B) 

36True 

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

38 

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

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

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

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

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

44Exception if the input graph for 

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

46is disconnected. 

47 

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

49 

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

51>>> bottom_nodes = set(B) - top_nodes 

52 

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

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

55 

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

570.5 

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

59 

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

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

62 

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

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

65>>> RB_bottom = set(RB) - RB_top 

66>>> list(RB_top) 

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

68>>> list(RB_bottom) 

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

70 

71For other bipartite graph generators see 

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

73 

74""" 

75 

76from networkx.algorithms.bipartite.basic import * 

77from networkx.algorithms.bipartite.centrality import * 

78from networkx.algorithms.bipartite.cluster import * 

79from networkx.algorithms.bipartite.covering import * 

80from networkx.algorithms.bipartite.edgelist import * 

81from networkx.algorithms.bipartite.matching import * 

82from networkx.algorithms.bipartite.matrix import * 

83from networkx.algorithms.bipartite.projection import * 

84from networkx.algorithms.bipartite.redundancy import * 

85from networkx.algorithms.bipartite.spectral import * 

86from networkx.algorithms.bipartite.generators import * 

87from networkx.algorithms.bipartite.extendability import *