Practical Application of Graph Theory - Route Planning
Case study: West Budama North – Tororo, Uganda
“Why does electricity take the shortest path?”
In Electricity, resistance is proportional to a wire's length, electricity moves from a higher potential to a lower one.
Potential = (current intensity * resistance), thus potential increases when resistance does. Eventually electricity will not choose the longer path because it has a higher potential.
Overview
Leonard Euler in 1735 published his work that solved a problem known as the
Konigsberg Bridge Problem. The basic concepts behind his work laid a strong foundation to
graph theory. This knowledge is currently being used in several modern fields of applied mathematics including; science, engineering, business, and industry.
This write-up is an application project that shall demonstrate a simple use of modern
graph theory. It will formulate a plan algorithm for finding the shortest distance (shortcut) between one start point of connection to another; that is, by calculating the distances between all neighbouring centres (village meeting points) up to the end-point centre. All routable neighbours, will be linked by a weighted distance (in kilometers).
The project will include the utilization of three basic algorithms (
depth first search,
Kruskal’s, and
Dijkstra's) as applied in
graph theory, in the process of finding the shortest connection path in the given
network. The implementation plan will involve modeling a simple technology using
NetworkX with
Python programming as applied to
graph modeling and manipulation
When testing (implementing), the algorithm will traverse through an entire
network of villages in the area and choose the most appropriate route with
the shortest cost(path) thus ensuring efficiency.
Method Overview
A distance between all the given centres is required (
NOTE:
If applying the algorithm in reality, please acquire all other necessary information
from local public libraries or a local bureau of statistics).
From a completely interconnected section of centres by the roads (
network), choose the nearest of the centres from a selected centre and use the result recursively up to the destination point to find the distance to all the other points in between.
Within all the specified
graph(s) weighted by the distances from and to their neighbours, Dijkstra’s algorithm will be the main algorithm to compute and derive the shortest distance (short-cut) from a specified points; say from
A to
B via (or not) any other point
C
Conclusion
This application project can be used by architects or any planning engineers to layout paths(connections) during any kind of connectivity design.
With the project implemented, it will make electricity connectivity
and maintenance very cost effective in terms of connection cables and
electricity poles (or connection points/nodes) that would be included, thus saving both financial and project time costs.
DEMO: (Python implementation)
"""
Implementation of:
Cost Effective Paths for Setting up Electricity Connection in a Given Area
#########################################################################
Practical Application of Graph Theory :: Route Planning
BY
Ochola Aloysius [2010/HD18/431U] :: Msc. Computer Sci :: MUK - Dec 2010
##########################################################################
NB: Testing the algorithm does not include exact/all values (villages)
not even do the distances and neighborhood reflect reality.
"""
import networkx as nx
def dijkstra(graph, begin, end):
"""
ref = Python Dijkstra Algorithm
"""
if begin == end:
return "within the same village. Minimum distance is 0Km"
labels={}
# record whether a label was updated
order={}
# populate an initial labels dictionary
for i in graph.keys():
if i == begin: labels[i] = 0 # shortest distance form s to s is 0
else: labels[i] = float("inf") # initial labels are infinity
from copy import copy
drop1 = copy(labels) # used for looping
## begin algorithm
while len(drop1) > 0:
# find the key with the lowest label
minNode = min(drop1, key = drop1.get) #minNode is the node with the smallest label
# update labels for nodes that are connected to minNode
for i in graph[minNode]:
if labels[i] > (labels[minNode] + graph[minNode][i]):
labels[i] = labels[minNode] + graph[minNode][i]
drop1[i] = labels[minNode] + graph[minNode][i]
order[i] = minNode
del drop1[minNode] # once a node has been visited, it's excluded from drop1
## end algorithm
# print shortest path
temp = copy(end)
rpath = []
path = ""#[]
while 1:
rpath.append(temp)
if order.has_key(temp): temp = order[temp]
else: return "There is no path from " + str(begin) + " to "+ str(end) + "."
if temp == begin:
rpath.append(temp)
break
for j in range(len(rpath)-1,-1,-1):
path += rpath[j]+','#.append(rpath[j])
return "The SHORTEST PATH from " + begin.upper() + " to " + end.upper() + " is through:\n"\
+ str(path) + "\nand the MINIMUM distance is " + str(labels[end]) + "Km."
##interactive, prompt user input
def getshortestdistance(graph):
print "LIST OF AVAILABLE VILLAGES"
for k in graph.keys():
print k
begin = str(raw_input("Enter village to start connectivity from "))
#sanity check
while graph.has_key(begin)==False:
try:
begin = str(raw_input("INVALID INPUT\nPlease refer to the available list of villages "))
except ValueError:
pass
else:
end = raw_input("Enter village to connect from {0} ".format(begin))
return [begin, end]
#test the algorithm
def main():
g = nx.Graph()
centres = [
('mukuju','okango',5),
('mukuju','kayoro',10),
('okango','kayoro',8),
('okango','bendo',5),
('bendo','mudodo',3),
('mudodo','mile3',4),
('mudodo','ayago',4),
('ayago','achilet',4),
('ayago','rubongi',3),
('mile3','achilet',5),
('mile3','ayago',1),
('achilet','rubongi',2),
('achilet','musukire',4),
('rubongi','musukire',4),
('musukire','uci',8),
('musukire','mulanda',10),
('mulanda','iyolwa',5),
('mulanda','ssiwa',7),
('mulanda','uci',14),
('iyolwa','ssiwa',2),
('iyolwa','uci',22),
('ssiwa','uci',19)]
#populate graph with weights
g.add_weighted_edges_from(centres)
neighbouring = dict(g.adjacency_iter())
#create a dictionary of neighbourhood
for j,k in neighbouring.items():
for i,d in k.items():
neighbouring[j][i]=d['weight']
#using the method
put = getshortestdistance(neighbouring)
print dijkstra(neighbouring, put[0],put[1])
if __name__ =='__main__':
main()
