Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.03 KB)

1
# Copyright (C) 2018
2
# Robert Gmyr <robert@gmyr.net>
3
# All rights reserved.
4
# BSD license.
5
"""Unit tests for the sparsifier computation functions."""
6
from nose.tools import *
7
import networkx as nx
8
from networkx.utils import py_random_state
9

    
10

    
11
_seed = 2
12

    
13

    
14
def _test_spanner(G, spanner, stretch, weight=None):
15
    """Test whether a spanner is valid.
16

17
    This function tests whether the given spanner is a subgraph of the
18
    given graph G with the same node set. It also tests for all shortest
19
    paths whether they adhere to the given stretch.
20

21
    Parameters
22
    ----------
23
    G : NetworkX graph
24
        The original graph for which the spanner was constructed.
25

26
    spanner : NetworkX graph
27
        The spanner to be tested.
28

29
    stretch : float
30
        The proclaimed stretch of the spanner.
31

32
    weight : object
33
        The edge attribute to use as distance.
34
    """
35
    # check node set
36
    assert set(G.nodes()) == set(spanner.nodes())
37

    
38
    # check edge set and weights
39
    for u, v in spanner.edges():
40
        assert G.has_edge(u, v)
41
        if weight:
42
            assert spanner[u][v][weight] == G[u][v][weight]
43

    
44
    # check connectivity and stretch
45
    original_length = dict(nx.shortest_path_length(G, weight=weight))
46
    spanner_length = dict(nx.shortest_path_length(spanner, weight=weight))
47
    for u in G.nodes():
48
        for v in G.nodes():
49
            if u in original_length and v in original_length[u]:
50
                assert spanner_length[u][v] <= stretch * original_length[u][v]
51

    
52

    
53
@py_random_state(1)
54
def _assign_random_weights(G, seed=None):
55
    """Assigns random weights to the edges of a graph.
56

57
    Parameters
58
    ----------
59

60
    G : NetworkX graph
61
        The original graph for which the spanner was constructed.
62

63
    seed : integer, random_state, or None (default)
64
        Indicator of random number generation state.
65
        See :ref:`Randomness<randomness>`.
66
    """
67
    for u, v in G.edges():
68
        G[u][v]['weight'] = seed.random()
69

    
70

    
71
def test_spanner_trivial():
72
    """Test a trivial spanner with stretch 1."""
73
    G = nx.complete_graph(20)
74
    spanner = nx.spanner(G, 1, seed=_seed)
75

    
76
    for u, v in G.edges:
77
        assert(spanner.has_edge(u, v))
78

    
79

    
80
def test_spanner_unweighted_complete_graph():
81
    """Test spanner construction on a complete unweighted graph."""
82
    G = nx.complete_graph(20)
83

    
84
    spanner = nx.spanner(G, 4, seed=_seed)
85
    _test_spanner(G, spanner, 4)
86

    
87
    spanner = nx.spanner(G, 10, seed=_seed)
88
    _test_spanner(G, spanner, 10)
89

    
90

    
91
def test_spanner_weighted_complete_graph():
92
    """Test spanner construction on a complete weighted graph."""
93
    G = nx.complete_graph(20)
94
    _assign_random_weights(G, seed=_seed)
95

    
96
    spanner = nx.spanner(G, 4, weight='weight', seed=_seed)
97
    _test_spanner(G, spanner, 4, weight='weight')
98

    
99
    spanner = nx.spanner(G, 10, weight='weight', seed=_seed)
100
    _test_spanner(G, spanner, 10, weight='weight')
101

    
102

    
103
def test_spanner_unweighted_gnp_graph():
104
    """Test spanner construction on an unweighted gnp graph."""
105
    G = nx.gnp_random_graph(20, 0.4, seed=_seed)
106

    
107
    spanner = nx.spanner(G, 4, seed=_seed)
108
    _test_spanner(G, spanner, 4)
109

    
110
    spanner = nx.spanner(G, 10, seed=_seed)
111
    _test_spanner(G, spanner, 10)
112

    
113

    
114
def test_spanner_weighted_gnp_graph():
115
    """Test spanner construction on an weighted gnp graph."""
116
    G = nx.gnp_random_graph(20, 0.4, seed=_seed)
117
    _assign_random_weights(G, seed=_seed)
118

    
119
    spanner = nx.spanner(G, 4, weight='weight', seed=_seed)
120
    _test_spanner(G, spanner, 4, weight='weight')
121

    
122
    spanner = nx.spanner(G, 10, weight='weight', seed=_seed)
123
    _test_spanner(G, spanner, 10, weight='weight')
124

    
125

    
126
def test_spanner_unweighted_disconnected_graph():
127
    """Test spanner construction on a disconnected graph."""
128
    G = nx.disjoint_union(nx.complete_graph(10), nx.complete_graph(10))
129

    
130
    spanner = nx.spanner(G, 4, seed=_seed)
131
    _test_spanner(G, spanner, 4)
132

    
133
    spanner = nx.spanner(G, 10, seed=_seed)
134
    _test_spanner(G, spanner, 10)
135

    
136

    
137
@raises(ValueError)
138
def test_spanner_invalid_stretch():
139
    """Check whether an invalid stretch is caught."""
140
    G = nx.empty_graph()
141
    nx.spanner(G, 0)