Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/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 import networkx as nx | |
4 from networkx.utils import not_implemented_for, arbitrary_element | |
5 from functools import partial | |
6 from itertools import chain | |
7 | |
8 | |
9 __all__ = ["min_edge_cover", "is_edge_cover"] | |
10 | |
11 | |
12 @not_implemented_for("directed") | |
13 @not_implemented_for("multigraph") | |
14 def min_edge_cover(G, matching_algorithm=None): | |
15 """Returns a set of edges which constitutes | |
16 the minimum edge cover of the graph. | |
17 | |
18 A smallest edge cover can be found in polynomial time by finding | |
19 a maximum matching and extending it greedily so that all nodes | |
20 are covered. | |
21 | |
22 Parameters | |
23 ---------- | |
24 G : NetworkX graph | |
25 An undirected bipartite graph. | |
26 | |
27 matching_algorithm : function | |
28 A function that returns a maximum cardinality matching in a | |
29 given bipartite graph. The function must take one input, the | |
30 graph ``G``, and return a dictionary mapping each node to its | |
31 mate. If not specified, | |
32 :func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching` | |
33 will be used. Other possibilities include | |
34 :func:`~networkx.algorithms.bipartite.matching.eppstein_matching`, | |
35 or matching algorithms in the | |
36 :mod:`networkx.algorithms.matching` module. | |
37 | |
38 Returns | |
39 ------- | |
40 min_cover : set | |
41 | |
42 It contains all the edges of minimum edge cover | |
43 in form of tuples. It contains both the edges `(u, v)` and `(v, u)` | |
44 for given nodes `u` and `v` among the edges of minimum edge cover. | |
45 | |
46 Notes | |
47 ----- | |
48 An edge cover of a graph is a set of edges such that every node of | |
49 the graph is incident to at least one edge of the set. | |
50 The minimum edge cover is an edge covering of smallest cardinality. | |
51 | |
52 Due to its implementation, the worst-case running time of this algorithm | |
53 is bounded by the worst-case running time of the function | |
54 ``matching_algorithm``. | |
55 | |
56 Minimum edge cover for bipartite graph can also be found using the | |
57 function present in :mod:`networkx.algorithms.bipartite.covering` | |
58 """ | |
59 if nx.number_of_isolates(G) > 0: | |
60 # ``min_cover`` does not exist as there is an isolated node | |
61 raise nx.NetworkXException( | |
62 "Graph has a node with no edge incident on it, " "so no edge cover exists." | |
63 ) | |
64 if matching_algorithm is None: | |
65 matching_algorithm = partial(nx.max_weight_matching, maxcardinality=True) | |
66 maximum_matching = matching_algorithm(G) | |
67 # ``min_cover`` is superset of ``maximum_matching`` | |
68 try: | |
69 min_cover = set( | |
70 maximum_matching.items() | |
71 ) # bipartite matching case returns dict | |
72 except AttributeError: | |
73 min_cover = maximum_matching | |
74 # iterate for uncovered nodes | |
75 uncovered_nodes = set(G) - {v for u, v in min_cover} - {u for u, v in min_cover} | |
76 for v in uncovered_nodes: | |
77 # Since `v` is uncovered, each edge incident to `v` will join it | |
78 # with a covered node (otherwise, if there were an edge joining | |
79 # uncovered nodes `u` and `v`, the maximum matching algorithm | |
80 # would have found it), so we can choose an arbitrary edge | |
81 # incident to `v`. (This applies only in a simple graph, not a | |
82 # multigraph.) | |
83 u = arbitrary_element(G[v]) | |
84 min_cover.add((u, v)) | |
85 min_cover.add((v, u)) | |
86 return min_cover | |
87 | |
88 | |
89 @not_implemented_for("directed") | |
90 def is_edge_cover(G, cover): | |
91 """Decides whether a set of edges is a valid edge cover of the graph. | |
92 | |
93 Given a set of edges, whether it is an edge covering can | |
94 be decided if we just check whether all nodes of the graph | |
95 has an edge from the set, incident on it. | |
96 | |
97 Parameters | |
98 ---------- | |
99 G : NetworkX graph | |
100 An undirected bipartite graph. | |
101 | |
102 cover : set | |
103 Set of edges to be checked. | |
104 | |
105 Returns | |
106 ------- | |
107 bool | |
108 Whether the set of edges is a valid edge cover of the graph. | |
109 | |
110 Notes | |
111 ----- | |
112 An edge cover of a graph is a set of edges such that every node of | |
113 the graph is incident to at least one edge of the set. | |
114 """ | |
115 return set(G) <= set(chain.from_iterable(cover)) |