<s> from nose . tools import assert_equal , assert_true , assert_false , assert_raises <EOL> import networkx as nx <EOL> from networkx . algorithms import flow <EOL> from networkx . algorithms . connectivity import minimum_st_edge_cut <EOL> from networkx . algorithms . connectivity import minimum_st_node_cut <EOL> from networkx . utils import arbitrary_element <EOL> flow_funcs = [ <EOL> flow . dinitz , <EOL> flow . edmonds_karp , <EOL> flow . preflow_push , <EOL> flow . shortest_augmenting_path , <EOL> ] <EOL> msg = "<STR_LIT>" <EOL> def _generate_no_biconnected ( max_attempts = <NUM_LIT:50> ) : <EOL> attempts = <NUM_LIT:0> <EOL> while True : <EOL> G = nx . fast_gnp_random_graph ( <NUM_LIT:100> , <NUM_LIT> ) <EOL> if nx . is_connected ( G ) and not nx . is_biconnected ( G ) : <EOL> attempts = <NUM_LIT:0> <EOL> yield G <EOL> else : <EOL> if attempts >= max_attempts : <EOL> msg = "<STR_LIT>" % attempts <EOL> raise Exception ( msg % max_attempts ) <EOL> else : <EOL> attempts += <NUM_LIT:1> <EOL> def test_articulation_points ( ) : <EOL> Ggen = _generate_no_biconnected ( ) <EOL> for flow_func in flow_funcs : <EOL> for i in range ( <NUM_LIT:3> ) : <EOL> G = next ( Ggen ) <EOL> cut = nx . minimum_node_cut ( G , flow_func = flow_func ) <EOL> assert_true ( len ( cut ) == <NUM_LIT:1> , msg = msg . format ( flow_func . __name__ ) ) <EOL> assert_true ( cut . pop ( ) in set ( nx . articulation_points ( G ) ) , <EOL> msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_brandes_erlebach_book ( ) : <EOL> G = nx . Graph ( ) <EOL> G . add_edges_from ( [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:1> , <NUM_LIT:3> ) , ( <NUM_LIT:1> , <NUM_LIT:4> ) , ( <NUM_LIT:1> , <NUM_LIT:5> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) , ( <NUM_LIT:2> , <NUM_LIT:6> ) , ( <NUM_LIT:3> , <NUM_LIT:4> ) , <EOL> ( <NUM_LIT:3> , <NUM_LIT:6> ) , ( <NUM_LIT:4> , <NUM_LIT:6> ) , ( <NUM_LIT:4> , <NUM_LIT:7> ) , ( <NUM_LIT:5> , <NUM_LIT:7> ) , ( <NUM_LIT:6> , <NUM_LIT:8> ) , ( <NUM_LIT:6> , <NUM_LIT:9> ) , ( <NUM_LIT:7> , <NUM_LIT:8> ) , <EOL> ( <NUM_LIT:7> , <NUM_LIT:10> ) , ( <NUM_LIT:8> , <NUM_LIT:11> ) , ( <NUM_LIT:9> , <NUM_LIT:10> ) , ( <NUM_LIT:9> , <NUM_LIT:11> ) , ( <NUM_LIT:10> , <NUM_LIT:11> ) ] ) <EOL> for flow_func in flow_funcs : <EOL> kwargs = dict ( flow_func = flow_func ) <EOL> assert_equal ( <NUM_LIT:3> , len ( nx . minimum_edge_cut ( G , <NUM_LIT:1> , <NUM_LIT:11> , ** kwargs ) ) , <EOL> msg = msg . format ( flow_func . __name__ ) ) <EOL> edge_cut = nx . minimum_edge_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:2> , len ( edge_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_edges_from ( edge_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> assert_equal ( set ( [ <NUM_LIT:6> , <NUM_LIT:7> ] ) , minimum_st_node_cut ( G , <NUM_LIT:1> , <NUM_LIT:11> , ** kwargs ) , <EOL> msg = msg . format ( flow_func . __name__ ) ) <EOL> assert_equal ( set ( [ <NUM_LIT:6> , <NUM_LIT:7> ] ) , nx . minimum_node_cut ( G , <NUM_LIT:1> , <NUM_LIT:11> , ** kwargs ) , <EOL> msg = msg . format ( flow_func . __name__ ) ) <EOL> node_cut = nx . minimum_node_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:2> , len ( node_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_nodes_from ( node_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_white_harary_paper ( ) : <EOL> G = nx . disjoint_union ( nx . complete_graph ( <NUM_LIT:4> ) , nx . complete_graph ( <NUM_LIT:4> ) ) <EOL> G . remove_node ( <NUM_LIT:7> ) <EOL> for i in range ( <NUM_LIT:4> , <NUM_LIT:7> ) : <EOL> G . add_edge ( <NUM_LIT:0> , i ) <EOL> G = nx . disjoint_union ( G , nx . complete_graph ( <NUM_LIT:4> ) ) <EOL> G . remove_node ( G . order ( ) - <NUM_LIT:1> ) <EOL> for i in range ( <NUM_LIT:7> , <NUM_LIT:10> ) : <EOL> G . add_edge ( <NUM_LIT:0> , i ) <EOL> for flow_func in flow_funcs : <EOL> kwargs = dict ( flow_func = flow_func ) <EOL> edge_cut = nx . minimum_edge_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:3> , len ( edge_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_edges_from ( edge_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> node_cut = nx . minimum_node_cut ( G , ** kwargs ) <EOL> assert_equal ( set ( [ <NUM_LIT:0> ] ) , node_cut , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_nodes_from ( node_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_petersen_cutset ( ) : <EOL> G = nx . petersen_graph ( ) <EOL> for flow_func in flow_funcs : <EOL> kwargs = dict ( flow_func = flow_func ) <EOL> edge_cut = nx . minimum_edge_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:3> , len ( edge_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_edges_from ( edge_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> node_cut = nx . minimum_node_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:3> , len ( node_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_nodes_from ( node_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_octahedral_cutset ( ) : <EOL> G = nx . octahedral_graph ( ) <EOL> for flow_func in flow_funcs : <EOL> kwargs = dict ( flow_func = flow_func ) <EOL> edge_cut = nx . minimum_edge_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:4> , len ( edge_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_edges_from ( edge_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> node_cut = nx . minimum_node_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:4> , len ( node_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_nodes_from ( node_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_icosahedral_cutset ( ) : <EOL> G = nx . icosahedral_graph ( ) <EOL> for flow_func in flow_funcs : <EOL> kwargs = dict ( flow_func = flow_func ) <EOL> edge_cut = nx . minimum_edge_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:5> , len ( edge_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_edges_from ( edge_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> node_cut = nx . minimum_node_cut ( G , ** kwargs ) <EOL> assert_equal ( <NUM_LIT:5> , len ( node_cut ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> H = G . copy ( ) <EOL> H . remove_nodes_from ( node_cut ) <EOL> assert_false ( nx . is_connected ( H ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_node_cutset_exception ( ) : <EOL> G = nx . Graph ( ) <EOL> G . add_edges_from ( [ ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:3> , <NUM_LIT:4> ) ] ) <EOL> for flow_func in flow_funcs : <EOL> assert_raises ( nx . NetworkXError , nx . minimum_node_cut , G , flow_func = flow_func ) <EOL> def test_node_cutset_random_graphs ( ) : <EOL> for flow_func in flow_funcs : <EOL> for i in range ( <NUM_LIT:3> ) : <EOL> G = nx . fast_gnp_random_graph ( <NUM_LIT:50> , <NUM_LIT> ) <EOL> if not nx . is_connected ( G ) : <EOL> ccs = iter ( nx . connected_components ( G ) ) <EOL> start = arbitrary_element ( next ( ccs ) ) <EOL> G . add_edges_from ( ( start , arbitrary_element ( c ) ) for c in ccs ) <EOL> cutset = nx . minimum_node_cut ( G , flow_func = flow_func ) <EOL> assert_equal ( nx . node_connectivity ( G ) , len ( cutset ) , <EOL> msg = msg . format ( flow_func . __name__ ) ) <EOL> G . remove_nodes_from ( cutset ) <EOL> assert_false ( nx . is_connected ( G ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_edge_cutset_random_graphs ( ) : <EOL> for flow_func in flow_funcs : <EOL> for i in range ( <NUM_LIT:3> ) : <EOL> G = nx . fast_gnp_random_graph ( <NUM_LIT:50> , <NUM_LIT> ) <EOL> if not nx . is_connected ( G ) : <EOL> ccs = iter ( nx . connected_components ( G ) ) <EOL> start = arbitrary_element ( next ( ccs ) ) <EOL> G . add_edges_from ( ( start , arbitrary_element ( c ) ) for c in ccs ) <EOL> cutset = nx . minimum_edge_cut ( G , flow_func = flow_func ) <EOL> assert_equal ( nx . edge_connectivity ( G ) , len ( cutset ) , <EOL> msg = msg . format ( flow_func . __name__ ) ) <EOL> G . remove_edges_from ( cutset ) <EOL> assert_false ( nx . is_connected ( G ) , msg = msg . format ( flow_func . __name__ ) ) <EOL> def test_empty_graphs ( ) : <EOL> G = nx . Graph ( ) <EOL> D = nx . DiGraph ( ) <EOL> for interface_func in [ nx . minimum_node_cut , nx . minimum_edge_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_raises ( nx . NetworkXPointlessConcept , interface_func , G , <EOL> flow_func = flow_func ) <EOL> assert_raises ( nx . NetworkXPointlessConcept , interface_func , D , <EOL> flow_func = flow_func ) <EOL> def test_unbounded ( ) : <EOL> G = nx . complete_graph ( <NUM_LIT:5> ) <EOL> for flow_func in flow_funcs : <EOL> assert_equal ( <NUM_LIT:4> , len ( minimum_st_edge_cut ( G , <NUM_LIT:1> , <NUM_LIT:4> , flow_func = flow_func ) ) ) <EOL> def test_missing_source ( ) : <EOL> G = nx . path_graph ( <NUM_LIT:4> ) <EOL> for interface_func in [ nx . minimum_edge_cut , nx . minimum_node_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_raises ( nx . NetworkXError , interface_func , G , <NUM_LIT:10> , <NUM_LIT:1> , <EOL> flow_func = flow_func ) <EOL> def test_missing_target ( ) : <EOL> G = nx . path_graph ( <NUM_LIT:4> ) <EOL> for interface_func in [ nx . minimum_edge_cut , nx . minimum_node_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_raises ( nx . NetworkXError , interface_func , G , <NUM_LIT:1> , <NUM_LIT:10> , <EOL> flow_func = flow_func ) <EOL> def test_not_weakly_connected ( ) : <EOL> G = nx . DiGraph ( ) <EOL> nx . add_path ( G , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> nx . add_path ( G , [ <NUM_LIT:4> , <NUM_LIT:5> ] ) <EOL> for interface_func in [ nx . minimum_edge_cut , nx . minimum_node_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_raises ( nx . NetworkXError , interface_func , G , <EOL> flow_func = flow_func ) <EOL> def test_not_connected ( ) : <EOL> G = nx . Graph ( ) <EOL> nx . add_path ( G , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> nx . add_path ( G , [ <NUM_LIT:4> , <NUM_LIT:5> ] ) <EOL> for interface_func in [ nx . minimum_edge_cut , nx . minimum_node_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_raises ( nx . NetworkXError , interface_func , G , <EOL> flow_func = flow_func ) <EOL> def tests_min_cut_complete ( ) : <EOL> G = nx . complete_graph ( <NUM_LIT:5> ) <EOL> for interface_func in [ nx . minimum_edge_cut , nx . minimum_node_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_equal ( <NUM_LIT:4> , len ( interface_func ( G , flow_func = flow_func ) ) ) <EOL> def tests_min_cut_complete_directed ( ) : <EOL> G = nx . complete_graph ( <NUM_LIT:5> ) <EOL> G = G . to_directed ( ) <EOL> for interface_func in [ nx . minimum_edge_cut , nx . minimum_node_cut ] : <EOL> for flow_func in flow_funcs : <EOL> assert_equal ( <NUM_LIT:4> , len ( interface_func ( G , flow_func = flow_func ) ) ) <EOL> def tests_minimum_st_node_cut ( ) : <EOL> G = nx . Graph ( ) <EOL> G . add_nodes_from ( [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:7> , <NUM_LIT:8> , <NUM_LIT:11> , <NUM_LIT:12> ] ) <EOL> G . add_edges_from ( [ ( <NUM_LIT:7> , <NUM_LIT:11> ) , ( <NUM_LIT:1> , <NUM_LIT:11> ) , ( <NUM_LIT:1> , <NUM_LIT:12> ) , ( <NUM_LIT:12> , <NUM_LIT:8> ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) ] ) <EOL> nodelist = minimum_st_node_cut ( G , <NUM_LIT:7> , <NUM_LIT:11> ) <EOL> assert ( nodelist == [ ] ) <EOL> def test_invalid_auxiliary ( ) : <EOL> G = nx . complete_graph ( <NUM_LIT:5> ) <EOL> assert_raises ( nx . NetworkXError , minimum_st_node_cut , G , <NUM_LIT:0> , <NUM_LIT:3> , <EOL> auxiliary = G ) <EOL> def test_interface_only_source ( ) : <EOL> G = nx . complete_graph ( <NUM_LIT:5> ) <EOL> for interface_func in [ nx . minimum_node_cut , nx . minimum_edge_cut ] : <EOL> assert_raises ( nx . NetworkXError , interface_func , G , s = <NUM_LIT:0> ) <EOL> def test_interface_only_target ( ) : <EOL> G = nx . complete_graph ( <NUM_LIT:5> ) <EOL> for interface_func in [ nx . minimum_node_cut , nx . minimum_edge_cut ] : <EOL> assert_raises ( nx . NetworkXError , interface_func , G , t = <NUM_LIT:3> ) </s>
