Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.19 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
import networkx as nx
10
from networkx.utils import not_implemented_for, arbitrary_element
11
from functools import partial
12
from itertools import chain
13

    
14

    
15
__all__ = ['min_edge_cover', 'is_edge_cover']
16

    
17

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

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

28
    Parameters
29
    ----------
30
    G : NetworkX graph
31
        An undirected bipartite graph.
32

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

44
    Returns
45
    -------
46
    min_cover : set
47

48
        It contains all the edges of minimum edge cover
49
        in form of tuples. It contains both the edges `(u, v)` and `(v, u)`
50
        for given nodes `u` and `v` among the edges of minimum edge cover.
51

52
    Notes
53
    -----
54
    An edge cover of a graph is a set of edges such that every node of
55
    the graph is incident to at least one edge of the set.
56
    The minimum edge cover is an edge covering of smallest cardinality.
57

58
    Due to its implementation, the worst-case running time of this algorithm
59
    is bounded by the worst-case running time of the function
60
    ``matching_algorithm``.
61

62
    Minimum edge cover for bipartite graph can also be found using the
63
    function present in :mod:`networkx.algorithms.bipartite.covering`
64
    """
65
    if nx.number_of_isolates(G) > 0:
66
        # ``min_cover`` does not exist as there is an isolated node
67
        raise nx.NetworkXException(
68
            "Graph has a node with no edge incident on it, "
69
            "so no edge cover exists.")
70
    if matching_algorithm is None:
71
        matching_algorithm = partial(nx.max_weight_matching,
72
                                     maxcardinality=True)
73
    maximum_matching = matching_algorithm(G)
74
    # ``min_cover`` is superset of ``maximum_matching``
75
    try:
76
        min_cover = set(maximum_matching.items())  # bipartite matching case returns dict
77
    except AttributeError:
78
        min_cover = maximum_matching
79
    # iterate for uncovered nodes
80
    uncovered_nodes = set(G) - {v for u, v in min_cover} - {u for u, v in min_cover}
81
    for v in uncovered_nodes:
82
        # Since `v` is uncovered, each edge incident to `v` will join it
83
        # with a covered node (otherwise, if there were an edge joining
84
        # uncovered nodes `u` and `v`, the maximum matching algorithm
85
        # would have found it), so we can choose an arbitrary edge
86
        # incident to `v`. (This applies only in a simple graph, not a
87
        # multigraph.)
88
        u = arbitrary_element(G[v])
89
        min_cover.add((u, v))
90
        min_cover.add((v, u))
91
    return min_cover
92

    
93

    
94
@not_implemented_for('directed')
95
def is_edge_cover(G, cover):
96
    """Decides whether a set of edges is a valid edge cover of the graph.
97

98
    Given a set of edges, whether it is an edge covering can
99
    be decided if we just check whether all nodes of the graph
100
    has an edge from the set, incident on it.
101

102
    Parameters
103
    ----------
104
    G : NetworkX graph
105
        An undirected bipartite graph.
106

107
    cover : set
108
        Set of edges to be checked.
109

110
    Returns
111
    -------
112
    bool
113
        Whether the set of edges is a valid edge cover of the graph.
114

115
    Notes
116
    -----
117
    An edge cover of a graph is a set of edges such that every node of
118
    the graph is incident to at least one edge of the set.
119
    """
120
    return set(G) <= set(chain.from_iterable(cover))