Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (2.44 KB)

1
# Copyright 2014 "cheebee7i".
2
# Copyright 2014 "alexbrc".
3
# Copyright 2014 Jeffrey Finkelstein <jeffrey.finkelstein@gmail.com>.
4
"""Unit tests for the :mod:`networkx.generators.expanders` module.
5

6
"""
7
try:
8
    import scipy
9
    is_scipy_available = True
10
except:
11
    is_scipy_available = False
12

    
13
import networkx as nx
14
from networkx import adjacency_matrix
15
from networkx import number_of_nodes
16
from networkx.generators.expanders import chordal_cycle_graph
17
from networkx.generators.expanders import margulis_gabber_galil_graph
18

    
19
from nose import SkipTest
20
from nose.tools import assert_equal
21
from nose.tools import assert_less
22
from nose.tools import assert_raises
23
from nose.tools import assert_true
24

    
25

    
26
def test_margulis_gabber_galil_graph():
27
    try:
28
        # Scipy is required for conversion to an adjacency matrix.
29
        # We also use scipy for computing the eigenvalues,
30
        # but this second use could be done using only numpy.
31
        import numpy as np
32
        import scipy.linalg
33
        has_scipy = True
34
    except ImportError as e:
35
        has_scipy = False
36
    for n in 2, 3, 5, 6, 10:
37
        g = margulis_gabber_galil_graph(n)
38
        assert_equal(number_of_nodes(g), n * n)
39
        for node in g:
40
            assert_equal(g.degree(node), 8)
41
            assert_equal(len(node), 2)
42
            for i in node:
43
                assert_equal(int(i), i)
44
                assert_true(0 <= i < n)
45
        if has_scipy:
46
            # Eigenvalues are already sorted using the scipy eigvalsh,
47
            # but the implementation in numpy does not guarantee order.
48
            w = sorted(scipy.linalg.eigvalsh(adjacency_matrix(g).A))
49
            assert_less(w[-2], 5 * np.sqrt(2))
50

    
51

    
52
def test_chordal_cycle_graph():
53
    """Test for the :func:`networkx.chordal_cycle_graph` function."""
54
    if not is_scipy_available:
55
        raise SkipTest('SciPy is not available')
56
    primes = [3, 5, 7, 11]
57
    for p in primes:
58
        G = chordal_cycle_graph(p)
59
        assert_equal(len(G), p)
60
        # TODO The second largest eigenvalue should be smaller than a constant,
61
        # independent of the number of nodes in the graph:
62
        #
63
        #     eigs = sorted(scipy.linalg.eigvalsh(adjacency_matrix(G).A))
64
        #     assert_less(eigs[-2], ...)
65
        #
66

    
67

    
68
def test_margulis_gabber_galil_graph_badinput():
69
    assert_raises(nx.NetworkXError, margulis_gabber_galil_graph, 3,
70
                  nx.DiGraph())
71
    assert_raises(nx.NetworkXError, margulis_gabber_galil_graph, 3,
72
                  nx.Graph())