df = pd.DataFrame(clusters_points)
df['new_conn'] = df['connected']
nodes = df[['X', 'Y', 'area_m2', 'pop_sum', 'connected', 'new_conn']].reset_index().values.astype(int).tolist()
for node in nodes:
node.extend([0, [], []]) # add default 0's for off_grid_cost
def get_hash_table(clusters, distance_limit):
hash_table = defaultdict(lambda: defaultdict(list))
for node in clusters:
hash_x = int(node[1] / distance_limit)
hash_y = int(node[2] / distance_limit)
hash_table[hash_x][hash_y].append(node[0])
return hash_table
def get_near(hash_table, unelec_cluster, distance_limit):
near = []
hash_x = int(unelec_cluster[1] / distance_limit)
hash_y = int(unelec_cluster[2] / distance_limit)
near.extend(hash_table.get(hash_x, {}).get(hash_y, []))
near.extend(hash_table.get(hash_x, {}).get(hash_y - 1, []))
near.extend(hash_table.get(hash_x, {}).get(hash_y + 1, []))
near.extend(hash_table.get(hash_x + 1, {}).get(hash_y, []))
near.extend(hash_table.get(hash_x + 1, {}).get(hash_y - 1, []))
near.extend(hash_table.get(hash_x + 1, {}).get(hash_y + 1, []))
near.extend(hash_table.get(hash_x - 1, {}).get(hash_y, []))
near.extend(hash_table.get(hash_x - 1, {}).get(hash_y - 1, []))
near.extend(hash_table.get(hash_x - 1, {}).get(hash_y + 1, []))
return near
search_radii = [1000, 2000, 5000, 10000, 20000, 50000, 150000]
hash_tables = {}
for radius in search_radii:
hash_tables[radius] = get_hash_table(nodes, radius)
network = []
counter = 0
for node in nodes:
if node[5] == 0:
xs = node[1]
ys = node[2]
for radius, table in hash_tables.items():
near = get_near(table, node, radius)
if len(near) >= 5 or radius == search_radii[-1]: # also check if any near are connected?
for n in near:
if n != node[0] and node[0] not in nodes[n][9]:
xe = nodes[n][1]
ye = nodes[n][2]
length = sqrt((xe - xs)**2 + (ye - ys)**2)
network.append([counter, xs, ys, xe, ye, node[0], n, length, 0])
nodes[n][8].append(counter)
nodes[n][9].append(node[0])
node[8].append(counter)
node[9].append(n)
counter += 1
break
# off-grid costs
demand_per_person_kwh_month = 2 # 6kWh/month = MTF Tier 2
demand_per_person_kw_peak = demand_per_person_kwh_month / (4*30) # 130 4hours/day*30days/month based on MTF numbers, should use a real demand curve
mg_gen_cost_per_kw = 9e99
mg_cost_per_m2 = 2
for node in nodes:
if node[5] == 0:
node[7] = node[4]*demand_per_person_kw_peak*mg_gen_cost_per_kw + node[3]*mg_cost_per_m2
# grid costs
cost_wire_per_m = 39
grid_cost_per_m2 = 2
def find_best(nodes, network, index, prev_arc, b_pop, b_length, b_nodes, b_arcs, c_pop, c_length, c_nodes, c_arcs, tbc):
if nodes[index][6] == 0:
c_pop += nodes[index][4]
c_length += network[prev_arc][7]
c_nodes.append(index)
c_arcs.append(prev_arc)
if c_pop/c_length > b_pop/b_length:
b_pop = c_pop
b_length = c_length
b_nodes[:] = c_nodes[:]
b_arcs[:] = c_arcs[:]
connected_arcs = [network[arc_index] for arc_index in nodes[index][8]]
for arc in connected_arcs:
if arc[8] == 0 and arc[0] != prev_arc and arc[0] not in c_arcs and arc[0] not in [j for sub in [item[2] for item in tbc] for j in sub]:
goto = 6 if arc[5] == index else 5
if arc[goto] not in c_nodes:
nodes, network, b_pop, b_length, best_nodes, best_arcs = find_best(
nodes, network, arc[goto], arc[0],
b_pop, b_length, b_nodes, b_arcs,
c_pop, c_length, c_nodes, c_arcs, tbc)
return nodes, network, b_pop, b_length, b_nodes, b_arcs
def alt_best(nodes, network, index, prev_arc, b_pop, b_length, b_nodes, b_arcs, c_pop, c_length, c_nodes, c_arcs, tbc):
if nodes[index][6] == 0 and index not in [j for sub in [item[1] for item in tbc] for j in sub]:
c_pop += nodes[index][4]
c_length += network[prev_arc][7]
c_nodes.append(index)
c_arcs.append(prev_arc)
if c_pop/c_length > b_pop/b_length:
b_pop = c_pop
b_length = c_length
b_nodes[:] = c_nodes[:]
b_arcs[:] = c_arcs[:]
connected_arcs = [network[arc_index] for arc_index in nodes[index][8]]
for arc in connected_arcs:
if arc[8] == 0 and arc[0] != prev_arc and arc[0] not in c_arcs and arc[0] not in [j for sub in [item[2] for item in tbc] for j in sub]:
goto = 6 if arc[5] == index else 5
if arc[goto] not in c_nodes and arc[goto] not in [j for sub in [item[1] for item in tbc] for j in sub]:
nodes, network, b_pop, b_length, best_nodes, best_arcs = alt_best(
nodes, network, arc[goto], arc[0],
b_pop, b_length, b_nodes, b_arcs,
c_pop, c_length, c_nodes, c_arcs, tbc)
return nodes, network, b_pop, b_length, b_nodes, b_arcs
tbc = []
found = True
while found:
found = False
for node in nodes:
if node[6] == 1 or node[0] in [j for sub in [item[1] for item in tbc] for j in sub]:
print()
print()
print(' -------NODE ', node[0], '------')
connected_arcs = [network[arc_index] for arc_index in node[8]]
for arc in connected_arcs:
print('--ARC ', arc[0])
if arc[8] == 0 and arc[0] not in [j for sub in [item[2] for item in tbc] for j in sub]:
goto = 6 if arc[5] == node[0] else 5
nodes, network, b_length, b_pop, b_nodes, b_arcs = find_best(
nodes, network, arc[goto], arc[0], 0, 1e-9, [], [], 0, 1e-9, [], [], tbc)
best_nodes = [nodes[i] for i in b_nodes]
best_arcs = [network[i] for i in b_arcs]
mg_cost = sum([node[7] for node in best_nodes])
grid_cost = (cost_wire_per_m * sum(arc[7] for arc in best_arcs) +
grid_cost_per_m2 * sum([node[3] for node in best_nodes]))
if grid_cost < mg_cost:
# check if any have marked as tbc
found_worse = False
found_better = False
for index, item in enumerate(tbc):
if set(b_nodes).intersection(item[1]):
if b_pop/b_length < item[0]:
found_worse = True
remove_from_tbc = index
else:
found_better = True
break
if found_worse:
print('found worse so removing', tbc[remove_from_tbc])
del tbc[remove_from_tbc]
elif found_better:
nodes, network, b_length, b_pop, b_nodes, b_arcs = alt_best(
nodes, network, arc[goto], arc[0], 0, 1e-9, [], [], 0, 1e-9, [], [], tbc)
best_nodes = [nodes[i] for i in b_nodes]
best_arcs = [network[i] for i in b_arcs]
mg_cost = sum([node[7] for node in best_nodes])
grid_cost = (cost_wire_per_m * sum(arc[7] for arc in best_arcs) +
grid_cost_per_m2 * sum([node[3] for node in best_nodes]))
if grid_cost < mg_cost:
#print()
#print(tbc)
print('found better but adding', b_nodes, 'arcs', b_arcs)
tbc.append((b_pop/b_length, b_nodes, b_arcs))
continue
# mark as to be connected
print('adding ', b_nodes, 'arcs', b_arcs)
print()
tbc.append((b_pop/b_length, b_nodes, b_arcs))
found = True
print('tbc', tbc)
print()
print('TBC ', tbc)
print('####')
print('####')
print('####')
for item in tbc:
for node in item[1]:
nodes[node][6] = 1
for arc in item[2]:
network[arc][8] = 1
def find_best(nodes, network, index, prev_arc, br, bs, cr, cs, tbc):
if nodes[index][6] == 0 and index not in [c[0] for c in cs]:
#print('cs', [c[0] for c in cs])
#print('idx', index)
pop = cr[0] + nodes[index][4]
length = cr[1] + network[prev_arc][7]
cont = True
tentatives = [n[0] for n in tbc]
if index in tentatives:
cont = False
if pop/length > tbc[tentatives.index(index)][2]:
print('removing', tbc[tentatives.index(index)])
del tbc[tentatives.index(index)]
cont = True
cr = [pop, length]
cs = cs[:] + [(index, prev_arc, pop/length)]
if cont:
if len(br) == 0 or cr[0]/cr[1] > br[0]/br[1]:
br[:] = cr[:]
bs[:] = cs[:]
connected_arcs = [network[arc_index] for arc_index in nodes[index][8]]
for arc in connected_arcs:
if arc[8] == 0 and arc[0] != prev_arc and arc[0] not in [c[1] for c in cs]:# and arc[0] not in [n[2] for n in tbc]:
goto = 6 if arc[5] == index else 5
if arc[goto] not in [c[0] for c in cs]:
nodes, network, br, bs = find_best(
nodes, network, arc[goto], arc[0], br, bs, cr, cs, tbc)
else:
goto_arc = tbc[tentatives.index(index)][1]
node = network[goto_arc][5] if network[goto_arc][5] != index else network[goto_arc][6]
if node not in [c[0] for c in cs]:
nodes, network, br, bs = find_best(
nodes, network, node, goto_arc, br, bs, cr, cs, tbc)
return nodes, network, br, bs
tbc = []
found = True
while found:
found = False
for node in nodes:
if node[6] == 1:# or node[0] in [n[0] for n in tbc]:
print()
print()
print(' -------NODE ', node[0], '------')
connected_arcs = [network[arc_index] for arc_index in node[8]]
for arc in connected_arcs:
print('--ARC ', arc[0])
if arc[8] == 0 and arc[0] not in [n[2] for n in tbc]:
goto = 6 if arc[5] == node[0] else 5
nodes, network, br, bs = find_best(
nodes, network, arc[goto], arc[0], [], [], [0,0], [], tbc)
best_nodes = [nodes[i] for i in [n[0] for n in bs]]
best_arcs = [network[i] for i in [n[1] for n in bs]]
mg_cost = sum([node[7] for node in best_nodes])
grid_cost = (cost_wire_per_m * sum(arc[7] for arc in best_arcs) +
grid_cost_per_m2 * sum([node[3] for node in best_nodes]))
if grid_cost < mg_cost:
print('adding ', bs)
tbc.extend(bs)
#found = True
print('TBC ', tbc)
print('####')
print('####')
print('####')
#if len(tbc) > 0:
# found = True
for item in tbc:
nodes[item[0]][6] = 1
network[item[1]][8] = 1
-------NODE 2 ------ --ARC 1 adding [(0, 1, 0.7756358109962858)] --ARC 6 adding [(1, 6, 0.01177840052747079)] --ARC 11 removing (0, 1, 0.7756358109962858) removing (1, 6, 0.01177840052747079) adding [(3, 11, 0.011537134449123543), (0, 2, 0.7816606141452157)] --ARC 15 removing (3, 11, 0.011537134449123543) adding [(5, 15, 0.00031040111162922656), (0, 3, 0.7756399723639926), (3, 2, 0.5575758670112337)] --ARC 18 removing (5, 15, 0.00031040111162922656) adding [(6, 18, 5.620494589928472e-05), (1, 10, 0.005913267245088932)] TBC [(0, 2, 0.7816606141452157), (0, 3, 0.7756399723639926), (3, 2, 0.5575758670112337), (6, 18, 5.620494589928472e-05), (1, 10, 0.005913267245088932)] -------NODE 4 ------ --ARC 4 --ARC 9 removing (1, 10, 0.005913267245088932) removing (6, 18, 5.620494589928472e-05) adding [(1, 9, 0.040032967303875414)] --ARC 13 --ARC 16 adding [(5, 16, 8.405093144184302e-05)] --ARC 19 adding [(6, 19, 4.725937634817695e-05)] TBC [(0, 2, 0.7816606141452157), (0, 3, 0.7756399723639926), (3, 2, 0.5575758670112337), (1, 9, 0.040032967303875414), (5, 16, 8.405093144184302e-05), (6, 19, 4.725937634817695e-05)] #### #### ####