wip

5 files changed, 108 insertions, 13 deletions

diff --git a/algorithms.py b/algorithms.py
index 9f3fd78..9d4f538 100644
--- a/algorithms.py
+++ b/algorithms.py
@@ -1,5 +1,6 @@
 import heapq
 import math
+from store import get_relevant_neighbours
 
 
 def length_haversine(p1, p2):
@@ -17,6 +18,7 @@ def length_haversine(p1, p2):
     return 6372797.560856 * c  # return the distance in meters
 
 
+<<<<<<< HEAD
 def grid_search(grid, source_node):
     """
     Finds closest node to source node by comparing distance to nodes within
@@ -72,19 +74,25 @@ def get_closest_node(nodes, source_node):
     Searches through all nodes in a specified grid and return node
     closes to source node.
     """
+def get_closest_node_id(nodes, source_node, transport_mode):
+    """ Search through all nodes and return the id of the node
+    that is closest to 'source_node'. """
     min_node = None
     min_value = None
 
     for node in nodes:
         length = length_haversine(source_node, node)
-        if min_node is None or length < min_value:
+
+        relevant_neighbours = get_relevant_neighbours(node, transport_mode)
+
+        if (min_node is None or length < min_value) and relevant_neighbours:
             min_node = node
             min_value = length
 
     return min_node
 
 
