<s> from __future__ import division , print_function , absolute_import <EOL> import numpy as np <EOL> from numpy . testing import ( assert_array_almost_equal , assert_raises , dec , <EOL> run_module_suite , assert_array_equal ) <EOL> from scipy . sparse . csgraph import ( shortest_path , dijkstra , johnson , <EOL> bellman_ford , construct_dist_matrix , NegativeCycleError ) <EOL> directed_G = np . array ( [ [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:4> ] , <EOL> [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:2> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:0> ] ] , dtype = float ) <EOL> undirected_G = np . array ( [ [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:1> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:4> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:2> , <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:0> ] ] , dtype = float ) <EOL> unweighted_G = ( directed_G > <NUM_LIT:0> ) . astype ( float ) <EOL> directed_SP = [ [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:5> , <NUM_LIT:7> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:4> ] , <EOL> [ np . inf , np . inf , <NUM_LIT:0> , np . inf , np . inf ] , <EOL> [ <NUM_LIT:1> , <NUM_LIT:4> , <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:8> ] , <EOL> [ <NUM_LIT:2> , <NUM_LIT:5> , <NUM_LIT:5> , <NUM_LIT:2> , <NUM_LIT:0> ] ] <EOL> directed_pred = np . array ( [ [ - <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> ] , <EOL> [ <NUM_LIT:3> , - <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> ] , <EOL> [ - <NUM_LIT> , - <NUM_LIT> , - <NUM_LIT> , - <NUM_LIT> , - <NUM_LIT> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:0> , - <NUM_LIT> , <NUM_LIT:1> ] , <EOL> [ <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:4> , - <NUM_LIT> ] ] , dtype = float ) <EOL> undirected_SP = np . array ( [ [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:1> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:4> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:6> , <NUM_LIT:0> , <NUM_LIT:4> , <NUM_LIT:5> ] , <EOL> [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:2> , <NUM_LIT:4> , <NUM_LIT:5> , <NUM_LIT:2> , <NUM_LIT:0> ] ] , dtype = float ) <EOL> undirected_SP_limit_2 = np . array ( [ [ <NUM_LIT:0> , np . inf , np . inf , <NUM_LIT:1> , <NUM_LIT:2> ] , <EOL> [ np . inf , <NUM_LIT:0> , np . inf , <NUM_LIT:2> , np . inf ] , <EOL> [ np . inf , np . inf , <NUM_LIT:0> , np . inf , np . inf ] , <EOL> [ <NUM_LIT:1> , <NUM_LIT:2> , np . inf , <NUM_LIT:0> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:2> , np . inf , np . inf , <NUM_LIT:2> , <NUM_LIT:0> ] ] , dtype = float ) <EOL> undirected_SP_limit_0 = np . ones ( ( <NUM_LIT:5> , <NUM_LIT:5> ) , dtype = float ) - np . eye ( <NUM_LIT:5> ) <EOL> undirected_SP_limit_0 [ undirected_SP_limit_0 > <NUM_LIT:0> ] = np . inf <EOL> undirected_pred = np . array ( [ [ - <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:1> , - <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> ] , <EOL> [ <NUM_LIT:2> , <NUM_LIT:0> , - <NUM_LIT> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:0> , - <NUM_LIT> , <NUM_LIT:3> ] , <EOL> [ <NUM_LIT:4> , <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:4> , - <NUM_LIT> ] ] , dtype = float ) <EOL> methods = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT:D>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> def test_dijkstra_limit ( ) : <EOL> limits = [ <NUM_LIT:0> , <NUM_LIT:2> , np . inf ] <EOL> results = [ undirected_SP_limit_0 , <EOL> undirected_SP_limit_2 , <EOL> undirected_SP ] <EOL> def check ( limit , result ) : <EOL> SP = dijkstra ( undirected_G , directed = False , limit = limit ) <EOL> assert_array_almost_equal ( SP , result ) <EOL> for limit , result in zip ( limits , results ) : <EOL> yield check , limit , result <EOL> def test_directed ( ) : <EOL> def check ( method ) : <EOL> SP = shortest_path ( directed_G , method = method , directed = True , <EOL> overwrite = False ) <EOL> assert_array_almost_equal ( SP , directed_SP ) <EOL> for method in methods : <EOL> yield check , method <EOL> def test_undirected ( ) : <EOL> def check ( method , directed_in ) : <EOL> if directed_in : <EOL> SP1 = shortest_path ( directed_G , method = method , directed = False , <EOL> overwrite = False ) <EOL> assert_array_almost_equal ( SP1 , undirected_SP ) <EOL> else : <EOL> SP2 = shortest_path ( undirected_G , method = method , directed = True , <EOL> overwrite = False ) <EOL> assert_array_almost_equal ( SP2 , undirected_SP ) <EOL> for method in methods : <EOL> for directed_in in ( True , False ) : <EOL> yield check , method , directed_in <EOL> def test_shortest_path_indices ( ) : <EOL> indices = np . arange ( <NUM_LIT:4> ) <EOL> def check ( func , indshape ) : <EOL> outshape = indshape + ( <NUM_LIT:5> , ) <EOL> SP = func ( directed_G , directed = False , <EOL> indices = indices . reshape ( indshape ) ) <EOL> assert_array_almost_equal ( SP , undirected_SP [ indices ] . reshape ( outshape ) ) <EOL> for indshape in [ ( <NUM_LIT:4> , ) , ( <NUM_LIT:4> , <NUM_LIT:1> ) , ( <NUM_LIT:2> , <NUM_LIT:2> ) ] : <EOL> for func in ( dijkstra , bellman_ford , johnson ) : <EOL> yield check , func , indshape <EOL> def test_predecessors ( ) : <EOL> SP_res = { True : directed_SP , <EOL> False : undirected_SP } <EOL> pred_res = { True : directed_pred , <EOL> False : undirected_pred } <EOL> def check ( method , directed ) : <EOL> SP , pred = shortest_path ( directed_G , method , directed = directed , <EOL> overwrite = False , <EOL> return_predecessors = True ) <EOL> assert_array_almost_equal ( SP , SP_res [ directed ] ) <EOL> assert_array_almost_equal ( pred , pred_res [ directed ] ) <EOL> for method in methods : <EOL> for directed in ( True , False ) : <EOL> yield check , method , directed <EOL> def test_construct_shortest_path ( ) : <EOL> def check ( method , directed ) : <EOL> SP1 , pred = shortest_path ( directed_G , <EOL> directed = directed , <EOL> overwrite = False , <EOL> return_predecessors = True ) <EOL> SP2 = construct_dist_matrix ( directed_G , pred , directed = directed ) <EOL> assert_array_almost_equal ( SP1 , SP2 ) <EOL> for method in methods : <EOL> for directed in ( True , False ) : <EOL> yield check , method , directed <EOL> def test_unweighted_path ( ) : <EOL> def check ( method , directed ) : <EOL> SP1 = shortest_path ( directed_G , <EOL> directed = directed , <EOL> overwrite = False , <EOL> unweighted = True ) <EOL> SP2 = shortest_path ( unweighted_G , <EOL> directed = directed , <EOL> overwrite = False , <EOL> unweighted = False ) <EOL> assert_array_almost_equal ( SP1 , SP2 ) <EOL> for method in methods : <EOL> for directed in ( True , False ) : <EOL> yield check , method , directed <EOL> def test_negative_cycles ( ) : <EOL> graph = np . ones ( [ <NUM_LIT:5> , <NUM_LIT:5> ] ) <EOL> graph . flat [ : : <NUM_LIT:6> ] = <NUM_LIT:0> <EOL> graph [ <NUM_LIT:1> , <NUM_LIT:2> ] = - <NUM_LIT:2> <EOL> def check ( method , directed ) : <EOL> assert_raises ( NegativeCycleError , shortest_path , graph , method , <EOL> directed ) <EOL> for method in [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] : <EOL> for directed in ( True , False ) : <EOL> yield check , method , directed <EOL> def test_masked_input ( ) : <EOL> G = np . ma . masked_equal ( directed_G , <NUM_LIT:0> ) <EOL> def check ( method ) : <EOL> SP = shortest_path ( directed_G , method = method , directed = True , <EOL> overwrite = False ) <EOL> assert_array_almost_equal ( SP , directed_SP ) <EOL> for method in methods : <EOL> yield check , method <EOL> def test_overwrite ( ) : <EOL> G = np . array ( [ [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:3> , <NUM_LIT:1> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:4> ] , <EOL> [ <NUM_LIT:3> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> ] , <EOL> [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:2> ] , <EOL> [ <NUM_LIT:2> , <NUM_LIT:4> , <NUM_LIT:0> , <NUM_LIT:2> , <NUM_LIT:0> ] ] , dtype = float ) <EOL> foo = G . copy ( ) <EOL> shortest_path ( foo , overwrite = False ) <EOL> assert_array_equal ( foo , G ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> run_module_suite ( ) </s>
