




'''simple docstring'''



from __future__ import annotations

from queue import Queue





class       lowerCAmelCase				:


       def __init__(				self					) ->					None:



            '''simple docstring'''




            __snake_case         =					{}


       def  lowerCAmelCase (				self					) ->					None:



            '''simple docstring'''




            for i in self.vertices:
                 print(__SCREAMING_SNAKE_CASE      ,					''' : '''      ,					''' -> '''.join([str(__SCREAMING_SNAKE_CASE					) for j in self.vertices[i]]					)					)


       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE      ,					__SCREAMING_SNAKE_CASE					) ->					None:



            '''simple docstring'''




            if from_vertex in self.vertices:
                 self.vertices[from_vertex].append(__SCREAMING_SNAKE_CASE					)
            else:
                 __snake_case         =					[to_vertex]




       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE					) ->					set[int]:



            '''simple docstring'''




            __snake_case         =					set()

            # create a first in first out queue to store all the vertices for BFS
            __snake_case         =					Queue()

            # mark the source node as visited and enqueue it
            visited.add(__SCREAMING_SNAKE_CASE					)
            queue.put(__SCREAMING_SNAKE_CASE					)

            while not queue.empty():
                 __snake_case         =					queue.get()

                 # loop through all adjacent vertex and enqueue it if not yet visited
                 for adjacent_vertex in self.vertices[vertex]:
                      if adjacent_vertex not in visited:
                           queue.put(__SCREAMING_SNAKE_CASE					)
                           visited.add(__SCREAMING_SNAKE_CASE					)
            return visited


if __name__ == "__main__":
     from doctest import testmod

     testmod(verbose=True)

     UpperCAmelCase_    :					Any					      =						Graph()
     g.add_edge(0, 1)
     g.add_edge(0, 2)
     g.add_edge(1, 2)
     g.add_edge(2, 0)
     g.add_edge(2, 3)
     g.add_edge(3, 3)

     g.print_graph()
     # 0  :  1 -> 2
     # 1  :  2
     # 2  :  0 -> 3
     # 3  :  3

     assert sorted(g.bfs(2)) == [0, 1, 2, 3]












'''simple docstring'''



from __future__ import annotations

from collections.abc import Iterator
from typing import Any





class       lowerCAmelCase				:


       def __init__(				self      ,					__SCREAMING_SNAKE_CASE					) ->					None:



            '''simple docstring'''




            __snake_case         =					data
            __snake_case         =					None




       def __str__(				self					) ->					str:



            '''simple docstring'''




            return F'''{self.data}'''





class       lowerCAmelCase				:


       def __init__(				self					) ->					None:



            '''simple docstring'''




            __snake_case         =					None
            __snake_case         =					None


       def __iter__(				self					) ->					Iterator[Any]:



            '''simple docstring'''




            __snake_case         =					self.front
            while node:
                 yield node.data
                 __snake_case         =					node.next


       def __len__(				self					) ->					int:



            '''simple docstring'''




            return len(tuple(iter(self					)					)					)


       def __str__(				self					) ->					str:



            '''simple docstring'''




            return " <- ".join(str(__SCREAMING_SNAKE_CASE					) for item in self					)


       def  lowerCAmelCase (				self					) ->					bool:



            '''simple docstring'''




            return len(self					) == 0


       def  lowerCAmelCase (				self      ,					__SCREAMING_SNAKE_CASE					) ->					None:



            '''simple docstring'''




            __snake_case         =					Node(__SCREAMING_SNAKE_CASE					)
            if self.is_empty():
                 __snake_case         =					__snake_case         =					node
            else:
                 assert isinstance(self.rear      ,					__SCREAMING_SNAKE_CASE					)
                 __snake_case         =					node
                 __snake_case         =					node


       def  lowerCAmelCase (				self					) ->					Any:



            '''simple docstring'''




            if self.is_empty():
                 raise IndexError('''dequeue from empty queue'''					)
            assert isinstance(self.front      ,					__SCREAMING_SNAKE_CASE					)
            __snake_case         =					self.front
            __snake_case         =					self.front.next
            if self.front is None:
                 __snake_case         =					None
            return node.data




       def  lowerCAmelCase (				self					) ->					None:



            '''simple docstring'''




            __snake_case         =					__snake_case         =					None


if __name__ == "__main__":
     from doctest import testmod

     testmod()






