From 2eef624ac866070dbfec8a88e4b76cba4a4593d8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 5 Nov 2020 16:41:03 +0100 Subject: neighbor -> neighbour --- store.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/store.py b/store.py index e03ae77..fa5e5dc 100644 --- a/store.py +++ b/store.py @@ -6,7 +6,7 @@ class Node: self.id = id self.lat = float(lat) self.lng = float(lng) - self.neighbors = [] + self.neighbours = [] def coord_tuple(self): @@ -28,8 +28,8 @@ def add_neighbours(nodes): node1 = road[i] node2 = road[i + 1] - nodes[node1].neighbors.append(nodes[node2]) - nodes[node2].neighbors.append(nodes[node1]) + nodes[node1].neighbours.append(nodes[node2]) + nodes[node2].neighbours.append(nodes[node1]) return nodes -- cgit v1.2.1 From 5bd68cac4b2aa953bcc63e8e903ed8c5f2aec5c2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 5 Nov 2020 16:42:34 +0100 Subject: remove nodes without neighbours --- store.py | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/store.py b/store.py index fa5e5dc..253087d 100644 --- a/store.py +++ b/store.py @@ -45,6 +45,11 @@ def extract_osm_nodes(f_name): add_neighbours(nodes) + # remove nodes without neighbours + for node_id, node in nodes.copy().items(): + if not node.neighbours: + del nodes[node_id] + return nodes -- cgit v1.2.1 From 3a7c90f683c1c29790c2033de02c501f76735aa9 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 5 Nov 2020 16:42:57 +0100 Subject: is --- algorithms.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/algorithms.py b/algorithms.py index cc8d35f..7140a17 100644 --- a/algorithms.py +++ b/algorithms.py @@ -23,7 +23,7 @@ def get_closest_node_id(nodes, source_node): for node_id, node in nodes.items(): length = length_haversine(source_node, node) - if min_node == None or length < min_value: + if min_node is None or length < min_value: min_node = node_id min_value = length -- cgit v1.2.1 From 7f66e5c211ced9bc0286b893b9a86534fe9ec43a Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 5 Nov 2020 16:43:16 +0100 Subject: initial dijkstra --- algorithms.py | 23 ++++++++++++++++++++++- server.py | 29 ++++++++++++++++++----------- 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 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() -- cgit v1.2.1 From b6898e9503fda2b7f7ae4366da0895c0e140c133 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Fri, 6 Nov 2020 10:33:53 +0100 Subject: remobe unnecessary globals --- server.py | 2 -- 1 file changed, 2 deletions(-) diff --git a/server.py b/server.py index 6424466..6a93018 100644 --- a/server.py +++ b/server.py @@ -17,7 +17,6 @@ def index(): @get('/show-area') def show_area(): - 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() @@ -26,7 +25,6 @@ def show_area(): @post('/shortest-path') def shortest_path(body): - global nodes 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'])) -- cgit v1.2.1 From 7200d4c39f0a1c59bc73d49fcde7e041d28c7dfa Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Fri, 6 Nov 2020 10:34:09 +0100 Subject: remove unnecessary print --- algorithms.py | 1 - 1 file changed, 1 deletion(-) diff --git a/algorithms.py b/algorithms.py index 06d768c..3c84cf2 100644 --- a/algorithms.py +++ b/algorithms.py @@ -49,7 +49,6 @@ def find_shortest_path(nodes, source_id, target_id): 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 -- cgit v1.2.1 From d2791410cc886ef9f1fbed7b9525477963b8b994 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Fri, 6 Nov 2020 10:46:13 +0100 Subject: minor refactor --- algorithms.py | 29 +++++++++++++++++++---------- 1 file changed, 19 insertions(+), 10 deletions(-) diff --git a/algorithms.py b/algorithms.py index 3c84cf2..9d83b26 100644 --- a/algorithms.py +++ b/algorithms.py @@ -33,23 +33,32 @@ 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. """ - queue = [] + # queue contains multiple (path_length, (node_0, node_1, ... node_n))-tuples + # where (node_0, node_1, ... node_n) is a walk to node_n + queue = [(0, (source_id,))] 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] + # consider an unchecked walk + walk_dist, walk = heapq.heappop(queue) + walk_end = walk[-1] if walk_end == target_id: - return cand_path + # you have reached your destination + return walk 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) + # consider all our neighbours for neighbour in nodes[walk_end].neighbours: - if neighbour not in visited: - heapq.heappush(queue, (cand_dist + length_haversine(nodes[walk_end], neighbour), cand_path + (neighbour.id, ))) + if neighbour in visited: + # there exists a shorter walk to neighbour + continue + # otherwise this MIGHT be the shortest walk to neighbour + # so put it in the queue + new_dist = walk_dist + length_haversine(nodes[walk_end], neighbour) + new_walk = walk + (neighbour.id,) + heapq.heappush(queue, (new_dist, new_walk)) # no path found return None -- cgit v1.2.1 From 606c3eebe19114bcd2d07546a7c7d800ca84973f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Fri, 6 Nov 2020 10:54:18 +0100 Subject: more comments --- algorithms.py | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/algorithms.py b/algorithms.py index 9d83b26..6e01287 100644 --- a/algorithms.py +++ b/algorithms.py @@ -33,8 +33,9 @@ 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. """ - # queue contains multiple (path_length, (node_0, node_1, ... node_n))-tuples + # 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 queue = [(0, (source_id,))] visited = set() -- cgit v1.2.1