Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.4 KB)

1
# test_bridges.py - unit tests for bridge-finding algorithms
2
#
3
# Copyright 2004-2019 NetworkX developers.
4
#
5
# This file is part of NetworkX.
6
#
7
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
8
# information.
9
"""Unit tests for bridge-finding algorithms."""
10
from unittest import TestCase
11
from nose.tools import assert_equal, assert_in
12

    
13
import networkx as nx
14

    
15

    
16
class TestBridges(TestCase):
17
    """Unit tests for the bridge-finding function."""
18

    
19
    def test_single_bridge(self):
20
        edges = [
21
            # DFS tree edges.
22
            (1, 2), (2, 3), (3, 4), (3, 5), (5, 6), (6, 7), (7, 8), (5, 9),
23
            (9, 10),
24
            # Nontree edges.
25
            (1, 3), (1, 4), (2, 5), (5, 10), (6, 8)
26
        ]
27
        G = nx.Graph(edges)
28
        source = 1
29
        bridges = list(nx.bridges(G, source))
30
        self.assertEqual(bridges, [(5, 6)])
31

    
32
    def test_barbell_graph(self):
33
        # The (3, 0) barbell graph has two triangles joined by a single edge.
34
        G = nx.barbell_graph(3, 0)
35
        source = 0
36
        bridges = list(nx.bridges(G, source))
37
        self.assertEqual(bridges, [(2, 3)])
38

    
39

    
40
class TestLocalBridges(TestCase):
41
    """Unit tests for the local_bridge function."""
42

    
43
    def setUp(self):
44
        self.BB = nx.barbell_graph(4, 0)
45
        self.square = nx.cycle_graph(4)
46
        self.tri = nx.cycle_graph(3)
47

    
48
    def test_nospan(self):
49
        expected = {(3, 4), (4, 3)}
50
        assert_in(next(nx.local_bridges(self.BB, with_span=False)), expected)
51
        assert_equal(set(nx.local_bridges(self.square, with_span=False)), self.square.edges)
52
        assert_equal(list(nx.local_bridges(self.tri, with_span=False)), [])
53

    
54
    def test_no_weight(self):
55
        inf = float('inf')
56
        expected = {(3, 4, inf), (4, 3, inf)}
57
        assert_in(next(nx.local_bridges(self.BB)), expected)
58
        expected = {(u, v, 3) for u, v, in self.square.edges}
59
        assert_equal(set(nx.local_bridges(self.square)), expected)
60
        assert_equal(list(nx.local_bridges(self.tri)), [])
61

    
62
    def test_weight(self):
63
        inf = float('inf')
64
        G = self.square.copy()
65

    
66
        G.edges[1, 2]['weight'] = 2
67
        expected = {(u, v, 5 - wt) for u, v, wt in G.edges(data='weight', default=1)}
68
        assert_equal(set(nx.local_bridges(G, weight='weight')), expected)
69

    
70
        expected = {(u, v, 6) for u, v in G.edges}
71
        lb = nx.local_bridges(G, weight=lambda u, v, d: 2)
72
        assert_equal(set(lb), expected)