I have some code for a routing algorithm in python programming language but i don't understand the code at all. I am only a beginner and i was wondering if anyone could explain it for me in plain text. Could you please go through and explain each part. Cheers. Here's the code :

def findRoute(source, dest):
global theGraph
global count1
global count2
global count3
theGraph.reset(source)
while theGraph.getChoices() != []:
u = theGraph.getBestChoice(source)
theGraph.addVisited(u)
if u == dest:
print "there is no other choice, we have reach the destination", dest
return True
for v in theGraph.getNode(u).getNeighbours():
theGraph.addChoice(v)
alt = theGraph.getNode(u).getDistanceFrom(sour... + theGraph.getLength(u, v)
#print "the distance is", theGraph.getNode(v).getDistanceFrom(sour...
count3= count3+1


if alt < theGraph.getNode(v).getDistanceFrom(sour...
theGraph.getNode(v).update(u, alt)
count2=count2+1
print " choicelist ", theGraph.getChoices(), "visitedlist", theGraph.getVisited()
print len(theGraph.getChoices())
if len(theGraph.getChoices())>= count1:
count1= len(theGraph.getChoices())
print u, "has neighbours", theGraph.getNode(u).getNeighbours()
#print "the distance is", theGraph.getNode(v).getDistanceFrom(sour...
print " "
print " "

Recommended Answers

All 2 Replies

We wont be able to help you unless you also provide the code for theGraph. Otherwise we are just guessing.

Hi i will try to wrap it in code tags i also attached the full code below as you asked for it, just need help with explaining the part i send you before thank you

#!/usr/bin/python

import string


infinity = 1000000
fileName = "unknown"
lineNo = 0
count1 = 0
count2 = 0
count3 = 0


#
#  scanner - opens file, name, and calls, function for each line.
#

def scanner(name, function):
    global fileName, lineNo

    fileName = name
    lineNo = 0
    file = open(name, 'r')
    line = file.readline()
    while line:
        lineNo += 1
        function(line)
        line = file.readline()
    file.close()


#
#  syntaxError - issues a syntax error using a format understood by
#                GNU emacs
#

def syntaxError(message):
    global lineNo, fileName
    print "%s:%d:%s" % (fileName, lineNo, message)

class node:
    global infinity
    
    name = ""
    neighbours = {}        #  dictionary of names of neighbours and their relative cost from us
    previous = 'undefined' #  where have we come from?
    distance = infinity    #  the absolute distance from source
    def __init__(self, n):
        self.name = n
        self.neighbours = {}
        self.previous = 'undefined'
        self.distance = infinity
    def reset(self):
        self.previous = 'undefined'
        self.distance = infinity
    def update(self, prev, dist):
        self.previous = prev
        self.distance = dist
    def getDistanceFrom(self, n):
        if n == self.name:
            return 0
        else:
            return self.distance
    def getPrevious(self):
        return self.previous
    def getName(self):
        return self.name
    def addLength(self, toNode, length):
        if self.neighbours.has_key(toNode):
            syntaxError(self.name + " already knows about node: " + toNode)
        else:
            self.neighbours[toNode] = length
    def getLength(self, toNode):
        if self.neighbours.has_key(toNode):
            return self.neighbours[toNode]
        else:
            syntaxError(self.name + " does not know about node: " + toNode)
    def getNeighbours(self):
        l = []
        for i,j in self.neighbours.iteritems():
            l += [i]
        return l

class graph:
    nodes = []
    choices = []
    consider = "unknown"
    visited = []
    def __init__(self):
        self.nodes = []
        self.choices = []
        self.consider = "unknown"
        self.visited = []
    def reset(self, source):
        self.choices = [source]
        self.visited = []
        self.getNode(source).update(source, 0)
    def setConsider(self, n):
        self.consider = n
    def getChoices(self):
        return self.choices
    def addChoice(self, n):
        if (not (n in self.visited)) and (not (n in self.choices)):
            print "adding node", n, "to choice list"
            self.choices += [n]
    def addVisited(self, n):
        self.visited += [n]
    def getVisited (self):
        return self.visited
    def getNode(self, n):
        for i in self.nodes:
            if n == i.getName():
                return i
        else:
            syntaxError("cannot find node " + n + " in graph")
    def addLength(self, source, dest, length):
        for i in self.nodes:
            if source == i.getName():
                i.addLength(dest, length)
        else:
            self.nodes += [node(source)]
            self.nodes[-1].addLength(dest, length)
    def getLength(self, u, v):
        for i in self.nodes:
            if u == i.getName():
                return i.getLength(v)
        else:
            syntaxError("cannot find node " + u + " in graph")
    def getBestChoice(self, source):
        # returns the node which has the shortest distance from the source
        i = 0
        bi = 0
        best = self.choices[0]
        for c in self.choices[1:]:
            i += 1
            if theGraph.getNode(c).getDistanceFrom(source)<theGraph.getNode(best).getDistanceFrom(source):
                best = c
                bi = i
        del self.choices[bi]
        print "the best choice was", best, "with a cost of", theGraph.getNode(best).getDistanceFrom(source)
        return best
           

#
#  findRoute - dijkstra's algorithm.
#

def findRoute(source, dest):
    global theGraph
    global count1
    global count2
    global count3
    theGraph.reset(source)
    while theGraph.getChoices() != []:
        u = theGraph.getBestChoice(source)
        theGraph.addVisited(u)
        if u == dest:
            print "there is no other choice, we have reach the destination", dest
            return True
        for v in theGraph.getNode(u).getNeighbours():
            theGraph.addChoice(v)
            alt = theGraph.getNode(u).getDistanceFrom(source) + theGraph.getLength(u, v)
            #print "the distance is", theGraph.getNode(v).getDistanceFrom(source)
            count3= count3+1


            if alt < theGraph.getNode(v).getDistanceFrom(source):
                theGraph.getNode(v).update(u, alt)
                count2=count2+1
        print " choicelist ", theGraph.getChoices(), "visitedlist", theGraph.getVisited()
        print len(theGraph.getChoices())
        if len(theGraph.getChoices())>= count1:
           count1= len(theGraph.getChoices()) 
        print u, "has neighbours", theGraph.getNode(u).getNeighbours()
        #print "the distance is", theGraph.getNode(v).getDistanceFrom(source)
        print "   "
        print "   "



    return False
    


#
#  displayRoute - 
#

def displayRoute(source, dest):
    global theGraph

    print "the route from", source, "to", dest
    route = [dest]
    while dest != source:
        #print dest
        dest = theGraph.getNode(dest).getPrevious()
        route = [dest] + route
    #print route
    total = 0
    if len(route)>1:
        p = route[0]
        print "initially start at node '", p, "'"
        for i in route[1:]:
            total += theGraph.getNode(i).getLength(p)
            print "go to '", i, "' a distance of", theGraph.getNode(i).getLength(p), " running total", total
            p = i
    print "the maximum number of nodes held in the choice list", count1
    print "the number of nodes whose absolute distance from source is modified", count2
    print "the number of distance comparisons made", count3
#
#  processLine - adds nodes to the graph, and in so doing it
#                creates a graph.  It also reads in the routing
#                questions and calls a function to solve them.
#

def processLine(line):
    global theGraph

    print line
    uncomment = string.split(line, '#')
    words = string.split(string.lstrip(uncomment[0]))
    if len(words)>=2:
        f=words[0]
        if f == "find":
            if (len(words) == 4) and (words[2] == "->"):
                if findRoute(words[1], words[3]):
                    displayRoute(words[1], words[3])
            else:
                syntaxError("expecting 'from source -> dest'")
        else:
            for word in words[1:]:
                t = string.split(word, ':')
                if len(t) == 2:
                    theGraph.addLength(f, t[0], int(t[1]))
                else:
                    syntaxError("expecting node:distance entity")

theGraph = graph()

#
#  main - calls scanner with a filename and a function to process each
#         line of the file.
#

def main():
    scanner("simplea.data", processLine)

main()
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.