Bug in `graphs/breadth_first_search.py`

[itsamirhn]

As you can see in the code below:

Python/graphs/breadth_first_search.py

Lines 25 to 38 in f31fa4e

	def add_edge(self, from_vertex: int, to_vertex: int) -> None:
	"""
	adding the edge between two vertices
	>>> g = Graph()
	>>> g.print_graph()
	>>> g.add_edge(0, 1)
	>>> g.print_graph()
	0 : 1
	"""
	if from_vertex in self.vertices:
	self.vertices[from_vertex].append(to_vertex)
	else:
	self.vertices[from_vertex] = [to_vertex]

this code only works for directed graphs and the BFS algorithm is wrong.
For example in this minimal example:

g = Graph()
g.add_edge(0, 1)
print(g.bfs(1))

You will get a KeyError: 1 because the node number 1 has not been added to the self.verices.

If you look closer, this code will raise a error too even when the graph is not directed:

g = Graph()
g.add_edge(0, 1)
print(g.bfs(0))

Cause in the BFS algorithm, when it reaches to node number 1, the previous problem appears here too.

This code is a little bugy and It should have stronger tests. Also the graphs/breadth_first_search_2.py file can be merged with this one too.

Please assign fixing this issue to me if I'm right about this problem.

[tanhm12]

You can work with both directed and undirected graphs (if an undirected graph has edge(a,b) then simply puts edge(b, a)) using same code. So why does this code need to be fixed ?

[itsamirhn]

In the second example, beside the graph is directed or not, You will get an error.

Also in the common algorithms, adding edge means bidirectional edge so maybe a just renaming the class to DirectedGraph is enough.

[Abdk4Moura]

I just added support for the non-directed graph by editing the add-edge function and adding a new function to carry out non-directional graphs routines.

class Graph:
    def __init__(self, directed=True):
        # ...

    def operation_for_nondirected(self, possibly_mono_connected_vertex: int) -> None:
        """
        >>> g = Graph(directed=False)
        >>> g.add_edge(0, 1)
        >>> g.print_graph()
        0  :  1
        """
        if self._directed is False:
            if possibly_mono_connected_vertex not in self.vertices:
                self.vertices[possibly_mono_connected_vertex] = []

    def add_edge(self, from_vertex: int, to_vertex: int) -> None:
        """
        adding the edge between two vertices
        >>> g = Graph()
        >>> g.print_graph()
        >>> g.add_edge(0, 1)
        >>> g.print_graph()
        0  :  1
        """
        # minor change here
        from_v = self.vertices[from_vertex] = self.vertices.get(from_vertex, [])
        from_v.append(to_vertex)
        # what to do if the graph itself is non-directed
        self.operation_for_nondirected(to_vertex)

@itsamirhn

[khoseomkar]

i am interested in solving this issue can you please assign this issue

[cclauss]

If multiple contributors submit solutions to the same algorithm, it is usually a learning experience for all parties. Therefore, we review pull requests and do not assign or reserve algorithms.