Python thinks object instance is list object

Question

So I am implementing BFS on a Graph to detect all the cycles. I implemented the graph via an adjacency list. But when I run my code I get the following error

    Traceback (most recent call last):
    File "C:\Python27\Data Structures\Graph\bfstree.py", line 228, in   <module>
    main()
    File "C:\Python27\Data Structures\Graph\bfstree.py", line 223, in main
    traverse(g.getVertex(2))
    File "C:\Python27\Data Structures\Graph\bfstree.py", line 168, in traverse
   while (x.getPred()):
   AttributeError: 'list' object has no attribute 'getPred'

So the problem occurs when I call the traverse() function. Here is my main function

def main():    

     g = Graph()

     for i in range(1,9):

          g.addVertex(i)

     g.addEdge(1,2)
     g.addEdge(1,4)
     g.addEdge(1,8)
     g.addEdge(2,3)
     g.addEdge(2,1)
     g.addEdge(3,2)
     g.addEdge(3,4)
     g.addEdge(3,7)
     g.addEdge(3,8)
     g.addEdge(4,1)
     g.addEdge(4,3)
     g.addEdge(4,5)
     g.addEdge(5,4)
     g.addEdge(5,6)
     g.addEdge(5,7)
     g.addEdge(6,5)
     g.addEdge(6,7)
     g.addEdge(7,3)
     g.addEdge(7,6)
     g.addEdge(7,5)
     g.addEdge(8,3)
     g.addEdge(8,1)

     for v in g:

          for w in v.getConnections():

               print("(%s,%s)"%(v.getId(),w.getId()))




     print("\nDoing BFS...")

     bfs_tree(g,g.getVertex(1))

     a = g.getVertex(2)

     print(type(a))

     traverse(g.getVertex(2))




main()

Here is the traverse function:

def traverse(y):

     x = y


     while (x.getPred()):
          print(x.getId())

          x = x.getPred()
     print(x.getId())

Here is the adjacency list implementation of the graph:

class Graph:

      def __init__(self):

           self.vertList = {}  #this is the masterlist
           self.numVertices = 0

      def addVertex(self,key): #turn something into a Vertex object

           self.numVertices = self.numVertices + 1

           newVertex = Vertex(key)

           self.vertList[key] = newVertex #maps vertex names to vertex objects

           return newVertex

      def getVertex(self,n):

           if n in self.vertList:

           return self.vertList[n] #returns the Vertex object
      else:

           return None

      def __contains__(self,n):#tweak the built-in operator 'in'(containment check)

           return n in self.vertList

      def addEdge(self,f,t,cost = 0):

           if f not in self.vertList: #if f is not a node in the graph

                nv = self.addVertex(f)

           if t not in self.vertList:     #if t is not a node in the graph

                nv = self.addVertex(t)

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

      def getVertices(self):

           return self.vertList.keys()

      def __iter__(self): # iterate over Vertex objects over the Graph

           return iter(self.vertList.values())
class Vertex:

     def __init__(self,key):

           self.id = key
           self.connectedTo={} #dictionary which contains all the other vertices it is connected to
           self.pred = [] #for BFS tree / a list because we are dealing with cycles
           self.color = "white" #for BFS tree


      def addNeighbor(self,nbr,weight=0):

           self.connectedTo[nbr] = weight #nbr is another Vertex object 

      def __str__(self):

           #TODO: lookup how that for loop works
           return str(self.id) + "connected to " + str([x.id for x in self.connectedTo])

      def getConnections(self):

           return self.connectedTo.keys()

      def getId(self):

           return self.id

      def getWeight(self,nbr):

           return self.connectedTo[nbr]

      def getColor(self):

           return self.color

      def setColor(self,color):

           self.color = color

      def setPred(self,node):

           self.pred.append(node)

      def getPred(self):

           if len(self.pred)>1:
                return self.pred
           elif len(self.pred) == 0:

                return self.pred[0]
           else:

                return self.pred

Why is it saying that g.getVertex(2) is a list object? I am pretty sure that it's a Vertex object. I even printed out the type in the main function and it says it's an instance and not a list object.

Answer 1

You replace x with the result of x.getPred() here:

 while (x.getPred()):
      print(x.getId())
      x = x.getPred()

x.getPred() returns self.pred:

  def getPred(self):

       if len(self.pred)>1:
            return self.pred
       elif len(self.pred) == 0:

            return self.pred[0]
       else:

            return self.pred

(Note that for len(self.pred) == 0 you try to return self.pred[0], which will raise an IndexError exception).

self.pred is a list:

class Vertex:
     def __init__(self,key):
           # ...
           self.pred = [] #for BFS tree / a list because we are dealing with cycles

So you replaced x with a list object, then loop back and call x.getPred() on that list object.

Answer 2

x = x.getPred() is the problem. The first check in the while loop is fine, but it breaks after x is updated the first time, then rechecked.

As implemented, getPred is returning self.pred (the only case where it returns a value from self.pred instead of the whole thing is broken; the length is 0, and you index, so it will raise IndexError). self.pred is a list.