1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
""" Functions related to graph covers."""
from functools import partial
from itertools import chain
import networkx as nx
from networkx.utils import arbitrary_element, not_implemented_for
__all__ = ["min_edge_cover", "is_edge_cover"]
@not_implemented_for("directed")
@not_implemented_for("multigraph")
def min_edge_cover(G, matching_algorithm=None):
"""Returns the min cardinality edge cover of the graph as a set of edges.
A smallest edge cover can be found in polynomial time by finding
a maximum matching and extending it greedily so that all nodes
are covered. This function follows that process. A maximum matching
algorithm can be specified for the first step of the algorithm.
The resulting set may return a set with one 2-tuple for each edge,
(the usual case) or with both 2-tuples `(u, v)` and `(v, u)` for
each edge. The latter is only done when a bipartite matching algorithm
is specified as `matching_algorithm`.
Parameters
----------
G : NetworkX graph
An undirected graph.
matching_algorithm : function
A function that returns a maximum cardinality matching for `G`.
The function must take one input, the graph `G`, and return
either a set of edges (with only one direction for the pair of nodes)
or a dictionary mapping each node to its mate. If not specified,
:func:`~networkx.algorithms.matching.max_weight_matching` is used.
Common bipartite matching functions include
:func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching`
or
:func:`~networkx.algorithms.bipartite.matching.eppstein_matching`.
Returns
-------
min_cover : set
A set of the edges in a minimum edge cover in the form of tuples.
It contains only one of the equivalent 2-tuples `(u, v)` and `(v, u)`
for each edge. If a bipartite method is used to compute the matching,
the returned set contains both the 2-tuples `(u, v)` and `(v, u)`
for each edge of a minimum edge cover.
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> sorted(nx.min_edge_cover(G))
[(2, 1), (3, 0)]
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.
The 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``.
Minimum edge cover for `G` can also be found using the `min_edge_covering`
function in :mod:`networkx.algorithms.bipartite.covering` which is
simply this function with a default matching algorithm of
:func:`~networkx.algorithms.bipartite.matching.hopcraft_karp_matching`
"""
if len(G) == 0:
return set()
if nx.number_of_isolates(G) > 0:
# ``min_cover`` does not exist as there is an isolated node
raise nx.NetworkXException(
"Graph has a node with no edge incident on it, " "so no edge cover exists."
)
if matching_algorithm is None:
matching_algorithm = partial(nx.max_weight_matching, maxcardinality=True)
maximum_matching = matching_algorithm(G)
# ``min_cover`` is superset of ``maximum_matching``
try:
# bipartite matching algs return dict so convert if needed
min_cover = set(maximum_matching.items())
bipartite_cover = True
except AttributeError:
min_cover = maximum_matching
bipartite_cover = False
# iterate for uncovered nodes
uncovered_nodes = set(G) - {v for u, v in min_cover} - {u for u, v in min_cover}
for v in uncovered_nodes:
# Since `v` is uncovered, each edge incident to `v` will join it
# with a covered node (otherwise, if there were an edge joining
# uncovered nodes `u` and `v`, the maximum matching algorithm
# would have found it), so we can choose an arbitrary edge
# incident to `v`. (This applies only in a simple graph, not a
# multigraph.)
u = arbitrary_element(G[v])
min_cover.add((u, v))
if bipartite_cover:
min_cover.add((v, u))
return min_cover
@not_implemented_for("directed")
def is_edge_cover(G, cover):
"""Decides whether a set of edges is a valid edge cover of the graph.
Given a set of edges, whether it is an edge covering can
be decided if we just check whether all nodes of the graph
has an edge from the set, incident on it.
Parameters
----------
G : NetworkX graph
An undirected bipartite graph.
cover : set
Set of edges to be checked.
Returns
-------
bool
Whether the set of edges is a valid edge cover of the graph.
Examples
--------
>>> G = nx.Graph([(0, 1), (0, 2), (0, 3), (1, 2), (1, 3)])
>>> cover = {(2, 1), (3, 0)}
>>> nx.is_edge_cover(G, cover)
True
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.
"""
return set(G) <= set(chain.from_iterable(cover))
|
