from unittest import TestCase

from nose.tools import assert_equal
from nose.tools import assert_false
try:
    from nose.tools import assert_count_equal
except ImportError:
    from nose.tools import assert_items_equal as assert_count_equal
from nose.tools import assert_true
from nose.tools import raises

import networkx as nx
from networkx import is_eulerian, eulerian_circuit


class TestIsEulerian(TestCase):

    def test_is_eulerian(self):
        assert_true(is_eulerian(nx.complete_graph(5)))
        assert_true(is_eulerian(nx.complete_graph(7)))
        assert_true(is_eulerian(nx.hypercube_graph(4)))
        assert_true(is_eulerian(nx.hypercube_graph(6)))

        assert_false(is_eulerian(nx.complete_graph(4)))
        assert_false(is_eulerian(nx.complete_graph(6)))
        assert_false(is_eulerian(nx.hypercube_graph(3)))
        assert_false(is_eulerian(nx.hypercube_graph(5)))

        assert_false(is_eulerian(nx.petersen_graph()))
        assert_false(is_eulerian(nx.path_graph(4)))

    def test_is_eulerian2(self):
        # not connected
        G = nx.Graph()
        G.add_nodes_from([1, 2, 3])
        assert_false(is_eulerian(G))
        # not strongly connected
        G = nx.DiGraph()
        G.add_nodes_from([1, 2, 3])
        assert_false(is_eulerian(G))
        G = nx.MultiDiGraph()
        G.add_edge(1, 2)
        G.add_edge(2, 3)
        G.add_edge(2, 3)
        G.add_edge(3, 1)
        assert_false(is_eulerian(G))


class TestEulerianCircuit(TestCase):

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

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

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

        G = nx.complete_graph(3)

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

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

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

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

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

    def test_multigraph(self):
        G = nx.MultiGraph()
        nx.add_cycle(G, [0, 1, 2, 3])
        G.add_edge(1, 2)
        G.add_edge(1, 2)
        edges = list(eulerian_circuit(G, source=0))
        nodes = [u for u, v in edges]
        assert_equal(nodes, [0, 3, 2, 1, 2, 1])
        assert_equal(edges, [(0, 3), (3, 2), (2, 1), (1, 2), (2, 1), (1, 0)])

    def test_multigraph_with_keys(self):
        G = nx.MultiGraph()
        nx.add_cycle(G, [0, 1, 2, 3])
        G.add_edge(1, 2)
        G.add_edge(1, 2)
        edges = list(eulerian_circuit(G, source=0, keys=True))
        nodes = [u for u, v, k in edges]
        assert_equal(nodes, [0, 3, 2, 1, 2, 1])
        assert_equal(edges[:2], [(0, 3, 0), (3, 2, 0)])
        assert_count_equal(edges[2:5], [(2, 1, 0), (1, 2, 1), (2, 1, 2)])
        assert_equal(edges[5:], [(1, 0, 0)])

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