diff options
Diffstat (limited to 'lib/python2.7/site-packages/setoolsgui/networkx/algorithms/approximation/matching.py')
| -rw-r--r-- | lib/python2.7/site-packages/setoolsgui/networkx/algorithms/approximation/matching.py | 46 |
1 files changed, 0 insertions, 46 deletions
diff --git a/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/approximation/matching.py b/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/approximation/matching.py deleted file mode 100644 index 231d501..0000000 --- a/lib/python2.7/site-packages/setoolsgui/networkx/algorithms/approximation/matching.py +++ /dev/null @@ -1,46 +0,0 @@ -# -*- coding: utf-8 -*- -""" -************** -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. - -http://en.wikipedia.org/wiki/Matching_(graph_theory) -""" -# Copyright (C) 2011-2012 by -# Nicholas Mancuso <nick.mancuso@gmail.com> -# All rights reserved. -# BSD license. -import networkx as nx -__all__ = ["min_maximal_matching"] -__author__ = """Nicholas Mancuso (nick.mancuso@gmail.com)""" - -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) |