CODEWITHSUNDEEP
python
Layla
Layla

Reputation: 5446

graph representation in Python with adjacency list

I have found the following Graph implementation in Python:

class Vertex:
    def __init__(self,key):
        self.id = key
        self.connectedTo = {}

    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight

    def getConnections(self):
        return self.connectedTo.keys()

    def getId(self):
        return self.id

    def getWeight(self,nbr):
        return self.connectedTo[nbr]

class Graph:
    def __init__(self):
        self.vertList = {}
        self.numVertices = 0

    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertList[key] = newVertex
        return newVertex

    def getVertex(self,n):
        if n in self.vertList:
            return self.vertList[n]
        else:
            return None

    def addEdge(self,f,t,cost=0):
        if f not in self.vertList:
            nv=self.addVertex(f)
        if t not in self.vertList:
            nv=self.addVertex(t)
        self.vertList[f].addNeighbor(self.vertList[t], cost)

    def getVertices(self):
        return self.vertList.keys()

    def __iter__(self):
        return iter(self.vertList.values())


def main():
    g=Graph()
    for i in range(6):
        g.addVertex(i)
    g.addEdge(0,1,5)
    g.addEdge(1,5,4)
    g.addEdge(5,3,6)
    g.addEdge(3,4,5)
    for v in g:
        for w in v.getConnections():
            print v.getId(),",",w.getId(),",",v.getWeight(w)

if __name__=="__main__":
    main()

The program executes fine, but I was wondering if the author put some redundant parts, like in the functions addEdge() and addVertex().

For what I see addEdge has an assignment that it never uses:

nv=self.addVertex(t)

also the part that says:

if t not in self.vertList:
    nv=self.addVertex(t)

in the same method does not do anything, and the variable nv is not used at all. For what I see this is the implementation of a directed graph so if I want to program a non-directed graph it will suffice to put:

self.vertList[t].addNeighbor(self.vertList[f], cost)

So I can also get rid of the return newVertex in the addVertex function. I have done those modifications and the program works still fine. Would those modifications be good and not bring any strange behaviour when I reuse this class?

And one last question, in the part that says:

for v in g:
    for w in v.getConnections():
        print v.getId(),",",w.getId(),",",v.getWeight(w)

it seems it only iterates over those values in the dictionary of G that has values and not with the empty ones (I mean those that have only a key), is it like that?

Upvotes: 0

Views: 351

Answers (1)

laike9m
laike9m

Reputation: 19318

Yes, I think nv= is redundant but self.addVertex(f) is necessary cause you need to add vertex.
Adding self.vertList[t].addNeighbor(self.vertList[f], cost) will make a non-directed graph, true.

it seems it only iterates over those values in the dictionary of G that has values and not with the empty ones (I mean those that have only a key), is it like that?

No, it will iterate all vertexes but only those with connections(edge) will generate output.

Upvotes: 1

Related Questions