ioftools / networkxMiCe / networkxmaster / networkx / algorithms / shortest_paths / tests / test_astar.py @ 5cef0f13
History  View  Annotate  Download (4.91 KB)
1 
from nose.tools import assert_equal 

2 
from nose.tools import assert_raises 
3 
from nose.tools import raises 
4  
5 
from math import sqrt 
6 
from random import random, choice 
7  
8 
import networkx as nx 
9 
from networkx.utils import pairwise 
10  
11  
12 
def dist(a, b): 
13 
"""Returns the Euclidean distance between points `a` and `b`."""

14 
return sqrt(sum((x1  x2) ** 2 for x1, x2 in zip(a, b))) 
15  
16  
17 
class TestAStar: 
18  
19 
def setUp(self): 
20 
edges = [('s', 'u', 10), ('s', 'x', 5), ('u', 'v', 1), ('u', 'x', 2), 
21 
('v', 'y', 1), ('x', 'u', 3), ('x', 'v', 5), ('x', 'y', 2), 
22 
('y', 's', 7), ('y', 'v', 6)] 
23 
self.XG = nx.DiGraph()

24 
self.XG.add_weighted_edges_from(edges)

25  
26 
def test_random_graph(self): 
27 
"""Tests that the A* shortest path agrees with Dijkstra's

28 
shortest path for a random graph.

29 

30 
"""

31  
32 
G = nx.Graph() 
33  
34 
points = [(random(), random()) for _ in range(100)] 
35  
36 
# Build a path from points[0] to points[1] to be sure it exists

37 
for p1, p2 in pairwise(points): 
38 
G.add_edge(p1, p2, weight=dist(p1, p2)) 
39  
40 
# Add other random edges

41 
for _ in range(100): 
42 
p1, p2 = choice(points), choice(points) 
43 
G.add_edge(p1, p2, weight=dist(p1, p2)) 
44  
45 
path = nx.astar_path(G, points[0], points[1], dist) 
46 
assert_equal(path, nx.dijkstra_path(G, points[0], points[1])) 
47  
48 
def test_astar_directed(self): 
49 
assert_equal(nx.astar_path(self.XG, 's', 'v'), ['s', 'x', 'u', 'v']) 
50 
assert_equal(nx.astar_path_length(self.XG, 's', 'v'), 9) 
51  
52 
def test_astar_multigraph(self): 
53 
G = nx.MultiDiGraph(self.XG)

54 
assert_raises(nx.NetworkXNotImplemented, nx.astar_path, G, 's', 'v') 
55 
assert_raises(nx.NetworkXNotImplemented, nx.astar_path_length, 
56 
G, 's', 'v') 
57  
58 
def test_astar_undirected(self): 
59 
GG = self.XG.to_undirected()

60 
# make sure we get lower weight

61 
# to_undirected might choose either edge with weight 2 or weight 3

62 
GG['u']['x']['weight'] = 2 
63 
GG['y']['v']['weight'] = 2 
64 
assert_equal(nx.astar_path(GG, 's', 'v'), ['s', 'x', 'u', 'v']) 
65 
assert_equal(nx.astar_path_length(GG, 's', 'v'), 8) 
66  
67 
def test_astar_directed2(self): 
68 
XG2 = nx.DiGraph() 
69 
edges = [(1, 4, 1), (4, 5, 1), (5, 6, 1), (6, 3, 1), (1, 3, 50), 
70 
(1, 2, 100), (2, 3, 100)] 
71 
XG2.add_weighted_edges_from(edges) 
72 
assert_equal(nx.astar_path(XG2, 1, 3), [1, 4, 5, 6, 3]) 
73  
74 
def test_astar_undirected2(self): 
75 
XG3 = nx.Graph() 
76 
edges = [(0, 1, 2), (1, 2, 12), (2, 3, 1), (3, 4, 5), (4, 5, 1), 
77 
(5, 0, 10)] 
78 
XG3.add_weighted_edges_from(edges) 
79 
assert_equal(nx.astar_path(XG3, 0, 3), [0, 1, 2, 3]) 
80 
assert_equal(nx.astar_path_length(XG3, 0, 3), 15) 
81  
82 
def test_astar_undirected3(self): 
83 
XG4 = nx.Graph() 
84 
edges = [(0, 1, 2), (1, 2, 2), (2, 3, 1), (3, 4, 1), (4, 5, 1), 
85 
(5, 6, 1), (6, 7, 1), (7, 0, 1)] 
86 
XG4.add_weighted_edges_from(edges) 
87 
assert_equal(nx.astar_path(XG4, 0, 2), [0, 1, 2]) 
88 
assert_equal(nx.astar_path_length(XG4, 0, 2), 4) 
89  
90 
# >>> MXG4=NX.MultiGraph(XG4)

91 
# >>> MXG4.add_edge(0,1,3)

92 
# >>> NX.dijkstra_path(MXG4,0,2)

93 
# [0, 1, 2]

94  
95 
def test_astar_w1(self): 
96 
G = nx.DiGraph() 
97 
G.add_edges_from([('s', 'u'), ('s', 'x'), ('u', 'v'), ('u', 'x'), 
98 
('v', 'y'), ('x', 'u'), ('x', 'w'), ('w', 'v'), 
99 
('x', 'y'), ('y', 's'), ('y', 'v')]) 
100 
assert_equal(nx.astar_path(G, 's', 'v'), ['s', 'u', 'v']) 
101 
assert_equal(nx.astar_path_length(G, 's', 'v'), 2) 
102  
103 
@raises(nx.NodeNotFound)

104 
def test_astar_nopath(self): 
105 
nx.astar_path(self.XG, 's', 'moon') 
106  
107 
def test_cycle(self): 
108 
C = nx.cycle_graph(7)

109 
assert_equal(nx.astar_path(C, 0, 3), [0, 1, 2, 3]) 
110 
assert_equal(nx.dijkstra_path(C, 0, 4), [0, 6, 5, 4]) 
111  
112 
def test_unorderable_nodes(self): 
113 
"""Tests that A* accommodates nodes that are not orderable.

114 

115 
For more information, see issue #554.

116 

117 
"""

118 
# TODO In Python 3, instances of the `object` class are

119 
# unorderable by default, so we wouldn't need to define our own

120 
# class here, we could just instantiate an instance of the

121 
# `object` class. However, we still support Python 2; when

122 
# support for Python 2 is dropped, this test can be simplified

123 
# by replacing `Unorderable()` by `object()`.

124 
class Unorderable(object): 
125  
126 
def __le__(self): 
127 
raise NotImplemented 
128  
129 
def __ge__(self): 
130 
raise NotImplemented 
131  
132 
# Create the cycle graph on four nodes, with nodes represented

133 
# as (unorderable) Python objects.

134 
nodes = [Unorderable() for n in range(4)] 
135 
G = nx.Graph() 
136 
G.add_edges_from(pairwise(nodes, cyclic=True))

137 
path = nx.astar_path(G, nodes[0], nodes[2]) 
138 
assert_equal(len(path), 3) 