Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.25 KB)

1
#!/usr/bin/env python
2
from nose.tools import *
3
import networkx as nx
4
from networkx.testing.utils import *
5

    
6

    
7
class TestCore:
8
    def setUp(self):
9
        # G is the example graph in Figure 1 from Batagelj and
10
        # Zaversnik's paper titled An O(m) Algorithm for Cores
11
        # Decomposition of Networks, 2003,
12
        # http://arXiv.org/abs/cs/0310049.  With nodes labeled as
13
        # shown, the 3-core is given by nodes 1-8, the 2-core by nodes
14
        # 9-16, the 1-core by nodes 17-20 and node 21 is in the
15
        # 0-core.
16
        t1 = nx.convert_node_labels_to_integers(nx.tetrahedral_graph(), 1)
17
        t2 = nx.convert_node_labels_to_integers(t1, 5)
18
        G = nx.union(t1, t2)
19
        G.add_edges_from([(3, 7), (2, 11), (11, 5), (11, 12), (5, 12),
20
                          (12, 19), (12, 18), (3, 9), (7, 9), (7, 10),
21
                          (9, 10), (9, 20), (17, 13), (13, 14), (14, 15),
22
                          (15, 16), (16, 13)])
23
        G.add_node(21)
24
        self.G = G
25

    
26
        # Create the graph H resulting from the degree sequence
27
        # [0, 1, 2, 2, 2, 2, 3] when using the Havel-Hakimi algorithm.
28

    
29
        degseq = [0, 1, 2, 2, 2, 2, 3]
30
        H = nx.havel_hakimi_graph(degseq)
31
        mapping = {6: 0, 0: 1, 4: 3, 5: 6, 3: 4, 1: 2, 2: 5}
32
        self.H = nx.relabel_nodes(H, mapping)
33

    
34
    def test_trivial(self):
35
        """Empty graph"""
36
        G = nx.Graph()
37
        assert_equal(nx.find_cores(G), {})
38

    
39
    def test_find_cores(self):
40
        core = nx.find_cores(self.G)
41
        nodes_by_core = [sorted([n for n in core if core[n] == val])
42
                         for val in range(4)]
43
        assert_nodes_equal(nodes_by_core[0], [21])
44
        assert_nodes_equal(nodes_by_core[1], [17, 18, 19, 20])
45
        assert_nodes_equal(nodes_by_core[2], [9, 10, 11, 12, 13, 14, 15, 16])
46
        assert_nodes_equal(nodes_by_core[3], [1, 2, 3, 4, 5, 6, 7, 8])
47

    
48
    def test_core_number(self):
49
        # smoke test real name
50
        cores = nx.core_number(self.G)
51

    
52
    def test_find_cores2(self):
53
        core = nx.find_cores(self.H)
54
        nodes_by_core = [sorted([n for n in core if core[n] == val])
55
                         for val in range(3)]
56
        assert_nodes_equal(nodes_by_core[0], [0])
57
        assert_nodes_equal(nodes_by_core[1], [1, 3])
58
        assert_nodes_equal(nodes_by_core[2], [2, 4, 5, 6])
59

    
60
    def test_directed_find_cores(self):
61
        '''core number had a bug for directed graphs found in issue #1959'''
62
        # small example where too timid edge removal can make cn[2] = 3
63
        G = nx.DiGraph()
64
        edges = [(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)]
65
        G.add_edges_from(edges)
66
        assert_equal(nx.core_number(G), {1: 2, 2: 2, 3: 2, 4: 2})
67
        # small example where too aggressive edge removal can make cn[2] = 2
68
        more_edges = [(1, 5), (3, 5), (4, 5), (3, 6), (4, 6), (5, 6)]
69
        G.add_edges_from(more_edges)
70
        assert_equal(nx.core_number(G), {1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3})
71

    
72
    def test_main_core(self):
73
        main_core_subgraph = nx.k_core(self.H)
74
        assert_equal(sorted(main_core_subgraph.nodes()), [2, 4, 5, 6])
75

    
76
    def test_k_core(self):
77
        # k=0
78
        k_core_subgraph = nx.k_core(self.H, k=0)
79
        assert_equal(sorted(k_core_subgraph.nodes()), sorted(self.H.nodes()))
80
        # k=1
81
        k_core_subgraph = nx.k_core(self.H, k=1)
