Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.algorithms.bipartite.covering

#    Copyright 2016-2017 NetworkX developers.
#    Copyright (C) 2016 by
#    Nishant Nikhil <nishantiam@gmail.com>
#    All rights reserved.
#    BSD license.

""" Functions related to graph covers."""

import networkx as nx
from networkx.utils import not_implemented_for, arbitrary_element
from networkx.algorithms.bipartite.matching import hopcroft_karp_matching
from networkx.algorithms.covering import min_edge_cover as _min_edge_cover

__all__ = ['min_edge_cover']


[docs]@not_implemented_for('directed') @not_implemented_for('multigraph') def min_edge_cover(G, matching_algorithm=None): """Returns a set of edges which constitutes the minimum edge cover of the graph. The smallest edge cover can be found in polynomial time by finding a maximum matching and extending it greedily so that all nodes are covered. Parameters ---------- G : NetworkX graph An undirected bipartite graph. matching_algorithm : function A function that returns a maximum cardinality matching in a given bipartite graph. The function must take one input, the graph ``G``, and return a dictionary mapping each node to its mate. If not specified, :func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching` will be used. Other possibilities include :func:`~networkx.algorithms.bipartite.matching.eppstein_matching`, Returns ------- set A set of the edges in a minimum edge cover of the graph, given as pairs of nodes. It contains both the edges `(u, v)` and `(v, u)` for given nodes `u` and `v` among the edges of minimum edge cover. Notes ----- An edge cover of a graph is a set of edges such that every node of the graph is incident to at least one edge of the set. A minimum edge cover is an edge covering of smallest cardinality. Due to its implementation, the worst-case running time of this algorithm is bounded by the worst-case running time of the function ``matching_algorithm``. """ if G.order() == 0: # Special case for the empty graph return set() if matching_algorithm is None: matching_algorithm = hopcroft_karp_matching return _min_edge_cover(G, matching_algorithm=matching_algorithm)