Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / bipartite / tests / test_covering.py @ 5cef0f13

History | View | Annotate | Download (1.55 KB)

1
#    Copyright 2016-2019 NetworkX developers.
2
#    Copyright (C) 2016 by
3
#    Nishant Nikhil <nishantiam@gmail.com>
4
#    All rights reserved.
5
#    BSD license.
6

    
7
from nose.tools import assert_equal, assert_true
8
import networkx as nx
9
import networkx.algorithms.bipartite as bipartite
10

    
11

    
12
class TestMinEdgeCover:
13
    """Tests for :func:`networkx.algorithms.bipartite.min_edge_cover`"""
14

    
15
    def test_empty_graph(self):
16
        G = nx.Graph()
17
        assert_equal(bipartite.min_edge_cover(G), set())
18

    
19
    def test_graph_single_edge(self):
20
        G = nx.Graph()
21
        G.add_edge(0, 1)
22
        assert_equal(bipartite.min_edge_cover(G),
23
                     {(0, 1), (1, 0)})
24

    
25
    def test_bipartite_default(self):
26
        G = nx.Graph()
27
        G.add_nodes_from([1, 2, 3, 4], bipartite=0)
28
        G.add_nodes_from(['a', 'b', 'c'], bipartite=1)
29
        G.add_edges_from([(1, 'a'), (1, 'b'), (2, 'b'),
30
                          (2, 'c'), (3, 'c'), (4, 'a')])
31
        min_cover = bipartite.min_edge_cover(G)
32
        assert_true(nx.is_edge_cover(G, min_cover))
33
        assert_equal(len(min_cover), 8)
34

    
35
    def test_bipartite_explicit(self):
36
        G = nx.Graph()
37
        G.add_nodes_from([1, 2, 3, 4], bipartite=0)
38
        G.add_nodes_from(['a', 'b', 'c'], bipartite=1)
39
        G.add_edges_from([(1, 'a'), (1, 'b'), (2, 'b'),
40
                          (2, 'c'), (3, 'c'), (4, 'a')])
41
        min_cover = bipartite.min_edge_cover(G,
42
                                             bipartite.eppstein_matching)
43
        assert_true(nx.is_edge_cover(G, min_cover))
44
        assert_equal(len(min_cover), 8)