Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/approximation/matching.py: 80%

1""" 

2************** 

3Graph Matching 

4************** 

5 

6Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent 

7edges; that is, no two edges share a common vertex. 

8 

9`Wikipedia: Matching <https://en.wikipedia.org/wiki/Matching_(graph_theory)>`_ 

10""" 

11import networkx as nx 

12 

13__all__ = ["min_maximal_matching"] 

14 

15 

16@nx._dispatch 

17def min_maximal_matching(G): 

18 r"""Returns the minimum maximal matching of G. That is, out of all maximal 

19 matchings of the graph G, the smallest is returned. 

20 

21 Parameters 

22 ---------- 

23 G : NetworkX graph 

24 Undirected graph 

25 

26 Returns 

27 ------- 

28 min_maximal_matching : set 

29 Returns a set of edges such that no two edges share a common endpoint 

30 and every edge not in the set shares some common endpoint in the set. 

31 Cardinality will be 2*OPT in the worst case. 

32 

33 Notes 

34 ----- 

35 The algorithm computes an approximate solution for the minimum maximal 

36 cardinality matching problem. The solution is no more than 2 * OPT in size. 

37 Runtime is $O(|E|)$. 

38 

39 References 

40 ---------- 

41 .. [1] Vazirani, Vijay Approximation Algorithms (2001) 

42 """ 

43 return nx.maximal_matching(G)