Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / bipartite / covering.py @ 5cef0f13

History | View | Annotate | Download (2.2 KB)

1
#    Copyright 2016-2019 NetworkX developers.
2
#    Copyright (C) 2016 by
3
#    Nishant Nikhil <nishantiam@gmail.com>
4
#    All rights reserved.
5
#    BSD license.
6

    
7
""" Functions related to graph covers."""
8

    
9
from networkx.utils import not_implemented_for
10
from networkx.algorithms.bipartite.matching import hopcroft_karp_matching
11
from networkx.algorithms.covering import min_edge_cover as _min_edge_cover
12

    
13
__all__ = ['min_edge_cover']
14

    
15

    
16
@not_implemented_for('directed')
17
@not_implemented_for('multigraph')
18
def min_edge_cover(G, matching_algorithm=None):
19
    """Returns a set of edges which constitutes
20
    the minimum edge cover of the graph.
21

22
    The smallest edge cover can be found in polynomial time by finding
23
    a maximum matching and extending it greedily so that all nodes
24
    are covered.
25

26
    Parameters
27
    ----------
28
    G : NetworkX graph
29
        An undirected bipartite graph.
30

31
    matching_algorithm : function
32
        A function that returns a maximum cardinality matching in a
33
        given bipartite graph. The function must take one input, the
34
        graph ``G``, and return a dictionary mapping each node to its
35
        mate. If not specified,
36
        :func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching`
37
        will be used. Other possibilities include
38
        :func:`~networkx.algorithms.bipartite.matching.eppstein_matching`,
39

40
    Returns
41
    -------
42
    set
43
        A set of the edges in a minimum edge cover of the graph, given as
44
        pairs of nodes. It contains both the edges `(u, v)` and `(v, u)`
45
        for given nodes `u` and `v` among the edges of minimum edge cover.
46

47
    Notes
48
    -----
49
    An edge cover of a graph is a set of edges such that every node of
50
    the graph is incident to at least one edge of the set.
51
    A minimum edge cover is an edge covering of smallest cardinality.
52

53
    Due to its implementation, the worst-case running time of this algorithm
54
    is bounded by the worst-case running time of the function
55
    ``matching_algorithm``.
56
    """
57
    if G.order() == 0:  # Special case for the empty graph
58
        return set()
59
    if matching_algorithm is None:
60
        matching_algorithm = hopcroft_karp_matching
61
    return _min_edge_cover(G, matching_algorithm=matching_algorithm)