diff options
| -rw-r--r-- | algorithms.py | 23 | ||||
| -rw-r--r-- | server.py | 29 | ||||
| -rw-r--r-- | store.py | 2 |
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 @@ -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) @@ -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() |