## Mercurial > repos > shellac > sam_consensus_v3

### comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/matching.py @ 0:4f3585e2f14b draft default tip

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

author | shellac |
---|---|

date | Mon, 22 Mar 2021 18:12:50 +0000 |

parents | |

children |

comparison

equal
deleted
inserted
replaced

-1:000000000000 | 0:4f3585e2f14b |
---|---|

1 """ | |

2 ************** | |

3 Graph Matching | |

4 ************** | |

5 | |

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

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

8 | |

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

10 """ | |

11 import networkx as nx | |

12 | |

13 __all__ = ["min_maximal_matching"] | |

14 | |

15 | |

16 def min_maximal_matching(G): | |

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

18 matchings of the graph G, the smallest is returned. | |

19 | |

20 Parameters | |

21 ---------- | |

22 G : NetworkX graph | |

23 Undirected graph | |

24 | |

25 Returns | |

26 ------- | |

27 min_maximal_matching : set | |

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

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

30 Cardinality will be 2*OPT in the worst case. | |

31 | |

32 Notes | |

33 ----- | |

34 The algorithm computes an approximate solution fo the minimum maximal | |

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

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

37 | |

38 References | |

39 ---------- | |

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

41 """ | |

42 return nx.maximal_matching(G) |