<s> from nose . tools import * <EOL> import networkx <EOL> import networkx as nx <EOL> from networkx . algorithms import find_cycle <EOL> FORWARD = nx . algorithms . edgedfs . FORWARD <EOL> REVERSE = nx . algorithms . edgedfs . REVERSE <EOL> class TestCycles : <EOL> def setUp ( self ) : <EOL> G = networkx . Graph ( ) <EOL> nx . add_cycle ( G , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> nx . add_cycle ( G , [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> ] ) <EOL> nx . add_cycle ( G , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> ] ) <EOL> G . add_edge ( <NUM_LIT:8> , <NUM_LIT:9> ) <EOL> self . G = G <EOL> def is_cyclic_permutation ( self , a , b ) : <EOL> n = len ( a ) <EOL> if len ( b ) != n : <EOL> return False <EOL> l = a + a <EOL> return any ( l [ i : i + n ] == b for i in range ( <NUM_LIT:2> * n - n + <NUM_LIT:1> ) ) <EOL> def test_cycle_basis ( self ) : <EOL> G = self . G <EOL> cy = networkx . cycle_basis ( G , <NUM_LIT:0> ) <EOL> sort_cy = sorted ( sorted ( c ) for c in cy ) <EOL> assert_equal ( sort_cy , [ [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> ] , [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> ] ] ) <EOL> cy = networkx . cycle_basis ( G , <NUM_LIT:1> ) <EOL> sort_cy = sorted ( sorted ( c ) for c in cy ) <EOL> assert_equal ( sort_cy , [ [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> ] , [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> ] ] ) <EOL> cy = networkx . cycle_basis ( G , <NUM_LIT:9> ) <EOL> sort_cy = sorted ( sorted ( c ) for c in cy ) <EOL> assert_equal ( sort_cy , [ [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> ] , [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> ] ] ) <EOL> nx . add_cycle ( G , "<STR_LIT>" ) <EOL> cy = networkx . cycle_basis ( G , <NUM_LIT:9> ) <EOL> sort_cy = sorted ( sorted ( c ) for c in cy [ : - <NUM_LIT:1> ] ) + [ sorted ( cy [ - <NUM_LIT:1> ] ) ] <EOL> assert_equal ( sort_cy , [ [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:6> , <NUM_LIT:7> , <NUM_LIT:8> ] , [ <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:4> , <NUM_LIT:5> ] , [ '<STR_LIT:A>' , '<STR_LIT:B>' , '<STR_LIT:C>' ] ] ) <EOL> @ raises ( nx . NetworkXNotImplemented ) <EOL> def test_cycle_basis ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> cy = networkx . cycle_basis ( G , <NUM_LIT:0> ) <EOL> @ raises ( nx . NetworkXNotImplemented ) <EOL> def test_cycle_basis ( self ) : <EOL> G = nx . MultiGraph ( ) <EOL> cy = networkx . cycle_basis ( G , <NUM_LIT:0> ) <EOL> def test_simple_cycles ( self ) : <EOL> G = nx . DiGraph ( [ ( <NUM_LIT:0> , <NUM_LIT:0> ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:0> , <NUM_LIT:2> ) , ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:0> ) , ( <NUM_LIT:2> , <NUM_LIT:1> ) , ( <NUM_LIT:2> , <NUM_LIT:2> ) ] ) <EOL> cc = sorted ( nx . simple_cycles ( G ) ) <EOL> ca = [ [ <NUM_LIT:0> ] , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> ] , [ <NUM_LIT:0> , <NUM_LIT:2> ] , [ <NUM_LIT:1> , <NUM_LIT:2> ] , [ <NUM_LIT:2> ] ] <EOL> for c in cc : <EOL> assert_true ( any ( self . is_cyclic_permutation ( c , rc ) for rc in ca ) ) <EOL> @ raises ( nx . NetworkXNotImplemented ) <EOL> def test_simple_cycles_graph ( self ) : <EOL> G = nx . Graph ( ) <EOL> c = sorted ( nx . simple_cycles ( G ) ) <EOL> def test_unsortable ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> nx . add_cycle ( G , [ '<STR_LIT:a>' , <NUM_LIT:1> ] ) <EOL> c = list ( nx . simple_cycles ( G ) ) <EOL> def test_simple_cycles_small ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> nx . add_cycle ( G , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> c = sorted ( nx . simple_cycles ( G ) ) <EOL> assert_equal ( len ( c ) , <NUM_LIT:1> ) <EOL> assert_true ( self . is_cyclic_permutation ( c [ <NUM_LIT:0> ] , [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) ) <EOL> nx . add_cycle ( G , [ <NUM_LIT:10> , <NUM_LIT:20> , <NUM_LIT:30> ] ) <EOL> cc = sorted ( nx . simple_cycles ( G ) ) <EOL> ca = [ [ <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] , [ <NUM_LIT:10> , <NUM_LIT:20> , <NUM_LIT:30> ] ] <EOL> for c in cc : <EOL> assert_true ( any ( self . is_cyclic_permutation ( c , rc ) for rc in ca ) ) <EOL> def test_simple_cycles_empty ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> assert_equal ( list ( nx . simple_cycles ( G ) ) , [ ] ) <EOL> def test_complete_directed_graph ( self ) : <EOL> ncircuits = [ <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT:20> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ] <EOL> for n , c in zip ( range ( <NUM_LIT:2> , <NUM_LIT:9> ) , ncircuits ) : <EOL> G = nx . DiGraph ( nx . complete_graph ( n ) ) <EOL> assert_equal ( len ( list ( nx . simple_cycles ( G ) ) ) , c ) <EOL> def worst_case_graph ( self , k ) : <EOL> G = nx . DiGraph ( ) <EOL> for n in range ( <NUM_LIT:2> , k + <NUM_LIT:2> ) : <EOL> G . add_edge ( <NUM_LIT:1> , n ) <EOL> G . add_edge ( n , k + <NUM_LIT:2> ) <EOL> G . add_edge ( <NUM_LIT:2> * k + <NUM_LIT:1> , <NUM_LIT:1> ) <EOL> for n in range ( k + <NUM_LIT:2> , <NUM_LIT:2> * k + <NUM_LIT:2> ) : <EOL> G . add_edge ( n , <NUM_LIT:2> * k + <NUM_LIT:2> ) <EOL> G . add_edge ( n , n + <NUM_LIT:1> ) <EOL> G . add_edge ( <NUM_LIT:2> * k + <NUM_LIT:3> , k + <NUM_LIT:2> ) <EOL> for n in range ( <NUM_LIT:2> * k + <NUM_LIT:3> , <NUM_LIT:3> * k + <NUM_LIT:3> ) : <EOL> G . add_edge ( <NUM_LIT:2> * k + <NUM_LIT:2> , n ) <EOL> G . add_edge ( n , <NUM_LIT:3> * k + <NUM_LIT:3> ) <EOL> G . add_edge ( <NUM_LIT:3> * k + <NUM_LIT:3> , <NUM_LIT:2> * k + <NUM_LIT:2> ) <EOL> return G <EOL> def test_worst_case_graph ( self ) : <EOL> for k in range ( <NUM_LIT:3> , <NUM_LIT:10> ) : <EOL> G = self . worst_case_graph ( k ) <EOL> l = len ( list ( nx . simple_cycles ( G ) ) ) <EOL> assert_equal ( l , <NUM_LIT:3> * k ) <EOL> def test_recursive_simple_and_not ( self ) : <EOL> for k in range ( <NUM_LIT:2> , <NUM_LIT:10> ) : <EOL> G = self . worst_case_graph ( k ) <EOL> cc = sorted ( nx . simple_cycles ( G ) ) <EOL> rcc = sorted ( nx . recursive_simple_cycles ( G ) ) <EOL> assert_equal ( len ( cc ) , len ( rcc ) ) <EOL> for c in cc : <EOL> assert_true ( any ( self . is_cyclic_permutation ( c , rc ) for rc in rcc ) ) <EOL> for rc in rcc : <EOL> assert_true ( any ( self . is_cyclic_permutation ( rc , c ) for c in cc ) ) <EOL> def test_simple_graph_with_reported_bug ( self ) : <EOL> G = nx . DiGraph ( ) <EOL> edges = [ ( <NUM_LIT:0> , <NUM_LIT:2> ) , ( <NUM_LIT:0> , <NUM_LIT:3> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:3> ) , ( <NUM_LIT:2> , <NUM_LIT:1> ) , ( <NUM_LIT:2> , <NUM_LIT:4> ) , ( <NUM_LIT:3> , <NUM_LIT:2> ) , ( <NUM_LIT:3> , <NUM_LIT:4> ) , ( <NUM_LIT:4> , <NUM_LIT:0> ) , ( <NUM_LIT:4> , <NUM_LIT:1> ) , ( <NUM_LIT:4> , <NUM_LIT:5> ) , ( <NUM_LIT:5> , <NUM_LIT:0> ) , ( <NUM_LIT:5> , <NUM_LIT:1> ) , ( <NUM_LIT:5> , <NUM_LIT:2> ) , ( <NUM_LIT:5> , <NUM_LIT:3> ) ] <EOL> G . add_edges_from ( edges ) <EOL> cc = sorted ( nx . simple_cycles ( G ) ) <EOL> assert_equal ( len ( cc ) , <NUM_LIT> ) <EOL> rcc = sorted ( nx . recursive_simple_cycles ( G ) ) <EOL> assert_equal ( len ( cc ) , len ( rcc ) ) <EOL> for c in cc : <EOL> assert_true ( any ( self . is_cyclic_permutation ( c , rc ) for rc in rcc ) ) <EOL> for rc in rcc : <EOL> assert_true ( any ( self . is_cyclic_permutation ( rc , c ) for c in cc ) ) <EOL> class TestFindCycle ( object ) : <EOL> def setUp ( self ) : <EOL> self . nodes = [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] <EOL> self . edges = [ ( - <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:2> , <NUM_LIT:1> ) , ( <NUM_LIT:3> , <NUM_LIT:1> ) ] <EOL> def test_graph ( self ) : <EOL> G = nx . Graph ( self . edges ) <EOL> assert_raises ( nx . exception . NetworkXNoCycle , find_cycle , G , self . nodes ) <EOL> def test_digraph ( self ) : <EOL> G = nx . DiGraph ( self . edges ) <EOL> x = list ( find_cycle ( G , self . nodes ) ) <EOL> x_ = [ ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:1> , <NUM_LIT:0> ) ] <EOL> assert_equal ( x , x_ ) <EOL> def test_multigraph ( self ) : <EOL> G = nx . MultiGraph ( self . edges ) <EOL> x = list ( find_cycle ( G , self . nodes ) ) <EOL> x_ = [ ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:1> ) ] <EOL> assert_equal ( x [ <NUM_LIT:0> ] , x_ [ <NUM_LIT:0> ] ) <EOL> assert_equal ( x [ <NUM_LIT:1> ] [ : <NUM_LIT:2> ] , x_ [ <NUM_LIT:1> ] [ : <NUM_LIT:2> ] ) <EOL> def test_multidigraph ( self ) : <EOL> G = nx . MultiDiGraph ( self . edges ) <EOL> x = list ( find_cycle ( G , self . nodes ) ) <EOL> x_ = [ ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0> ) , ( <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:0> ) ] <EOL> assert_equal ( x [ <NUM_LIT:0> ] , x_ [ <NUM_LIT:0> ] ) <EOL> assert_equal ( x [ <NUM_LIT:1> ] [ : <NUM_LIT:2> ] , x_ [ <NUM_LIT:1> ] [ : <NUM_LIT:2> ] ) <EOL> def test_digraph_ignore ( self ) : <EOL> G = nx . DiGraph ( self . edges ) <EOL> x = list ( find_cycle ( G , self . nodes , orientation = '<STR_LIT:ignore>' ) ) <EOL> x_ = [ ( <NUM_LIT:0> , <NUM_LIT:1> , FORWARD ) , ( <NUM_LIT:1> , <NUM_LIT:0> , FORWARD ) ] <EOL> assert_equal ( x , x_ ) <EOL> def test_multidigraph_ignore ( self ) : <EOL> G = nx . MultiDiGraph ( self . edges ) <EOL> x = list ( find_cycle ( G , self . nodes , orientation = '<STR_LIT:ignore>' ) ) <EOL> x_ = [ ( <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0> , FORWARD ) , ( <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:0> , FORWARD ) ] <EOL> assert_equal ( x [ <NUM_LIT:0> ] , x_ [ <NUM_LIT:0> ] ) <EOL> assert_equal ( x [ <NUM_LIT:1> ] [ : <NUM_LIT:2> ] , x_ [ <NUM_LIT:1> ] [ : <NUM_LIT:2> ] ) <EOL> assert_equal ( x [ <NUM_LIT:1> ] [ <NUM_LIT:3> ] , x_ [ <NUM_LIT:1> ] [ <NUM_LIT:3> ] ) <EOL> def test_multidigraph_ignore2 ( self ) : <EOL> G = nx . MultiDiGraph ( [ ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:1> , <NUM_LIT:2> ) ] ) <EOL> x = list ( find_cycle ( G , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> ] , orientation = '<STR_LIT:ignore>' ) ) <EOL> x_ = [ ( <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:0> , FORWARD ) , ( <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:1> , REVERSE ) ] <EOL> assert_equal ( x , x_ ) <EOL> def test_multidigraph_ignore2 ( self ) : <EOL> G = nx . MultiDiGraph ( [ ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:1> , <NUM_LIT:2> ) , ( <NUM_LIT:2> , <NUM_LIT:3> ) , ( <NUM_LIT:4> , <NUM_LIT:2> ) ] ) <EOL> assert_raises ( nx . exception . NetworkXNoCycle , <EOL> find_cycle , G , [ <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> , <NUM_LIT:4> ] , orientation = '<STR_LIT>' ) <EOL> def test_dag ( self ) : <EOL> G = nx . DiGraph ( [ ( <NUM_LIT:0> , <NUM_LIT:1> ) , ( <NUM_LIT:0> , <NUM_LIT:2> ) , ( <NUM_LIT:1> , <NUM_LIT:2> ) ] ) <EOL> assert_raises ( nx . exception . NetworkXNoCycle , <EOL> find_cycle , G , orientation = '<STR_LIT>' ) <EOL> x = list ( find_cycle ( G , orientation = '<STR_LIT:ignore>' ) ) <EOL> assert_equal ( x , [ ( <NUM_LIT:0> , <NUM_LIT:1> , FORWARD ) , ( <NUM_LIT:1> , <NUM_LIT:2> , FORWARD ) , ( <NUM_LIT:0> , <NUM_LIT:2> , REVERSE ) ] ) </s>
