Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / tests / test_harary_graph.py @ 5cef0f13

History | View | Annotate | Download (5.17 KB)

1
"""Unit tests for the :mod:`networkx.generators.harary_graph` module.
2
"""
3

    
4
from nose.tools import assert_equal
5
from nose.tools import assert_true
6
from nose.tools import assert_raises
7

    
8
import networkx as nx
9
from networkx import *
10
from networkx.generators.harary_graph import hnm_harary_graph
11
from networkx.generators.harary_graph import hkn_harary_graph
12
from networkx.algorithms.isomorphism.isomorph import is_isomorphic
13
from networkx.testing import assert_edges_equal
14
from networkx.testing import assert_nodes_equal
15

    
16

    
17
class TestHararyGraph:
18
    """
19
        Suppose n nodes, m >= n-1 edges, d = 2m // n, r = 2m % n
20
    """
21
    def test_hnm_harary_graph(self):
22
        # When d is even and r = 0, the hnm_harary_graph(n,m) is
23
        # the circulant_graph(n, list(range(1,d/2+1)))
24
        for (n, m) in [(5, 5), (6, 12), (7, 14)]:
25
            G1 = hnm_harary_graph(n, m)
26
            d = 2*m // n
27
            G2 = circulant_graph(n, list(range(1, d//2 + 1)))
28
            assert_true(is_isomorphic(G1, G2))
29

    
30
        # When d is even and r > 0, the hnm_harary_graph(n,m) is
31
        # the circulant_graph(n, list(range(1,d/2+1)))
32
        # with r edges added arbitrarily
33
        for (n, m) in [(5, 7), (6, 13), (7, 16)]:
34
            G1 = hnm_harary_graph(n, m)
35
            d = 2*m // n
36
            G2 = circulant_graph(n, list(range(1, d//2 + 1)))
37
            assert_true(set(G2.edges) < set(G1.edges))
38
            assert_equal(G1.number_of_edges(), m)
39

    
40
        # When d is odd and n is even and r = 0, the hnm_harary_graph(n,m)
41
        # is the circulant_graph(n, list(range(1,(d+1)/2) plus [n//2])
42
        for (n, m) in [(6, 9), (8, 12), (10, 15)]:
43
            G1 = hnm_harary_graph(n, m)
44
            d = 2*m // n
45
            L = list(range(1, (d+1)//2))
46
            L.append(n//2)
47
            G2 = circulant_graph(n, L)
48
            assert_true(is_isomorphic(G1, G2))
49

    
50
        # When d is odd and n is even and r > 0, the hnm_harary_graph(n,m)
51
        # is the circulant_graph(n, list(range(1,(d+1)/2) plus [n//2])
52
        # with r edges added arbitrarily
53
        for (n, m) in [(6, 10), (8, 13), (10, 17)]:
54
            G1 = hnm_harary_graph(n, m)
55
            d = 2*m // n
56
            L = list(range(1, (d+1)//2))
57
            L.append(n//2)
58
            G2 = circulant_graph(n, L)
59
            assert_true(set(G2.edges) < set(G1.edges))
60
            assert_equal(G1.number_of_edges(), m)
61

    
62
        # When d is odd and n is odd, the hnm_harary_graph(n,m) is
63
        # the circulant_graph(n, list(range(1,(d+1)/2))
64
        # with m - n*(d-1)/2 edges added arbitrarily
65
        for (n, m) in [(5, 4), (7, 12), (9, 14)]:
66
            G1 = hnm_harary_graph(n, m)
67
            d = 2*m // n
68
            L = list(range(1, (d+1)//2))
69
            G2 = circulant_graph(n, L)
70
            assert_true(set(G2.edges) < set(G1.edges))
71
            assert_equal(G1.number_of_edges(), m)
72

    
73
        # Raise NetworkXError if n<1
74
        n = 0
75
        m = 0
76
        assert_raises(networkx.exception.NetworkXError, hnm_harary_graph, n, m)
77

    
78
        # Raise NetworkXError if m < n-1
79
        n = 6
80
        m = 4
81
        assert_raises(networkx.exception.NetworkXError, hnm_harary_graph, n, m)
82

    
83
        # Raise NetworkXError if m > n(n-1)/2
84
        n = 6
85
        m = 16
86
        assert_raises(networkx.exception.NetworkXError, hnm_harary_graph, n, m)
87

    
88
    """
89
        Suppose connectivity k, number of nodes n
90
    """
91
    def test_hkn_harary_graph(self):
92
        # When k == 1, the hkn_harary_graph(k,n) is
93
        # the path_graph(n)
94
        for (k, n) in [(1, 6), (1, 7)]:
95
            G1 = hkn_harary_graph(k, n)
96
            G2 = path_graph(n)
97
            assert_true(is_isomorphic(G1, G2))
98

    
99
        # When k is even, the hkn_harary_graph(k,n) is
100
        # the circulant_graph(n, list(range(1,k/2+1)))
101
        for (k, n) in [(2, 6), (2, 7), (4, 6), (4, 7)]:
102
            G1 = hkn_harary_graph(k, n)
103
            G2 = circulant_graph(n, list(range(1, k//2 + 1)))
104
            assert_true(is_isomorphic(G1, G2))
105

    
106
        # When k is odd and n is even, the hkn_harary_graph(k,n) is
107
        # the circulant_graph(n, list(range(1,(k+1)/2)) plus [n/2])
108
        for (k, n) in [(3, 6), (5, 8), (7, 10)]:
109
            G1 = hkn_harary_graph(k, n)
110
            L = list(range(1, (k+1)//2))
111
            L.append(n//2)
112
            G2 = circulant_graph(n, L)
113
            assert_true(is_isomorphic(G1, G2))
114

    
115
        # When k is odd and n is odd, the hkn_harary_graph(k,n) is
116
        # the circulant_graph(n, list(range(1,(k+1)/2))) with
117
        # n//2+1 edges added between node i and node i+n//2+1
118
        for (k, n) in [(3, 5), (5, 9), (7, 11)]:
119
            G1 = hkn_harary_graph(k, n)
120
            G2 = circulant_graph(n, list(range(1, (k+1)//2)))
121
            eSet1 = set(G1.edges)
122
            eSet2 = set(G2.edges)
123
            eSet3 = set()
124
            half = n // 2
125
            for i in range(0, half+1):
126
                # add half+1 edges between i and i+half
127
                eSet3.add((i, (i+half) % n))
128
            assert_equal(eSet1, eSet2 | eSet3)
129

    
130
        # Raise NetworkXError if k<1
131
        k = 0
132
        n = 0
133
        assert_raises(networkx.exception.NetworkXError, hkn_harary_graph, k, n)
134

    
135
        # Raise NetworkXError if n<k+1
136
        k = 6
137
        n = 6
138
        assert_raises(networkx.exception.NetworkXError, hkn_harary_graph, k, n)