Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.9 KB)

1
import networkx as nx
2
from nose.tools import *
3

    
4
import networkx.generators.line as line
5
from networkx.testing.utils import *
6

    
7

    
8
def test_node_func():
9
    # graph
10
    G = nx.Graph()
11
    G.add_edge(1, 2)
12
    nf = line._node_func(G)
13
    assert_equal(nf(1, 2), (1, 2))
14
    assert_equal(nf(2, 1), (1, 2))
15

    
16
    # multigraph
17
    G = nx.MultiGraph()
18
    G.add_edge(1, 2)
19
    G.add_edge(1, 2)
20
    nf = line._node_func(G)
21
    assert_equal(nf(1, 2, 0), (1, 2, 0))
22
    assert_equal(nf(2, 1, 0), (1, 2, 0))
23

    
24

    
25
def test_edge_func():
26
    # graph
27
    G = nx.Graph()
28
    G.add_edge(1, 2)
29
    G.add_edge(2, 3)
30
    ef = line._edge_func(G)
31
    expected = [(1, 2), (2, 3)]
32
    assert_edges_equal(ef(), expected)
33

    
34
    # digraph
35
    G = nx.MultiDiGraph()
36
    G.add_edge(1, 2)
37
    G.add_edge(2, 3)
38
    G.add_edge(2, 3)
39
    ef = line._edge_func(G)
40
    expected = [(1, 2, 0), (2, 3, 0), (2, 3, 1)]
41
    result = sorted(ef())
42
    assert_equal(expected, result)
43

    
44

    
45
def test_sorted_edge():
46
    assert_equal((1, 2), line._sorted_edge(1, 2))
47
    assert_equal((1, 2), line._sorted_edge(2, 1))
48

    
49

    
50
class TestGeneratorLine():
51
    def test_star(self):
52
        G = nx.star_graph(5)
53
        L = nx.line_graph(G)
54
        assert_true(nx.is_isomorphic(L, nx.complete_graph(5)))
55

    
56
    def test_path(self):
57
        G = nx.path_graph(5)
58
        L = nx.line_graph(G)
59
        assert_true(nx.is_isomorphic(L, nx.path_graph(4)))
60

    
61
    def test_cycle(self):
62
        G = nx.cycle_graph(5)
63
        L = nx.line_graph(G)
64
        assert_true(nx.is_isomorphic(L, G))
65

    
66
    def test_digraph1(self):
67
        G = nx.DiGraph()
68
        G.add_edges_from([(0, 1), (0, 2), (0, 3)])
69
        L = nx.line_graph(G)
70
        # no edge graph, but with nodes
71
        assert_equal(L.adj, {(0, 1): {}, (0, 2): {}, (0, 3): {}})
72

    
73
    def test_digraph2(self):
74
        G = nx.DiGraph()
75
        G.add_edges_from([(0, 1), (1, 2), (2, 3)])
76
        L = nx.line_graph(G)
77
        assert_edges_equal(L.edges(), [((0, 1), (1, 2)), ((1, 2), (2, 3))])
78

    
79
    def test_create1(self):
80
        G = nx.DiGraph()
81
        G.add_edges_from([(0, 1), (1, 2), (2, 3)])
82
        L = nx.line_graph(G, create_using=nx.Graph())
83
        assert_edges_equal(L.edges(), [((0, 1), (1, 2)), ((1, 2), (2, 3))])
84

    
85
    def test_create2(self):
86
        G = nx.Graph()
87
        G.add_edges_from([(0, 1), (1, 2), (2, 3)])
88
        L = nx.line_graph(G, create_using=nx.DiGraph())
89
        assert_edges_equal(L.edges(), [((0, 1), (1, 2)), ((1, 2), (2, 3))])
90

    
91

    
92
class TestGeneratorInverseLine():
93
    def test_example(self):
94
        G = nx.Graph()
95
        G_edges = [[1, 2], [1, 3], [1, 4], [1, 5], [2, 3], [2, 5], [2, 6],
96
                   [2, 7], [3, 4], [3, 5], [6, 7], [6, 8], [7, 8]]
97
        G.add_edges_from(G_edges)
98
        H = nx.inverse_line_graph(G)
99
        solution = nx.Graph()
100
        solution_edges = [('a', 'b'), ('a', 'c'), ('a', 'd'), ('a', 'e'),
101
                          ('c', 'd'), ('e', 'f'), ('e', 'g'), ('f', 'g')]
102
        solution.add_edges_from(solution_edges)
103
        assert_true(nx.is_isomorphic(H, solution))
104

    
105
    def test_example_2(self):
106
        G = nx.Graph()
107
        G_edges = [[1, 2], [1, 3], [2, 3],
108
                   [3, 4], [3, 5], [4, 5]]
109
        G.add_edges_from(G_edges)
110
        H = nx.inverse_line_graph(G)
111
        solution = nx.Graph()
112
        solution_edges = [('a', 'c'), ('b', 'c'), ('c', 'd'),
113
                          ('d', 'e'), ('d', 'f')]
