<s> from nose . tools import * <EOL> import networkx as nx <EOL> class TestMST : <EOL> def setUp ( self ) : <EOL> G = nx . Graph ( ) <EOL> edgelist = [ ( <NUM_LIT:0> , <NUM_LIT:3> , [ ( '<STR_LIT>' , <NUM_LIT:5> ) ] ) , <EOL> ( <NUM_LIT:0> , <NUM_LIT:1> , [ ( '<STR_LIT>' , <NUM_LIT:7> ) ] ) , <EOL> ( <NUM_LIT:1> , <NUM_LIT:3> , [ ( '<STR_LIT>' , <NUM_LIT:9> ) ] ) , <EOL> ( <NUM_LIT:1> , <NUM_LIT:2> , [ ( '<STR_LIT>' , <NUM_LIT:8> ) ] ) , <EOL> ( <NUM_LIT:1> , <NUM_LIT:4> , [ ( '<STR_LIT>' , <NUM_LIT:7> ) ] ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:4> , [ ( '<STR_LIT>' , <NUM_LIT:15> ) ] ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:5> , [ ( '<STR_LIT>' , <NUM_LIT:6> ) ] ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:4> , [ ( '<STR_LIT>' , <NUM_LIT:5> ) ] ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:5> , [ ( '<STR_LIT>' , <NUM_LIT:8> ) ] ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:6> , [ ( '<STR_LIT>' , <NUM_LIT:9> ) ] ) , <EOL> ( <NUM_LIT:5> , <NUM_LIT:6> , [ ( '<STR_LIT>' , <NUM_LIT:11> ) ] ) ] <EOL> G . add_edges_from ( edgelist ) <EOL> self . G = G <EOL> tree_edgelist = [ ( <NUM_LIT:0> , <NUM_LIT:1> , { '<STR_LIT>' : <NUM_LIT:7> } ) , <EOL> ( <NUM_LIT:0> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:5> } ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:5> , { '<STR_LIT>' : <NUM_LIT:6> } ) , <EOL> ( <NUM_LIT:1> , <NUM_LIT:4> , { '<STR_LIT>' : <NUM_LIT:7> } ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:2> , { '<STR_LIT>' : <NUM_LIT:5> } ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:6> , { '<STR_LIT>' : <NUM_LIT:9> } ) ] <EOL> self . tree_edgelist = sorted ( ( sorted ( ( u , v ) ) [ <NUM_LIT:0> ] , sorted ( ( u , v ) ) [ <NUM_LIT:1> ] , d ) <EOL> for u , v , d in tree_edgelist ) <EOL> def test_mst ( self ) : <EOL> T = nx . minimum_spanning_tree ( self . G ) <EOL> assert_equal ( T . edges ( data = True ) , self . tree_edgelist ) <EOL> def test_mst_edges ( self ) : <EOL> edgelist = sorted ( nx . minimum_spanning_edges ( self . G ) ) <EOL> assert_equal ( edgelist , self . tree_edgelist ) <EOL> def test_mst_disconnected ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_path ( [ <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> G . add_path ( [ <NUM_LIT:10> , <NUM_LIT:20> ] ) <EOL> T = nx . minimum_spanning_tree ( G ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:20> , <NUM_LIT:10> ) ] ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:10> , <NUM_LIT:20> ] ) <EOL> def test_mst_isolate ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_nodes_from ( [ <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> T = nx . minimum_spanning_tree ( G ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ] ) <EOL> def test_mst_attributes ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:2> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:7> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:3> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:2> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:3> , weight = <NUM_LIT:10> , color = '<STR_LIT>' , distance = <NUM_LIT:1> ) <EOL> G . add_node ( <NUM_LIT> , color = '<STR_LIT>' ) <EOL> G . graph [ '<STR_LIT:foo>' ] = '<STR_LIT:bar>' <EOL> T = nx . minimum_spanning_tree ( G ) <EOL> assert_equal ( T . graph , G . graph ) <EOL> assert_equal ( T . node [ <NUM_LIT> ] , G . node [ <NUM_LIT> ] ) <EOL> assert_equal ( T . edge [ <NUM_LIT:1> ] [ <NUM_LIT:2> ] , G . edge [ <NUM_LIT:1> ] [ <NUM_LIT:2> ] ) <EOL> def test_mst_edges_specify_weight ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:2> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:7> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:3> , weight = <NUM_LIT:30> , color = '<STR_LIT>' , distance = <NUM_LIT:1> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:3> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:1> ) <EOL> G . add_node ( <NUM_LIT> , color = '<STR_LIT>' ) <EOL> G . graph [ '<STR_LIT:foo>' ] = '<STR_LIT:bar>' <EOL> T = nx . minimum_spanning_tree ( G ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ] ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) ] ) <EOL> T = nx . minimum_spanning_tree ( G , weight = '<STR_LIT>' ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ( <NUM_LIT:1> , <NUM_LIT:3> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) ] ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ] ) <EOL> def test_prim_mst ( self ) : <EOL> T = nx . prim_mst ( self . G ) <EOL> assert_equal ( T . edges ( data = True ) , self . tree_edgelist ) <EOL> def test_prim_mst_edges ( self ) : <EOL> edgelist = sorted ( nx . prim_mst_edges ( self . G ) ) <EOL> edgelist = sorted ( ( sorted ( ( u , v ) ) [ <NUM_LIT:0> ] , sorted ( ( u , v ) ) [ <NUM_LIT:1> ] , d ) <EOL> for u , v , d in edgelist ) <EOL> assert_equal ( edgelist , self . tree_edgelist ) <EOL> def test_prim_mst_disconnected ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_path ( [ <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> G . add_path ( [ <NUM_LIT:10> , <NUM_LIT:20> ] ) <EOL> T = nx . prim_mst ( G ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:20> , <NUM_LIT:10> ) ] ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:10> , <NUM_LIT:20> ] ) <EOL> def test_prim_mst_isolate ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_nodes_from ( [ <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> T = nx . prim_mst ( G ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> ] ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ] ) <EOL> def test_prim_mst_attributes ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:2> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:7> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:3> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:2> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:3> , weight = <NUM_LIT:10> , color = '<STR_LIT>' , distance = <NUM_LIT:1> ) <EOL> G . add_node ( <NUM_LIT> , color = '<STR_LIT>' ) <EOL> G . graph [ '<STR_LIT:foo>' ] = '<STR_LIT:bar>' <EOL> T = nx . prim_mst ( G ) <EOL> assert_equal ( T . graph , G . graph ) <EOL> assert_equal ( T . node [ <NUM_LIT> ] , G . node [ <NUM_LIT> ] ) <EOL> assert_equal ( T . edge [ <NUM_LIT:1> ] [ <NUM_LIT:2> ] , G . edge [ <NUM_LIT:1> ] [ <NUM_LIT:2> ] ) <EOL> def test_prim_mst_edges_specify_weight ( self ) : <EOL> G = nx . Graph ( ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:2> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:7> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:3> , weight = <NUM_LIT:30> , color = '<STR_LIT>' , distance = <NUM_LIT:1> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:3> , weight = <NUM_LIT:1> , color = '<STR_LIT>' , distance = <NUM_LIT:1> ) <EOL> G . add_node ( <NUM_LIT> , color = '<STR_LIT>' ) <EOL> G . graph [ '<STR_LIT:foo>' ] = '<STR_LIT:bar>' <EOL> T = nx . prim_mst ( G ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ] ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) ] ) <EOL> T = nx . prim_mst ( G , weight = '<STR_LIT>' ) <EOL> assert_equal ( sorted ( T . edges ( ) ) , [ ( <NUM_LIT:1> , <NUM_LIT:3> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) ] ) <EOL> assert_equal ( sorted ( T . nodes ( ) ) , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ] ) </s>
