Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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)