Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (4.71 KB)

1
from unittest import TestCase
2

    
3
from nose.tools import assert_equal
4
from nose.tools import assert_false
5
try:
6
    from nose.tools import assert_count_equal
7
except ImportError:
8
    from nose.tools import assert_items_equal as assert_count_equal
9
from nose.tools import assert_true
10
from nose.tools import raises
11

    
12
import networkx as nx
13
from networkx import is_eulerian, eulerian_circuit
14

    
15

    
16
class TestIsEulerian(TestCase):
17

    
18
    def test_is_eulerian(self):
19
        assert_true(is_eulerian(nx.complete_graph(5)))
20
        assert_true(is_eulerian(nx.complete_graph(7)))
21
        assert_true(is_eulerian(nx.hypercube_graph(4)))
22
        assert_true(is_eulerian(nx.hypercube_graph(6)))
23

    
24
        assert_false(is_eulerian(nx.complete_graph(4)))
25
        assert_false(is_eulerian(nx.complete_graph(6)))
26
        assert_false(is_eulerian(nx.hypercube_graph(3)))
27
        assert_false(is_eulerian(nx.hypercube_graph(5)))
28

    
29
        assert_false(is_eulerian(nx.petersen_graph()))
30
        assert_false(is_eulerian(nx.path_graph(4)))
31

    
32
    def test_is_eulerian2(self):
33
        # not connected
34
        G = nx.Graph()
35
        G.add_nodes_from([1, 2, 3])
36
        assert_false(is_eulerian(G))
37
        # not strongly connected
38
        G = nx.DiGraph()
39
        G.add_nodes_from([1, 2, 3])
40
        assert_false(is_eulerian(G))
41
        G = nx.MultiDiGraph()
42
        G.add_edge(1, 2)
43
        G.add_edge(2, 3)
44
        G.add_edge(2, 3)
45
        G.add_edge(3, 1)
46
        assert_false(is_eulerian(G))
47

    
48

    
49
class TestEulerianCircuit(TestCase):
50

    
51
    def test_eulerian_circuit_cycle(self):
52
        G = nx.cycle_graph(4)
53

    
54
        edges = list(eulerian_circuit(G, source=0))
55
        nodes = [u for u, v in edges]
56
        assert_equal(nodes, [0, 3, 2, 1])
57
        assert_equal(edges, [(0, 3), (3, 2), (2, 1), (1, 0)])
58

    
59
        edges = list(eulerian_circuit(G, source=1))
60
        nodes = [u for u, v in edges]
61
        assert_equal(nodes, [1, 2, 3, 0])
62
        assert_equal(edges, [(1, 2), (2, 3), (3, 0), (0, 1)])
63

    
64
        G = nx.complete_graph(3)
65

    
66
        edges = list(eulerian_circuit(G, source=0))
67
        nodes = [u for u, v in edges]
68
        assert_equal(nodes, [0, 2, 1])
69
        assert_equal(edges, [(0, 2), (2, 1), (1, 0)])
70

    
71
        edges = list(eulerian_circuit(G, source=1))
72
        nodes = [u for u, v in edges]
73
        assert_equal(nodes, [1, 2, 0])
74
        assert_equal(edges, [(1, 2), (2, 0), (0, 1)])
75

    
76
    def test_eulerian_circuit_digraph(self):
77
        G = nx.DiGraph()
78
        nx.add_cycle(G, [0, 1, 2, 3])
79

    
80
        edges = list(eulerian_circuit(G, source=0))
81
        nodes = [u for u, v in edges]
82
        assert_equal(nodes, [0, 1, 2, 3])
83
        assert_equal(edges, [(0, 1), (1, 2), (2, 3), (3, 0)])
84

    
85
        edges = list(eulerian_circuit(G, source=1))
86
        nodes = [u for u, v in edges]
87
        assert_equal(nodes, [1, 2, 3, 0])
88
        assert_equal(edges, [(1, 2), (2, 3), (3, 0), (0, 1)])
89

    
90
    def test_multigraph(self):
91
        G = nx.MultiGraph()
92
        nx.add_cycle(G, [0, 1, 2, 3])
93
        G.add_edge(1, 2)
94
        G.add_edge(1, 2)
95
        edges = list(eulerian_circuit(G, source=0))
96
        nodes = [u for u, v in edges]
97
        assert_equal(nodes, [0, 3, 2, 1, 2, 1])
98
        assert_equal(edges, [(0, 3), (3, 2), (2, 1), (1, 2), (2, 1), (1, 0)])
99

    
100
    def test_multigraph_with_keys(self):
101
        G = nx.MultiGraph()
102
        nx.add_cycle(G, [0, 1, 2, 3])
103
        G.add_edge(1, 2)
104
        G.add_edge(1, 2)
105
        edges = list(eulerian_circuit(G, source=0, keys=True))
106
        nodes = [u for u, v, k in edges]
107
        assert_equal(nodes, [0, 3, 2, 1, 2, 1])
108
        assert_equal(edges[:2], [(0, 3, 0), (3, 2, 0)])
109
        assert_count_equal(edges[2:5], [(2, 1, 0), (1, 2, 1), (2, 1, 2)])
110
        assert_equal(edges[5:], [(1, 0, 0)])
111

    
112
    @raises(nx.NetworkXError)
113
    def test_not_eulerian(self):
114
        f = list(eulerian_circuit(nx.complete_graph(4)))
115

    
116

    
117
class TestEulerize(TestCase):
118

    
119
    @raises(nx.NetworkXError)
120
    def test_disconnected(self):
121
        G = nx.from_edgelist([(0, 1), (2, 3)])
122
        nx.eulerize(G)
123

    
124
    @raises(nx.NetworkXPointlessConcept)
125
    def test_null_graph(self):
126
        nx.eulerize(nx.Graph())
127

    
128
    @raises(nx.NetworkXPointlessConcept)
129
    def test_null_multigraph(self):
130
        nx.eulerize(nx.MultiGraph())
131

    
132
    @raises(nx.NetworkXError)
133
    def test_on_empty_graph(self):
134
        nx.eulerize(nx.empty_graph(3))
135

    
136
    def test_on_eulerian(self):
137
        G = nx.cycle_graph(3)
138
        H = nx.eulerize(G)
139
        assert_true(nx.is_isomorphic(G, H))
140

    
141
    def test_on_eulerian_multigraph(self):
142
        G = nx.MultiGraph(nx.cycle_graph(3))
143
        G.add_edge(0, 1)
144
        H = nx.eulerize(G)
145
        assert_true(nx.is_eulerian(H))
146

    
147
    def test_on_complete_graph(self):
148
        G = nx.complete_graph(4)
149
        assert_true(nx.is_eulerian(nx.eulerize(G)))
150
        assert_true(nx.is_eulerian(nx.eulerize(nx.MultiGraph(G))))