Cost Effective Paths for Setting up Electricity Connection in a Given Area

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()