Python - Type Error: 'Graph' object is not subscriptable

Question

I am trying to implement Graph and bfs (breadth-first search) algoritm. I have this graph_object class:

class Vertex:
    def __init__(self,id):
        self.id=id #just a character representing each node/vertex name e.g. 'a', 'b'...
        self.neighbors=[]
        '''list of adjacent vertices. we call them neighbors. 
        d.neighbors=[b,c,g]. 
        note that here we are talking about the Vertex objects b,c,g. Not their corresponding vertex IDS ('b', 'c' and 'g')
        '''
        self.parent=None
        '''parent of a vertex depends on order of visit of the vertices in a graph.  

        calling the function bfs() on above graph will assign a.parent=None, b.parent=a , c.parent=d, d.parent=b, g.parent=d '''
    def __str__(self):
        return "{}:{}".format(self.id,self.get_neighbors()) #
    def get_neighbors(self):
        return [v.id for v in self.neighbors]
    def get_id(self):
        return self.id
    def get_parent(self):
        return self.parent
    def add_neigbor(self,v):
        self.neighbors.append(v)

class Graph:
    def __init__(self):
        self.vertices={}
        self.num_vert=0
    def get_vertex(self,v_id):
        if v_id not in self.get_vertices():
            return None
        else:
            return [v for v in self.vertices if v.id==v_id].pop(0) #to understand what happens here, refer to dict_exercise.py
    def add_vertex(self,v_id):
        if v_id not in self.get_vertices():
            new=Vertex(v_id)
            self.vertices[new]=new.neighbors
    def add_edge(self,v1_id,v2_id):
        if v1_id not in self.get_vertices():
            self.add_vertex(v1_id)
        if v2_id not in self.get_vertices():
            self.add_vertex(v2_id)
        #vertices with IDs v1_id and v2_id are now guaranteed to exist in graph, we get the corresponding vertex objects v1 and v2
        v1=self.get_vertex(v1_id)
        v2=self.get_vertex(v2_id)
        if v2_id not in v1.get_neighbors():
            v1.add_neigbor(v2)
        if v1_id not in v2.get_neighbors():
            v2.add_neigbor(v1)
    def get_vertices(self):
        return [v.id for v in self.vertices.keys()]

I also am using a test class which has bfs algoritm in it:

from graph_object import *


def bfs(g, s):
    explored, queue = [], [s]
    while queue:
        current_vertex = queue.pop(0)
        if current_vertex not in explored:
            explored.append(current_vertex)
            neighbors = g[current_vertex]
            queue += neighbors
    return explored


graph = Graph()

graph.add_edge('a', 'b')
graph.add_edge('b', 'c')
graph.add_edge('c', 'd')
graph.add_edge('d', 'b')
graph.add_edge('d', 'g')

print("List of vertex IDs in graph:")
vertices = graph.get_vertices() #returns graph vertices as a list of vertex IDs
print(vertices)

vertices_dict = graph.vertices
print("Vertex information in format <vertex id>:<list of neighbors>")
for vertex in vertices_dict.keys():
    print(vertex)


print("BFS(a) explored the elements in graph in the order:")
print(*bfs(graph, 'a'), sep=', ')

When I run the code, I get this error:

Traceback (most recent call last):
List of vertex IDs in graph:
File "C:/Users/rawsly/PycharmProjects/MiniProject/test.py", line 40, in <module>
['a', 'b', 'c', 'd', 'g']
print(*bfs(graph, 'a'), sep=', ')
Vertex information in format <vertex id>:<list of neighbors>
File "C:/Users/rawsly/PycharmProjects/MiniProject/test.py", line 10, in bfs
a:['b']
neighbors = g[current_vertex]
b:['a', 'c', 'd']
TypeError: 'Graph' object is not subscriptable

I know it is better to use set structure for explored in bfs but then I realized that the output is not ordered since set structure is not ordered. Therefore I wanted to use list instead. On the other hand using dequeue is also more efficient but right now I am not considering the efficiency. I will improve the code later on but first, I want to solve this error.

Please show the actual traceback. Where is this error occurring in that huge amount of code you have posted? — Daniel Roseman
– Daniel Roseman, Commented Mar 28, 2018 at 11:51

ForFunAndProfit · Accepted Answer · 2018-03-28 12:13:58Z

2

How you are accessing the graph is wrong. It isn't a dictionary so it doesn't know how to get an item the way you have it coded now. You are also going to run into problems with the queue as that is not how you add items to a list. You have a getter for vertices in the graph class you can use and adding to the queue list you can use append.

def bfs(g, s):
    explored, queue = [], [s]
    while queue:
        current_vertex = queue.pop(0)
        print(current_vertex)
        if current_vertex not in explored:
            explored.append(current_vertex)
            neighbors = g.get_vertex(current_vertex).get_neighbors()
            queue.extend(neighbors)
    return explored

Edited: I see you want to extend the queue and not append. Also you want to use the get_neighbors function as well as getting the vertex.

edited Mar 28, 2018 at 12:13

answered Mar 28, 2018 at 12:05

ForFunAndProfit

1,15813 silver badges17 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sreeragh A R · Accepted Answer · 2018-03-28 12:09:18Z

0

Replace

neighbors = g[current_vertex]

with

neighbors = g.get_vertex(current_vertex).get_neighbors()

answered Mar 28, 2018 at 12:09

Sreeragh A R

3,0413 gold badges32 silver badges58 bronze badges

Collectives™ on Stack Overflow

Python - Type Error: 'Graph' object is not subscriptable

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related