<s> import networkx as nx <EOL> from nose . tools import assert_equal , assert_raises <EOL> import os <EOL> class TestMinCostFlow : <EOL> def test_simple_digraph ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( '<STR_LIT:a>' , demand = - <NUM_LIT:5> ) <EOL> G . add_node ( '<STR_LIT:d>' , demand = <NUM_LIT:5> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , weight = <NUM_LIT:3> , capacity = <NUM_LIT:4> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:c>' , weight = <NUM_LIT:6> , capacity = <NUM_LIT:10> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:d>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:9> ) <EOL> G . add_edge ( '<STR_LIT:c>' , '<STR_LIT:d>' , weight = <NUM_LIT:2> , capacity = <NUM_LIT:5> ) <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> soln = { '<STR_LIT:a>' : { '<STR_LIT:b>' : <NUM_LIT:4> , '<STR_LIT:c>' : <NUM_LIT:1> } , <EOL> '<STR_LIT:b>' : { '<STR_LIT:d>' : <NUM_LIT:4> } , <EOL> '<STR_LIT:c>' : { '<STR_LIT:d>' : <NUM_LIT:1> } , <EOL> '<STR_LIT:d>' : { } } <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( nx . min_cost_flow_cost ( G ) , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . min_cost_flow ( G ) , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> def test_negcycle_infcap ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( '<STR_LIT:s>' , demand = - <NUM_LIT:5> ) <EOL> G . add_node ( '<STR_LIT:t>' , demand = <NUM_LIT:5> ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:a>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , weight = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:c>' , '<STR_LIT:a>' , weight = - <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:d>' , weight = <NUM_LIT:1> ) <EOL> G . add_edge ( '<STR_LIT:d>' , '<STR_LIT:c>' , weight = - <NUM_LIT:2> ) <EOL> G . add_edge ( '<STR_LIT:d>' , '<STR_LIT:t>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:3> ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . capacity_scaling , G ) <EOL> def test_sum_demands_not_zero ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( '<STR_LIT:s>' , demand = - <NUM_LIT:5> ) <EOL> G . add_node ( '<STR_LIT:t>' , demand = <NUM_LIT:4> ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:a>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , weight = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:c>' , weight = - <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:d>' , weight = <NUM_LIT:1> ) <EOL> G . add_edge ( '<STR_LIT:c>' , '<STR_LIT:d>' , weight = - <NUM_LIT:2> ) <EOL> G . add_edge ( '<STR_LIT:d>' , '<STR_LIT:t>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:3> ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . capacity_scaling , G ) <EOL> def test_no_flow_satisfying_demands ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( '<STR_LIT:s>' , demand = - <NUM_LIT:5> ) <EOL> G . add_node ( '<STR_LIT:t>' , demand = <NUM_LIT:5> ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:a>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , weight = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:c>' , weight = - <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:d>' , weight = <NUM_LIT:1> ) <EOL> G . add_edge ( '<STR_LIT:c>' , '<STR_LIT:d>' , weight = - <NUM_LIT:2> ) <EOL> G . add_edge ( '<STR_LIT:d>' , '<STR_LIT:t>' , weight = <NUM_LIT:1> , capacity = <NUM_LIT:3> ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . capacity_scaling , G ) <EOL> def test_transshipment ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( '<STR_LIT:a>' , demand = <NUM_LIT:1> ) <EOL> G . add_node ( '<STR_LIT:b>' , demand = - <NUM_LIT:2> ) <EOL> G . add_node ( '<STR_LIT:c>' , demand = - <NUM_LIT:2> ) <EOL> G . add_node ( '<STR_LIT:d>' , demand = <NUM_LIT:3> ) <EOL> G . add_node ( '<STR_LIT:e>' , demand = - <NUM_LIT:4> ) <EOL> G . add_node ( '<STR_LIT:f>' , demand = - <NUM_LIT:4> ) <EOL> G . add_node ( '<STR_LIT:g>' , demand = <NUM_LIT:3> ) <EOL> G . add_node ( '<STR_LIT:h>' , demand = <NUM_LIT:2> ) <EOL> G . add_node ( '<STR_LIT:r>' , demand = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:c>' , weight = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:r>' , '<STR_LIT:a>' , weight = <NUM_LIT:2> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:a>' , weight = <NUM_LIT:9> ) <EOL> G . add_edge ( '<STR_LIT:r>' , '<STR_LIT:c>' , weight = <NUM_LIT:0> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:r>' , weight = - <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:c>' , '<STR_LIT:d>' , weight = <NUM_LIT:5> ) <EOL> G . add_edge ( '<STR_LIT:e>' , '<STR_LIT:r>' , weight = <NUM_LIT:4> ) <EOL> G . add_edge ( '<STR_LIT:e>' , '<STR_LIT:f>' , weight = <NUM_LIT:3> ) <EOL> G . add_edge ( '<STR_LIT:h>' , '<STR_LIT:b>' , weight = <NUM_LIT:4> ) <EOL> G . add_edge ( '<STR_LIT:f>' , '<STR_LIT:d>' , weight = <NUM_LIT:7> ) <EOL> G . add_edge ( '<STR_LIT:f>' , '<STR_LIT:h>' , weight = <NUM_LIT:12> ) <EOL> G . add_edge ( '<STR_LIT:g>' , '<STR_LIT:d>' , weight = <NUM_LIT:12> ) <EOL> G . add_edge ( '<STR_LIT:f>' , '<STR_LIT:g>' , weight = - <NUM_LIT:1> ) <EOL> G . add_edge ( '<STR_LIT:h>' , '<STR_LIT:g>' , weight = - <NUM_LIT:10> ) <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> soln = { '<STR_LIT:a>' : { '<STR_LIT:c>' : <NUM_LIT:0> } , <EOL> '<STR_LIT:b>' : { '<STR_LIT:a>' : <NUM_LIT:0> , '<STR_LIT:r>' : <NUM_LIT:2> } , <EOL> '<STR_LIT:c>' : { '<STR_LIT:d>' : <NUM_LIT:3> } , <EOL> '<STR_LIT:d>' : { } , <EOL> '<STR_LIT:e>' : { '<STR_LIT:r>' : <NUM_LIT:3> , '<STR_LIT:f>' : <NUM_LIT:1> } , <EOL> '<STR_LIT:f>' : { '<STR_LIT:d>' : <NUM_LIT:0> , '<STR_LIT:g>' : <NUM_LIT:3> , '<STR_LIT:h>' : <NUM_LIT:2> } , <EOL> '<STR_LIT:g>' : { '<STR_LIT:d>' : <NUM_LIT:0> } , <EOL> '<STR_LIT:h>' : { '<STR_LIT:b>' : <NUM_LIT:0> , '<STR_LIT:g>' : <NUM_LIT:0> } , <EOL> '<STR_LIT:r>' : { '<STR_LIT:a>' : <NUM_LIT:1> , '<STR_LIT:c>' : <NUM_LIT:1> } } <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( nx . min_cost_flow_cost ( G ) , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . min_cost_flow ( G ) , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> def test_max_flow_min_cost ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:a>' , bandwidth = <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:c>' , bandwidth = <NUM_LIT:10> , cost = <NUM_LIT:10> ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , cost = <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:d>' , bandwidth = <NUM_LIT:8> , cost = <NUM_LIT:7> ) <EOL> G . add_edge ( '<STR_LIT:c>' , '<STR_LIT:d>' , cost = <NUM_LIT:10> ) <EOL> G . add_edge ( '<STR_LIT:d>' , '<STR_LIT:t>' , bandwidth = <NUM_LIT:5> , cost = <NUM_LIT:5> ) <EOL> soln = { '<STR_LIT:s>' : { '<STR_LIT:a>' : <NUM_LIT:5> , '<STR_LIT:c>' : <NUM_LIT:0> } , <EOL> '<STR_LIT:a>' : { '<STR_LIT:b>' : <NUM_LIT:5> } , <EOL> '<STR_LIT:b>' : { '<STR_LIT:d>' : <NUM_LIT:5> } , <EOL> '<STR_LIT:c>' : { '<STR_LIT:d>' : <NUM_LIT:0> } , <EOL> '<STR_LIT:d>' : { '<STR_LIT:t>' : <NUM_LIT:5> } , <EOL> '<STR_LIT:t>' : { } } <EOL> flow = nx . max_flow_min_cost ( G , '<STR_LIT:s>' , '<STR_LIT:t>' , capacity = '<STR_LIT>' , <EOL> weight = '<STR_LIT>' ) <EOL> assert_equal ( flow , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , flow , weight = '<STR_LIT>' ) , <NUM_LIT> ) <EOL> G . add_edge ( '<STR_LIT:t>' , '<STR_LIT:s>' , cost = - <NUM_LIT:100> ) <EOL> flowCost , flow = nx . capacity_scaling ( G , capacity = '<STR_LIT>' , <EOL> weight = '<STR_LIT>' ) <EOL> G . remove_edge ( '<STR_LIT:t>' , '<STR_LIT:s>' ) <EOL> assert_equal ( flowCost , - <NUM_LIT> ) <EOL> assert_equal ( flow [ '<STR_LIT:t>' ] [ '<STR_LIT:s>' ] , <NUM_LIT:5> ) <EOL> del flow [ '<STR_LIT:t>' ] [ '<STR_LIT:s>' ] <EOL> assert_equal ( flow , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , flow , weight = '<STR_LIT>' ) , <NUM_LIT> ) <EOL> def test_digraph1 ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( <NUM_LIT:1> , demand = - <NUM_LIT:20> ) <EOL> G . add_node ( <NUM_LIT:4> , demand = <NUM_LIT:5> ) <EOL> G . add_node ( <NUM_LIT:5> , demand = <NUM_LIT:15> ) <EOL> G . add_edges_from ( [ ( <NUM_LIT:1> , <NUM_LIT:2> , { '<STR_LIT>' : <NUM_LIT:15> , '<STR_LIT>' : <NUM_LIT:4> } ) , <EOL> ( <NUM_LIT:1> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:8> , '<STR_LIT>' : <NUM_LIT:4> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:2> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:4> , { '<STR_LIT>' : <NUM_LIT:4> , '<STR_LIT>' : <NUM_LIT:2> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:5> , { '<STR_LIT>' : <NUM_LIT:10> , '<STR_LIT>' : <NUM_LIT:6> } ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:4> , { '<STR_LIT>' : <NUM_LIT:15> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:5> , { '<STR_LIT>' : <NUM_LIT:5> , '<STR_LIT>' : <NUM_LIT:3> } ) , <EOL> ( <NUM_LIT:4> , <NUM_LIT:5> , { '<STR_LIT>' : <NUM_LIT:2> } ) , <EOL> ( <NUM_LIT:5> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:4> , '<STR_LIT>' : <NUM_LIT:1> } ) ] ) <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> soln = { <NUM_LIT:1> : { <NUM_LIT:2> : <NUM_LIT:12> , <NUM_LIT:3> : <NUM_LIT:8> } , <EOL> <NUM_LIT:2> : { <NUM_LIT:3> : <NUM_LIT:8> , <NUM_LIT:4> : <NUM_LIT:4> , <NUM_LIT:5> : <NUM_LIT:0> } , <EOL> <NUM_LIT:3> : { <NUM_LIT:4> : <NUM_LIT:11> , <NUM_LIT:5> : <NUM_LIT:5> } , <EOL> <NUM_LIT:4> : { <NUM_LIT:5> : <NUM_LIT:10> } , <EOL> <NUM_LIT:5> : { <NUM_LIT:3> : <NUM_LIT:0> } } <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( nx . min_cost_flow_cost ( G ) , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . min_cost_flow ( G ) , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> def test_digraph2 ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_edge ( '<STR_LIT:s>' , <NUM_LIT:1> , capacity = <NUM_LIT:12> ) <EOL> G . add_edge ( '<STR_LIT:s>' , <NUM_LIT:2> , capacity = <NUM_LIT:6> ) <EOL> G . add_edge ( '<STR_LIT:s>' , <NUM_LIT:3> , capacity = <NUM_LIT> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:2> , capacity = <NUM_LIT:11> , weight = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:3> , capacity = <NUM_LIT:9> , weight = <NUM_LIT:6> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:4> , capacity = <NUM_LIT:5> , weight = <NUM_LIT:5> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:5> , capacity = <NUM_LIT:2> , weight = <NUM_LIT:12> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:5> , capacity = <NUM_LIT:4> , weight = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:2> , <NUM_LIT:6> , capacity = <NUM_LIT:2> , weight = <NUM_LIT:6> ) <EOL> G . add_edge ( <NUM_LIT:3> , <NUM_LIT:6> , capacity = <NUM_LIT> , weight = <NUM_LIT:3> ) <EOL> G . add_edge ( <NUM_LIT:4> , <NUM_LIT:5> , capacity = <NUM_LIT> , weight = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:5> , <NUM_LIT:6> , capacity = <NUM_LIT:9> , weight = <NUM_LIT:5> ) <EOL> G . add_edge ( <NUM_LIT:4> , '<STR_LIT:t>' , capacity = <NUM_LIT:3> ) <EOL> G . add_edge ( <NUM_LIT:5> , '<STR_LIT:t>' , capacity = <NUM_LIT:7> ) <EOL> G . add_edge ( <NUM_LIT:6> , '<STR_LIT:t>' , capacity = <NUM_LIT> ) <EOL> flow = nx . max_flow_min_cost ( G , '<STR_LIT:s>' , '<STR_LIT:t>' ) <EOL> soln = { <NUM_LIT:1> : { <NUM_LIT:2> : <NUM_LIT:6> , <NUM_LIT:4> : <NUM_LIT:5> , <NUM_LIT:5> : <NUM_LIT:1> } , <EOL> <NUM_LIT:2> : { <NUM_LIT:3> : <NUM_LIT:6> , <NUM_LIT:5> : <NUM_LIT:4> , <NUM_LIT:6> : <NUM_LIT:2> } , <EOL> <NUM_LIT:3> : { <NUM_LIT:6> : <NUM_LIT:20> } , <EOL> <NUM_LIT:4> : { <NUM_LIT:5> : <NUM_LIT:2> , '<STR_LIT:t>' : <NUM_LIT:3> } , <EOL> <NUM_LIT:5> : { <NUM_LIT:6> : <NUM_LIT:0> , '<STR_LIT:t>' : <NUM_LIT:7> } , <EOL> <NUM_LIT:6> : { '<STR_LIT:t>' : <NUM_LIT> } , <EOL> '<STR_LIT:s>' : { <NUM_LIT:1> : <NUM_LIT:12> , <NUM_LIT:2> : <NUM_LIT:6> , <NUM_LIT:3> : <NUM_LIT> } , <EOL> '<STR_LIT:t>' : { } } <EOL> assert_equal ( flow , soln ) <EOL> G . add_edge ( '<STR_LIT:t>' , '<STR_LIT:s>' , weight = - <NUM_LIT:100> ) <EOL> flowCost , flow = nx . capacity_scaling ( G ) <EOL> G . remove_edge ( '<STR_LIT:t>' , '<STR_LIT:s>' ) <EOL> assert_equal ( flow [ '<STR_LIT:t>' ] [ '<STR_LIT:s>' ] , <NUM_LIT:32> ) <EOL> assert_equal ( flowCost , - <NUM_LIT> ) <EOL> del flow [ '<STR_LIT:t>' ] [ '<STR_LIT:s>' ] <EOL> assert_equal ( flow , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , flow ) , <NUM_LIT> ) <EOL> def test_digraph3 ( self ) : <EOL> """<STR_LIT>""" <EOL> G = nx . DiGraph ( ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:a>' , { <NUM_LIT:0> : <NUM_LIT:2> , <NUM_LIT:1> : <NUM_LIT:4> } ) <EOL> G . add_edge ( '<STR_LIT:s>' , '<STR_LIT:b>' , { <NUM_LIT:0> : <NUM_LIT:2> , <NUM_LIT:1> : <NUM_LIT:1> } ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , { <NUM_LIT:0> : <NUM_LIT:5> , <NUM_LIT:1> : <NUM_LIT:2> } ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:t>' , { <NUM_LIT:0> : <NUM_LIT:1> , <NUM_LIT:1> : <NUM_LIT:5> } ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:a>' , { <NUM_LIT:0> : <NUM_LIT:1> , <NUM_LIT:1> : <NUM_LIT:3> } ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:t>' , { <NUM_LIT:0> : <NUM_LIT:3> , <NUM_LIT:1> : <NUM_LIT:2> } ) <EOL> "<STR_LIT>" <EOL> sol = nx . max_flow_min_cost ( G , '<STR_LIT:s>' , '<STR_LIT:t>' , capacity = <NUM_LIT:0> , weight = <NUM_LIT:1> ) <EOL> flow = sum ( v for v in sol [ '<STR_LIT:s>' ] . values ( ) ) <EOL> assert_equal ( <NUM_LIT:4> , flow ) <EOL> assert_equal ( <NUM_LIT> , nx . cost_of_flow ( G , sol , weight = <NUM_LIT:1> ) ) <EOL> assert_equal ( sol [ '<STR_LIT:s>' ] , { '<STR_LIT:a>' : <NUM_LIT:2> , '<STR_LIT:b>' : <NUM_LIT:2> } ) <EOL> assert_equal ( sol [ '<STR_LIT:a>' ] , { '<STR_LIT:b>' : <NUM_LIT:1> , '<STR_LIT:t>' : <NUM_LIT:1> } ) <EOL> assert_equal ( sol [ '<STR_LIT:b>' ] , { '<STR_LIT:a>' : <NUM_LIT:0> , '<STR_LIT:t>' : <NUM_LIT:3> } ) <EOL> assert_equal ( sol [ '<STR_LIT:t>' ] , { } ) <EOL> G . add_edge ( '<STR_LIT:t>' , '<STR_LIT:s>' , { <NUM_LIT:1> : - <NUM_LIT:100> } ) <EOL> flowCost , sol = nx . capacity_scaling ( G , capacity = <NUM_LIT:0> , weight = <NUM_LIT:1> ) <EOL> G . remove_edge ( '<STR_LIT:t>' , '<STR_LIT:s>' ) <EOL> flow = sum ( v for v in sol [ '<STR_LIT:s>' ] . values ( ) ) <EOL> assert_equal ( <NUM_LIT:4> , flow ) <EOL> assert_equal ( sol [ '<STR_LIT:t>' ] [ '<STR_LIT:s>' ] , <NUM_LIT:4> ) <EOL> assert_equal ( flowCost , - <NUM_LIT> ) <EOL> del sol [ '<STR_LIT:t>' ] [ '<STR_LIT:s>' ] <EOL> assert_equal ( sol [ '<STR_LIT:s>' ] , { '<STR_LIT:a>' : <NUM_LIT:2> , '<STR_LIT:b>' : <NUM_LIT:2> } ) <EOL> assert_equal ( sol [ '<STR_LIT:a>' ] , { '<STR_LIT:b>' : <NUM_LIT:1> , '<STR_LIT:t>' : <NUM_LIT:1> } ) <EOL> assert_equal ( sol [ '<STR_LIT:b>' ] , { '<STR_LIT:a>' : <NUM_LIT:0> , '<STR_LIT:t>' : <NUM_LIT:3> } ) <EOL> assert_equal ( sol [ '<STR_LIT:t>' ] , { } ) <EOL> assert_equal ( nx . cost_of_flow ( G , sol , weight = <NUM_LIT:1> ) , <NUM_LIT> ) <EOL> def test_zero_capacity_edges ( self ) : <EOL> """<STR_LIT>""" <EOL> G = nx . DiGraph ( ) <EOL> G . add_edges_from ( [ ( <NUM_LIT:1> , <NUM_LIT:2> , { '<STR_LIT>' : <NUM_LIT:1> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:1> , <NUM_LIT:5> , { '<STR_LIT>' : <NUM_LIT:1> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:0> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:5> , { '<STR_LIT>' : <NUM_LIT:1> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:5> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:2> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:5> , <NUM_LIT:4> , { '<STR_LIT>' : <NUM_LIT:0> , '<STR_LIT>' : <NUM_LIT:1> } ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:4> , { '<STR_LIT>' : <NUM_LIT:2> , '<STR_LIT>' : <NUM_LIT:1> } ) ] ) <EOL> G . node [ <NUM_LIT:1> ] [ '<STR_LIT>' ] = - <NUM_LIT:1> <EOL> G . node [ <NUM_LIT:2> ] [ '<STR_LIT>' ] = - <NUM_LIT:1> <EOL> G . node [ <NUM_LIT:4> ] [ '<STR_LIT>' ] = <NUM_LIT:2> <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> soln = { <NUM_LIT:1> : { <NUM_LIT:2> : <NUM_LIT:0> , <NUM_LIT:5> : <NUM_LIT:1> } , <EOL> <NUM_LIT:2> : { <NUM_LIT:3> : <NUM_LIT:0> , <NUM_LIT:5> : <NUM_LIT:1> } , <EOL> <NUM_LIT:3> : { <NUM_LIT:4> : <NUM_LIT:2> } , <EOL> <NUM_LIT:4> : { } , <EOL> <NUM_LIT:5> : { <NUM_LIT:3> : <NUM_LIT:2> , <NUM_LIT:4> : <NUM_LIT:0> } } <EOL> assert_equal ( flowCost , <NUM_LIT:6> ) <EOL> assert_equal ( nx . min_cost_flow_cost ( G ) , <NUM_LIT:6> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . min_cost_flow ( G ) , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT:6> ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT:6> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT:6> ) <EOL> def test_digon ( self ) : <EOL> """<STR_LIT>""" <EOL> nodes = [ ( <NUM_LIT:1> , { } ) , <EOL> ( <NUM_LIT:2> , { '<STR_LIT>' : - <NUM_LIT:4> } ) , <EOL> ( <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:4> } ) , <EOL> ] <EOL> edges = [ ( <NUM_LIT:1> , <NUM_LIT:2> , { '<STR_LIT>' : <NUM_LIT:3> , '<STR_LIT>' : <NUM_LIT> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:1> , { '<STR_LIT>' : <NUM_LIT:2> , '<STR_LIT>' : <NUM_LIT:0> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:5> , '<STR_LIT>' : <NUM_LIT> } ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:2> , { '<STR_LIT>' : <NUM_LIT:2> , '<STR_LIT>' : <NUM_LIT:0> } ) , <EOL> ] <EOL> G = nx . DiGraph ( edges ) <EOL> G . add_nodes_from ( nodes ) <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> soln = { <NUM_LIT:1> : { <NUM_LIT:2> : <NUM_LIT:0> } , <EOL> <NUM_LIT:2> : { <NUM_LIT:1> : <NUM_LIT:0> , <NUM_LIT:3> : <NUM_LIT:4> } , <EOL> <NUM_LIT:3> : { <NUM_LIT:2> : <NUM_LIT:0> } } <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( nx . min_cost_flow_cost ( G ) , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . min_cost_flow ( G ) , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT> ) <EOL> assert_equal ( H , soln ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , <NUM_LIT> ) <EOL> def test_infinite_capacity_neg_digon ( self ) : <EOL> """<STR_LIT>""" <EOL> nodes = [ ( <NUM_LIT:1> , { } ) , <EOL> ( <NUM_LIT:2> , { '<STR_LIT>' : - <NUM_LIT:4> } ) , <EOL> ( <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:4> } ) , <EOL> ] <EOL> edges = [ ( <NUM_LIT:1> , <NUM_LIT:2> , { '<STR_LIT>' : - <NUM_LIT> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:1> , { '<STR_LIT>' : <NUM_LIT:0> } ) , <EOL> ( <NUM_LIT:2> , <NUM_LIT:3> , { '<STR_LIT>' : <NUM_LIT:5> , '<STR_LIT>' : <NUM_LIT> } ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:2> , { '<STR_LIT>' : <NUM_LIT:2> , '<STR_LIT>' : <NUM_LIT:0> } ) , <EOL> ] <EOL> G = nx . DiGraph ( edges ) <EOL> G . add_nodes_from ( nodes ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . capacity_scaling , G ) <EOL> def test_finite_capacity_neg_digon ( self ) : <EOL> """<STR_LIT>""" <EOL> G = nx . DiGraph ( ) <EOL> G . add_edge ( '<STR_LIT:a>' , '<STR_LIT:b>' , capacity = <NUM_LIT:1> , weight = - <NUM_LIT:1> ) <EOL> G . add_edge ( '<STR_LIT:b>' , '<STR_LIT:a>' , capacity = <NUM_LIT:1> , weight = - <NUM_LIT:1> ) <EOL> min_cost = - <NUM_LIT:2> <EOL> assert_equal ( nx . min_cost_flow_cost ( G ) , min_cost ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , - <NUM_LIT:2> ) <EOL> assert_equal ( H , { '<STR_LIT:a>' : { '<STR_LIT:b>' : <NUM_LIT:1> } , '<STR_LIT:b>' : { '<STR_LIT:a>' : <NUM_LIT:1> } } ) <EOL> assert_equal ( nx . cost_of_flow ( G , H ) , - <NUM_LIT:2> ) <EOL> def test_multidigraph ( self ) : <EOL> """<STR_LIT>""" <EOL> G = nx . MultiDiGraph ( ) <EOL> G . add_weighted_edges_from ( [ ( <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:1> ) , ( <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:2> ) ] , weight = '<STR_LIT>' ) <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT:0> ) <EOL> assert_equal ( H , { <NUM_LIT:1> : { <NUM_LIT:2> : { <NUM_LIT:0> : <NUM_LIT:0> } } , <NUM_LIT:2> : { <NUM_LIT:3> : { <NUM_LIT:0> : <NUM_LIT:0> } } , <NUM_LIT:3> : { } } ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT:0> ) <EOL> assert_equal ( H , { <NUM_LIT:1> : { <NUM_LIT:2> : { <NUM_LIT:0> : <NUM_LIT:0> } } , <NUM_LIT:2> : { <NUM_LIT:3> : { <NUM_LIT:0> : <NUM_LIT:0> } } , <NUM_LIT:3> : { } } ) <EOL> def test_negative_selfloops ( self ) : <EOL> """<STR_LIT>""" <EOL> G = nx . DiGraph ( ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:1> , weight = - <NUM_LIT:1> ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . capacity_scaling , G ) <EOL> G [ <NUM_LIT:1> ] [ <NUM_LIT:1> ] [ '<STR_LIT>' ] = <NUM_LIT:2> <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> assert_equal ( flowCost , - <NUM_LIT:2> ) <EOL> assert_equal ( H , { <NUM_LIT:1> : { <NUM_LIT:1> : <NUM_LIT:2> } } ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , - <NUM_LIT:2> ) <EOL> assert_equal ( H , { <NUM_LIT:1> : { <NUM_LIT:1> : <NUM_LIT:2> } } ) <EOL> G = nx . MultiDiGraph ( ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:1> , '<STR_LIT:x>' , weight = - <NUM_LIT:1> ) <EOL> G . add_edge ( <NUM_LIT:1> , <NUM_LIT:1> , '<STR_LIT:y>' , weight = <NUM_LIT:1> ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnbounded , nx . capacity_scaling , G ) <EOL> G [ <NUM_LIT:1> ] [ <NUM_LIT:1> ] [ '<STR_LIT:x>' ] [ '<STR_LIT>' ] = <NUM_LIT:2> <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> assert_equal ( flowCost , - <NUM_LIT:2> ) <EOL> assert_equal ( H , { <NUM_LIT:1> : { <NUM_LIT:1> : { '<STR_LIT:x>' : <NUM_LIT:2> , '<STR_LIT:y>' : <NUM_LIT:0> } } } ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , - <NUM_LIT:2> ) <EOL> assert_equal ( H , { <NUM_LIT:1> : { <NUM_LIT:1> : { '<STR_LIT:x>' : <NUM_LIT:2> , '<STR_LIT:y>' : <NUM_LIT:0> } } } ) <EOL> def test_bone_shaped ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> G . add_node ( <NUM_LIT:0> , demand = - <NUM_LIT:4> ) <EOL> G . add_node ( <NUM_LIT:1> , demand = <NUM_LIT:2> ) <EOL> G . add_node ( <NUM_LIT:2> , demand = <NUM_LIT:2> ) <EOL> G . add_node ( <NUM_LIT:3> , demand = <NUM_LIT:4> ) <EOL> G . add_node ( <NUM_LIT:4> , demand = - <NUM_LIT:2> ) <EOL> G . add_node ( <NUM_LIT:5> , demand = - <NUM_LIT:2> ) <EOL> G . add_edge ( <NUM_LIT:0> , <NUM_LIT:1> , capacity = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:0> , <NUM_LIT:2> , capacity = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:4> , <NUM_LIT:3> , capacity = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:5> , <NUM_LIT:3> , capacity = <NUM_LIT:4> ) <EOL> G . add_edge ( <NUM_LIT:0> , <NUM_LIT:3> , capacity = <NUM_LIT:0> ) <EOL> flowCost , H = nx . network_simplex ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT:0> ) <EOL> assert_equal ( <EOL> H , { <NUM_LIT:0> : { <NUM_LIT:1> : <NUM_LIT:2> , <NUM_LIT:2> : <NUM_LIT:2> , <NUM_LIT:3> : <NUM_LIT:0> } , <NUM_LIT:1> : { } , <NUM_LIT:2> : { } , <NUM_LIT:3> : { } , <NUM_LIT:4> : { <NUM_LIT:3> : <NUM_LIT:2> } , <NUM_LIT:5> : { <NUM_LIT:3> : <NUM_LIT:2> } } ) <EOL> flowCost , H = nx . capacity_scaling ( G ) <EOL> assert_equal ( flowCost , <NUM_LIT:0> ) <EOL> assert_equal ( <EOL> H , { <NUM_LIT:0> : { <NUM_LIT:1> : <NUM_LIT:2> , <NUM_LIT:2> : <NUM_LIT:2> , <NUM_LIT:3> : <NUM_LIT:0> } , <NUM_LIT:1> : { } , <NUM_LIT:2> : { } , <NUM_LIT:3> : { } , <NUM_LIT:4> : { <NUM_LIT:3> : <NUM_LIT:2> } , <NUM_LIT:5> : { <NUM_LIT:3> : <NUM_LIT:2> } } ) <EOL> def test_exceptions ( self ) : <EOL> G = nx . Graph ( ) <EOL> assert_raises ( nx . NetworkXNotImplemented , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXNotImplemented , nx . capacity_scaling , G ) <EOL> G = nx . MultiGraph ( ) <EOL> assert_raises ( nx . NetworkXNotImplemented , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXNotImplemented , nx . capacity_scaling , G ) <EOL> G = nx . DiGraph ( ) <EOL> assert_raises ( nx . NetworkXError , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXError , nx . capacity_scaling , G ) <EOL> G . add_node ( <NUM_LIT:0> , demand = float ( '<STR_LIT>' ) ) <EOL> assert_raises ( nx . NetworkXError , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . capacity_scaling , G ) <EOL> G . node [ <NUM_LIT:0> ] [ '<STR_LIT>' ] = <NUM_LIT:0> <EOL> G . add_node ( <NUM_LIT:1> , demand = <NUM_LIT:0> ) <EOL> G . add_edge ( <NUM_LIT:0> , <NUM_LIT:1> , weight = - float ( '<STR_LIT>' ) ) <EOL> assert_raises ( nx . NetworkXError , nx . network_simplex , G ) <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . capacity_scaling , G ) <EOL> G [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ '<STR_LIT>' ] = <NUM_LIT:0> <EOL> G . add_edge ( <NUM_LIT:0> , <NUM_LIT:0> , weight = float ( '<STR_LIT>' ) ) <EOL> assert_raises ( nx . NetworkXError , nx . network_simplex , G ) <EOL> G [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] [ '<STR_LIT>' ] = <NUM_LIT:0> <EOL> G [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ '<STR_LIT>' ] = - <NUM_LIT:1> <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . network_simplex , G ) <EOL> G [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] [ '<STR_LIT>' ] = <NUM_LIT:0> <EOL> G [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] [ '<STR_LIT>' ] = - <NUM_LIT:1> <EOL> assert_raises ( nx . NetworkXUnfeasible , nx . network_simplex , G ) <EOL> def test_large ( self ) : <EOL> fname = os . path . join ( os . path . dirname ( __file__ ) , '<STR_LIT>' ) <EOL> G = nx . read_gpickle ( fname ) <EOL> flowCost , flowDict = nx . network_simplex ( G ) <EOL> assert_equal ( <NUM_LIT> , flowCost ) <EOL> assert_equal ( <NUM_LIT> , nx . cost_of_flow ( G , flowDict ) ) <EOL> flowCost , flowDict = nx . capacity_scaling ( G ) <EOL> assert_equal ( <NUM_LIT> , flowCost ) <EOL> assert_equal ( <NUM_LIT> , nx . cost_of_flow ( G , flowDict ) ) </s>
