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

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/env/lib/python3.9/site-packages/networkx/algorithms/approximation/matching.py	Mon Mar 22 18:12:50 2021 +0000
@@ -0,0 +1,42 @@
+"""
+**************
+Graph Matching
+**************
+
+Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent
+edges; that is, no two edges share a common vertex.
+
+`Wikipedia: Matching <https://en.wikipedia.org/wiki/Matching_(graph_theory)>`_
+"""
+import networkx as nx
+
+__all__ = ["min_maximal_matching"]
+
+
+def min_maximal_matching(G):
+    r"""Returns the minimum maximal matching of G. That is, out of all maximal
+    matchings of the graph G, the smallest is returned.
+
+    Parameters
+    ----------
+    G : NetworkX graph
+      Undirected graph
+
+    Returns
+    -------
+    min_maximal_matching : set
+      Returns a set of edges such that no two edges share a common endpoint
+      and every edge not in the set shares some common endpoint in the set.
+      Cardinality will be 2*OPT in the worst case.
+
+    Notes
+    -----
+    The algorithm computes an approximate solution fo the minimum maximal
+    cardinality matching problem. The solution is no more than 2 * OPT in size.
+    Runtime is $O(|E|)$.
+
+    References
+    ----------
+    .. [1] Vazirani, Vijay Approximation Algorithms (2001)
+    """
+    return nx.maximal_matching(G)