From 37e518cf9300cf88d71a2a63548be33fb0468cb4 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= <gusso230@student.liu.se>
Date: Thu, 12 Nov 2020 17:21:00 +0100
Subject: report number of iterations

---
 algorithms.py |  8 ++++++--
 server.py     | 16 ++++++++--------
 2 files changed, 14 insertions(+), 10 deletions(-)

diff --git a/algorithms.py b/algorithms.py
index 0537607..bd3cb75 100644
--- a/algorithms.py
+++ b/algorithms.py
@@ -46,14 +46,16 @@ def find_shortest_path_dijkstra(nodes, source_id, target_id):
     # and walk_dist is the total length of the walk in meters
     queue = [(0, (source_id,))]
     visited = set()
+    iterations = 0
 
     while queue:
+        iterations += 1
         # consider an unchecked walk
         walk_dist, walk = heapq.heappop(queue)
         walk_end = walk[-1]
         if walk_end == target_id:
             # you have reached your destination
-            return walk
+            return walk, iterations
         if walk_end in visited:
             # there exists a shorter walk to walk_end
             continue
@@ -77,12 +79,14 @@ def find_shortest_path_astar(nodes, source_id, target_id):
     """ Return the shortest path using A*. """
     queue = [(0, (source_id,))]
     visited = set()
+    iterations = 0
 
     while queue:
         walk_dist, walk = heapq.heappop(queue)
+        iterations += 1
         walk_end = walk[-1]
         if walk_end == target_id:
-            return walk
+            return walk, iterations
         if walk_end in visited:
             continue
         visited.add(walk_end)
diff --git a/server.py b/server.py
index bfe5b0f..9024ee2 100644
--- a/server.py
+++ b/server.py
@@ -31,18 +31,18 @@ def shortest_path(body):
     target_id = algorithms.get_closest_node_id(nodes, store.Node(-1, body['lat2'], body['lng2']))
 
     start = time.time()
-    astar = algorithms.find_shortest_path_astar(nodes,
-                                                source_id,
-                                                target_id)
+    astar, iters = algorithms.find_shortest_path_astar(nodes,
+                                                       source_id,
+                                                       target_id)
     stop = time.time()
-    print(f"A*   {stop-start:.4f}s  {algorithms.path_length(nodes, astar)}")
+    print(f"A*   {iters}  {stop-start:.4f}s  {algorithms.path_length(nodes, astar)}")
 
     start = time.time()
-    dijkstra = algorithms.find_shortest_path_dijkstra(nodes,
-                                                      source_id,
-                                                      target_id)
+    dijkstra, iters = algorithms.find_shortest_path_dijkstra(nodes,
+                                                             source_id,
+                                                             target_id)
     stop = time.time()
-    print(f"Dij  {stop-start:.4f}s  {algorithms.path_length(nodes, dijkstra)}")
+    print(f"Dij  {iters}  {stop-start:.4f}s  {algorithms.path_length(nodes, dijkstra)}")
 
     response = {"path": [(nodes[node].lat, nodes[node].lng) for node in astar]}
     return json.dumps(response)
-- 
cgit v1.2.1