Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.37 KB)

1
# test_wiener.py - unit tests for the wiener module
2
#
3
# Copyright 2015 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 the :mod:`networkx.algorithms.wiener` module."""
10
from __future__ import division
11

    
12
from nose.tools import eq_
13

    
14
from networkx import complete_graph
15
from networkx import DiGraph
16
from networkx import empty_graph
17
from networkx import path_graph
18
from networkx import wiener_index
19

    
20

    
21
class TestWienerIndex(object):
22
    """Unit tests for computing the Wiener index of a graph."""
23

    
24
    def test_disconnected_graph(self):
25
        """Tests that the Wiener index of a disconnected graph is
26
        positive infinity.
27

28
        """
29
        eq_(wiener_index(empty_graph(2)), float('inf'))
30

    
31
    def test_directed(self):
32
        """Tests that each pair of nodes in the directed graph is
33
        counted once when computing the Wiener index.
34

35
        """
36
        G = complete_graph(3)
37
        H = DiGraph(G)
38
        eq_(2 * wiener_index(G), wiener_index(H))
39

    
40
    def test_complete_graph(self):
41
        """Tests that the Wiener index of the complete graph is simply
42
        the number of edges.
43

44
        """
45
        n = 10
46
        G = complete_graph(n)
47
        eq_(wiener_index(G), n * (n - 1) / 2)
48

    
49
    def test_path_graph(self):
50
        """Tests that the Wiener index of the path graph is correctly
51
        computed.
52

53
        """
54
        # In P_n, there are n - 1 pairs of vertices at distance one, n -
55
        # 2 pairs at distance two, n - 3 at distance three, ..., 1 at
56
        # distance n - 1, so the Wiener index should be
57
        #
58
        #     1 * (n - 1) + 2 * (n - 2) + ... + (n - 2) * 2 + (n - 1) * 1
59
        #
60
        # For example, in P_5,
61
        #
62
        #     1 * 4 + 2 * 3 + 3 * 2 + 4 * 1 = 2 (1 * 4 + 2 * 3)
63
        #
64
        # and in P_6,
65
        #
66
        #     1 * 5 + 2 * 4 + 3 * 3 + 4 * 2 + 5 * 1 = 2 (1 * 5 + 2 * 4) + 3 * 3
67
        #
68
        # assuming n is *odd*, this gives the formula
69
        #
70
        #     2 \sum_{i = 1}^{(n - 1) / 2} [i * (n - i)]
71
        #
72
        # assuming n is *even*, this gives the formula
73
        #
74
        #     2 \sum_{i = 1}^{n / 2} [i * (n - i)] - (n / 2) ** 2
75
        #
76
        n = 9
77
        G = path_graph(n)
78
        expected = 2 * sum(i * (n - i) for i in range(1, (n // 2) + 1))
79
        actual = wiener_index(G)
80
        eq_(expected, actual)