#!/usr/bin/env python
"""
====================
Generators - Classic
====================

Unit tests for various classic graph generators in generators/classic.py
"""
import itertools

from nose.tools import *
import networkx as nx
from networkx import *
from networkx.algorithms.isomorphism.isomorph import graph_could_be_isomorphic
from networkx.testing import assert_edges_equal
from networkx.testing import assert_nodes_equal

is_isomorphic = graph_could_be_isomorphic


class TestGeneratorClassic():
    def test_balanced_tree(self):
        # balanced_tree(r,h) is a tree with (r**(h+1)-1)/(r-1) edges
        for r, h in [(2, 2), (3, 3), (6, 2)]:
            t = balanced_tree(r, h)
            order = t.order()
            assert_true(order == (r**(h + 1) - 1) / (r - 1))
            assert_true(is_connected(t))
            assert_true(t.size() == order - 1)
            dh = degree_histogram(t)
            assert_equal(dh[0], 0)  # no nodes of 0
            assert_equal(dh[1], r**h)  # nodes of degree 1 are leaves
            assert_equal(dh[r], 1)  # root is degree r
            assert_equal(dh[r + 1], order - r**h - 1)  # everyone else is degree r+1
            assert_equal(len(dh), r + 2)

    def test_balanced_tree_star(self):
        # balanced_tree(r,1) is the r-star
        t = balanced_tree(r=2, h=1)
        assert_true(is_isomorphic(t, star_graph(2)))
        t = balanced_tree(r=5, h=1)
        assert_true(is_isomorphic(t, star_graph(5)))
        t = balanced_tree(r=10, h=1)
        assert_true(is_isomorphic(t, star_graph(10)))

    def test_balanced_tree_path(self):
        """Tests that the balanced tree with branching factor one is the
        path graph.

        """
        # A tree of height four has five levels.
        T = balanced_tree(1, 4)
        P = path_graph(5)
        assert_true(is_isomorphic(T, P))

    def test_full_rary_tree(self):
        r = 2
        n = 9
        t = full_rary_tree(r, n)
        assert_equal(t.order(), n)
        assert_true(is_connected(t))
        dh = degree_histogram(t)
        assert_equal(dh[0], 0)  # no nodes of 0
        assert_equal(dh[1], 5)  # nodes of degree 1 are leaves
        assert_equal(dh[r], 1)  # root is degree r
        assert_equal(dh[r + 1], 9 - 5 - 1)  # everyone else is degree r+1
        assert_equal(len(dh), r + 2)

    def test_full_rary_tree_balanced(self):
        t = full_rary_tree(2, 15)
        th = balanced_tree(2, 3)
        assert_true(is_isomorphic(t, th))

    def test_full_rary_tree_path(self):
        t = full_rary_tree(1, 10)
        assert_true(is_isomorphic(t, path_graph(10)))

    def test_full_rary_tree_empty(self):
        t = full_rary_tree(0, 10)
        assert_true(is_isomorphic(t, empty_graph(10)))
        t = full_rary_tree(3, 0)
        assert_true(is_isomorphic(t, empty_graph(0)))

    def test_full_rary_tree_3_20(self):
        t = full_rary_tree(3, 20)
        assert_equal(t.order(), 20)

    def test_barbell_graph(self):
        # number of nodes = 2*m1 + m2 (2 m1-complete graphs + m2-path + 2 edges)
        # number of edges = 2*(number_of_edges(m1-complete graph) + m2 + 1
        m1 = 3
        m2 = 5
        b = barbell_graph(m1, m2)
        assert_true(number_of_nodes(b) == 2 * m1 + m2)
        assert_true(number_of_edges(b) == m1 * (m1 - 1) + m2 + 1)

        m1 = 4
        m2 = 10
        b = barbell_graph(m1, m2)
        assert_true(number_of_nodes(b) == 2 * m1 + m2)
        assert_true(number_of_edges(b) == m1 * (m1 - 1) + m2 + 1)

        m1 = 3
        m2 = 20
        b = barbell_graph(m1, m2)
        assert_true(number_of_nodes(b) == 2 * m1 + m2)
        assert_true(number_of_edges(b) == m1 * (m1 - 1) + m2 + 1)

        # Raise NetworkXError if m1<2
        m1 = 1
        m2 = 20
        assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2)

        # Raise NetworkXError if m2<0
        m1 = 5
        m2 = -2
        assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2)

        # barbell_graph(2,m) = path_graph(m+4)
        m1 = 2
        m2 = 5
        b = barbell_graph(m1, m2)
        assert_true(is_isomorphic(b, path_graph(m2 + 4)))

        m1 = 2
        m2 = 10
        b = barbell_graph(m1, m2)
        assert_true(is_isomorphic(b, path_graph(m2 + 4)))

        m1 = 2
        m2 = 20
        b = barbell_graph(m1, m2)
        assert_true(is_isomorphic(b, path_graph(m2 + 4)))

        assert_raises(networkx.exception.NetworkXError, barbell_graph, m1, m2,
                      create_using=DiGraph())

        mb = barbell_graph(m1, m2, create_using=MultiGraph())
        assert_edges_equal(mb.edges(), b.edges())

    def test_complete_graph(self):
        # complete_graph(m) is a connected graph with
        # m nodes and  m*(m+1)/2 edges
        for m in [0, 1, 3, 5]:
            g = complete_graph(m)
            assert_true(number_of_nodes(g) == m)
            assert_true(number_of_edges(g) == m * (m - 1) // 2)

        mg = complete_graph(m, create_using=MultiGraph())
        assert_edges_equal(mg.edges(), g.edges())

        g = complete_graph("abc")
        assert_nodes_equal(g.nodes(), ['a', 'b', 'c'])
        assert_equal(g.size(), 3)

    def test_complete_digraph(self):
        # complete_graph(m) is a connected graph with
        # m nodes and  m*(m+1)/2 edges
        for m in [0, 1, 3, 5]:
            g = complete_graph(m, create_using=nx.DiGraph())
            assert_true(number_of_nodes(g) == m)
            assert_true(number_of_edges(g) == m * (m - 1))

        g = complete_graph("abc", create_using=nx.DiGraph())
        assert_equal(len(g), 3)
        assert_equal(g.size(), 6)
        assert_true(g.is_directed())

    def test_circular_ladder_graph(self):
        G = circular_ladder_graph(5)
        assert_raises(networkx.exception.NetworkXError, circular_ladder_graph,
                      5, create_using=DiGraph())
        mG = circular_ladder_graph(5, create_using=MultiGraph())
        assert_edges_equal(mG.edges(), G.edges())

    def test_circulant_graph(self):
        # Ci_n(1) is the cycle graph for all n
        Ci6_1 = circulant_graph(6, [1])
        C6 = cycle_graph(6)
        assert_edges_equal(Ci6_1.edges(), C6.edges())

        # Ci_n(1, 2, ..., n div 2) is the complete graph for all n
        Ci7 = circulant_graph(7, [1, 2, 3])
        K7 = complete_graph(7)
        assert_edges_equal(Ci7.edges(), K7.edges())

        # Ci_6(1, 3) is K_3,3 i.e. the utility graph
        Ci6_1_3 = circulant_graph(6, [1, 3])
        K3_3 = complete_bipartite_graph(3, 3)
        assert_true(is_isomorphic(Ci6_1_3, K3_3))

    def test_cycle_graph(self):
        G = cycle_graph(4)
        assert_edges_equal(G.edges(), [(0, 1), (0, 3), (1, 2), (2, 3)])
        mG = cycle_graph(4, create_using=MultiGraph())
        assert_edges_equal(mG.edges(), [(0, 1), (0, 3), (1, 2), (2, 3)])
        G = cycle_graph(4, create_using=DiGraph())
        assert_false(G.has_edge(2, 1))
        assert_true(G.has_edge(1, 2))
        assert_true(G.is_directed())

        G = cycle_graph("abc")
        assert_equal(len(G), 3)
        assert_equal(G.size(), 3)
        g = cycle_graph("abc", nx.DiGraph())
        assert_equal(len(g), 3)
        assert_equal(g.size(), 3)
        assert_true(g.is_directed())

    def test_dorogovtsev_goltsev_mendes_graph(self):
        G = dorogovtsev_goltsev_mendes_graph(0)
        assert_edges_equal(G.edges(), [(0, 1)])
        assert_nodes_equal(list(G), [0, 1])
        G = dorogovtsev_goltsev_mendes_graph(1)
        assert_edges_equal(G.edges(), [(0, 1), (0, 2), (1, 2)])
        assert_equal(average_clustering(G), 1.0)
        assert_equal(sorted(triangles(G).values()), [1, 1, 1])
        G = dorogovtsev_goltsev_mendes_graph(10)
        assert_equal(number_of_nodes(G), 29526)
        assert_equal(number_of_edges(G), 59049)
        assert_equal(G.degree(0), 1024)
        assert_equal(G.degree(1), 1024)
        assert_equal(G.degree(2), 1024)

        assert_raises(networkx.exception.NetworkXError,
                      dorogovtsev_goltsev_mendes_graph, 7,
                      create_using=DiGraph())
        assert_raises(networkx.exception.NetworkXError,
                      dorogovtsev_goltsev_mendes_graph, 7,
                      create_using=MultiGraph())

    def test_empty_graph(self):
        G = empty_graph()
        assert_equal(number_of_nodes(G), 0)
        G = empty_graph(42)
        assert_equal(number_of_nodes(G), 42)
        assert_equal(number_of_edges(G), 0)

        G = empty_graph("abc")
        assert_equal(len(G), 3)
        assert_equal(G.size(), 0)

        # create empty digraph
        G = empty_graph(42, create_using=DiGraph(name="duh"))
        assert_equal(number_of_nodes(G), 42)
        assert_equal(number_of_edges(G), 0)
        assert_true(isinstance(G, DiGraph))

        # create empty multigraph
        G = empty_graph(42, create_using=MultiGraph(name="duh"))
        assert_equal(number_of_nodes(G), 42)
        assert_equal(number_of_edges(G), 0)
        assert_true(isinstance(G, MultiGraph))

        # create empty graph from another
        pete = petersen_graph()
        G = empty_graph(42, create_using=pete)
        assert_equal(number_of_nodes(G), 42)
        assert_equal(number_of_edges(G), 0)
        assert_true(isinstance(G, Graph))

    def test_ladder_graph(self):
        for i, G in [(0, empty_graph(0)), (1, path_graph(2)),
                     (2, hypercube_graph(2)), (10, grid_graph([2, 10]))]:
            assert_true(is_isomorphic(ladder_graph(i), G))

        assert_raises(networkx.exception.NetworkXError,
                      ladder_graph, 2, create_using=DiGraph())

        g = ladder_graph(2)
        mg = ladder_graph(2, create_using=MultiGraph())
        assert_edges_equal(mg.edges(), g.edges())

    def test_lollipop_graph(self):
        # number of nodes = m1 + m2
        # number of edges = number_of_edges(complete_graph(m1)) + m2
        for m1, m2 in [(3, 5), (4, 10), (3, 20)]:
            b = lollipop_graph(m1, m2)
            assert_equal(number_of_nodes(b), m1 + m2)
            assert_equal(number_of_edges(b), m1 * (m1 - 1) / 2 + m2)

        # Raise NetworkXError if m<2
        assert_raises(networkx.exception.NetworkXError,
                      lollipop_graph, 1, 20)

        # Raise NetworkXError if n<0
        assert_raises(networkx.exception.NetworkXError,
                      lollipop_graph, 5, -2)

        # lollipop_graph(2,m) = path_graph(m+2)
        for m1, m2 in [(2, 5), (2, 10), (2, 20)]:
            b = lollipop_graph(m1, m2)
            assert_true(is_isomorphic(b, path_graph(m2 + 2)))

        assert_raises(networkx.exception.NetworkXError,
                      lollipop_graph, m1, m2, create_using=DiGraph())

        mb = lollipop_graph(m1, m2, create_using=MultiGraph())
        assert_edges_equal(mb.edges(), b.edges())

        g = lollipop_graph([1, 2, 3, 4], "abc")
        assert_equal(len(g), 7)
        assert_equal(g.size(), 9)

    def test_null_graph(self):
        assert_equal(number_of_nodes(null_graph()), 0)

    def test_path_graph(self):
        p = path_graph(0)
        assert_true(is_isomorphic(p, null_graph()))

        p = path_graph(1)
        assert_true(is_isomorphic(p, empty_graph(1)))

        p = path_graph(10)
        assert_true(is_connected(p))
        assert_equal(sorted(d for n, d in p.degree()),
                     [1, 1, 2, 2, 2, 2, 2, 2, 2, 2])
        assert_equal(p.order() - 1, p.size())

        dp = path_graph(3, create_using=DiGraph())
        assert_true(dp.has_edge(0, 1))
        assert_false(dp.has_edge(1, 0))

        mp = path_graph(10, create_using=MultiGraph())
        assert_edges_equal(mp.edges(), p.edges())

        G = path_graph("abc")
        assert_equal(len(G), 3)
        assert_equal(G.size(), 2)
        g = path_graph("abc", nx.DiGraph())
        assert_equal(len(g), 3)
        assert_equal(g.size(), 2)
        assert_true(g.is_directed())

    def test_star_graph(self):
        assert_true(is_isomorphic(star_graph(0), empty_graph(1)))
        assert_true(is_isomorphic(star_graph(1), path_graph(2)))
        assert_true(is_isomorphic(star_graph(2), path_graph(3)))
        assert_true(is_isomorphic(star_graph(5), nx.complete_bipartite_graph(1, 5)))

        s = star_graph(10)
        assert_equal(sorted(d for n, d in s.degree()),
                     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10])

        assert_raises(networkx.exception.NetworkXError,
                      star_graph, 10, create_using=DiGraph())

        ms = star_graph(10, create_using=MultiGraph())
        assert_edges_equal(ms.edges(), s.edges())

        G = star_graph("abcdefg")
        assert_equal(len(G), 7)
        assert_equal(G.size(), 6)

    def test_trivial_graph(self):
        assert_equal(number_of_nodes(trivial_graph()), 1)

    def test_turan_graph(self):
        assert_equal(number_of_edges(turan_graph(13, 4)), 63)
        assert_true(is_isomorphic(turan_graph(13, 4), complete_multipartite_graph(3, 4, 3, 3)))

    def test_wheel_graph(self):
        for n, G in [(0, null_graph()), (1, empty_graph(1)),
                     (2, path_graph(2)), (3, complete_graph(3)),
                     (4, complete_graph(4))]:
            g = wheel_graph(n)
            assert_true(is_isomorphic(g, G))

        g = wheel_graph(10)
        assert_equal(sorted(d for n, d in g.degree()),
                     [3, 3, 3, 3, 3, 3, 3, 3, 3, 9])

        assert_raises(networkx.exception.NetworkXError,
                      wheel_graph, 10, create_using=DiGraph())

        mg = wheel_graph(10, create_using=MultiGraph())
        assert_edges_equal(mg.edges(), g.edges())

        G = wheel_graph("abc")
        assert_equal(len(G), 3)
        assert_equal(G.size(), 3)

    def test_complete_0_partite_graph(self):
        """Tests that the complete 0-partite graph is the null graph."""
        G = nx.complete_multipartite_graph()
        H = nx.null_graph()
        assert_nodes_equal(G, H)
        assert_edges_equal(G.edges(), H.edges())

    def test_complete_1_partite_graph(self):
        """Tests that the complete 1-partite graph is the empty graph."""
        G = nx.complete_multipartite_graph(3)
        H = nx.empty_graph(3)
        assert_nodes_equal(G, H)
        assert_edges_equal(G.edges(), H.edges())

    def test_complete_2_partite_graph(self):
        """Tests that the complete 2-partite graph is the complete bipartite
        graph.

        """
        G = nx.complete_multipartite_graph(2, 3)
        H = nx.complete_bipartite_graph(2, 3)
        assert_nodes_equal(G, H)
        assert_edges_equal(G.edges(), H.edges())

    def test_complete_multipartite_graph(self):
        """Tests for generating the complete multipartite graph."""
        G = nx.complete_multipartite_graph(2, 3, 4)
        blocks = [(0, 1), (2, 3, 4), (5, 6, 7, 8)]
        # Within each block, no two vertices should be adjacent.
        for block in blocks:
            for u, v in itertools.combinations_with_replacement(block, 2):
                assert_true(v not in G[u])
                assert_equal(G.nodes[u], G.nodes[v])
        # Across blocks, all vertices should be adjacent.
        for (block1, block2) in itertools.combinations(blocks, 2):
            for u, v in itertools.product(block1, block2):
                assert_true(v in G[u])
                assert_not_equal(G.nodes[u], G.nodes[v])