<s> from nose import SkipTest <EOL> from nose . tools import * <EOL> import networkx as nx <EOL> try : <EOL> import numpy as np <EOL> except : <EOL> raise SkipTest ( '<STR_LIT>' ) <EOL> from networkx . algorithms . tree import branchings <EOL> from networkx . algorithms . tree import recognition <EOL> from networkx . testing import * <EOL> G_array = np . array ( [ <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:12> , <NUM_LIT:0> , <NUM_LIT:12> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:12> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:5> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:12> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:12> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:15> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:15> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT> , <NUM_LIT:0> ] , <EOL> ] , dtype = int ) <EOL> def G1 ( ) : <EOL> G = nx . DiGraph ( ) <EOL> G = nx . from_numpy_matrix ( G_array , create_using = G ) <EOL> G = nx . MultiDiGraph ( G ) <EOL> return G <EOL> def G2 ( ) : <EOL> G = nx . DiGraph ( ) <EOL> Garr = G_array . copy ( ) <EOL> Garr [ np . nonzero ( Garr ) ] -= <NUM_LIT:10> <EOL> G = nx . from_numpy_matrix ( Garr , create_using = G ) <EOL> G = nx . MultiDiGraph ( G ) <EOL> return G <EOL> optimal_arborescence_1 = [ <EOL> ( <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:12> ) , ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT> ) , ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ) , ( <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT> ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT> ) , ( <NUM_LIT:3> , <NUM_LIT:6> , <NUM_LIT> ) , ( <NUM_LIT:6> , <NUM_LIT:8> , <NUM_LIT:15> ) , ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT> ) , <EOL> ] <EOL> optimal_branching_2a = [ <EOL> ( <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT:4> ) , ( <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:11> ) , ( <NUM_LIT:6> , <NUM_LIT:8> , <NUM_LIT:5> ) , ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT:8> ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:7> ) , ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:11> ) , ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:7> ) , <EOL> ] <EOL> optimal_branching_2b = [ <EOL> ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT:8> ) , ( <NUM_LIT:7> , <NUM_LIT:3> , <NUM_LIT:9> ) , ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:7> ) , ( <NUM_LIT:3> , <NUM_LIT:6> , <NUM_LIT:8> ) , <EOL> ( <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:11> ) , ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:7> ) , ( <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT:3> ) , <EOL> ] <EOL> optimal_arborescence_2 = [ <EOL> ( <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:7> ) , ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:11> ) , ( <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT:3> ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:7> ) , ( <NUM_LIT:3> , <NUM_LIT:6> , <NUM_LIT:8> ) , ( <NUM_LIT:6> , <NUM_LIT:8> , <NUM_LIT:5> ) , ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT:8> ) , <EOL> ] <EOL> greedy_subopt_branching_1a = [ <EOL> ( <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT> ) , ( <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT> ) , ( <NUM_LIT:6> , <NUM_LIT:8> , <NUM_LIT:15> ) , ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT> ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT> ) , ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ) , ( <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:5> ) , ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT> ) , <EOL> ] <EOL> greedy_subopt_branching_1b = [ <EOL> ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT> ) , ( <NUM_LIT:7> , <NUM_LIT:6> , <NUM_LIT:15> ) , ( <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT> ) , ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT> ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ) , ( <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT> ) , ( <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:5> ) , ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT> ) , <EOL> ] <EOL> def build_branching ( edges ) : <EOL> G = nx . DiGraph ( ) <EOL> for u , v , weight in edges : <EOL> G . add_edge ( u , v , weight = weight ) <EOL> return G <EOL> def sorted_edges ( G , attr = '<STR_LIT>' , default = <NUM_LIT:1> ) : <EOL> edges = [ ( u , v , data . get ( attr , default ) ) for ( u , v , data ) in G . edges ( data = True ) ] <EOL> edges = sorted ( edges , key = lambda x : x [ <NUM_LIT:2> ] ) <EOL> return edges <EOL> def assert_equal_branchings ( G1 , G2 , attr = '<STR_LIT>' , default = <NUM_LIT:1> ) : <EOL> edges1 = list ( G1 . edges ( data = True ) ) <EOL> edges2 = list ( G2 . edges ( data = True ) ) <EOL> e1 = sorted_edges ( G1 , attr , default ) <EOL> e2 = sorted_edges ( G2 , attr , default ) <EOL> print ( e1 ) <EOL> print ( e2 ) <EOL> print <EOL> for a , b in zip ( e1 , e2 ) : <EOL> assert_equal ( a [ : <NUM_LIT:2> ] , b [ : <NUM_LIT:2> ] ) <EOL> np . testing . assert_almost_equal ( a [ <NUM_LIT:2> ] , b [ <NUM_LIT:2> ] ) <EOL> assert_equal ( len ( edges1 ) , len ( edges2 ) ) <EOL> def test_optimal_branching1 ( ) : <EOL> G = build_branching ( optimal_arborescence_1 ) <EOL> assert_true ( recognition . is_arborescence ( G ) , True ) <EOL> assert_equal ( branchings . branching_weight ( G ) , <NUM_LIT> ) <EOL> def test_optimal_branching2a ( ) : <EOL> G = build_branching ( optimal_branching_2a ) <EOL> assert_true ( recognition . is_arborescence ( G ) , True ) <EOL> assert_equal ( branchings . branching_weight ( G ) , <NUM_LIT> ) <EOL> def test_optimal_branching2b ( ) : <EOL> G = build_branching ( optimal_branching_2b ) <EOL> assert_true ( recognition . is_arborescence ( G ) , True ) <EOL> assert_equal ( branchings . branching_weight ( G ) , <NUM_LIT> ) <EOL> def test_optimal_arborescence2 ( ) : <EOL> G = build_branching ( optimal_arborescence_2 ) <EOL> assert_true ( recognition . is_arborescence ( G ) , True ) <EOL> assert_equal ( branchings . branching_weight ( G ) , <NUM_LIT> ) <EOL> def test_greedy_suboptimal_branching1a ( ) : <EOL> G = build_branching ( greedy_subopt_branching_1a ) <EOL> assert_true ( recognition . is_arborescence ( G ) , True ) <EOL> assert_equal ( branchings . branching_weight ( G ) , <NUM_LIT> ) <EOL> def test_greedy_suboptimal_branching1b ( ) : <EOL> G = build_branching ( greedy_subopt_branching_1b ) <EOL> assert_true ( recognition . is_arborescence ( G ) , True ) <EOL> assert_equal ( branchings . branching_weight ( G ) , <NUM_LIT> ) <EOL> def test_greedy_max1 ( ) : <EOL> G = G1 ( ) <EOL> B = branchings . greedy_branching ( G ) <EOL> B_ = build_branching ( greedy_subopt_branching_1b ) <EOL> assert_equal_branchings ( B , B_ ) <EOL> def test_greedy_max2 ( ) : <EOL> G = G1 ( ) <EOL> del G [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] [ '<STR_LIT>' ] <EOL> B = branchings . greedy_branching ( G , default = <NUM_LIT:6> ) <EOL> edges = [ <EOL> ( <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:6> ) , ( <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT> ) , ( <NUM_LIT:7> , <NUM_LIT:6> , <NUM_LIT:15> ) , ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT> ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT> ) , ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT> ) , ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT> ) , ( <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT> ) , <EOL> ] <EOL> B_ = build_branching ( edges ) <EOL> assert_equal_branchings ( B , B_ ) <EOL> def test_greedy_max3 ( ) : <EOL> G = G1 ( ) <EOL> B = branchings . greedy_branching ( G , attr = None ) <EOL> edges = [ <EOL> ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT:1> ) , ( <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:1> ) , ( <NUM_LIT:5> , <NUM_LIT:8> , <NUM_LIT:1> ) , <EOL> ( <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:1> ) , ( <NUM_LIT:7> , <NUM_LIT:3> , <NUM_LIT:1> ) , ( <NUM_LIT:7> , <NUM_LIT:6> , <NUM_LIT:1> ) , ( <NUM_LIT:8> , <NUM_LIT:7> , <NUM_LIT:1> ) , <EOL> ] <EOL> B_ = build_branching ( edges ) <EOL> assert_equal_branchings ( B , B_ , default = <NUM_LIT:1> ) <EOL> def test_greedy_min ( ) : <EOL> G = G1 ( ) <EOL> B = branchings . greedy_branching ( G , kind = '<STR_LIT>' ) <EOL> edges = [ <EOL> ( <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:4> ) , ( <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:12> ) , ( <NUM_LIT:0> , <NUM_LIT:4> , <NUM_LIT:12> ) , ( <NUM_LIT:2> , <NUM_LIT:5> , <NUM_LIT:12> ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:7> , <NUM_LIT:12> ) , ( <NUM_LIT:5> , <NUM_LIT:8> , <NUM_LIT:12> ) , ( <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT> ) , ( <NUM_LIT:7> , <NUM_LIT:3> , <NUM_LIT> ) <EOL> ] <EOL> B_ = build_branching ( edges ) <EOL> assert_equal_branchings ( B , B_ ) <EOL> def test_edmonds1_maxbranch ( ) : <EOL> G = G1 ( ) <EOL> x = branchings . maximum_branching ( G ) <EOL> x_ = build_branching ( optimal_arborescence_1 ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_edmonds1_maxarbor ( ) : <EOL> G = G1 ( ) <EOL> x = branchings . maximum_spanning_arborescence ( G ) <EOL> x_ = build_branching ( optimal_arborescence_1 ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_edmonds2_maxbranch ( ) : <EOL> G = G2 ( ) <EOL> x = branchings . maximum_branching ( G ) <EOL> x_ = build_branching ( optimal_branching_2a ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_edmonds2_maxarbor ( ) : <EOL> G = G2 ( ) <EOL> x = branchings . maximum_spanning_arborescence ( G ) <EOL> x_ = build_branching ( optimal_arborescence_2 ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_edmonds2_minarbor ( ) : <EOL> G = G1 ( ) <EOL> x = branchings . minimum_spanning_arborescence ( G ) <EOL> edges = [ <EOL> ( <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:5> ) , ( <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:12> ) , ( <NUM_LIT:0> , <NUM_LIT:4> , <NUM_LIT:12> ) , ( <NUM_LIT:2> , <NUM_LIT:5> , <NUM_LIT:12> ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:7> , <NUM_LIT:12> ) , ( <NUM_LIT:5> , <NUM_LIT:8> , <NUM_LIT:12> ) , ( <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT> ) , ( <NUM_LIT:2> , <NUM_LIT:1> , <NUM_LIT> ) <EOL> ] <EOL> x_ = build_branching ( edges ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_edmonds3_minbranch1 ( ) : <EOL> G = G1 ( ) <EOL> x = branchings . minimum_branching ( G ) <EOL> edges = [ ] <EOL> x_ = build_branching ( edges ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_edmonds3_minbranch2 ( ) : <EOL> G = G1 ( ) <EOL> G . add_edge ( <NUM_LIT:8> , <NUM_LIT:9> , weight = - <NUM_LIT:10> ) <EOL> x = branchings . minimum_branching ( G ) <EOL> edges = [ ( <NUM_LIT:8> , <NUM_LIT:9> , - <NUM_LIT:10> ) ] <EOL> x_ = build_branching ( edges ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> def test_mst ( ) : <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> G = G . to_directed ( ) <EOL> x = branchings . minimum_spanning_arborescence ( G ) <EOL> edges = [ ( set ( [ <NUM_LIT:0> , <NUM_LIT:1> ] ) , <NUM_LIT:7> ) , ( set ( [ <NUM_LIT:0> , <NUM_LIT:3> ] ) , <NUM_LIT:5> ) , ( set ( [ <NUM_LIT:3> , <NUM_LIT:5> ] ) , <NUM_LIT:6> ) , <EOL> ( set ( [ <NUM_LIT:1> , <NUM_LIT:4> ] ) , <NUM_LIT:7> ) , ( set ( [ <NUM_LIT:4> , <NUM_LIT:2> ] ) , <NUM_LIT:5> ) , ( set ( [ <NUM_LIT:4> , <NUM_LIT:6> ] ) , <NUM_LIT:9> ) ] <EOL> assert_equal ( x . number_of_edges ( ) , len ( edges ) ) <EOL> for u , v , d in x . edges ( data = True ) : <EOL> assert_true ( ( set ( [ u , v ] ) , d [ '<STR_LIT>' ] ) in edges ) <EOL> def test_mixed_nodetypes ( ) : <EOL> G = nx . Graph ( ) <EOL> edgelist = [ ( <NUM_LIT:0> , <NUM_LIT:3> , [ ( '<STR_LIT>' , <NUM_LIT:5> ) ] ) , <EOL> ( <NUM_LIT:0> , '<STR_LIT:1>' , [ ( '<STR_LIT>' , <NUM_LIT:5> ) ] ) ] <EOL> G . add_edges_from ( edgelist ) <EOL> G = G . to_directed ( ) <EOL> x = branchings . minimum_spanning_arborescence ( G ) <EOL> def test_edmonds1_minbranch ( ) : <EOL> edges = [ ( u , v , - w ) for ( u , v , w ) in optimal_arborescence_1 ] <EOL> G = nx . DiGraph ( ) <EOL> G = nx . from_numpy_matrix ( - G_array , create_using = G ) <EOL> x = branchings . maximum_branching ( G ) <EOL> x_ = build_branching ( [ ] ) <EOL> assert_equal_branchings ( x , x_ ) <EOL> x = branchings . minimum_branching ( G ) <EOL> x_ = build_branching ( edges ) <EOL> assert_equal_branchings ( x , x_ ) </s>
