ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_bridges.py @ 5cef0f13
History  View  Annotate  Download (2.4 KB)
1 
# test_bridges.py  unit tests for bridgefinding algorithms


2 
#

3 
# Copyright 20042019 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 bridgefinding 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 bridgefinding 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)
