visualize minimal number of iterations per edge

3 files changed, 37 insertions, 13 deletions

diff --git a/algorithms.py b/algorithms.py
index 1e70fa1..11f9e6b 100644
--- a/algorithms.py
+++ b/algorithms.py
@@ -69,24 +69,29 @@ def find_shortest_path(nodes, source_id, target_id):
     """ Return the shortest path using Dijkstra's algortihm. """
     # queue contains multiple (walk_dist, (node_0, node_1, ... node_n))-tuples
     # where (node_0, node_1, ... node_n) is a walk to node_n
-    # and walk_dist is the total length of the walk in meters
+    # and walk_dist is the total length of the walk in meters.
+    # iterations is the number of iterations the algorithm took before finding
+    # this node and is used for coloring.
     queue = [(0, (source_id,))]
     iterations = 0
-    visited = set()
+    visited = {}
 
     while queue:
         # consider an unchecked walk
         walk_dist, walk = heapq.heappop(queue)
-        walk_end = walk[-1]
         iterations += 1
+        walk_end = walk[-1]
         if walk_end == target_id:
             # you have reached your destination
-            return walk, iterations
+            return walk, iterations, visited
         if walk_end in visited:
             # there exists a shorter walk to walk_end
             continue
         # otherwise this is the shortest walk to walk_end
-        visited.add(walk_end)
+        if len(walk) == 1:
+            visited[walk_end] = (walk[-1], walk[-1], iterations)
+        else:
+            visited[walk_end] = (walk[-2], walk[-1], iterations)
         # consider all our neighbours
         for neighbour in nodes[walk_end].neighbours:
             if neighbour in visited:
diff --git a/server.py b/server.py
index d2bc8cc..1f4a93d 100644
--- a/server.py
+++ b/server.py
@@ -23,20 +23,39 @@ def show_area():
     return json.dumps(rect)
 
 
+def color_edges(nodes, colorer):
+    """ Color all edges in a list of nodes with a coloring function. """
+    return [{"path": [[node0.lat, node0.lng],
+                      [node1.lat, node1.lng]],
+             "color": colorer(colorer_t)}
+            for node0, node1, colorer_t in nodes]
+
+
 @post('/shortest-path')
 def shortest_path(body):
     body = json.loads(body)
     source_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat1'], body['lng1']))
     target_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat2'], body['lng2']))
 
-    path, iterations = algorithms.find_shortest_path(nodes, source_id, target_id)
-    edges = []
-    for i in range(len(path)-1):
-        edges.append({"path": [[nodes[path[i]].lat, nodes[path[i]].lng],
-                               [nodes[path[i+1]].lat, nodes[path[i+1]].lng]],
-                      "color": "#ff0000"})
+    path, total_iters, edges = algorithms.find_shortest_path(nodes, source_id, target_id)
+
+    def shortest_path_color(_):
+        """ Color edge as the shortest path. """
+        return "#2674CA"
+
+    def edge_color_iter(iters):
+        """ Color edge depending on how many iterations were taken to get there. """
+        return algorithms.lerp_color("#ff0000", "#00cc00", iters/total_iters)
+
+    shortest_path = color_edges([(nodes[path[i+0]], nodes[path[i+1]], None)
+                                 for i in range(len(path)-1)],
+                                shortest_path_color)
+
+    all_edges = color_edges([(nodes[node0], nodes[node1], iterations)
+                             for node0, node1, iterations in edges.values()],
+                            edge_color_iter)
 
-    return json.dumps({"edges": edges})
+    return json.dumps({"edges": all_edges + shortest_path})
 
 
 run_server()
diff --git a/templates/index.js b/templates/index.js
index a7cfd90..f7550c0 100644
--- a/templates/index.js
+++ b/templates/index.js
@@ -30,7 +30,7 @@ async function postShortestPath(event){
     res = await res.json()
 
     for (edge of res.edges) {
-        console.log(edge.path)
+        console.log(edge)
         L.polyline(edge.path, {
             color: edge.color
         }).addTo(map)