INTRODUCTION¶
The city has houses, malls, and single center– none of which are connected by roads. The objective is to plan the roads. There are fast roads and slow roads. Fast roads connect malls to malls and malls to the city center. Slow roads connect houses to houses and houses to malls.
Write a program that takes as input:
• a set of H house coordinates (x,y)
• a set of M mall coordinates (x,y)
• x center coordinates (x,y)
and returns:
• a list of planned slow roads
• a list of planned fast roads
• sum of lengths of all the slow roads
• sum of lengths of all the fast roads
• visualization of the solution
Objective¶
Plan the roads such that the total road cost is minimized, with the total cost given by a weighted sum of the fast and slow total lenghts, i.e cost= a * total_length(slow) +(1-a)* total_length(fast) with a element of [0,1].*
Algorithm Rules¶
• you must be able to travel from any house to any other house
• you must be able to travel from any house to at least one mall
• you must be able to travel from any house to the city center
• travel refers to traveling via fast or slow roads, possibly via other houses or malls
• not all shops need to be connected
import sys
import matplotlib.pyplot as plt
import networkx as nx
from scipy.spatial import distance
import time
start_time = time.time()
def prepareGraph(attrs):
G = nx.Graph()
for node in attrs.keys():
G.add_node(node)
nx.set_node_attributes(G, attrs)
a = 0.1 # weight
key_list = list(attrs.keys())
for i, j in itertools.combinations(key_list, 2):
dst = distance.euclidean(attrs[i]["coordinates"], attrs[j]["coordinates"])
if attrs[i]["obj_type"] == 'House' and attrs[j]["obj_type"] == 'House' \
or attrs[i]["obj_type"] == 'House' and attrs[j]["obj_type"] == 'Mall' \
or attrs[j]["obj_type"] == 'House' and attrs[i]["obj_type"] == 'Mall':
G.add_edge(i, j, weight=(1 - a) * dst, distance=dst, road_type='Local', color='black')
elif attrs[i]["obj_type"] == 'Mall' and attrs[j]["obj_type"] == 'Center' \
or attrs[j]["obj_type"] == 'Mall' and attrs[i]["obj_type"] == 'Center':
G.add_edge(i, j, weight=a * dst, distance=dst, road_type='Express', color='r')
return nx.adjacency_matrix(G).todense(), G
#listing all the roads, their weight, and road type
def printMST(graph, graphNX, parent):
MSTedges = []
MSTweights = []
loc_len = 0
exp_len = 0
print("Edge \tWeight \t\t\t\tRoad Type")
for i in range(1, len(parent)):
print(parent[i], "-", i, "\t", graph[i][parent[i]], graphNX[parent[i]][i]['road_type'])
MSTedges.append((parent[i], i))
MSTweights.append(graph[i][parent[i]])
if graphNX[parent[i]][i]['road_type'] == 'Local':
loc_len += graphNX[parent[i]][i]['distance']
else:
exp_len += graphNX[parent[i]][i]['distance']
print('Total length of Local and Express roads is {} and {}, respectively'.format(loc_len, exp_len))
return MSTedges, MSTweights
#plotting the MST
def plotMST(graphNX, parent, attrs):
MSTedges, MSTweights = printMST(graph, graphNX, parent)
pos = nx.kamada_kawai_layout(graphNX)
nx.draw_networkx_nodes(graphNX, pos, node_size=500)
labels = {}
for node_name in range(len(attrs)):
labels[node_name] = str(attrs[node_name]["obj_type"]) + str(node_name)
nx.draw_networkx_labels(graphNX, pos, labels, font_size=10)
for edge in MSTedges:
width = graphNX[edge[0]][edge[1]]['weight'] * 3
nx.draw_networkx_edges(graphNX, pos, edgelist=[edge], width=width, edge_color=graphNX[edge[0]][edge[1]]['color'])
plt.axis('off')
plt.title('Town Plan')
plt.savefig("town_plan.png")
plt.show()
def minKey(key, mstSet):
min = sys.maxsize
for v in range(len(key)):
if key[v] < min and mstSet[v] == False:
min = key[v]
min_index = v
return min_index
def primMST(graph, V):
key = [sys.maxsize] * V
parent = [None] * V
key[0] = 0
mstSet = [False] * V
parent[0] = -1
for _ in range(V):
u = minKey(key, mstSet)
mstSet[u] = True
for v in range(V):
if graph[u][v] > 0 and mstSet[v] == False and key[v] > graph[u][v]:
key[v] = graph[u][v]
parent[v] = u
printMST(graph, graphNX, parent)
plotMST(graphNX, parent, attrs)
return time.time() - start_time
attrs = {
0: {"obj_type": 'House', "coordinates": (1,2)},
1: {"obj_type": 'Mall', "coordinates": (2,3)},
2: {"obj_type": 'House', "coordinates": (1,3)},
3: {"obj_type": 'House', "coordinates": (1,4)},
4: {"obj_type": 'Mall', "coordinates": (3,3)},
5: {"obj_type": 'House', "coordinates": (2,4)},
6: {"obj_type": 'Center', "coordinates": (3,5)},
7: {"obj_type": 'House', "coordinates": (1,2)},
8: {"obj_type": 'Mall', "coordinates": (5,3)},
9: {"obj_type": 'House', "coordinates": (3,7)},
10: {"obj_type": 'House', "coordinates": (1,1)},
11: {"obj_type": 'Mall', "coordinates": (1,5)},
12: {"obj_type": 'House', "coordinates": (2,2)},
13: {"obj_type": 'House', "coordinates": (4,4)}
}
graph, graphNX = prepareGraph(attrs)
V = len(attrs)
primMST(graph, V)
print("--- %s seconds ---" % (time.time() - start_time))
Edge Weight Road Type 2 - 1 0.9 Local 0 - 2 0.9 Local 2 - 3 0.9 Local 6 - 4 0.2 Express 1 - 5 0.9 Local 1 - 6 0.223606797749979 Express 2 - 7 0.9 Local 6 - 8 0.28284271247461906 Express 11 - 9 2.5455844122715714 Local 0 - 10 0.9 Local 6 - 11 0.2 Express 0 - 12 0.9 Local 4 - 13 1.2727922061357857 Local Total length of Local and Express roads is 11.242640687119286 and 9.06449510224598, respectively Edge Weight Road Type 2 - 1 0.9 Local 0 - 2 0.9 Local 2 - 3 0.9 Local 6 - 4 0.2 Express 1 - 5 0.9 Local 1 - 6 0.223606797749979 Express 2 - 7 0.9 Local 6 - 8 0.28284271247461906 Express 11 - 9 2.5455844122715714 Local 0 - 10 0.9 Local 6 - 11 0.2 Express 0 - 12 0.9 Local 4 - 13 1.2727922061357857 Local Total length of Local and Express roads is 11.242640687119286 and 9.06449510224598, respectively
--- 0.3707883358001709 seconds ---