ioftools / networkxMiCe / networkxmaster / networkx / algorithms / bipartite / covering.py @ 5cef0f13
History  View  Annotate  Download (2.2 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 
from networkx.utils import not_implemented_for 
10 
from networkx.algorithms.bipartite.matching import hopcroft_karp_matching 
11 
from networkx.algorithms.covering import min_edge_cover as _min_edge_cover 
12  
13 
__all__ = ['min_edge_cover']

14  
15  
16 
@not_implemented_for('directed') 
17 
@not_implemented_for('multigraph') 
18 
def min_edge_cover(G, matching_algorithm=None): 
19 
"""Returns a set of edges which constitutes

20 
the minimum edge cover of the graph.

21 

22 
The smallest edge cover can be found in polynomial time by finding

23 
a maximum matching and extending it greedily so that all nodes

24 
are covered.

25 

26 
Parameters

27 


28 
G : NetworkX graph

29 
An undirected bipartite graph.

30 

31 
matching_algorithm : function

32 
A function that returns a maximum cardinality matching in a

33 
given bipartite graph. The function must take one input, the

34 
graph ``G``, and return a dictionary mapping each node to its

35 
mate. If not specified,

36 
:func:`~networkx.algorithms.bipartite.matching.hopcroft_karp_matching`

37 
will be used. Other possibilities include

38 
:func:`~networkx.algorithms.bipartite.matching.eppstein_matching`,

39 

40 
Returns

41 


42 
set

43 
A set of the edges in a minimum edge cover of the graph, given as

44 
pairs of nodes. It contains both the edges `(u, v)` and `(v, u)`

45 
for given nodes `u` and `v` among the edges of minimum edge cover.

46 

47 
Notes

48 


49 
An edge cover of a graph is a set of edges such that every node of

50 
the graph is incident to at least one edge of the set.

51 
A minimum edge cover is an edge covering of smallest cardinality.

52 

53 
Due to its implementation, the worstcase running time of this algorithm

54 
is bounded by the worstcase running time of the function

55 
``matching_algorithm``.

56 
"""

57 
if G.order() == 0: # Special case for the empty graph 
58 
return set() 
59 
if matching_algorithm is None: 
60 
matching_algorithm = hopcroft_karp_matching 
61 
return _min_edge_cover(G, matching_algorithm=matching_algorithm)
