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

class TestMCS:

    def setUp(self):
        # simple graph
        connected_chordal_G=nx.Graph()
        connected_chordal_G.add_edges_from([(1,2),(1,3),(2,3),(2,4),(3,4),
                                            (3,5),(3,6),(4,5),(4,6),(5,6)])
        self.connected_chordal_G=connected_chordal_G

        chordal_G = nx.Graph()
        chordal_G.add_edges_from([(1,2),(1,3),(2,3),(2,4),(3,4),
                                  (3,5),(3,6),(4,5),(4,6),(5,6),(7,8)])
        chordal_G.add_node(9)
        self.chordal_G=chordal_G

        non_chordal_G = nx.Graph()
        non_chordal_G.add_edges_from([(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)])
        self.non_chordal_G = non_chordal_G

    def test_is_chordal(self):
        assert_false(nx.is_chordal(self.non_chordal_G))
        assert_true(nx.is_chordal(self.chordal_G))
        assert_true(nx.is_chordal(self.connected_chordal_G))
        assert_true(nx.is_chordal(nx.complete_graph(3)))
        assert_true(nx.is_chordal(nx.cycle_graph(3)))
        assert_false(nx.is_chordal(nx.cycle_graph(5)))
    
    def test_induced_nodes(self):
        G = nx.generators.classic.path_graph(10)
        I = nx.find_induced_nodes(G,1,9,2)
        assert_equal(I,set([1,2,3,4,5,6,7,8,9]))
        assert_raises(nx.NetworkXTreewidthBoundExceeded,
                      nx.find_induced_nodes,G,1,9,1)
        I = nx.find_induced_nodes(self.chordal_G,1,6)
        assert_equal(I,set([1,2,4,6]))
        assert_raises(nx.NetworkXError,
		      nx.find_induced_nodes,self.non_chordal_G,1,5)
        
    def test_chordal_find_cliques(self):
        cliques = set([frozenset([9]),frozenset([7,8]),frozenset([1,2,3]),
                       frozenset([2,3,4]),frozenset([3,4,5,6])])
        assert_equal(nx.chordal_graph_cliques(self.chordal_G),cliques)

    def test_chordal_find_cliques_path(self):
        G = nx.path_graph(10)
        cliqueset = nx.chordal_graph_cliques(G)
        for (u,v) in G.edges_iter():
            assert_true(frozenset([u,v]) in cliqueset 
                        or frozenset([v,u]) in cliqueset)
    
    def test_chordal_find_cliquesCC(self):
        cliques = set([frozenset([1,2,3]),frozenset([2,3,4]),
                       frozenset([3,4,5,6])])
        assert_equal(nx.chordal_graph_cliques(self.connected_chordal_G),cliques)