114
        solution.add_edges_from(solution_edges)
115
        assert_true(nx.is_isomorphic(H, solution))
116

    
117
    def test_pair(self):
118
        G = nx.path_graph(2)
119
        H = nx.inverse_line_graph(G)
120
        solution = nx.path_graph(3)
121
        assert_true(nx.is_isomorphic(H, solution))
122

    
123
    def test_line(self):
124
        G = nx.path_graph(5)
125
        solution = nx.path_graph(6)
126
        H = nx.inverse_line_graph(G)
127
        assert_true(nx.is_isomorphic(H, solution))
128

    
129
    def test_triangle_graph(self):
130
        G = nx.complete_graph(3)
131
        H = nx.inverse_line_graph(G)
132
        alternative_solution = nx.Graph()
133
        alternative_solution.add_edges_from([[0, 1], [0, 2], [0, 3]])
134
        # there are two alternative inverse line graphs for this case
135
        # so long as we get one of them the test should pass
136
        assert_true(nx.is_isomorphic(H, G) or
137
                    nx.is_isomorphic(H, alternative_solution))
138

    
139
    def test_cycle(self):
140
        G = nx.cycle_graph(5)
141
        H = nx.inverse_line_graph(G)
142
        assert_true(nx.is_isomorphic(H, G))
143

    
144
    def test_empty(self):
145
        G = nx.Graph()
146
        assert_raises(nx.NetworkXError, nx.inverse_line_graph, G)
147

    
148
    def test_claw(self):
149
        # This is the simplest non-line graph
150
        G = nx.Graph()
151
        G_edges = [[0, 1], [0, 2], [0, 3]]
152
        G.add_edges_from(G_edges)
153
        assert_raises(nx.NetworkXError, nx.inverse_line_graph, G)
154

    
155
    def test_non_line_graph(self):
156
        # These are other non-line graphs
157
        G = nx.Graph()
158
        G_edges = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [1, 2],
159
                   [2, 3], [3, 4], [4, 5], [5, 1]]
160
        G.add_edges_from(G_edges)
161
        assert_raises(nx.NetworkXError, nx.inverse_line_graph, G)
162

    
163
        G = nx.Graph()
164
        G_edges = [[0, 1], [1, 2], [3, 4], [4, 5], [0, 3], [1, 3],
165
                   [1, 4], [2, 4], [2, 5]]
166
        G.add_edges_from(G_edges)
167
        assert_raises(nx.NetworkXError, nx.inverse_line_graph, G)
168

    
169
    def test_wrong_graph_type(self):
170
        G = nx.DiGraph()
171
        G_edges = [[0, 1], [0, 2], [0, 3]]
172
        G.add_edges_from(G_edges)
173
        assert_raises(nx.NetworkXNotImplemented, nx.inverse_line_graph, G)
174

    
175
        G = nx.MultiGraph()
176
        G_edges = [[0, 1], [0, 2], [0, 3]]
177
        G.add_edges_from(G_edges)
178
        assert_raises(nx.NetworkXNotImplemented, nx.inverse_line_graph, G)
179

    
180
    def test_line_inverse_line_complete(self):
181
        G = nx.complete_graph(10)
182
        H = nx.line_graph(G)
183
        J = nx.inverse_line_graph(H)
184
        assert_true(nx.is_isomorphic(G, J))
185

    
186
    def test_line_inverse_line_path(self):
187
        G = nx.path_graph(10)
188
        H = nx.line_graph(G)
189
        J = nx.inverse_line_graph(H)
190
        assert_true(nx.is_isomorphic(G, J))
191

    
192
    def test_line_inverse_line_hypercube(self):
193
        G = nx.hypercube_graph(5)
194
        H = nx.line_graph(G)
195
        J = nx.inverse_line_graph(H)
196
        assert_true(nx.is_isomorphic(G, J))
197

    
198
    def test_line_inverse_line_cycle(self):
199
        G = nx.cycle_graph(10)
200
        H = nx.line_graph(G)
201
        J = nx.inverse_line_graph(H)
202
        assert_true(nx.is_isomorphic(G, J))
203

    
204
    def test_line_inverse_line_star(self):
205
        G = nx.star_graph(20)
206
        H = nx.line_graph(G)
207
        J = nx.inverse_line_graph(H)
208
        assert_true(nx.is_isomorphic(G, J))
209

    
210
    def test_line_inverse_line_multipartite(self):
211
        G = nx.complete_multipartite_graph(3, 4, 5)
212
        H = nx.line_graph(G)
213
        J = nx.inverse_line_graph(H)
214
        assert_true(nx.is_isomorphic(G, J))
215

    
216
    def test_line_inverse_line_dgm(self):
217
        G = nx.dorogovtsev_goltsev_mendes_graph(4)
218
        H = nx.line_graph(G)
219
        J = nx.inverse_line_graph(H)
220
        assert_true(nx.is_isomorphic(G, J))