ioftools / networkxMiCe / networkxmaster / 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, "iset not found by ramsey!") 
14  
15 
# this trival graph has no cliques. should just find isets

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, "iset 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, "iset not found by ramsey!") 