Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/approximation/matching.py @ 0:4f3585e2f14b draft default tip
"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) |