Aluode/PerceptionLabPortable

1from collections import defaultdict
2
3import numpy as np
4from numpy.testing import assert_array_almost_equal
5
6from sklearn.utils.graph import single_source_shortest_path_length
7
8
9def floyd_warshall_slow(graph, directed=False):
10    N = graph.shape[0]
11
12    # set nonzero entries to infinity
13    graph[np.where(graph == 0)] = np.inf
14
15    # set diagonal to zero
16    graph.flat[:: N + 1] = 0
17
18    if not directed:
19        graph = np.minimum(graph, graph.T)
20
21    for k in range(N):
22        for i in range(N):
23            for j in range(N):
24                graph[i, j] = min(graph[i, j], graph[i, k] + graph[k, j])
25
26    graph[np.where(np.isinf(graph))] = 0
27
28    return graph
29
30
31def generate_graph(N=20):
32    # sparse grid of distances
33    rng = np.random.RandomState(0)
34    dist_matrix = rng.random_sample((N, N))
35
36    # make symmetric: distances are not direction-dependent
37    dist_matrix = dist_matrix + dist_matrix.T
38
39    # make graph sparse
40    i = (rng.randint(N, size=N * N // 2), rng.randint(N, size=N * N // 2))
41    dist_matrix[i] = 0
42
43    # set diagonal to zero
44    dist_matrix.flat[:: N + 1] = 0
45
46    return dist_matrix
47
48
49def test_shortest_path():
50    dist_matrix = generate_graph(20)
51    # We compare path length and not costs (-> set distances to 0 or 1)
52    dist_matrix[dist_matrix != 0] = 1
53
54    for directed in (True, False):
55        if not directed:
56            dist_matrix = np.minimum(dist_matrix, dist_matrix.T)
57
58        graph_py = floyd_warshall_slow(dist_matrix.copy(), directed)
59        for i in range(dist_matrix.shape[0]):
60            # Non-reachable nodes have distance 0 in graph_py
61            dist_dict = defaultdict(int)
62            dist_dict.update(single_source_shortest_path_length(dist_matrix, i))
63
64            for j in range(graph_py[i].shape[0]):
65                assert_array_almost_equal(dist_dict[j], graph_py[i, j])
66