Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / shortest_paths / tests / test_astar.py @ 5cef0f13

1 2 3 5cef0f13 tiamilani ```from nose.tools import assert_equal ``` ```from nose.tools import assert_raises ``` ```from nose.tools import raises ``` ```from math import sqrt ``` ```from random import random, choice ``` ```import networkx as nx ``` ```from networkx.utils import pairwise ``` ```def dist(a, b): ``` ``` """Returns the Euclidean distance between points `a` and `b`.""" ``` ``` return sqrt(sum((x1 - x2) ** 2 for x1, x2 in zip(a, b))) ``` ```class TestAStar: ``` ``` def setUp(self): ``` ``` edges = [('s', 'u', 10), ('s', 'x', 5), ('u', 'v', 1), ('u', 'x', 2), ``` ``` ('v', 'y', 1), ('x', 'u', 3), ('x', 'v', 5), ('x', 'y', 2), ``` ``` ('y', 's', 7), ('y', 'v', 6)] ``` ``` self.XG = nx.DiGraph() ``` ``` self.XG.add_weighted_edges_from(edges) ``` ``` def test_random_graph(self): ``` ``` """Tests that the A* shortest path agrees with Dijkstra's ``` ``` shortest path for a random graph. ``` ``` ``` ``` """ ``` ``` G = nx.Graph() ``` ``` points = [(random(), random()) for _ in range(100)] ``` ``` # Build a path from points[0] to points[-1] to be sure it exists ``` ``` for p1, p2 in pairwise(points): ``` ``` G.add_edge(p1, p2, weight=dist(p1, p2)) ``` ``` # Add other random edges ``` ``` for _ in range(100): ``` ``` p1, p2 = choice(points), choice(points) ``` ``` G.add_edge(p1, p2, weight=dist(p1, p2)) ``` ``` path = nx.astar_path(G, points[0], points[-1], dist) ``` ``` assert_equal(path, nx.dijkstra_path(G, points[0], points[-1])) ``` ``` def test_astar_directed(self): ``` ``` assert_equal(nx.astar_path(self.XG, 's', 'v'), ['s', 'x', 'u', 'v']) ``` ``` assert_equal(nx.astar_path_length(self.XG, 's', 'v'), 9) ``` ``` def test_astar_multigraph(self): ``` ``` G = nx.MultiDiGraph(self.XG) ``` ``` assert_raises(nx.NetworkXNotImplemented, nx.astar_path, G, 's', 'v') ``` ``` assert_raises(nx.NetworkXNotImplemented, nx.astar_path_length, ``` ``` G, 's', 'v') ``` ``` def test_astar_undirected(self): ``` ``` GG = self.XG.to_undirected() ``` ``` # make sure we get lower weight ``` ``` # to_undirected might choose either edge with weight 2 or weight 3 ``` ``` GG['u']['x']['weight'] = 2 ``` ``` GG['y']['v']['weight'] = 2 ``` ``` assert_equal(nx.astar_path(GG, 's', 'v'), ['s', 'x', 'u', 'v']) ``` ``` assert_equal(nx.astar_path_length(GG, 's', 'v'), 8) ``` ``` def test_astar_directed2(self): ``` ``` XG2 = nx.DiGraph() ``` ``` edges = [(1, 4, 1), (4, 5, 1), (5, 6, 1), (6, 3, 1), (1, 3, 50), ``` ``` (1, 2, 100), (2, 3, 100)] ``` ``` XG2.add_weighted_edges_from(edges) ``` ``` assert_equal(nx.astar_path(XG2, 1, 3), [1, 4, 5, 6, 3]) ``` ``` def test_astar_undirected2(self): ``` ``` XG3 = nx.Graph() ``` ``` edges = [(0, 1, 2), (1, 2, 12), (2, 3, 1), (3, 4, 5), (4, 5, 1), ``` ``` (5, 0, 10)] ``` ``` XG3.add_weighted_edges_from(edges) ``` ``` assert_equal(nx.astar_path(XG3, 0, 3), [0, 1, 2, 3]) ``` ``` assert_equal(nx.astar_path_length(XG3, 0, 3), 15) ``` ``` def test_astar_undirected3(self): ``` ``` XG4 = nx.Graph() ``` ``` edges = [(0, 1, 2), (1, 2, 2), (2, 3, 1), (3, 4, 1), (4, 5, 1), ``` ``` (5, 6, 1), (6, 7, 1), (7, 0, 1)] ``` ``` XG4.add_weighted_edges_from(edges) ``` ``` assert_equal(nx.astar_path(XG4, 0, 2), [0, 1, 2]) ``` ``` assert_equal(nx.astar_path_length(XG4, 0, 2), 4) ``` ```# >>> MXG4=NX.MultiGraph(XG4) ``` ```# >>> MXG4.add_edge(0,1,3) ``` ```# >>> NX.dijkstra_path(MXG4,0,2) ``` ```# [0, 1, 2] ``` ``` def test_astar_w1(self): ``` ``` G = nx.DiGraph() ``` ``` G.add_edges_from([('s', 'u'), ('s', 'x'), ('u', 'v'), ('u', 'x'), ``` ``` ('v', 'y'), ('x', 'u'), ('x', 'w'), ('w', 'v'), ``` ``` ('x', 'y'), ('y', 's'), ('y', 'v')]) ``` ``` assert_equal(nx.astar_path(G, 's', 'v'), ['s', 'u', 'v']) ``` ``` assert_equal(nx.astar_path_length(G, 's', 'v'), 2) ``` ``` @raises(nx.NodeNotFound) ``` ``` def test_astar_nopath(self): ``` ``` nx.astar_path(self.XG, 's', 'moon') ``` ``` def test_cycle(self): ``` ``` C = nx.cycle_graph(7) ``` ``` assert_equal(nx.astar_path(C, 0, 3), [0, 1, 2, 3]) ``` ``` assert_equal(nx.dijkstra_path(C, 0, 4), [0, 6, 5, 4]) ``` ``` def test_unorderable_nodes(self): ``` ``` """Tests that A* accommodates nodes that are not orderable. ``` ``` ``` ``` For more information, see issue #554. ``` ``` ``` ``` """ ``` ``` # TODO In Python 3, instances of the `object` class are ``` ``` # unorderable by default, so we wouldn't need to define our own ``` ``` # class here, we could just instantiate an instance of the ``` ``` # `object` class. However, we still support Python 2; when ``` ``` # support for Python 2 is dropped, this test can be simplified ``` ``` # by replacing `Unorderable()` by `object()`. ``` ``` class Unorderable(object): ``` ``` def __le__(self): ``` ``` raise NotImplemented ``` ``` def __ge__(self): ``` ``` raise NotImplemented ``` ``` # Create the cycle graph on four nodes, with nodes represented ``` ``` # as (unorderable) Python objects. ``` ``` nodes = [Unorderable() for n in range(4)] ``` ``` G = nx.Graph() ``` ``` G.add_edges_from(pairwise(nodes, cyclic=True)) ``` ``` path = nx.astar_path(G, nodes[0], nodes[2]) ``` ` assert_equal(len(path), 3)`