| #!/usr/bin/env python |
| from nose.tools import * |
| import networkx as nx |
| |
| def test_all_simple_paths(): |
| G = nx.path_graph(4) |
| paths = nx.all_simple_paths(G,0,3) |
| assert_equal(list(list(p) for p in paths),[[0,1,2,3]]) |
| |
| def test_all_simple_paths_cutoff(): |
| G = nx.complete_graph(4) |
| paths = nx.all_simple_paths(G,0,1,cutoff=1) |
| assert_equal(list(list(p) for p in paths),[[0,1]]) |
| paths = nx.all_simple_paths(G,0,1,cutoff=2) |
| assert_equal(list(list(p) for p in paths),[[0,1],[0,2,1],[0,3,1]]) |
| |
| def test_all_simple_paths_multigraph(): |
| G = nx.MultiGraph([(1,2),(1,2)]) |
| paths = nx.all_simple_paths(G,1,2) |
| assert_equal(list(list(p) for p in paths),[[1,2],[1,2]]) |
| |
| def test_all_simple_paths_multigraph_with_cutoff(): |
| G = nx.MultiGraph([(1,2),(1,2),(1,10),(10,2)]) |
| paths = nx.all_simple_paths(G,1,2, cutoff=1) |
| assert_equal(list(list(p) for p in paths),[[1,2],[1,2]]) |
| |
| |
| def test_all_simple_paths_directed(): |
| G = nx.DiGraph() |
| G.add_path([1,2,3]) |
| G.add_path([3,2,1]) |
| paths = nx.all_simple_paths(G,1,3) |
| assert_equal(list(list(p) for p in paths),[[1,2,3]]) |
| |
| def test_all_simple_paths_empty(): |
| G = nx.path_graph(4) |
| paths = nx.all_simple_paths(G,0,3,cutoff=2) |
| assert_equal(list(list(p) for p in paths),[]) |
| |
| def hamiltonian_path(G,source): |
| source = next(G.nodes_iter()) |
| neighbors = set(G[source])-set([source]) |
| n = len(G) |
| for target in neighbors: |
| for path in nx.all_simple_paths(G,source,target): |
| if len(path) == n: |
| yield path |
| |
| def test_hamiltonian_path(): |
| from itertools import permutations |
| G=nx.complete_graph(4) |
| paths = [list(p) for p in hamiltonian_path(G,0)] |
| exact = [[0]+list(p) for p in permutations([1,2,3],3) ] |
| assert_equal(sorted(paths),sorted(exact)) |
| |
| def test_cutoff_zero(): |
| G = nx.complete_graph(4) |
| paths = nx.all_simple_paths(G,0,3,cutoff=0) |
| assert_equal(list(list(p) for p in paths),[]) |
| paths = nx.all_simple_paths(nx.MultiGraph(G),0,3,cutoff=0) |
| assert_equal(list(list(p) for p in paths),[]) |
| |
| @raises(nx.NetworkXError) |
| def test_source_missing(): |
| G = nx.Graph() |
| G.add_path([1,2,3]) |
| paths = list(nx.all_simple_paths(nx.MultiGraph(G),0,3)) |
| |
| @raises(nx.NetworkXError) |
| def test_target_missing(): |
| G = nx.Graph() |
| G.add_path([1,2,3]) |
| paths = list(nx.all_simple_paths(nx.MultiGraph(G),1,4)) |