1 #!/usr/bin/env python 2 from nose.tools import * 3 import networkx as nx 4 5 class TestMCS: 6 7 def setUp(self): 8 # simple graph 9 connected_chordal_G=nx.Graph() 10 connected_chordal_G.add_edges_from([(1,2),(1,3),(2,3),(2,4),(3,4), 11 (3,5),(3,6),(4,5),(4,6),(5,6)]) 12 self.connected_chordal_G=connected_chordal_G 13 14 chordal_G = nx.Graph() 15 chordal_G.add_edges_from([(1,2),(1,3),(2,3),(2,4),(3,4), 16 (3,5),(3,6),(4,5),(4,6),(5,6),(7,8)]) 17 chordal_G.add_node(9) 18 self.chordal_G=chordal_G 19 20 non_chordal_G = nx.Graph() 21 non_chordal_G.add_edges_from([(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)]) 22 self.non_chordal_G = non_chordal_G 23 24 def test_is_chordal(self): 25 assert_false(nx.is_chordal(self.non_chordal_G)) 26 assert_true(nx.is_chordal(self.chordal_G)) 27 assert_true(nx.is_chordal(self.connected_chordal_G)) 28 assert_true(nx.is_chordal(nx.complete_graph(3))) 29 assert_true(nx.is_chordal(nx.cycle_graph(3))) 30 assert_false(nx.is_chordal(nx.cycle_graph(5))) 31 32 def test_induced_nodes(self): 33 G = nx.generators.classic.path_graph(10) 34 I = nx.find_induced_nodes(G,1,9,2) 35 assert_equal(I,set([1,2,3,4,5,6,7,8,9])) 36 assert_raises(nx.NetworkXTreewidthBoundExceeded, 37 nx.find_induced_nodes,G,1,9,1) 38 I = nx.find_induced_nodes(self.chordal_G,1,6) 39 assert_equal(I,set([1,2,4,6])) 40 assert_raises(nx.NetworkXError, 41 nx.find_induced_nodes,self.non_chordal_G,1,5) 42 43 def test_chordal_find_cliques(self): 44 cliques = set([frozenset([9]),frozenset([7,8]),frozenset([1,2,3]), 45 frozenset([2,3,4]),frozenset([3,4,5,6])]) 46 assert_equal(nx.chordal_graph_cliques(self.chordal_G),cliques) 47 48 def test_chordal_find_cliques_path(self): 49 G = nx.path_graph(10) 50 cliqueset = nx.chordal_graph_cliques(G) 51 for (u,v) in G.edges_iter(): 52 assert_true(frozenset([u,v]) in cliqueset 53 or frozenset([v,u]) in cliqueset) 54 55 def test_chordal_find_cliquesCC(self): 56 cliques = set([frozenset([1,2,3]),frozenset([2,3,4]), 57 frozenset([3,4,5,6])]) 58 assert_equal(nx.chordal_graph_cliques(self.connected_chordal_G),cliques) 59 60
