Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/bipartite/covering.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ Functions related to graph covers.""" | |
2 | |
3 from networkx.utils import not_implemented_for | |
4 from networkx.algorithms.bipartite.matching import hopcroft_karp_matching | |
5 from networkx.algorithms.covering import min_edge_cover as _min_edge_cover | |
6 | |
7 __all__ = ["min_edge_cover"] | |
8 | |
9 | |
10 @not_implemented_for("directed") | |
11 @not_implemented_for("multigraph") | |
12 def min_edge_cover(G, matching_algorithm=None): | |
13 """Returns a set of edges which constitutes | |
14 the minimum edge cover of the graph. | |
15 | |
16 The smallest edge cover can be found in polynomial time by finding | |
17 a maximum matching and extending it greedily so that all nodes | |
18 are covered. | |
19 | |
20 Parameters | |
21 ---------- | |
22 G : NetworkX graph | |
23 An undirected bipartite graph. | |
24 | |
25 matching_algorithm : function | |
26 A function that returns a maximum cardinality matching in a | |
27 given bipartite graph. The function must take one input, the | |
28 graph ``G``, and return a dictionary mapping each node to its | |
29 mate. If not specified, | |
30 :func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching` | |
31 will be used. Other possibilities include | |
32 :func:`~networkx.algorithms.bipartite.matching.eppstein_matching`, | |
33 | |
34 Returns | |
35 ------- | |
36 set | |
37 A set of the edges in a minimum edge cover of the graph, given as | |
38 pairs of nodes. It contains both the edges `(u, v)` and `(v, u)` | |
39 for given nodes `u` and `v` among the edges of minimum edge cover. | |
40 | |
41 Notes | |
42 ----- | |
43 An edge cover of a graph is a set of edges such that every node of | |
44 the graph is incident to at least one edge of the set. | |
45 A minimum edge cover is an edge covering of smallest cardinality. | |
46 | |
47 Due to its implementation, the worst-case running time of this algorithm | |
48 is bounded by the worst-case running time of the function | |
49 ``matching_algorithm``. | |
50 """ | |
51 if G.order() == 0: # Special case for the empty graph | |
52 return set() | |
53 if matching_algorithm is None: | |
54 matching_algorithm = hopcroft_karp_matching | |
55 return _min_edge_cover(G, matching_algorithm=matching_algorithm) |