Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / approximation / tests / test_ramsey.py @ 5cef0f13

History | View | Annotate | Download (1007 Bytes)

1
from nose.tools import *
2
import networkx as nx
3
import networkx.algorithms.approximation as apxa
4

    
5

    
6
def test_ramsey():
7
    # this should only find the complete graph
8
    graph = nx.complete_graph(10)
9
    c, i = apxa.ramsey_R2(graph)
10
    cdens = nx.density(graph.subgraph(c))
11
    eq_(cdens, 1.0, "clique not found by ramsey!")
12
    idens = nx.density(graph.subgraph(i))
13
    eq_(idens, 0.0, "i-set not found by ramsey!")
14

    
15
    # this trival graph has no cliques. should just find i-sets
16
    graph = nx.trivial_graph(nx.Graph())
17
    c, i = apxa.ramsey_R2(graph)
18
    cdens = nx.density(graph.subgraph(c))
19
    eq_(cdens, 0.0, "clique not found by ramsey!")
20
    idens = nx.density(graph.subgraph(i))
21
    eq_(idens, 0.0, "i-set not found by ramsey!")
22

    
23
    graph = nx.barbell_graph(10, 5, nx.Graph())
24
    c, i = apxa.ramsey_R2(graph)
25
    cdens = nx.density(graph.subgraph(c))
26
    eq_(cdens, 1.0, "clique not found by ramsey!")
27
    idens = nx.density(graph.subgraph(i))
28
    eq_(idens, 0.0, "i-set not found by ramsey!")