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

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

2 

3import networkx as nx 

4from networkx.algorithms.bipartite.matching import hopcroft_karp_matching 

5from networkx.algorithms.covering import min_edge_cover as _min_edge_cover 

6from networkx.utils import not_implemented_for 

7 

8__all__ = ["min_edge_cover"] 

9 

10 

11@not_implemented_for("directed") 

12@not_implemented_for("multigraph") 

13@nx._dispatch(name="bipartite_min_edge_cover") 

14def min_edge_cover(G, matching_algorithm=None): 

15 """Returns a set of edges which constitutes 

16 the minimum edge cover of the graph. 

17 

18 The 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. 

21 

22 Parameters 

23 ---------- 

24 G : NetworkX graph 

25 An undirected bipartite graph. 

26 

27 matching_algorithm : function 

28 A function that returns a maximum cardinality matching in a 

29 given bipartite graph. The function must take one input, the 

30 graph ``G``, and return a dictionary mapping each node to its 

31 mate. If not specified, 

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

33 will be used. Other possibilities include 

34 :func:`~networkx.algorithms.bipartite.matching.eppstein_matching`, 

35 

36 Returns 

37 ------- 

38 set 

39 A set of the edges in a minimum edge cover of the graph, given as 

40 pairs of nodes. It contains both the edges `(u, v)` and `(v, u)` 

41 for given nodes `u` and `v` among the edges of minimum edge cover. 

42 

43 Notes 

44 ----- 

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

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

47 A minimum edge cover is an edge covering of smallest cardinality. 

48 

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

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

51 ``matching_algorithm``. 

52 """ 

53 if G.order() == 0: # Special case for the empty graph 

54 return set() 

55 if matching_algorithm is None: 

56 matching_algorithm = hopcroft_karp_matching 

57 return _min_edge_cover(G, matching_algorithm=matching_algorithm)