-def find_shortest_path(nodes, source_id, target_id):
+def find_shortest_path(nodes, source_id, target_id, transport_mode: str):
     """ 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
@@ -102,10 +110,15 @@ def find_shortest_path(nodes, source_id, target_id):
         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:
+        end_node = nodes[walk_end]
+
+        relevant_neighbours = get_relevant_neighbours(end_node, transport_mode)
+
+        for neighbour in relevant_neighbours:
             if neighbour in visited:
                 # there exists a shorter walk to neighbour
                 continue
@@ -114,5 +127,6 @@ def find_shortest_path(nodes, source_id, target_id):
             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
diff --git a/server.py b/server.py
index 25d2826..7c89bf6 100644
--- a/server.py
+++ b/server.py
@@ -47,17 +47,28 @@ def show_unconnected_nodes():
 @post('/shortest-path')
 def shortest_path(body):
     body = json.loads(body)
+<<<<<<< HEAD
     source_id = algorithms.grid_search(grid,
                                        store.Node(-1, body['lat1'],
                                                   body['lng1']))
     target_id = algorithms.grid_search(grid,
                                        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]}
+=======
+    transport_mode = body['transport_mode']
+
+    source_id = algorithms.get_closest_node_id(nodes,
+                                               store.Node(-1, body['lat1'],
+                                                          body['lng1'])
+                                               transport_mode)
+    target_id = algorithms.get_closest_node_id(nodes,
+                                               store.Node(-1, body['lat2'],
+                                                          body['lng2'])
+                                               transport_mode)
+>>>>>>> 532c0cb... wip
+
+    path = algorithms.find_shortest_path(nodes, source_id, target_id, transport_mode)
+    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 c988e47..23dc50a 100644
--- a/store.py
+++ b/store.py
@@ -7,7 +7,8 @@ class Node:
         self.id = id
         self.lat = float(lat)
         self.lng = float(lng)
-        self.neighbours = []
+        self.neighbours_bike = []
+        self.neighbours_car = []
 
         self.parent = None
         self.size = 1
@@ -45,25 +46,43 @@ class Node:
 parser = None  # Have a global reusable parser object
 
 
-def add_neighbours(nodes):
+def add_neighbours_bike(nodes):
     for way in parser.iter_ways():
         if 'highway' not in way['tags']:
             continue
 
+        print(way)
+
         road = way['road']
 
         for i in range(len(road) - 1):
             node1 = road[i]
             node2 = road[i + 1]
 
+<<<<<<< HEAD
             nodes[node1].neighbours.append(nodes[node2])
             nodes[node2].neighbours.append(nodes[node1])
             # These two are neighbours and should be part of the same tree.
             nodes[node1].union(nodes[node2])
+=======
+            if suitable_car(way):
+                nodes[node1].neighbours_car.append(nodes[node2])
+                nodes[node2].neighbours_car.append(nodes[node1])
+
+            if suitable_bike(way):
+                nodes[node1].neighbours_bike.append(nodes[node2])
+                nodes[node2].neighbours_bike.append(nodes[node1])
+>>>>>>> 532c0cb... wip
 
     return nodes
 
 
+def add_neighbours_car(nodes):
+    for way in parser.iter_ways():
+        if 'highway' not in way['tags']:
+            continue
+
+
 def extract_osm_nodes(f_name):
     global parser
     parser = get_default_parser(f_name)
@@ -78,7 +97,7 @@ def extract_osm_nodes(f_name):
 
     # Remove nodes without neighbours
     for node_id, node in nodes.copy().items():
-        if not node.neighbours:
+        if not node.neighbours_car or not node.neighbours_bike:
             del nodes[node_id]
 
     # Construct a forest of disjoint trees.
@@ -131,3 +150,40 @@ def select_nodes_in_rectangle(nodes, min_lat, max_lat, min_long, max_long):
     return [node for node in nodes.values()
             if min_lat <= node.lat <= max_lat
             and min_long <= node.lng <= max_long]
+
+
+def get_relevant_neighbours(nodes, transport_mode):
+    if transport_mode == "bike":
+        return nodes.neighbours_bike
+    else:
+        return nodes.neighbours_car
+
+
+suitable_highway_types_bike = [
+    # Special road types
+    'living_street', 'service', 'pedestrian', 'track', 'road'
+]
+
+def suitable_bike(way):
+    tags = way['tags']
+
+    suitable_generic_type = tags['highway'] in suitable_highway_types_bike
+    suitable_bike = tags['bicycle'] == 'yes' if 'bicycle' in tags else False
+
+    return suitable_generic_type or suitable_bike
+
+
+suitable_highway_types_car = [
+    # Roads
+    'motorway', 'trunk', 'primary', 'secondary',
+    'tertiary', 'unclassified', 'residential',
+    # Link roads
+    'motorway_link', 'trunk_link', 'primary_link', 'secondary_link',
+    'tertiary_link',
+    # Special road types
+    'living_street', 'service',
+    'pedestrian', 'road' # FIXME: Handle predestrian and road differently?
+]
+
+def suitable_car(way):
+    return way['tags']['highway'] in suitable_highway_types_car
diff --git a/templates/index.html b/templates/index.html
index b29f84f..00e6208 100644
--- a/templates/index.html
+++ b/templates/index.html
@@ -9,6 +9,17 @@
         <form id="path-form">
                 <div class="row" >
                     <div class="col">
+                        Mode of transport:
+                        <div>
+                            <input type="radio" name="transport-mode" id="transport-mode-bike" checked="true" />
+                            <label for="transport-mode-bike">Bike</label>
+                        </div>
+                        <div>
+                            <input type="radio" name="transport-mode" id="transport-mode-car" />
+                            <label for="transport-mode-car">Car</label>
+                        </div>
+                    </div>
+                    <div class="col">
                         Place marker for:
                         <div>
                             <input type="radio" name="marker-point" id="marker-point-start" checked="true" />
@@ -47,4 +58,4 @@
         {{ templates/index.js }}
         
     </body>
-</html>
\ No newline at end of file
+</html>
diff --git a/templates/index.js b/templates/index.js
index 01e3880..42f8398 100644
--- a/templates/index.js
+++ b/templates/index.js
@@ -19,7 +19,10 @@ async function postShortestPath(event){
     if(!lat1 || !lng1  || !lat2 || !lng2)
         return alert('Formatting Error: Coordinates are not float values.')
     
-    req = {lat1, lng1, lat2, lng2} // Dictionary auto-keys
+    const transport_mode_elem = document.getElementById("transport-mode-bike")
+    const transport_mode = transport_mode_elem.checked ? "bike" : "car"
+
+    req = {lat1, lng1, lat2, lng2, transport_mode} // Dictionary auto-keys
 
     res = await fetch('/shortest-path', {
         method:'POST',