diff options
| -rw-r--r-- | Graph.pyc | bin | 12796 -> 0 bytes | |||
| -rw-r--r-- | data/dijkstra.test | 59 | ||||
| -rw-r--r-- | lib.py | 42 | ||||
| -rw-r--r-- | templates/user.html | 2 | ||||
| -rw-r--r-- | test_dijkstra.py | 46 |
5 files changed, 126 insertions, 23 deletions
diff --git a/Graph.pyc b/Graph.pyc Binary files differdeleted file mode 100644 index 9e3b5d9..0000000 --- a/Graph.pyc +++ /dev/null diff --git a/data/dijkstra.test b/data/dijkstra.test new file mode 100644 index 0000000..22aba2d --- /dev/null +++ b/data/dijkstra.test @@ -0,0 +1,59 @@ +# -- Answers for the shortest path of the given graphs -- +# The file consists of a number of test cases. +# Feel free to provide your own test cases! +# Each test case has this structure: +# <number of nodes> +# <space separated SOURCE and DESTINATION node indexes> +# ... <space separated x y coordinates of each node> +# <number of edges> +# ... <space separated nodes edges> (NODE1 is connected to NODE2) +# <distance of the shortest path> +# ...<node ids of the shortest path in the order visited> +# Test case 1: +6 +0 5 +0 0 +2 2 +2 -2 +4 1 +4 -2 +6 1 +7 +0 1 +0 2 +2 3 +1 2 +3 5 +1 4 +0 5 +6.082762530298219 +0 5 +# Test case 2: +4 +0 3 +0 0 +2 0 +2 2 +4 0 +4 +0 1 +0 2 +1 3 +2 3 +4.0 +0 1 3 +# Test case 3: +5 +0 3 +1 3 +4 2 +-2 4 +1 5 +-1 4 +4 +0 1 +1 3 +4 3 +1 4 +7.404918347287664 +0 1 3
\ No newline at end of file @@ -1,22 +1,31 @@ import os import io import re +import sys from http.server import HTTPServer, BaseHTTPRequestHandler posts = {} gets = {} def find_get(path): + """ [Internal] - Used by the Handler class to try and + find the correct handler for a GET request. + """ try: return gets[path]() - except KeyError: + except Exception as e: + print(type(e), e) return "404" def find_post(path, request): + """ [Internal] - Used by the Handler class to try and + find the correct handler for a POST request. + """ try: return posts[path](request) - except KeyError: + except Exception as e: + print(type(e), e) return "404" def get_relative_path(): @@ -39,7 +48,7 @@ def read_html(relative_file_path): return html_content def inject_external_files(html_content): - """ Replaces {{ 'file_path' }} with the file content of that file + """ [Internal] - Replaces {{ 'file_path' }} with the file content of that file path. Useful for seperation of javascript and css files. Uses regex to capture the pattern. Here is a link to see how it works: https://regex101.com/r/v917NK/2 @@ -67,8 +76,8 @@ def inject_external_files(html_content): def post(route = '/'): """ A decorator that takes in the route path as argument, and then puts the post handler in the dictionary, with the route as a key. - The handler will receive one argument called 'body', where the body - of the post request will exist. """ + The handler will receive one `str` argument called 'body', + where the body of the post request will exist. """ def decorator(handler_function): posts[route] = handler_function @@ -89,19 +98,25 @@ def get(route = '/'): # Explanation: https://blog.anvileight.com/posts/simple-python-http-server/ + class Handler(BaseHTTPRequestHandler): - """ The class responsible for handling all the - different requests made to our server + """ [Internal] - The class responsible for handling all the + different requests made to our server. """ def _set_headers(self): - """ Standard header stuff that has to be done """ + """ Sets the headers for a response. This is to tell the browser + the status of the request that was sent. '200' means that everything + went fine. + """ self.send_response(200) self.send_header("Content-type", "text/html") self.end_headers() def do_GET(self): - """ Just serve up our one and only html page """ + """ Tries to find the handler for this GET request. The handler can + return either `bytes` or `str`. + """ self._set_headers() res = find_get(self.path) if hasattr(res, 'encode'): @@ -111,20 +126,21 @@ class Handler(BaseHTTPRequestHandler): def do_POST(self): - """ An async ajax request. Find the function from 'posts.py' to handle this - particular request. + """ Tries to find the handler for this POST request. The handler + will get the 'body' of the request as the argument. The body + is a `str`, formatted in JSON. """ self.send_response(200) self.end_headers() content_length = int(self.headers['Content-Length']) body = self.rfile.read(content_length) - res = find_post(self.path, body) + res = find_post(self.path, body.decode('utf-8')) self.wfile.write(res.encode()) def run_server (port = 8314): server_adress = ('', port) # Should make the port a command line argument server = HTTPServer(server_adress, Handler) - print(f'Starting server on port: {port}.') + print('Starting server on port: {}.'.format(port)) server.serve_forever()
\ No newline at end of file diff --git a/templates/user.html b/templates/user.html index cde9267..9245e91 100644 --- a/templates/user.html +++ b/templates/user.html @@ -1,4 +1,4 @@ - +<!--Template for the EXPANSION 'Allowing users to login and register 'securely' (2 points) ' --> <div id="user-stuff"> <button id="login">Show Login</button> <div id="login-info"> diff --git a/test_dijkstra.py b/test_dijkstra.py index a0f315c..f906b59 100644 --- a/test_dijkstra.py +++ b/test_dijkstra.py @@ -1,21 +1,49 @@ -import notebooks.Graph as Graph from collections import defaultdict from heapq import heappush, heappop import math def dijkstra(adjacency_list, source_id, target_id): - """ To be implemented by students. `adjacency_list` is a dictionary with structure: + """ To be implemented by students (optional exercise). `adjacency_list` is a dictionary with structure: {node_id: [...(neighbor_id, weight)]}. Function should return (distance, path). Path should be a list of the nodes in the shortest path - **including** the source_id and target_id. If no shortest path is found, it should return (infinity, []) """ - - return math.inf, [source_id] + **including** the source_id and target_id. If no shortest path is found, it should return (float('inf'), []) """ + return float('inf'), [] if __name__ == '__main__': + file = open('data/dijkstra.test') # Feel free to add your own test cases to the file! + testcase = 0 try: - Graph.test_dijkstra(dijkstra) - print('Passed ALL tests!') + while True: + num_nodes = file.readline() + if num_nodes[0] == '#': + continue + testcase += 1 + num_nodes = int(num_nodes) + source, target = map(int, file.readline().split()) + nodes = [] + for n in range(num_nodes): + x, y = map(float, file.readline().split()) + nodes.append((x, y)) + adjacency_list = defaultdict(list) + num_edges = int(file.readline()) + for m in range(num_edges): + v1, v2 = map(int, file.readline().split()) + x1, y1 = nodes[v1] + x2, y2 = nodes[v2] + weight = math.hypot(x2-x1, y2-y1) # Get distance between the nodes + adjacency_list[v1].append((v2, weight)) + adjacency_list[v2].append((v1, weight)) + correct_dist = float(file.readline()) + correct_path = [int(v) for v in file.readline().split()] + dist, path = dijkstra(adjacency_list, source, target) + assert abs(correct_dist-dist) < 1e-3 + assert correct_path == path + print("Passed test case {}".format(testcase)) except AssertionError: - print('Failed one or more tests') - + print("Failed test case {}".format(testcase)) + except IndexError: + print('Passed all test cases') + except EOFError: + print('Passed all test cases') + |