From cdcdf5de8846b0fe1cb91cc0c6ec41f5842c7c98 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 19 Nov 2020 15:38:33 +0100 Subject: implement union-find --- store.py | 41 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 39 insertions(+), 2 deletions(-) diff --git a/store.py b/store.py index 9e6d4f7..f98bb25 100644 --- a/store.py +++ b/store.py @@ -1,4 +1,5 @@ from osm_parser import get_default_parser +from collections import defaultdict class Node: @@ -8,6 +9,27 @@ class Node: self.lng = float(lng) self.neighbours = [] + self.parent = None + self.size = 1 + + def find_root(self): + if not self.parent: + return self + else: + return self.parent.find_root() + + def union(self, other): + this = self.find_root() + other = other.find_root() + + if this == other: + return + + if this.size < other.size: + this, other = other, this + + other.parent = this + this.size += other.size def coord_tuple(self): return self.lat, self.lng @@ -29,6 +51,7 @@ def add_neighbours(nodes): nodes[node1].neighbours.append(nodes[node2]) nodes[node2].neighbours.append(nodes[node1]) + nodes[node1].union(nodes[node2]) return nodes @@ -48,11 +71,25 @@ def extract_osm_nodes(f_name): if not node.neighbours: del nodes[node_id] - return nodes + # construct a forest of disjoint trees using union-find + forest = defaultdict(dict) # contains {root: tree} + for node_id, node in nodes.items(): + forest[node.find_root().id][node_id] = node + + # find the largest disjoin tree + best_size = 0 + best_tree = None + for root in forest: + tree = forest[root] + size = len(tree) + if size > best_size: + best_size = size + best_tree = tree + + return best_tree 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] - -- cgit v1.2.1 From 7f6aae6eb8f07b71c32311347ddbce92a3874c7d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 19 Nov 2020 16:19:42 +0100 Subject: show unconnected nodes on map --- server.py | 10 +++++++++- store.py | 9 ++++++++- templates/index.js | 11 +++++++++-- 3 files changed, 26 insertions(+), 4 deletions(-) diff --git a/server.py b/server.py index 6a93018..ae74084 100644 --- a/server.py +++ b/server.py @@ -11,7 +11,9 @@ nodes = None @get('/') def index(): global nodes - nodes = store.extract_osm_nodes("university.osm") + global unconnected_nodes + nodes, unconnected_nodes = store.extract_osm_nodes("university.osm") + return read_html('templates/index.html') @@ -23,6 +25,12 @@ def show_area(): return json.dumps(rect) +@get('/show-unconnected-nodes') +def show_unconnected_nodes(): + print(f"Showing {len(unconnected_nodes)} unconnected nodes") + return json.dumps({node.id: node.coord_tuple() for node in unconnected_nodes}) + + @post('/shortest-path') def shortest_path(body): body = json.loads(body) diff --git a/store.py b/store.py index f98bb25..c74415b 100644 --- a/store.py +++ b/store.py @@ -79,14 +79,21 @@ def extract_osm_nodes(f_name): # find the largest disjoin tree best_size = 0 best_tree = None + best_root = None for root in forest: tree = forest[root] size = len(tree) if size > best_size: best_size = size best_tree = tree + best_root = root - return best_tree + unconnected_nodes = [] + for _, node in nodes.items(): + if node.find_root().id != best_root: + unconnected_nodes.append(node) + + return best_tree, unconnected_nodes def select_nodes_in_rectangle(nodes, min_lat, max_lat, min_long, max_long): diff --git a/templates/index.js b/templates/index.js index b7b3b58..3edbd26 100644 --- a/templates/index.js +++ b/templates/index.js @@ -49,7 +49,6 @@ map.on('click', handleMapClick) function showMarker(){ var marker = L.marker([58.3984, 15.5733]).addTo(map) } - showMarker() async function showMarkers() { @@ -59,5 +58,13 @@ async function showMarkers() { var marker = L.marker(res[key]).addTo(map) } } - showMarkers() + +async function showUnconnectedMarkers() { + res = await fetch('/show-unconnected-nodes'); + res = await res.json(); + for (let key in res) { + var marker = L.marker(res[key]).addTo(map) + } +} +showUnconnectedMarkers() -- cgit v1.2.1 From 929d4caa2ba4771d92dfb979eda94649ba27c8a4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Tue, 24 Nov 2020 12:39:20 +0100 Subject: update comments --- store.py | 24 ++++++++++++++++++++---- 1 file changed, 20 insertions(+), 4 deletions(-) diff --git a/store.py b/store.py index c74415b..d0e1cff 100644 --- a/store.py +++ b/store.py @@ -13,21 +13,28 @@ class Node: self.size = 1 def find_root(self): + """ Recursively find the root of this node. """ if not self.parent: return self else: return self.parent.find_root() def union(self, other): + """ Mark this node and some other node as part of the same tree. """ this = self.find_root() other = other.find_root() + # If we share the same root we are already part of the same tree if this == other: return + # Minimize tree size. This ensures optimal complexity. + # We could also store the rank instead. if this.size < other.size: this, other = other, this + # This is safe since other is a root node and currently doesn't have a + # parent. other.parent = this this.size += other.size @@ -51,6 +58,7 @@ def add_neighbours(nodes): 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]) return nodes @@ -66,17 +74,25 @@ def extract_osm_nodes(f_name): add_neighbours(nodes) - # remove nodes without neighbours + # Remove nodes without neighbours for node_id, node in nodes.copy().items(): if not node.neighbours: del nodes[node_id] - # construct a forest of disjoint trees using union-find - forest = defaultdict(dict) # contains {root: tree} + # Construct a forest of disjoint trees. + # The forest is a { root: tree }-dict. If we construct a relation where + # two nodes relate to each other if they are a part of the same tree, + # this can be shown to be an equivalence relation where the equivalence + # class is some node in the tree. In our case, the equivalence class + # becomes the root of each node since it will be the same for all nodes + # in the same tree due our use of union-find. + forest = defaultdict(dict) for node_id, node in nodes.items(): forest[node.find_root().id][node_id] = node - # find the largest disjoin tree + # Find the largest disjoint tree. + # We store the root so we can easily test if a node is part of this + # tree or not. best_size = 0 best_tree = None best_root = None -- cgit v1.2.1 From 28bf2e9d0df6e093c80d62d5fc9a27bff7d87104 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Tue, 15 Dec 2020 09:33:56 +0100 Subject: Apply 1 suggestion(s) to 1 file(s) --- templates/index.js | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/templates/index.js b/templates/index.js index 3edbd26..0bbcdbe 100644 --- a/templates/index.js +++ b/templates/index.js @@ -62,7 +62,7 @@ showMarkers() async function showUnconnectedMarkers() { res = await fetch('/show-unconnected-nodes'); - res = await res.json(); + const res = await fetch('/show-unconnected-nodes').then(res => res.json()); for (let key in res) { var marker = L.marker(res[key]).addTo(map) } -- cgit v1.2.1 From 21a531eac5b953aeab14e4e8ae887695e8a4c4aa Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Tue, 15 Dec 2020 09:35:12 +0100 Subject: remove unused line --- templates/index.js | 1 - 1 file changed, 1 deletion(-) diff --git a/templates/index.js b/templates/index.js index 0bbcdbe..01e3880 100644 --- a/templates/index.js +++ b/templates/index.js @@ -61,7 +61,6 @@ async function showMarkers() { showMarkers() async function showUnconnectedMarkers() { - res = await fetch('/show-unconnected-nodes'); const res = await fetch('/show-unconnected-nodes').then(res => res.json()); for (let key in res) { var marker = L.marker(res[key]).addTo(map) -- cgit v1.2.1