82
        assert_equal(sorted(k_core_subgraph.nodes()), [1, 2, 3, 4, 5, 6])
83
        # k = 2
84
        k_core_subgraph = nx.k_core(self.H, k=2)
85
        assert_equal(sorted(k_core_subgraph.nodes()), [2, 4, 5, 6])
86

    
87
    def test_main_crust(self):
88
        main_crust_subgraph = nx.k_crust(self.H)
89
        assert_equal(sorted(main_crust_subgraph.nodes()), [0, 1, 3])
90

    
91
    def test_k_crust(self):
92
        # k = 0
93
        k_crust_subgraph = nx.k_crust(self.H, k=2)
94
        assert_equal(sorted(k_crust_subgraph.nodes()), sorted(self.H.nodes()))
95
        # k=1
96
        k_crust_subgraph = nx.k_crust(self.H, k=1)
97
        assert_equal(sorted(k_crust_subgraph.nodes()), [0, 1, 3])
98
        # k=2
99
        k_crust_subgraph = nx.k_crust(self.H, k=0)
100
        assert_equal(sorted(k_crust_subgraph.nodes()), [0])
101

    
102
    def test_main_shell(self):
103
        main_shell_subgraph = nx.k_shell(self.H)
104
        assert_equal(sorted(main_shell_subgraph.nodes()), [2, 4, 5, 6])
105

    
106
    def test_k_shell(self):
107
        # k=0
108
        k_shell_subgraph = nx.k_shell(self.H, k=2)
109
        assert_equal(sorted(k_shell_subgraph.nodes()), [2, 4, 5, 6])
110
        # k=1
111
        k_shell_subgraph = nx.k_shell(self.H, k=1)
112
        assert_equal(sorted(k_shell_subgraph.nodes()), [1, 3])
113
        # k=2
114
        k_shell_subgraph = nx.k_shell(self.H, k=0)
115
        assert_equal(sorted(k_shell_subgraph.nodes()), [0])
116

    
117
    def test_k_corona(self):
118
        # k=0
119
        k_corona_subgraph = nx.k_corona(self.H, k=2)
120
        assert_equal(sorted(k_corona_subgraph.nodes()), [2, 4, 5, 6])
121
        # k=1
122
        k_corona_subgraph = nx.k_corona(self.H, k=1)
123
        assert_equal(sorted(k_corona_subgraph.nodes()), [1])
124
        # k=2
125
        k_corona_subgraph = nx.k_corona(self.H, k=0)
126
        assert_equal(sorted(k_corona_subgraph.nodes()), [0])
127

    
128
    def test_k_truss(self):
129
        # k=-1
130
        k_truss_subgraph = nx.k_truss(self.G, -1)
131
        assert_equal(sorted(k_truss_subgraph.nodes()), list(range(1,21)))
132
        # k=0
133
        k_truss_subgraph = nx.k_truss(self.G, 0)
134
        assert_equal(sorted(k_truss_subgraph.nodes()), list(range(1,21)))
135
        # k=1
136
        k_truss_subgraph = nx.k_truss(self.G, 1)
137
        assert_equal(sorted(k_truss_subgraph.nodes()), list(range(1,13)))
138
        # k=2
139
        k_truss_subgraph = nx.k_truss(self.G, 2)
140
        assert_equal(sorted(k_truss_subgraph.nodes()), list(range(1,9)))
141
        # k=3
142
        k_truss_subgraph = nx.k_truss(self.G, 3)
143
        assert_equal(sorted(k_truss_subgraph.nodes()), [])
144

    
145
    def test_onion_layers(self):
146
        layers = nx.onion_layers(self.G)
147
        nodes_by_layer = [sorted([n for n in layers if layers[n] == val])
148
                          for val in range(1, 7)]
149
        assert_nodes_equal(nodes_by_layer[0], [21])
150
        assert_nodes_equal(nodes_by_layer[1], [17, 18, 19, 20])
151
        assert_nodes_equal(nodes_by_layer[2], [10, 12, 13, 14, 15, 16])
152
        assert_nodes_equal(nodes_by_layer[3], [9, 11])
153
        assert_nodes_equal(nodes_by_layer[4], [1, 2, 4, 5, 6, 8])
154
        assert_nodes_equal(nodes_by_layer[5], [3, 7])