ioftools / networkxMiCe / networkxmaster / networkx / algorithms / tests / test_chordal.py @ 5cef0f13
History  View  Annotate  Download (2.42 KB)
1 
#!/usr/bin/env python


2 
from nose.tools import * 
3 
import networkx as nx 
4  
5  
6 
class TestMCS: 
7  
8 
def setUp(self): 
9 
# simple graph

10 
connected_chordal_G = nx.Graph() 
11 
connected_chordal_G.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), 
12 
(3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]) 
13 
self.connected_chordal_G = connected_chordal_G

14  
15 
chordal_G = nx.Graph() 
16 
chordal_G.add_edges_from([(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), 
17 
(3, 5), (3, 6), (4, 5), (4, 6), (5, 6), (7, 8)]) 
18 
chordal_G.add_node(9)

19 
self.chordal_G = chordal_G

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

24  
25 
def test_is_chordal(self): 
26 
assert_false(nx.is_chordal(self.non_chordal_G))

27 
assert_true(nx.is_chordal(self.chordal_G))

28 
assert_true(nx.is_chordal(self.connected_chordal_G))

29 
assert_true(nx.is_chordal(nx.complete_graph(3)))

30 
assert_true(nx.is_chordal(nx.cycle_graph(3)))

31 
assert_false(nx.is_chordal(nx.cycle_graph(5)))

32  
33 
def test_induced_nodes(self): 
34 
G = nx.generators.classic.path_graph(10)

35 
I = nx.find_induced_nodes(G, 1, 9, 2) 
36 
assert_equal(I, set([1, 2, 3, 4, 5, 6, 7, 8, 9])) 
37 
assert_raises(nx.NetworkXTreewidthBoundExceeded, 
38 
nx.find_induced_nodes, G, 1, 9, 1) 
39 
I = nx.find_induced_nodes(self.chordal_G, 1, 6) 
40 
assert_equal(I, set([1, 2, 4, 6])) 
41 
assert_raises(nx.NetworkXError, 
42 
nx.find_induced_nodes, self.non_chordal_G, 1, 5) 
43  
44 
def test_chordal_find_cliques(self): 
45 
cliques = set([frozenset([9]), frozenset([7, 8]), frozenset([1, 2, 3]), 
46 
frozenset([2, 3, 4]), frozenset([3, 4, 5, 6])]) 
47 
assert_equal(nx.chordal_graph_cliques(self.chordal_G), cliques)

48  
49 
def test_chordal_find_cliques_path(self): 
50 
G = nx.path_graph(10)

51 
cliqueset = nx.chordal_graph_cliques(G) 
52 
for (u, v) in G.edges(): 
53 
assert_true(frozenset([u, v]) in cliqueset 
54 
or frozenset([v, u]) in cliqueset) 
55  
56 
def test_chordal_find_cliquesCC(self): 
57 
cliques = set([frozenset([1, 2, 3]), frozenset([2, 3, 4]), 
58 
frozenset([3, 4, 5, 6])]) 
59 
assert_equal(nx.chordal_graph_cliques(self.connected_chordal_G), cliques)
