#!/usr/bin/env python
from nose.tools import *
import networkx as nx
from networkx.testing.utils import *


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

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

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

    def test_trivial(self):
        """Empty graph"""
        G = nx.Graph()
        assert_equal(nx.find_cores(G), {})

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

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

    def test_find_cores2(self):
        core = nx.find_cores(self.H)
        nodes_by_core = [sorted([n for n in core if core[n] == val])
                         for val in range(3)]
        assert_nodes_equal(nodes_by_core[0], [0])
        assert_nodes_equal(nodes_by_core[1], [1, 3])
        assert_nodes_equal(nodes_by_core[2], [2, 4, 5, 6])

    def test_directed_find_cores(Self):
        '''core number had a bug for directed graphs found in issue #1959'''
        # small example where too timid edge removal can make cn[2] = 3
        G = nx.DiGraph()
        edges = [(1, 2), (2, 1), (2, 3), (2, 4), (3, 4), (4, 3)]
        G.add_edges_from(edges)
        assert_equal(nx.core_number(G), {1: 2, 2: 2, 3: 2, 4: 2})
        # small example where too aggressive edge removal can make cn[2] = 2
        more_edges = [(1, 5), (3, 5), (4, 5), (3, 6), (4, 6), (5, 6)]
        G.add_edges_from(more_edges)
        assert_equal(nx.core_number(G), {1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3})

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

    def test_k_core(self):
        # k=0
        k_core_subgraph = nx.k_core(self.H, k=0)
        assert_equal(sorted(k_core_subgraph.nodes()), sorted(self.H.nodes()))
        # k=1
        k_core_subgraph = nx.k_core(self.H, k=1)
        assert_equal(sorted(k_core_subgraph.nodes()), [1, 2, 3, 4, 5, 6])
        # k = 2
        k_core_subgraph = nx.k_core(self.H, k=2)
        assert_equal(sorted(k_core_subgraph.nodes()), [2, 4, 5, 6])

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

    def test_k_crust(self):
        # k = 0
        k_crust_subgraph = nx.k_crust(self.H, k=2)
        assert_equal(sorted(k_crust_subgraph.nodes()), sorted(self.H.nodes()))
        # k=1
        k_crust_subgraph = nx.k_crust(self.H, k=1)
        assert_equal(sorted(k_crust_subgraph.nodes()), [0, 1, 3])
        # k=2
        k_crust_subgraph = nx.k_crust(self.H, k=0)
        assert_equal(sorted(k_crust_subgraph.nodes()), [0])

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

    def test_k_shell(self):
        # k=0
        k_shell_subgraph = nx.k_shell(self.H, k=2)
        assert_equal(sorted(k_shell_subgraph.nodes()), [2, 4, 5, 6])
        # k=1
        k_shell_subgraph = nx.k_shell(self.H, k=1)
        assert_equal(sorted(k_shell_subgraph.nodes()), [1, 3])
        # k=2
        k_shell_subgraph = nx.k_shell(self.H, k=0)
        assert_equal(sorted(k_shell_subgraph.nodes()), [0])

    def test_k_corona(self):
        # k=0
        k_corona_subgraph = nx.k_corona(self.H, k=2)
        assert_equal(sorted(k_corona_subgraph.nodes()), [2, 4, 5, 6])
        # k=1
        k_corona_subgraph = nx.k_corona(self.H, k=1)
        assert_equal(sorted(k_corona_subgraph.nodes()), [1])
        # k=2
        k_corona_subgraph = nx.k_corona(self.H, k=0)
        assert_equal(sorted(k_corona_subgraph.nodes()), [0])