Sabanci-opt/algos.py at main · N1hatG/Sabanci-opt · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from model import *
from typing import List

def get_points_in_range(radius, nodes: List[PopulationNode], min_dist = -1):
    # For each node i, returns the list of nodes that are in the radius of i, with population weighted
    # O(n^2) for now, maybe there is an O(nlogn) algorithm
    res = [[] for _ in range(len(nodes))]
    for i in range(len(nodes)):
        for j in range(len(nodes)):
            if i==j:
                res[i].append(j)
                continue
            if ((nodes[i].population_size * nodes[i].dist_to(nodes[j])) <= radius) and \
               ((nodes[i].population_size * nodes[i].dist_to(nodes[j])) >= min_dist):
                res[i].append(j)
    return res

def get_points_out_range(radius, nodes: List[PopulationNode], min_dist = -1):
    # For each node i, returns the list of nodes that are in the radius of i, with population weighted
    # O(n^2) for now, maybe there is an O(nlogn) algorithm
    res = [[] for _ in range(len(nodes))]
    for i in range(len(nodes)):
        for j in range(len(nodes)):
            if i==j:
                continue
            if (nodes[i].population_size * nodes[i].dist_to(nodes[j])) > radius:
                res[i].append(j)
            if (nodes[i].population_size * nodes[i].dist_to(nodes[j])) < min_dist:
                res[i].append(j)
    return res

def get_points_out_range_nw(radius, nodes: List[PopulationNode], min_dist = -1):
    # For each node i, returns the list of nodes that are in the radius of i, with population weighted
    # O(n^2) for now, maybe there is an O(nlogn) algorithm
    res = [[] for _ in range(len(nodes))]
    for i in range(len(nodes)):
        for j in range(len(nodes)):
            if i==j:
                continue
            if (nodes[i].dist_to(nodes[j])) > radius:
                res[i].append(j)
            if (nodes[i].dist_to(nodes[j])) < min_dist:
                res[i].append(j)
    return res