Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (3.17 KB)

1
from nose.tools import assert_raises, raises
2
import networkx as nx
3
from networkx.algorithms.approximation.steinertree import metric_closure
4
from networkx.algorithms.approximation.steinertree import steiner_tree
5
from networkx.testing.utils import assert_edges_equal
6

    
7

    
8
class TestSteinerTree:
9
    def setUp(self):
10
        G = nx.Graph()
11
        G.add_edge(1, 2, weight=10)
12
        G.add_edge(2, 3, weight=10)
13
        G.add_edge(3, 4, weight=10)
14
        G.add_edge(4, 5, weight=10)
15
        G.add_edge(5, 6, weight=10)
16
        G.add_edge(2, 7, weight=1)
17
        G.add_edge(7, 5, weight=1)
18
        self.G = G
19
        self.term_nodes = [1, 2, 3, 4, 5]
20

    
21
    def test_connected_metric_closure(self):
22
        G = self.G.copy()
23
        G.add_node(100)
24
        assert_raises(nx.NetworkXError, metric_closure, G)
25

    
26
    def test_metric_closure(self):
27
        M = metric_closure(self.G)
28
        mc = [(1, 2, {'distance': 10, 'path': [1, 2]}),
29
              (1, 3, {'distance': 20, 'path': [1, 2, 3]}),
30
              (1, 4, {'distance': 22, 'path': [1, 2, 7, 5, 4]}),
31
              (1, 5, {'distance': 12, 'path': [1, 2, 7, 5]}),
32
              (1, 6, {'distance': 22, 'path': [1, 2, 7, 5, 6]}),
33
              (1, 7, {'distance': 11, 'path': [1, 2, 7]}),
34
              (2, 3, {'distance': 10, 'path': [2, 3]}),
35
              (2, 4, {'distance': 12, 'path': [2, 7, 5, 4]}),
36
              (2, 5, {'distance': 2, 'path': [2, 7, 5]}),
37
              (2, 6, {'distance': 12, 'path': [2, 7, 5, 6]}),
38
              (2, 7, {'distance': 1, 'path': [2, 7]}),
39
              (3, 4, {'distance': 10, 'path': [3, 4]}),
40
              (3, 5, {'distance': 12, 'path': [3, 2, 7, 5]}),
41
              (3, 6, {'distance': 22, 'path': [3, 2, 7, 5, 6]}),
42
              (3, 7, {'distance': 11, 'path': [3, 2, 7]}),
43
              (4, 5, {'distance': 10, 'path': [4, 5]}),
44
              (4, 6, {'distance': 20, 'path': [4, 5, 6]}),
45
              (4, 7, {'distance': 11, 'path': [4, 5, 7]}),
46
              (5, 6, {'distance': 10, 'path': [5, 6]}),
47
              (5, 7, {'distance': 1, 'path': [5, 7]}),
48
              (6, 7, {'distance': 11, 'path': [6, 5, 7]})]
49
        assert_edges_equal(list(M.edges(data=True)), mc)
50

    
51
    def test_steiner_tree(self):
52
        S = steiner_tree(self.G, self.term_nodes)
53
        expected_steiner_tree = [(1, 2, {'weight': 10}),
54
                                 (2, 3, {'weight': 10}),
55
                                 (2, 7, {'weight': 1}),
56
                                 (3, 4, {'weight': 10}),
57
                                 (5, 7, {'weight': 1})]
58
        assert_edges_equal(list(S.edges(data=True)), expected_steiner_tree)
59

    
60
    @raises(nx.NetworkXNotImplemented)
61
    def test_multigraph_steiner_tree(self):
62
        G = nx.MultiGraph()
63
        G.add_edges_from([
64
            (1, 2, 0, {'weight': 1}),
65
            (2, 3, 0, {'weight': 999}),
66
            (2, 3, 1, {'weight': 1}),
67
            (3, 4, 0, {'weight': 1}),
68
            (3, 5, 0, {'weight': 1})
69
        ])
70
        terminal_nodes = [2, 4, 5]
71
        expected_edges = [
72
            (2, 3, 1, {'weight': 1}),  # edge with key 1 has lower weight
73
            (3, 4, 0, {'weight': 1}),
74
            (3, 5, 0, {'weight': 1})
75
        ]
76
        # not implemented
77
        T = steiner_tree(G, terminal_nodes)