Python-TypeError: 'Graph' object is not subscriptable

Question

I am implementing a Graph class comparing breadth-first search with Prim's algorithm, and I have my code:

class Graph:
    def __init__(self, n):

        """This is an initialization function to creat a random graph with a specified number of vertices"""
        self.graph = [[inf for i in range(n)] for i in range(n)]
        self.number = n
        self.edge = tuple(range(n))
        for i in self.edge[1:]:
            j = random.randint(1, i)
            k = random.sample(range(i), j)
            for l in k:
                weight = random.randint(1, 100)
                self.graph[i][l] = self.graph[l][i] = weight

    def get_neighbours(self, i):

        """This is a function used to get neighbours of the specified vertex"""
        neighbours = []
        for e in self.edge:
            if self[i][e] < inf:
                neighbours.append(e)
        return neighbours

    def breadth_first_search(self):
        """
        This is a function used to return the total of the weight of the edges from a randomly-selected vertex
        :return: the total of the weight of the edges
        """
        all = set(self.edge)
        q = deque([all.pop()])
        total_weight = 0
        while q:
            i = q.popleft()
            for j in self.get_neighbours(i):
                if j in all:
                    all.remove(j)
                    q.append(j)
                    total_weight = total_weight + self.graph[i][j]
        return total_weight

    def test_bfst(self):
        """
        This function is used to test breadth first search tree
        :return:
        """
        graph = [
            [inf, 15, inf, 7, 10, inf],
            [15, inf, 9, 11, inf, 9],
            [inf, 9, inf, inf, 12, 7],
            [7, 11, inf, inf, 8, 14],
            [10, inf, 12, 8, inf, 8],
            [inf, 9, 7, 14, 8, inf]
        ]
        self.graph = graph
        print(self.breadth_first_search())

    def prime_mst(self):
        """
        This is prime's minimum spanning tree algorithm
        :return: the total of the weight of the edges
        """
        all = set(self.edge)
        list = [inf for i in self.edge]
        i = all.pop()
        total_weight = 0
        while True:
            for j in self.get_neighbours(i):
                if (i in all) and (k := self.graph[i][j] < list[j]):
                    list[j] = k

            if all:
                average_min, min = sorted([(j, list[j]) for j in all], key=lambda group: group[1])[0]
                all.remove(average_min)
                total_weight += min
                i = average_min
            else:
                break

        return total_weight


if __name__ == "__main__":
    times = int(input("please input an positive integer which represents testing times:"))
    for n in [20, 40, 60]:
        graph = Graph(n)
        diff = 0
        for i in range(times):
            bfs = graph.breadth_first_search()
            pmst = graph.prime_mst()
            diff = diff + (bfs - pmst) / pmst
        diff = diff / times
        print(diff)

And the error is like this when I run the code:

Traceback (most recent call last):
  File "C:\Users\52799\Desktop\Bsf_Prims\BSFvPRIM.py", line 99, in 
    bfs = graph.breadth_first_search()
  File "C:\Users\52799\Desktop\Bsf_Prims\BSFvPRIM.py", line 45, in breadth_first_search
    for j in self.get_neighbours(i):
  File "C:\Users\52799\Desktop\Bsf_Prims\BSFvPRIM.py", line 31, in get_neighbours
    if self[i][e] < inf:
TypeError: 'Graph' object is not subscriptable

I am thinking that I might make mistakes in getting the vertex neighbors, but I don't know why this error occurs. And my test graph is more like a matrix with nodes in it. I kind of stuck on getting the neighbors and the rest two algorithms will be improved later.

user_15611679 · Answer

When you say this:

if self[i][e] < inf:

You're trying to get a particular item from the instance of the object as if it's a container, like a sequence or mapping type, e.g. something implementing a __getitem__() method like a list or dictionary.

Worth noting, strings and bytestrings are also considered sequences and implement a __getitem__() method, which means they too are subscriptable:

In [1]: from typing import Sequence                                             

In [2]: string = "something"                                                    

In [3]: isinstance(string, Sequence)                                            
Out[3]: True

In [4]: string[2]                                                              
Out[4]: 'm'

You probably wanted to specify a particular attribute here like:

if self.graph[i][e] < inf:

I'm not familiar enough with what you're doing exactly to say what your intentions here were for sure, but you want something like the above. You don't want to "subscript" the class instance itself but some attribute that has a value that is subscriptable container.

If you really do need the class to be subscriptable, you would need to add a __getitem__() method like mappings or sequences.

Python-TypeError: 'Graph' object is not subscriptable

1 Answers