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

1""" Provides a function for computing the extendability of a graph which is 

2undirected, simple, connected and bipartite and contains at least one perfect matching.""" 

3 

4 

5import networkx as nx 

6from networkx.utils import not_implemented_for 

7 

8__all__ = ["maximal_extendability"] 

9 

10 

11@not_implemented_for("directed") 

12@not_implemented_for("multigraph") 

13def maximal_extendability(G): 

14 """Computes the extendability of a graph. 

15 

16 The extendability of a graph is defined as the maximum $k$ for which `G` 

17 is $k$-extendable. Graph `G` is $k$-extendable if and only if `G` has a 

18 perfect matching and every set of $k$ independent edges can be extended 

19 to a perfect matching in `G`. 

20 

21 Parameters 

22 ---------- 

23 G : NetworkX Graph 

24 A fully-connected bipartite graph without self-loops 

25 

26 Returns 

27 ------- 

28 extendability : int 

29 

30 Raises 

31 ------ 

32 NetworkXError 

33 If the graph `G` is disconnected. 

34 If the graph `G` is not bipartite. 

35 If the graph `G` does not contain a perfect matching. 

36 If the residual graph of `G` is not strongly connected. 

37 

38 Notes 

39 ----- 

40 Definition: 

41 Let `G` be a simple, connected, undirected and bipartite graph with a perfect 

42 matching M and bipartition (U,V). The residual graph of `G`, denoted by $G_M$, 

43 is the graph obtained from G by directing the edges of M from V to U and the 

44 edges that do not belong to M from U to V. 

45 

46 Lemma([1]_): 

47 Let M be a perfect matching of `G`. `G` is $k$-extendable if and only if its residual 

48 graph $G_M$ is strongly connected and there are $k$ vertex-disjoint directed 

49 paths between every vertex of U and every vertex of V. 

50 

51 Assuming that input graph `G` is undirected, simple, connected, bipartite and contains 

52 a perfect matching M, this function constructs the residual graph $G_M$ of G and 

53 returns the minimum value among the maximum vertex-disjoint directed paths between 

54 every vertex of U and every vertex of V in $G_M$. By combining the definitions 

55 and the lemma, this value represents the extendability of the graph `G`. 

56 

57 Time complexity O($n^3$ $m^2$)) where $n$ is the number of vertices 

58 and $m$ is the number of edges. 

59 

60 References 

61 ---------- 

62 ..[1] "A polynomial algorithm for the extendability problem in bipartite graphs", 

63 J. Lakhal, L. Litzler, Information Processing Letters, 1998. 

64 ..[2] "On n-extendible graphs", M. D. Plummer, Discrete Mathematics, 31:201–210, 1980 

65 https://doi.org/10.1016/0012-365X(80)90037-0 

66 

67 """ 

68 if not nx.is_connected(G): 

69 raise nx.NetworkXError("Graph G is not connected") 

70 

71 if not nx.bipartite.is_bipartite(G): 

72 raise nx.NetworkXError("Graph G is not bipartite") 

73 

74 U, V = nx.bipartite.sets(G) 

75 

76 maximum_matching = nx.bipartite.hopcroft_karp_matching(G) 

77 

78 if not nx.is_perfect_matching(G, maximum_matching): 

79 raise nx.NetworkXError("Graph G does not contain a perfect matching") 

80 

81 # list of edges in perfect matching, directed from V to U 

82 pm = [(node, maximum_matching[node]) for node in V & maximum_matching.keys()] 

83 

84 # Direct all the edges of G, from V to U if in matching, else from U to V 

85 directed_edges = [ 

86 (x, y) if (x in V and (x, y) in pm) or (x in U and (y, x) not in pm) else (y, x) 

87 for x, y in G.edges 

88 ] 

89 

90 # Construct the residual graph of G 

91 residual_G = nx.DiGraph() 

92 residual_G.add_nodes_from(G) 

93 residual_G.add_edges_from(directed_edges) 

94 

95 if not nx.is_strongly_connected(residual_G): 

96 raise nx.NetworkXError("The residual graph of G is not strongly connected") 

97 

98 # For node-pairs between V & U, keep min of max number of node-disjoint paths 

99 # Variable $k$ stands for the extendability of graph G 

100 k = float("Inf") 

101 for u in U: 

102 for v in V: 

103 num_paths = sum(1 for _ in nx.node_disjoint_paths(residual_G, u, v)) 

104 k = k if k < num_paths else num_paths 

105 return k