initial dijkstra

3 files changed, 40 insertions, 14 deletions

diff --git a/algorithms.py b/algorithms.py
index 7140a17..06d768c 100644
--- a/algorithms.py
+++ b/algorithms.py
@@ -1,3 +1,4 @@
+import heapq
 import math
 
 
@@ -32,4 +33,24 @@ def get_closest_node_id(nodes, source_node):
 
 def find_shortest_path(nodes, source_id, target_id):
     """ Return the shortest path using Dijkstra's algortihm. """
-    return []
+    queue = []
+    visited = set()
+
+    print("neighbours", nodes[source_id].neighbours)
+    for neighbour in nodes[source_id].neighbours:
+        heapq.heappush(queue, (length_haversine(nodes[source_id], neighbour), (source_id, neighbour.id)))
+
+    while queue:
+        cand_dist, cand_path = heapq.heappop(queue)
+        walk_end = cand_path[-1]
+        if walk_end == target_id:
+            return cand_path
+        if walk_end in visited:
+            continue
+        visited.add(walk_end)
+        for neighbour in nodes[walk_end].neighbours:
+            print(neighbour)
+            if neighbour not in visited:
+                heapq.heappush(queue, (cand_dist + length_haversine(nodes[walk_end], neighbour), cand_path + (neighbour.id, )))
+    # no path found
+    return None
diff --git a/server.py b/server.py
index e6ff6c2..6424466 100644
--- a/server.py
+++ b/server.py
@@ -5,29 +5,36 @@ import store
 from lib import run_server, get, post, read_html
 
 
+nodes = None
+
+
 @get('/')
 def index():
+    global nodes
+    nodes = store.extract_osm_nodes("university.osm")
     return read_html('templates/index.html')
 
 
 @get('/show-area')
 def show_area():
-    all = dict()
-    for (k, node) in enumerate(store.select_nodes_in_rectangle(store.extract_osm_nodes("university.osm"), 58.3984, 58.3990, 15.5733, 15.576)):
-        all[node.id] = node.coord_tuple()
-    return json.dumps(all)
+    global nodes
+    rect = dict()
+    for (k, node) in enumerate(store.select_nodes_in_rectangle(nodes, 58.3984, 58.3990, 15.5733, 15.576)):
+        rect[node.id] = node.coord_tuple()
+    return json.dumps(rect)
 
 
 @post('/shortest-path')
 def shortest_path(body):
+    global nodes
     body = json.loads(body)
-    source_id = algorithms.get_closest_node_id(store.nodes, store.Node(-1, body['lat1'], body['lng1']))
-    target_id = algorithms.get_closest_node_id(store.nodes, store.Node(-1, body['lat2'], body['lng2']))
-    print(source_id, target_id)
-    source_node = store.nodes[source_id]
-    target_node = store.nodes[target_id]
-    path = [(source_node.lat, source_node.lng), (target_node.lat, target_node.lng)]
-    response = {'path': path}
+    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 = algorithms.find_shortest_path(nodes, source_id, target_id)
+    print(path)
+    response = {"path": [(nodes[node].lat, nodes[node].lng) for node in path]}
+
     return json.dumps(response)
 
 
diff --git a/store.py b/store.py
index 253087d..9e6d4f7 100644
--- a/store.py
+++ b/store.py
@@ -14,7 +14,6 @@ class Node:
 
 
 parser = None  # Have a global reusable parser object
-nodes = None
 
 
 def add_neighbours(nodes):
@@ -36,7 +35,6 @@ def add_neighbours(nodes):
 
 def extract_osm_nodes(f_name):
     global parser
-    global nodes
     parser = get_default_parser(f_name)
     nodes = dict()