Skip to main content

Python : Graph Implementation


class Vertex:
   
    def __init__(self,node):
        self.id = node
        self.adjacent = {}
        self.distance = 99999
        self.visited = False
        self.previous = None
   
    def addNeighbour(self,neighbour,weight = 0):
        self.adjacent[neighbour] = weight
   
    def getConnections(self):
        return self.adjacent.keys()
       
    def getVertexID(self):
        return self.id
   
    def getWeight(self,neighbour):
        return self.adjacent[neighbour]
       
    def setDistance(self,dist):
        self.distance = dist
   
    def getDistance(self):
        return self.distance
       
    def setPrevious(self,prev):
        self.previous = prev
       
    def setVisited(self):
        self.visited = True
       
    def __str__(self):
        return str(self.id) + 'adjacent:' + str([x.id for x in self.adjacent])

class Graph:
    def __init__(self):
        self.vertDictionary = {}
        self.numVertices = 0
       
    def __iter__(self):
        return iter(self.vertDictionary.values())
       
    def addVertex(self,node):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(node)
        self.vertDictionary[node] = newVertex
        return newVertex
   
    def getVertex(self,n):
        if n in self.vertDictionary:
            return self.vertDictionary[n]
        else:
            return None
   
    def addEdge(self,frm,to,cost =0):
        if frm not in self.vertDictionary:
            self.addVertex(frm)
        if to not in self.vertDictionary:
            self.addVertex(to)
   
        self.vertDictionary[frm].addNeighbour(self.vertDictionary[to],cost)
        self.vertDictionary[to].addNeighbour(self.vertDictionary[frm],cost)
       
    def getVertices(self):
        return self.vertDictionary.keys()
       
    def setPrevious(self,current):
        self.previous = current
   
    def getPrevious(self,current):
        return self.previous
       
    def getEdges(self):
        edges = []
        for v in G:
            for w in v.getConnections():
                vid = v.getVertexID()
                wid = w.getVertexID()
                edges.append((vid,wid,v.getWeight(w)))
        return edges

if __name__ == '__main__':
    G = Graph()
    G.addVertex('a')
    G.addVertex('b')
    G.addVertex('c')
    G.addVertex('d')
    G.addVertex('e')
    G.addEdge('a','b',4)
    G.addEdge('a','c',1)    
    G.addEdge('c','b',2)
    G.addEdge('b','e',4)   
    G.addEdge('c','d',4)   
    G.addEdge('d','e',4)
    print'graph Data'
    print G.getEdges()
Labels:

Comments

Post a Comment

Popular posts from this blog

UNIX : How to ignore lines with certain names

Sometimes we need to ignore multiple lines with certain words and get the list out of the file. usually it will be a log file to read . The below grep command can be used to ignore multiple words present in a text file. Lets say the file contain $ cat list.txt apple orange apple banana papaya Now we need to ignore line with orange , banana and papaya . So we can use the below grep command. $ cat list.txt | grep -Ev "orange|banana|papaya" apple apple It will ignore lines with the words in -v part of grep.
Post a Comment
Read more

UNIX : How to get record count from zipped file

Sometimes we may need to get records count from file . For that we can use wc -l , command with file name. In some situation the file will be in compressed format . wc -l will not directly work with zipped files . In this case we can do zcat the file and pipe the word count command with it. Example : Let say we have a file cricketData.dat.gz To get word count from the file use : zcat cricketData.dat.gz | wc -l This will give the record count.
Post a Comment
Read more

Python : How to create your own module in python

Python modules are easy to create and imported in to your python program. How to create a module? The python program itself can be called as a python module. All the function which you find that can be grouped together can be put into the file. Here a simple example to print the text on display is used and called as techinfotalks. #!/usr/bin/python # Python Module def func_hi(): print "Welcome to the module" #End How to use the module in program? You just import the module created by calling the import.After that directly call the function which ever you need.The module named techinfotalks is imported as named as ti. #!/usr/bin/python import techinfotalks as ti print "Calling funcion in module" ti.func_hi() #End of program
Post a Comment
Read more