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-2019 NetworkX developers.
#    Nishant Nikhil <nishantiam@gmail.com>

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

from networkx.utils import not_implemented_for
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)