<s> from nose . tools import assert_equal , assert_true , assert_false , assert_raises , raises <EOL> import networkx as nx <EOL> from networkx . algorithms . approximation import k_components <EOL> from networkx . algorithms . approximation . kcomponents import _AntiGraph , _same <EOL> def build_k_number_dict ( k_components ) : <EOL> k_num = { } <EOL> for k , comps in sorted ( k_components . items ( ) ) : <EOL> for comp in comps : <EOL> for node in comp : <EOL> k_num [ node ] = k <EOL> return k_num <EOL> def graph_example_1 ( ) : <EOL> G = nx . convert_node_labels_to_integers ( nx . grid_graph ( [ <NUM_LIT:5> , <NUM_LIT:5> ] ) , <EOL> label_attribute = '<STR_LIT>' ) <EOL> rlabels = nx . get_node_attributes ( G , '<STR_LIT>' ) <EOL> labels = dict ( ( v , k ) for k , v in rlabels . items ( ) ) <EOL> for nodes in [ ( labels [ ( <NUM_LIT:0> , <NUM_LIT:0> ) ] , labels [ ( <NUM_LIT:1> , <NUM_LIT:0> ) ] ) , <EOL> ( labels [ ( <NUM_LIT:0> , <NUM_LIT:4> ) ] , labels [ ( <NUM_LIT:1> , <NUM_LIT:4> ) ] ) , <EOL> ( labels [ ( <NUM_LIT:3> , <NUM_LIT:0> ) ] , labels [ ( <NUM_LIT:4> , <NUM_LIT:0> ) ] ) , <EOL> ( labels [ ( <NUM_LIT:3> , <NUM_LIT:4> ) ] , labels [ ( <NUM_LIT:4> , <NUM_LIT:4> ) ] ) ] : <EOL> new_node = G . order ( ) + <NUM_LIT:1> <EOL> P = nx . petersen_graph ( ) <EOL> G = nx . disjoint_union ( G , P ) <EOL> G . add_edge ( new_node + <NUM_LIT:1> , nodes [ <NUM_LIT:0> ] ) <EOL> G . add_edge ( new_node , nodes [ <NUM_LIT:1> ] ) <EOL> K = nx . complete_graph ( <NUM_LIT:5> ) <EOL> G = nx . disjoint_union ( G , K ) <EOL> G . add_edge ( new_node + <NUM_LIT:2> , new_node + <NUM_LIT:11> ) <EOL> G . add_edge ( new_node + <NUM_LIT:3> , new_node + <NUM_LIT:12> ) <EOL> G . add_edge ( new_node + <NUM_LIT:4> , new_node + <NUM_LIT> ) <EOL> G = nx . disjoint_union ( G , K ) <EOL> nbrs = G [ new_node + <NUM_LIT:10> ] <EOL> G . remove_node ( new_node + <NUM_LIT:10> ) <EOL> for nbr in nbrs : <EOL> G . add_edge ( new_node + <NUM_LIT> , nbr ) <EOL> G . add_edge ( new_node + <NUM_LIT:16> , new_node + <NUM_LIT:5> ) <EOL> G . name = '<STR_LIT>' <EOL> return G <EOL> def torrents_and_ferraro_graph ( ) : <EOL> G = nx . convert_node_labels_to_integers ( nx . grid_graph ( [ <NUM_LIT:5> , <NUM_LIT:5> ] ) , <EOL> label_attribute = '<STR_LIT>' ) <EOL> rlabels = nx . get_node_attributes ( G , '<STR_LIT>' ) <EOL> labels = dict ( ( v , k ) for k , v in rlabels . items ( ) ) <EOL> for nodes in [ ( labels [ ( <NUM_LIT:0> , <NUM_LIT:4> ) ] , labels [ ( <NUM_LIT:1> , <NUM_LIT:4> ) ] ) , <EOL> ( labels [ ( <NUM_LIT:3> , <NUM_LIT:4> ) ] , labels [ ( <NUM_LIT:4> , <NUM_LIT:4> ) ] ) ] : <EOL> new_node = G . order ( ) + <NUM_LIT:1> <EOL> P = nx . petersen_graph ( ) <EOL> G = nx . disjoint_union ( G , P ) <EOL> G . add_edge ( new_node + <NUM_LIT:1> , nodes [ <NUM_LIT:0> ] ) <EOL> G . add_edge ( new_node , nodes [ <NUM_LIT:1> ] ) <EOL> K = nx . complete_graph ( <NUM_LIT:5> ) <EOL> G = nx . disjoint_union ( G , K ) <EOL> G . add_edge ( new_node + <NUM_LIT:2> , new_node + <NUM_LIT:11> ) <EOL> G . add_edge ( new_node + <NUM_LIT:3> , new_node + <NUM_LIT:12> ) <EOL> G . add_edge ( new_node + <NUM_LIT:4> , new_node + <NUM_LIT> ) <EOL> G = nx . disjoint_union ( G , K ) <EOL> nbrs = G [ new_node + <NUM_LIT:10> ] <EOL> G . remove_node ( new_node + <NUM_LIT:10> ) <EOL> for nbr in nbrs : <EOL> G . add_edge ( new_node + <NUM_LIT> , nbr ) <EOL> G . add_edge ( new_node + <NUM_LIT:16> , new_node + <NUM_LIT:8> ) <EOL> for nodes in [ ( labels [ ( <NUM_LIT:0> , <NUM_LIT:0> ) ] , labels [ ( <NUM_LIT:1> , <NUM_LIT:0> ) ] ) , <EOL> ( labels [ ( <NUM_LIT:3> , <NUM_LIT:0> ) ] , labels [ ( <NUM_LIT:4> , <NUM_LIT:0> ) ] ) ] : <EOL> new_node = G . order ( ) + <NUM_LIT:1> <EOL> P = nx . petersen_graph ( ) <EOL> G = nx . disjoint_union ( G , P ) <EOL> G . add_edge ( new_node + <NUM_LIT:1> , nodes [ <NUM_LIT:0> ] ) <EOL> G . add_edge ( new_node , nodes [ <NUM_LIT:1> ] ) <EOL> K = nx . complete_graph ( <NUM_LIT:5> ) <EOL> G = nx . disjoint_union ( G , K ) <EOL> G . add_edge ( new_node + <NUM_LIT:2> , new_node + <NUM_LIT:11> ) <EOL> G . add_edge ( new_node + <NUM_LIT:3> , new_node + <NUM_LIT:12> ) <EOL> G . add_edge ( new_node + <NUM_LIT:4> , new_node + <NUM_LIT> ) <EOL> G = nx . disjoint_union ( G , K ) <EOL> nbrs = G [ new_node + <NUM_LIT:10> ] <EOL> G . remove_node ( new_node + <NUM_LIT:10> ) <EOL> for nbr in nbrs : <EOL> G . add_edge ( new_node + <NUM_LIT> , nbr ) <EOL> nbrs2 = G [ new_node + <NUM_LIT:9> ] <EOL> G . remove_node ( new_node + <NUM_LIT:9> ) <EOL> for nbr in nbrs2 : <EOL> G . add_edge ( new_node + <NUM_LIT> , nbr ) <EOL> G . name = '<STR_LIT>' <EOL> return G <EOL> def _check_connectivity ( G ) : <EOL> result = k_components ( G ) <EOL> for k , components in result . items ( ) : <EOL> if k < <NUM_LIT:3> : <EOL> continue <EOL> for component in components : <EOL> C = G . subgraph ( component ) <EOL> K = nx . node_connectivity ( C ) <EOL> assert_true ( K >= k ) <EOL> def test_torrents_and_ferraro_graph ( ) : <EOL> G = torrents_and_ferraro_graph ( ) <EOL> _check_connectivity ( G ) <EOL> def test_example_1 ( ) : <EOL> G = graph_example_1 ( ) <EOL> _check_connectivity ( G ) <EOL> def test_karate_0 ( ) : <EOL> G = nx . karate_club_graph ( ) <EOL> _check_connectivity ( G ) <EOL> def test_karate_1 ( ) : <EOL> karate_k_num = { <NUM_LIT:0> : <NUM_LIT:4> , <NUM_LIT:1> : <NUM_LIT:4> , <NUM_LIT:2> : <NUM_LIT:4> , <NUM_LIT:3> : <NUM_LIT:4> , <NUM_LIT:4> : <NUM_LIT:3> , <NUM_LIT:5> : <NUM_LIT:3> , <NUM_LIT:6> : <NUM_LIT:3> , <NUM_LIT:7> : <NUM_LIT:4> , <NUM_LIT:8> : <NUM_LIT:4> , <NUM_LIT:9> : <NUM_LIT:2> , <EOL> <NUM_LIT:10> : <NUM_LIT:3> , <NUM_LIT:11> : <NUM_LIT:1> , <NUM_LIT:12> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:4> , <NUM_LIT> : <NUM_LIT:2> , <NUM_LIT:15> : <NUM_LIT:2> , <NUM_LIT:16> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:2> , <EOL> <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT:20> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT> : <NUM_LIT:2> , <NUM_LIT> : <NUM_LIT:3> , <EOL> <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT:30> : <NUM_LIT:4> , <NUM_LIT> : <NUM_LIT:3> , <NUM_LIT:32> : <NUM_LIT:4> , <NUM_LIT> : <NUM_LIT:4> } <EOL> G = nx . karate_club_graph ( ) <EOL> k_comps = k_components ( G ) <EOL> k_num = build_k_number_dict ( k_comps ) <EOL> assert_equal ( karate_k_num , k_num ) <EOL> def test_example_1_detail_3_and_4 ( ) : <EOL> solution = { <EOL> <NUM_LIT:3> : [ set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT:32> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:30> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:50> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT:64> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:100> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT:100> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) <EOL> ] , <EOL> <NUM_LIT:4> : [ set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT:100> , <NUM_LIT> ] ) , <EOL> set ( [ <NUM_LIT> , <NUM_LIT:100> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] ) <EOL> ] , <EOL> } <EOL> G = graph_example_1 ( ) <EOL> result = k_components ( G ) <EOL> for k , components in result . items ( ) : <EOL> if k < <NUM_LIT:3> : <EOL> continue <EOL> for component in components : <EOL> assert_true ( component in solution [ k ] ) <EOL> @ raises ( nx . NetworkXNotImplemented ) <EOL> def test_directed ( ) : <EOL> G = nx . gnp_random_graph ( <NUM_LIT:10> , <NUM_LIT> , directed = True ) <EOL> kc = k_components ( G ) <EOL> def test_same ( ) : <EOL> equal = { '<STR_LIT:A>' : <NUM_LIT:2> , '<STR_LIT:B>' : <NUM_LIT:2> , '<STR_LIT:C>' : <NUM_LIT:2> } <EOL> slightly_different = { '<STR_LIT:A>' : <NUM_LIT:2> , '<STR_LIT:B>' : <NUM_LIT:1> , '<STR_LIT:C>' : <NUM_LIT:2> } <EOL> different = { '<STR_LIT:A>' : <NUM_LIT:2> , '<STR_LIT:B>' : <NUM_LIT:8> , '<STR_LIT:C>' : <NUM_LIT> } <EOL> assert_true ( _same ( equal ) ) <EOL> assert_false ( _same ( slightly_different ) ) <EOL> assert_true ( _same ( slightly_different , tol = <NUM_LIT:1> ) ) <EOL> assert_false ( _same ( different ) ) <EOL> assert_false ( _same ( different , tol = <NUM_LIT:4> ) ) <EOL> class TestAntiGraph : <EOL> def setUp ( self ) : <EOL> self . Gnp = nx . gnp_random_graph ( <NUM_LIT:20> , <NUM_LIT> ) <EOL> self . Anp = _AntiGraph ( nx . complement ( self . Gnp ) ) <EOL> self . Gd = nx . davis_southern_women_graph ( ) <EOL> self . Ad = _AntiGraph ( nx . complement ( self . Gd ) ) <EOL> self . Gk = nx . karate_club_graph ( ) <EOL> self . Ak = _AntiGraph ( nx . complement ( self . Gk ) ) <EOL> self . GA = [ ( self . Gnp , self . Anp ) , <EOL> ( self . Gd , self . Ad ) , <EOL> ( self . Gk , self . Ak ) ] <EOL> def test_size ( self ) : <EOL> for G , A in self . GA : <EOL> n = G . order ( ) <EOL> s = len ( list ( G . edges ( ) ) ) + len ( list ( A . edges ( ) ) ) <EOL> assert_true ( s == ( n * ( n - <NUM_LIT:1> ) ) / <NUM_LIT:2> ) <EOL> def test_degree ( self ) : <EOL> for G , A in self . GA : <EOL> assert_equal ( G . degree ( ) , A . degree ( ) ) <EOL> def test_core_number ( self ) : <EOL> for G , A in self . GA : <EOL> assert_equal ( nx . core_number ( G ) , nx . core_number ( A ) ) <EOL> def test_connected_components ( self ) : <EOL> for G , A in self . GA : <EOL> gc = [ set ( c ) for c in nx . connected_components ( G ) ] <EOL> ac = [ set ( c ) for c in nx . connected_components ( A ) ] <EOL> for comp in ac : <EOL> assert_true ( comp in gc ) <EOL> def test_adjacency ( self ) : <EOL> for G , A in self . GA : <EOL> a_adj = list ( A . adjacency ( ) ) <EOL> for n , nbrs in G . adjacency ( ) : <EOL> assert_true ( ( n , set ( nbrs ) ) in a_adj ) <EOL> def test_neighbors ( self ) : <EOL> for G , A in self . GA : <EOL> node = list ( G . nodes ( ) ) [ <NUM_LIT:0> ] <EOL> assert_equal ( set ( G . neighbors ( node ) ) , set ( A . neighbors ( node ) ) ) <EOL> def test_node_not_in_graph ( self ) : <EOL> for G , A in self . GA : <EOL> node = '<STR_LIT>' <EOL> assert_raises ( nx . NetworkXError , A . neighbors , node ) <EOL> assert_raises ( nx . NetworkXError , G . neighbors , node ) <EOL> def test_degree ( self ) : <EOL> for G , A in self . GA : <EOL> node = list ( G . nodes ( ) ) [ <NUM_LIT:0> ] <EOL> nodes = list ( G . nodes ( ) ) [ <NUM_LIT:1> : <NUM_LIT:4> ] <EOL> assert_equal ( G . degree ( node ) , A . degree ( node ) ) <EOL> assert_equal ( sum ( d for n , d in G . degree ( ) ) , sum ( d for n , d in A . degree ( ) ) ) <EOL> assert_equal ( sum ( d for n , d in A . degree ( ) ) , <EOL> sum ( d for n , d in A . degree ( weight = '<STR_LIT>' ) ) ) <EOL> assert_equal ( sum ( d for n , d in G . degree ( nodes ) ) , <EOL> sum ( d for n , d in A . degree ( nodes ) ) ) </s>
