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

History | View | Annotate | Download (4.91 KB)

1 | 5cef0f13 | tiamilani | 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) |