diff options
| -rw-r--r-- | Graph.pyc | bin | 6081 -> 12796 bytes | |||
| -rw-r--r-- | algorithms.py | 64 | ||||
| -rw-r--r-- | lib.py | 70 | ||||
| -rw-r--r-- | routes.py | 0 | ||||
| -rw-r--r-- | server.py | 58 | ||||
| -rw-r--r-- | templates/index.html | 2 | ||||
| -rw-r--r-- | test_dijkstra.py | 46 |
7 files changed, 91 insertions, 149 deletions
| Binary files differ diff --git a/algorithms.py b/algorithms.py index 75cd3b7..f39910c 100644 --- a/algorithms.py +++ b/algorithms.py @@ -1,50 +1,14 @@ -import math -from collections import defaultdict - - - -def disjoint_forest(nodes, edges): - """ Algorithm to test how many components there are - in our graph. There should optimally be few components - and one with the bulk of all the nodes.""" - ranks = defaultdict(int) - parents = {} - - for node in nodes.keys(): - parents[node] = node - - def find_parent(node): - if node != parents[node]: - node = find_parent(parents[node]) - return node - - def union (node1, node2): - node1, node2 = find_parent(node1), find_parent(node2) - rank1, rank2 = ranks[node1], ranks[node2] - if rank1 < rank2: - parents[node1] = node2 - else: - parents[node2] = node1 - if rank1 == rank2: - ranks[node1] += 1 - - for node, node2 in edges: - union(node, node2) - - sets = defaultdict(set) - for node, parent in parents.items(): - parent = find_parent(parent) - sets[parent].add(node) - - print("Total Nodes: ", len(nodes)) - print("Disjoint components: ", len(sets.keys())) - - max_size = 0 - for set_nodes in sets.values(): # Find biggest component - if len(set_nodes) > max_size: - max_size = len(set_nodes) - - print("Size of biggest component:", max_size) - - return sets, find_parent - +import math + +def length_haversine(p1, p2): + lat1 = p1.lat + lng1 = p1.lng + lat2 = p2.lat + lng2 = p2.lng + lat1, lng1, lat2, lng2 = map(math.radians, [lat1, lng1, lat2, lng2]) + dlat = lat2 - lat1 + dlng = lng2 - lng1 + a = math.sin(dlat / 2) ** 2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlng / 2) ** 2 + c = 2 * math.asin(math.sqrt(a)) + + return 6372797.560856 * c # return the distance in meters
\ No newline at end of file @@ -1,7 +1,7 @@ import os import io import re - +from http.server import HTTPServer, BaseHTTPRequestHandler posts = {} gets = {} @@ -26,7 +26,11 @@ def get_relative_path(): def read_html(relative_file_path): """ Reads the html file on the file location provided and injects any external files (marked with {{file_path}} ) - that may be present. """ + that may be present. Returns the html content as a string. + + Example: + >>> html_string = read_html('templates/index.html') + """ dir_path = get_relative_path() file_path = os.path.join(dir_path, relative_file_path) with open(file_path) as file: @@ -35,10 +39,13 @@ 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 path. Useful for seperation of javascript and css files.""" - - pattern = r'{{([^<]+)}}' + """ 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 + """ + # https://regex101.com/ + pattern = r'{{([^}]+)}}' external_files = re.findall(pattern, html_content) new_html_content = html_content for match in external_files: @@ -59,7 +66,9 @@ 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. """ + 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. """ def decorator(handler_function): posts[route] = handler_function @@ -69,10 +78,53 @@ def post(route = '/'): def get(route = '/'): """ A decorator that takes in the route path as argument, and then - puts the get handler in the dictionary, with the route as a key. """ + puts the get handler in the dictionary, with the route as a key. + The handler function should return either `bytes` or `str`. """ def decorator(handler_function): gets[route] = handler_function return handler_function - return decorator
\ No newline at end of file + return decorator + + +# 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 + """ + + def _set_headers(self): + """ Standard header stuff that has to be done """ + 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 """ + self._set_headers() + res = find_get(self.path) + if hasattr(res, 'encode'): + self.wfile.write(res.encode()) + else: + self.wfile.write(res) + + + def do_POST(self): + """ An async ajax request. Find the function from 'posts.py' to handle this + particular request. + """ + 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) + 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}.') + server.serve_forever() +
\ No newline at end of file diff --git a/routes.py b/routes.py deleted file mode 100644 index e69de29..0000000 --- a/routes.py +++ /dev/null @@ -1,57 +1 @@ -from http.server import HTTPServer, BaseHTTPRequestHandler -import lib - - - -class Request(): - def __init__(self, body): - self.body = body - - -# 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 - """ - - def _set_headers(self): - """ Standard header stuff that has to be done """ - 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 """ - self._set_headers() - res = lib.find_get(self.path) - if hasattr(res, 'encode'): - self.wfile.write(res.encode()) - else: - self.wfile.write(res) - - - def do_POST(self): - """ An async ajax request. Find the function from 'posts.py' to handle this - particular request. - """ - self.send_response(200) - self.end_headers() - content_length = int(self.headers['Content-Length']) - body = self.rfile.read(content_length) - request = Request(body) - res = lib.find_post(self.path, request) - self.wfile.write(res.encode()) - - -def run (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}.') - server.serve_forever() - - - -if __name__ == '__main__': - run() - +## Work yo magic xDDDD
\ No newline at end of file diff --git a/templates/index.html b/templates/index.html index 004c33f..717adc7 100644 --- a/templates/index.html +++ b/templates/index.html @@ -47,6 +47,8 @@ </div> </form> <script type="text/javascript" src="http://maps.googleapis.com/maps/api/js?key=REPLACE_WITH_YOUR_API_KEY&sensor=false"></script> + {{ templates/index.js }} + </body> </html> diff --git a/test_dijkstra.py b/test_dijkstra.py index 76799de..4f54b4e 100644 --- a/test_dijkstra.py +++ b/test_dijkstra.py @@ -1,39 +1,19 @@ import Graph - +from collections import defaultdict +from heapq import heappush, heappop +import math def dijkstra(adjacency_list, source, target): - """ To be implemented by students. Should return (distance, path). - Path should be a list of the vertices in the shortest path - including the source and target. """ - return 6.433, ['A', 'C', 'D'] - - -def test_dijkstra(): - vertices = [ - ('A', 0, 0), - ('B', 2, 2), - ('C', 2, -2), - ('D', 4, 1), - ('E', 4, -2), - ('F', 6, 1) - ] - - edges = [ - ('A', 'B'), - ('A', 'C'), - ('C', 'D'), - ('B', 'C'), - ('D', 'F'), - ('B', 'E'), - ('A', 'F') - ] + """ To be implemented by students. `adjacency_list` is a dictionary with values: (vertice, weight). + Function should return (distance, path). Path should be a list of the vertices in the shortest path + **including** the source and target. If no shortest path is found, it should return (infinity, []) """ - graph = Graph.Dijkstra(vertices, edges, 'A', 'D') - dist1, path1 = graph.get_shortest_path() - dist2, path2 = dijkstra(graph.adjacency_list, graph.source, graph.target) - assert abs(dist1-dist2) < 1e-3 - print('Correct distance') - assert path1 == path2 - print('Correct path') + return math.inf, [source] +if __name__ == '__main__': + try: + Graph.test_dijkstra(dijkstra) + print('Passed ALL tests!') + except AssertionError: + print('Failed one or more tests')
\ No newline at end of file |