Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/covering.py: 36%

1""" Functions related to graph covers.""" 

2 

3from functools import partial 

4from itertools import chain 

5 

6import networkx as nx 

7from networkx.utils import arbitrary_element, not_implemented_for 

8 

9__all__ = ["min_edge_cover", "is_edge_cover"] 

10 

11 

12@not_implemented_for("directed") 

13@not_implemented_for("multigraph") 

14@nx._dispatch 

15def min_edge_cover(G, matching_algorithm=None): 

16 """Returns the min cardinality edge cover of the graph as a set of edges. 

17 

18 A smallest edge cover can be found in polynomial time by finding 

19 a maximum matching and extending it greedily so that all nodes 

20 are covered. This function follows that process. A maximum matching 

21 algorithm can be specified for the first step of the algorithm. 

22 The resulting set may return a set with one 2-tuple for each edge, 

23 (the usual case) or with both 2-tuples `(u, v)` and `(v, u)` for 

24 each edge. The latter is only done when a bipartite matching algorithm 

25 is specified as `matching_algorithm`. 

26 

27 Parameters 

28 ---------- 

29 G : NetworkX graph 

30 An undirected graph. 

31 

32 matching_algorithm : function 

33 A function that returns a maximum cardinality matching for `G`. 

34 The function must take one input, the graph `G`, and return 

35 either a set of edges (with only one direction for the pair of nodes) 

36 or a dictionary mapping each node to its mate. If not specified, 

37 :func:`~networkx.algorithms.matching.max_weight_matching` is used. 

38 Common bipartite matching functions include 

39 :func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching` 

40 or 

41 :func:`~networkx.algorithms.bipartite.matching.eppstein_matching`. 

42 

43 Returns 

44 ------- 

45 min_cover : set 

46 

47 A set of the edges in a minimum edge cover in the form of tuples. 

48 It contains only one of the equivalent 2-tuples `(u, v)` and `(v, u)` 

49 for each edge. If a bipartite method is used to compute the matching, 

50 the returned set contains both the 2-tuples `(u, v)` and `(v, u)` 

51 for each edge of a minimum edge cover. 

52 

53 Examples 

54 -------- 

55 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)]) 

56 >>> sorted(nx.min_edge_cover(G)) 

57 [(2, 1), (3, 0)] 

58 

59 Notes 

60 ----- 

61 An edge cover of a graph is a set of edges such that every node of 

62 the graph is incident to at least one edge of the set. 

63 The minimum edge cover is an edge covering of smallest cardinality. 

64 

65 Due to its implementation, the worst-case running time of this algorithm 

66 is bounded by the worst-case running time of the function 

67 ``matching_algorithm``. 

68 

69 Minimum edge cover for `G` can also be found using the `min_edge_covering` 

70 function in :mod:`networkx.algorithms.bipartite.covering` which is 

71 simply this function with a default matching algorithm of 

72 :func:`~networkx.algorithms.bipartite.matching.hopcraft_karp_matching` 

73 """ 

74 if len(G) == 0: 

75 return set() 

76 if nx.number_of_isolates(G) > 0: 

77 # ``min_cover`` does not exist as there is an isolated node 

78 raise nx.NetworkXException( 

79 "Graph has a node with no edge incident on it, " "so no edge cover exists." 

80 ) 

81 if matching_algorithm is None: 

82 matching_algorithm = partial(nx.max_weight_matching, maxcardinality=True) 

83 maximum_matching = matching_algorithm(G) 

84 # ``min_cover`` is superset of ``maximum_matching`` 

85 try: 

86 # bipartite matching algs return dict so convert if needed 

87 min_cover = set(maximum_matching.items()) 

88 bipartite_cover = True 

89 except AttributeError: 

90 min_cover = maximum_matching 

91 bipartite_cover = False 

92 # iterate for uncovered nodes 

93 uncovered_nodes = set(G) - {v for u, v in min_cover} - {u for u, v in min_cover} 

94 for v in uncovered_nodes: 

95 # Since `v` is uncovered, each edge incident to `v` will join it 

96 # with a covered node (otherwise, if there were an edge joining 

97 # uncovered nodes `u` and `v`, the maximum matching algorithm 

98 # would have found it), so we can choose an arbitrary edge 

99 # incident to `v`. (This applies only in a simple graph, not a 

100 # multigraph.) 

101 u = arbitrary_element(G[v]) 

102 min_cover.add((u, v)) 

103 if bipartite_cover: 

104 min_cover.add((v, u)) 

105 return min_cover 

106 

107 

108@not_implemented_for("directed") 

109@nx._dispatch 

110def is_edge_cover(G, cover): 

111 """Decides whether a set of edges is a valid edge cover of the graph. 

112 

113 Given a set of edges, whether it is an edge covering can 

114 be decided if we just check whether all nodes of the graph 

115 has an edge from the set, incident on it. 

116 

117 Parameters 

118 ---------- 

119 G : NetworkX graph 

120 An undirected bipartite graph. 

121 

122 cover : set 

123 Set of edges to be checked. 

124 

125 Returns 

126 ------- 

127 bool 

128 Whether the set of edges is a valid edge cover of the graph. 

129 

130 Examples 

131 -------- 

132 >>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)]) 

133 >>> cover = {(2, 1), (3, 0)} 

134 >>> nx.is_edge_cover(G, cover) 

135 True 

136 

137 Notes 

138 ----- 

139 An edge cover of a graph is a set of edges such that every node of 

140 the graph is incident to at least one edge of the set. 

141 """ 

142 return set(G) <= set(chain.from_iterable(cover))