Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / 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)