ioftools / networkxMiCe / networkxmaster / networkx / algorithms / covering.py @ 5cef0f13
History  View  Annotate  Download (4.19 KB)
1 
# Copyright 20162019 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 worstcase running time of this algorithm

59 
is bounded by the worstcase 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)) 