diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Graph.pyc | bin | 0 -> 6081 bytes | |||
| -rw-r--r-- | README.md | 10 | ||||
| -rw-r--r-- | algorithms.py | 50 | ||||
| -rw-r--r-- | data/favicon.ico | bin | 0 -> 1150 bytes | |||
| -rw-r--r-- | lib.py | 78 | ||||
| -rw-r--r-- | osm_parser.py | 201 | ||||
| -rw-r--r-- | routes.py | 0 | ||||
| -rw-r--r-- | server.py | 57 | ||||
| -rw-r--r-- | store.py | 0 | ||||
| -rw-r--r-- | templates/index.css | 11 | ||||
| -rw-r--r-- | templates/index.html | 52 | ||||
| -rw-r--r-- | templates/index.js | 79 | ||||
| -rw-r--r-- | test_dijkstra.py | 39 |
14 files changed, 578 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..ed8ebf5 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +__pycache__
\ No newline at end of file diff --git a/Graph.pyc b/Graph.pyc Binary files differnew file mode 100644 index 0000000..5f61861 --- /dev/null +++ b/Graph.pyc diff --git a/README.md b/README.md new file mode 100644 index 0000000..6d72bc5 --- /dev/null +++ b/README.md @@ -0,0 +1,10 @@ +## Getting started + +Clone this repo and then remove the `.git` folder: +``` +git clone https://gitlab.ida.liu.se/tdde25/ctf +cd ctf +rm -rf .git +``` +> After you have cloned the repo, feel free to delete this `README.md` file. +Next go to our [wiki](https://gitlab.ida.liu.se/tdde25/maps/wikis/home) and get started on the tutorials. diff --git a/algorithms.py b/algorithms.py new file mode 100644 index 0000000..75cd3b7 --- /dev/null +++ b/algorithms.py @@ -0,0 +1,50 @@ +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 + diff --git a/data/favicon.ico b/data/favicon.ico Binary files differnew file mode 100644 index 0000000..3678e16 --- /dev/null +++ b/data/favicon.ico @@ -0,0 +1,78 @@ +import os +import io +import re + + +posts = {} +gets = {} + +def find_get(path): + try: + return gets[path]() + except KeyError: + return "404" + + +def find_post(path, request): + try: + return posts[path](request) + except KeyError: + return "404" + +def get_relative_path(): + return os.path.dirname(os.path.abspath(__file__)) + + +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. """ + dir_path = get_relative_path() + file_path = os.path.join(dir_path, relative_file_path) + with open(file_path) as file: + html_content = file.read() + html_content = inject_external_files(html_content) + 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'{{([^<]+)}}' + external_files = re.findall(pattern, html_content) + new_html_content = html_content + for match in external_files: + external_file_path = match.replace(' ', '') + external_file = open(os.path.join(get_relative_path(), external_file_path)) + file_content = external_file.read() + external_file.close() + + if match.find('.css') != -1: + file_content = '<style>\n' + file_content + '</style>' + elif match.find('.js') != -1: + file_content = '<script>\n' + file_content + '</script>' + + to_be_replaced = '{{' + match + '}}' + new_html_content = new_html_content.replace(to_be_replaced, file_content) + return new_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. """ + + def decorator(handler_function): + posts[route] = handler_function + return handler_function + + return decorator + +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. """ + + def decorator(handler_function): + gets[route] = handler_function + return handler_function + + return decorator
\ No newline at end of file diff --git a/osm_parser.py b/osm_parser.py new file mode 100644 index 0000000..60754c9 --- /dev/null +++ b/osm_parser.py @@ -0,0 +1,201 @@ +# Henrik 'catears' Adolfsson, henad221@student.liu.se +# Date: 2014-11-09 +# Copyright (c) 2014 Henrik Adolfsson +# Licensed under MIT License (see bottom of file) + +""" +In this file you will find a class that can parse OpenStreetMap Node-data and OpenStreetMap Way-data. +There is a helper function for retrieving a default parser called get_default_parser(fname) +It provides you with a basic parser that can iterate over nodes and iterate over ways + +If you want to tweak the behaviour of the default parser you can change the +tags that will be returned with the tuples DEFAULT_NODE/WAY_TAGS under the Module Config-section + +The default parser will return edges with tags if they exist in "DEFAULT_WAY_TAGS". +You can tweak the behaviour of the default parser so that it will return all tags it encounters. +You do this by calling 'get_default_parser(fname, allow_all=True)' + +The only dependency of the module is the xml.etree.ElementTree which +is a part of the python library for both py2 and py3 +""" + +import xml.etree.ElementTree as ET +FILEEXT = ".osm" + + +########################################## +# Module config # +########################################## +DEFAULT_NODE_TAGS = ('id', 'lat', 'lon') +DEFAULT_WAY_TAGS = ('highway', 'name', 'oneway') + + +########################################## +# OSM Specific Keys # +########################################## +OSM_NODE = "node" +OSM_WAY = "way" +OSM_WAYNODE = "nd" +OSM_NODE_REFERENCE = "ref" +OSM_TAG = "tag" +OSM_WAY_ID = "id" +OSM_TAG_KEY = "k" +OSM_TAG_VALUE = "v" + + +########################################## +# Ouput keys for returned dictionary # +########################################## +OUT_EDGE_ID = "id" +OUT_EDGES_KEY = "road" +OUT_TAGS_KEY = "tags" + + +########################################## +# Parser implementation # +########################################## + +class OSMParser: + """ + A Parser that parses OSM data and enables iterating over + Nodes and Ways as well as selecting which tags to show from the data. + + One of the focuses of the parser has been to create something simple + that abstracts away as much object oriented features as possible from a normal user + + Essentially the parser will parse the XML file and convert each element present + in the XML file into a python dictionary. (since this key-value stuff is basically what xml is) + """ + + + def __init__(self, fname, all_way_tags): + """ + Initialize. if all_way_tags is True then the parser will return ways + with all tags, otherwise it will only choose specific tags + """ + if not FILEEXT in fname: + fname = fname + FILEEXT + + self.tree = ET.parse(fname) # ET, parse home + self.node_tags = set() + self.way_tags = set() + self.allow_all = all_way_tags + + + def add_node_tag(self, tag): + """ Adds a tag to be searched for when looking at nodes """ + self.node_tags.add(tag) + + + def add_way_tag(self, tag): + """ Adds a tag to be searched for when looking at ways (edges) """ + self.way_tags.add(tag) + + + def iter_nodes(self): + """ + Iterator-object for all nodes in osm-tree. + Returns a dictionary with the (manually) added tags + """ + # Root of xml tree + root = self.tree.getroot() + for node in root.iter(OSM_NODE): + + # yield a dictionary with all tags that are added to self.node_tags + yield { tag : node.attrib.get(tag, None) + for tag in self.node_tags + if tag in node.attrib } + + + def iter_ways(self): + """ + Iterator-object for all ways (edges) in osm-tree. + Returns a dictionary with the ways + """ + # Root of xml-tree + root = self.tree.getroot() + for way in root.iter(OSM_WAY): + + # Take out roads and tags + road = tuple( node.attrib[OSM_NODE_REFERENCE] + for node in way.iter(OSM_WAYNODE) ) + tags = { tag.attrib[OSM_TAG_KEY] : tag.attrib[OSM_TAG_VALUE] + for tag in way.iter(OSM_TAG) + if self.allow_all or tag.attrib[OSM_TAG_KEY] in self.way_tags} + + # Yield the edge id, the road and the tags + yield { + OUT_EDGE_ID : way.attrib[OSM_WAY_ID], + OUT_EDGES_KEY : road, + OUT_TAGS_KEY : tags, + } + + +########################################## +# Example Usage and Default Getter # +########################################## + +def get_default_parser(fname, allow_all=False, verbose=True): + """ + Returns a default parser + The config used can be tweaked inside the Module Config section + + allow_all sets if the parser should take all tags or if it should just + take the tags specified, in this case all tags inside DEFAULT_WAY_TAGS + """ + if verbose: + print("Parsing OSM data from: {}".format(fname)) + + parser = OSMParser(fname, allow_all) + + # Add default node and way tags + for tag in DEFAULT_NODE_TAGS: + parser.add_node_tag(tag) + + for tag in DEFAULT_WAY_TAGS: + parser.add_way_tag(tag) + + return parser + + +def print_osm_data(fname): + """ + Prints all the nodes and all the ways in the map + Good example of how to use the code =D + """ + # Create parser + parser = get_default_parser(fname) + + # Print all nodes + for node in parser.iter_nodes(): + print (node) + + # Print all ways that are tagged with highway + for way in parser.iter_ways(): + if 'highway' in way['tags']: + print (way) + + +""" +The MIT License + +Copyright (c) 2014 Henrik Adolfsson + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +""" diff --git a/routes.py b/routes.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/routes.py diff --git a/server.py b/server.py new file mode 100644 index 0000000..13e5697 --- /dev/null +++ b/server.py @@ -0,0 +1,57 @@ +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() + diff --git a/store.py b/store.py new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/store.py diff --git a/templates/index.css b/templates/index.css new file mode 100644 index 0000000..f8bab2c --- /dev/null +++ b/templates/index.css @@ -0,0 +1,11 @@ +html { height: 100% } +body { height: 80%; margin: 0; padding: 0 } +#map_canvas { height: 100%; width: 100% } +.row { + display:flex; +} +.col { + display: flex; + flex-direction: column; + margin: 2%; +}
\ No newline at end of file diff --git a/templates/index.html b/templates/index.html new file mode 100644 index 0000000..71a0005 --- /dev/null +++ b/templates/index.html @@ -0,0 +1,52 @@ +<html> + <head> + <meta name="viewport"content="initial-scale=1.0, user-scalable=no"/> + + {{ templates/index.css }} + + </head> + + <body> + + <div id="map_canvas"></div> + + <form id="path-form"> + <div class="row" > + <div class="col"> + Place marker for: + <div> + <input type="radio" name="marker-point" id="marker-point-start" checked="true" /> + <label for="marker-point-start">Start</label> + </div> + <div> + <input type="radio" name="marker-point" id="marker-point-end" /> + <label for="marker-point-end">Destination</label> + </div> + </div> + <div class="col"> + <div> + <label for="lat1">Start lat:</label> + <input name="lat1" id="lat1" /> + </div> + <div> + <label for="lng1">Start lng:</label> + <input name="lng1" id="lng1" /> + </div> + </div> + <div class="col"> + <div> + <label for="lat2">End latitude:</label> + <input name="lat2" id="lat2" /> + </div> + <div> + <label for="lng2">End longitude:</label> + <input name="lng2" id="lng2" /> + </div> + </div> + <input type="submit" /> + </div> + </form> + <script type="text/javascript" src="http://maps.googleapis.com/maps/api/js?key=AIzaSyBO7iAytSrxMTS21EovrsGI2TI73F3TyYg&sensor=false"></script> + {{ templates/index.js }} + </body> +</html> diff --git a/templates/index.js b/templates/index.js new file mode 100644 index 0000000..bc05ed7 --- /dev/null +++ b/templates/index.js @@ -0,0 +1,79 @@ +var map; +const form = document.querySelector('#path-form') +const markerIsStart = document.querySelector("#marker-point-start") +const markerIsEnd = document.querySelector("#marker-point-end") + +google.maps.event.addDomListener(window, 'load', initialize); +form.addEventListener('submit', postShortestPath, false) + + +function initialize() { + var mapOptions = { + center: new google.maps.LatLng(58.40384776751319, 15.578484535217285), + zoom: 15, + mapTypeId: google.maps.MapTypeId.ROADMAP + }; + var mapCanvas = document.getElementById("map_canvas") + map = new google.maps.Map(mapCanvas, mapOptions); + google.maps.event.addListener(map, 'click', handleMapClick) +} + +async function postShortestPath(event){ + event.preventDefault() + var lat1 = parseFloat(document.querySelector('#lat1').value) + var lng1 = parseFloat(document.querySelector('#lng1').value) + var lat2 = parseFloat(document.querySelector('#lat2').value) + var lng2 = parseFloat(document.querySelector('#lng2').value) + + // Check that they're not Nan (stops function if one is Nan) + if(!lat1 || !lng1 || !lat2 || !lng2) + return alert('Formatting Error: Coordinates are not float values.') + + req = {lat1, lng1, lat2, lng2} // Dictionary auto-keys + + res = await fetch('/shortest-path', { + method:'POST', + credentials: 'same-origin', + body: JSON.stringify(req) + }) + + res = await res.json() + var points = new google.maps.MVCArray() + console.log(res.path) + res.path.map(coord=>{ + var [lat, lng] = coord + var point = new google.maps.LatLng(lat, lng) + points.push(point) + }) + + createPolyline(points) +} + +function createPolyline(points){ + var polyline = new google.maps.Polyline({ + path: points, + map: map + }); +} + +function handleMapClick ({latLng}){ + createMarker(latLng, `Click: ${latLng}`) + console.log(latLng) + var {lat, lng} = latLng + var posNumber = markerIsStart.checked ? '1' : '2' + document.querySelector('#lat' + posNumber).value = lat() + document.querySelector('#lng' + posNumber).value = lng() + if(markerIsStart.checked) + markerIsEnd.checked = true + + +} + + +function createMarker (position, title){ + return new google.maps.Marker({ + map, + position, + title + }) +}
\ No newline at end of file diff --git a/test_dijkstra.py b/test_dijkstra.py new file mode 100644 index 0000000..76799de --- /dev/null +++ b/test_dijkstra.py @@ -0,0 +1,39 @@ +import Graph + + +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') + ] + + 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') + + |