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.

Answer 1

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.

Answer 2

Replace

neighbors = g[current_vertex]

with

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