diff options
Diffstat (limited to 'algorithms.py')
| -rw-r--r-- | algorithms.py | 64 |
1 files changed, 14 insertions, 50 deletions
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 |