import googlemaps

results =

gmaps = googlemaps.Client (

key = ‘AIzaSyAOb182lMCRvfDVATsNsskC23ua7Eih5U8′ )

“””Node class for the tree”””

class node ( object ) :

def __init__ (self, location, children = ):

self.location = location

self.children = children

self.totalDistance = 0

self.dFP = 0;

def getDistance(self):

return self.totalDistance

“””initializing the static tree”””

def initialize():

A = “University of Pretoria , Pretoria ”

B = “CSIR , Meiring Naude Road , Pretoria ”

C = “Armscor, Delmas Road, Pretoria”

D = “Denel Dynamics, Nellmapius Drive, Centurion”

E = “Air Force Base Waterkloof, Centurion”

tree = node(A,

node(B, node(C, node(D, node(E, node(A))),

node(E, node(D, node(A)))),

node(D, node(C, node(E, node(A))),

node(E, node(C, node(A)))),

node(E, node(C, node(D, node(A))),

node(D, node(C, node(A))))),

node(C, node(B, node(D, node(E, node(A))),

node(E, node(D, node(A)))),

node(D, node(B, node(E, node(A))),

node(E, node(B, node(A)))),

node(E, node(B, node(D, node(A))),

node(D, node(B, node(A))))),

node(D, node(B, node(C, node(E, node(A))),

node(E, node(C, node(A)))),

node(C, node(B, node(E, node(A))),

node(E, node(B, node(A)))),

node(E, node(B, node(C, node(A))),

node(C, node(B, node(A))))),

node(E, node(B, node(C, node(D, node(A))),

node(D, node(C, node(A)))),

node(C, node(B, node(D, node(A))),

node(D, node(B, node(A)))),

node(D, node(B, node(C, node(A))),

node(C, node(B, node(A))))))

return tree

“””DFS code, working “””

def DFS(tRoute):

global counter

counter += 1

try:

for x in range(0, len(tRoute.children)):

directions_result = gmaps.distance_matrix(tRoute.location, tRoute.childrenx.location)

nextDis = directions_result’rows’0’elements’0’distance”value’

tRoute.childrenx.totalDistance = tRoute.totalDistance + nextDis

tRoute.childrenx.dFP = nextDis

DFS(tRoute.childrenx)

return

except:

directions_result = gmaps.distance_matrix(tRoute.location, “University of Pretoria , Pretoria “)

nextDis = directions_result’rows’0’elements’0’distance”value’

tDis = tRoute.getDistance() + nextDis

results.append(tDis)

return

“”” The BFS code that do not work”””

”’

def BFS(tRoute):

try:

print(tRoute.location)

for x in range(0, len(tRoute.children)):

print(x.location)

directions_result = gmaps.distance_matrix(tRoute.location, tRoute.childrenx.location)

xDis = directions_result’rows’0’elements’0’distance”value’

print(xDis)

tRoute.childrenx.totalDistance = tRoute.totalDistance + xDis

for x in range(0, len(tRoute.children)):

sRoute = tRoute.childrenx

for y in range(0, len(sRoute.children)):

directions_result = gmaps.distance_matrix(sRoute.location, sRoute.childreny.location)

yDis = directions_result’rows’0’elements’0’distance”location’

sRoute.childreny.totalDistance = sRoute.totalDistance + yDis

for x in range(0, len(tRoute.children)):

sRoute = tRoute.childrenx

for y in range(0, len(sRoute.children)):

rRoute = sRoute.childreny

print(rRoute.location)

for z in range(0, len(rRoute.children)):

directions_result = gmaps.distance_matrix(rRoute.location, rRoute.childrenz.location)

zDis = directions_result’rows’0’elements’0’distance”location’

rRoute.childrenz.totalDistance = rRoute.totalDistance + zDis

print(rRoute.childrenz.totalDistance)

except:

return

”’

root = initialize()

“””Printing all the locations before going back to the end location”””

print(root.location)

for x in range(0, len(root.children)):

print(“–” + root.childrenx.location)

for y in range(0, len(root.childrenx.children)):

print(“—-” + root.childrenx.childreny.location)

for z in range(0, len(root.childrenx.childreny.children)):

print(“——” + root.childrenx.childreny.childrenz.location)

print(“”)

counter = 0

DFS(root)

print(results)

best = results.index(min(results))

kmB = min(results) / 1000

print(“”)

print(“Nodes visited ” + str(counter))

print(“The shortest route for the TSP is route ” + str(best))

print(“With total distance of ” + str(kmB) + “km”)