Python: Simple graph representation. Test fails

Question

I have a problem with my graph representation with dictionary. Here is my code:

from typing import List

class GraphAdjacencyDictionary:

    def __init__(self, number_of_vertices: int):
        self.dic = {}
        for i in range(number_of_vertices):
            self.dic[i] = []

    def add_new_edge(self, vertex1: int, vertex2: int):
        self.dic[vertex1].append(vertex2)
        self.dic[vertex2].append(vertex1)
        print(self.dic)

    def get_list_of_adjacent_vertices(self, vertex: int) -> List[int]:
        res = []
        for i in self.dic:
            res.append(1) if i in self.dic[vertex] else res.append(0)
        return res

    def get_number_of_adjacent_vertices(self, vertex: int) -> int:
        return len(self.dic[vertex])

    def is_edge(self, vertex1: int, vertex2: int) -> bool:
        return vertex2 in self.dic[vertex1]

So, one of the test fails on get_number_of_adjacent_vertices - Assertion Error: 5 == 4

I think I did task correct, and have a supposition, that there is a mistake in tests, could you please confirm or refute my theory

Answer 1

The root of your problem can be in your add_new_edge() function, where the test case can contain duplicate entries.

def add_new_edge(self, vertex1: int, vertex2: int):
    if vertex2 not in self.dic[vertex1]:
        self.dic[vertex1].append(vertex2)
        self.dic[vertex2].append(vertex1)
    print(self.dic)

Although it's better to use set instead of list inside your dictionary. Since it does not store duplicate values.