1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#!/usr/bin/env python
from nose.tools import *
import networkx as nx
from random import random, choice
class TestAStar:
def setUp(self):
self.XG=nx.DiGraph()
self.XG.add_edges_from([('s','u',{'weight':10}),
('s','x',{'weight':5}),
('u','v',{'weight':1}),
('u','x',{'weight':2}),
('v','y',{'weight':1}),
('x','u',{'weight':3}),
('x','v',{'weight':5}),
('x','y',{'weight':2}),
('y','s',{'weight':7}),
('y','v',{'weight':6})])
def test_random_graph(self):
def dist((x1, y1), (x2, y2)):
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
G = nx.Graph()
points = [(random(), random()) for _ in xrange(100)]
# Build a path from points[0] to points[-1] to be sure it exists
for p1, p2 in zip(points[:-1], points[1:]):
G.add_edge(p1, p2, weight=dist(p1, p2))
# Add other random edges
for _ in xrange(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 path == nx.dijkstra_path(G, points[0], points[-1])
def test_astar_directed(self):
assert nx.astar_path(self.XG,'s','v')==['s', 'x', 'u', 'v']
assert nx.astar_path_length(self.XG,'s','v')==9
def test_astar_multigraph(self):
G=nx.MultiDiGraph(self.XG)
assert_raises((TypeError,nx.NetworkXError),
nx.astar_path, [G,'s','v'])
assert_raises((TypeError,nx.NetworkXError),
nx.astar_path_length, [G,'s','v'])
def test_astar_undirected(self):
GG=self.XG.to_undirected()
assert nx.astar_path(GG,'s','v')==['s', 'x', 'u', 'v']
assert nx.astar_path_length(GG,'s','v')==8
def test_astar_directed2(self):
XG2=nx.DiGraph()
XG2.add_edges_from([[1,4,{'weight':1}],
[4,5,{'weight':1}],
[5,6,{'weight':1}],
[6,3,{'weight':1}],
[1,3,{'weight':50}],
[1,2,{'weight':100}],
[2,3,{'weight':100}]])
assert nx.astar_path(XG2,1,3)==[1, 4, 5, 6, 3]
def test_astar_undirected2(self):
XG3=nx.Graph()
XG3.add_edges_from([ [0,1,{'weight':2}],
[1,2,{'weight':12}],
[2,3,{'weight':1}],
[3,4,{'weight':5}],
[4,5,{'weight':1}],
[5,0,{'weight':10}] ])
assert nx.astar_path(XG3,0,3)==[0, 1, 2, 3]
assert nx.astar_path_length(XG3,0,3)==15
def test_astar_undirected3(self):
XG4=nx.Graph()
XG4.add_edges_from([ [0,1,{'weight':2}],
[1,2,{'weight':2}],
[2,3,{'weight':1}],
[3,4,{'weight':1}],
[4,5,{'weight':1}],
[5,6,{'weight':1}],
[6,7,{'weight':1}],
[7,0,{'weight':1}] ])
assert nx.astar_path(XG4,0,2)==[0, 1, 2]
assert 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','v'), ('x','y'), ('y','s'), ('y','v')])
assert nx.astar_path(G,'s','v')==['s', 'u', 'v']
assert nx.astar_path_length(G,'s','v')== 2
def test_astar_nopath(self):
G=self.XG
assert_raises((TypeError,nx.NetworkXError),
nx.astar_path, [G,'s','moon'])
def test_cycle(self):
C=nx.cycle_graph(7)
assert nx.astar_path(C,0,3)==[0, 1, 2, 3]
assert nx.dijkstra_path(C,0,4)==[0, 6, 5, 4]
|
