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

Comments

Popular posts from this blog

Excel : How to pad zeros

Today I got a requirement to format the number in excel cell - to left pad number with zeros.i find the following function very useful to do it. In case one to make the number left padded with "0" s give the formula =TEXT(A1,"0000") In case two even more enhanced form to make it left padded with "0" and add two decimal places give the formula as =TEXT(A2,"0000.00")

Mount an iso image in ubuntu using no GUI

We can easily mount an iso image file in our system to a directory in linux.We need not require an GUI application to do this.It is easy to do from the terminal itself. We use the mount command for that. The steps are as follows  1. Open the terminal in ubuntu (Shortcut press ctrl+Alt+t) 2. Create a directory to mount the iso image              $sudo mkdir /media/myimage 3. Then type the following command     $sudo modprobe loop 4.After that go to the location of the iso image file and type     $sudo mount /media/myimage -t iso9660 -0 loop     The iso file is mounted to the specified directory To unmount it give the command   sudo unmount /media/myimage That all.Cool isn't! sudo modprobe loop will loads the module for loopback file system iso9660 is the file system used by CD-ROM -t specify the file system type -o loop additional option used by a loopback filesystem

How to add fonts in Ubuntu?

To add fonts like Times New Roman , Ariel etc in Ubuntu do the following. 1. open ubuntu Software Center  2. Searh fo r  ttf-mscorefonts   in search  bar. 3. Install the item listing in the page. Now you can use new fonts in ubuntu.