graphs.breadth_first_search_zero_one_shortest_path
==================================================

.. py:module:: graphs.breadth_first_search_zero_one_shortest_path

.. autoapi-nested-parse::

   Finding the shortest path in 0-1-graph in O(E + V) which is faster than dijkstra.
   0-1-graph is the weighted graph with the weights equal to 0 or 1.
   Link: https://codeforces.com/blog/entry/22276



Classes
-------

.. autoapisummary::

   graphs.breadth_first_search_zero_one_shortest_path.AdjacencyList
   graphs.breadth_first_search_zero_one_shortest_path.Edge


Module Contents
---------------

.. py:class:: AdjacencyList(size: int)

   Graph adjacency list.


   .. py:method:: __getitem__(vertex: int) -> collections.abc.Iterator[Edge]

      Get all the vertices adjacent to the given one.



   .. py:method:: add_edge(from_vertex: int, to_vertex: int, weight: int)

      >>> g = AdjacencyList(2)
      >>> g.add_edge(0, 1, 0)
      >>> g.add_edge(1, 0, 1)
      >>> list(g[0])
      [Edge(destination_vertex=1, weight=0)]
      >>> list(g[1])
      [Edge(destination_vertex=0, weight=1)]
      >>> g.add_edge(0, 1, 2)
      Traceback (most recent call last):
          ...
      ValueError: Edge weight must be either 0 or 1.
      >>> g.add_edge(0, 2, 1)
      Traceback (most recent call last):
          ...
      ValueError: Vertex indexes must be in [0; size).



   .. py:method:: get_shortest_path(start_vertex: int, finish_vertex: int) -> int | None

      Return the shortest distance from start_vertex to finish_vertex in 0-1-graph.
            1                  1         1
       0--------->3        6--------7>------->8
       |          ^        ^        ^         |1
       |          |        |        |0        v
      0|          |0      1|        9-------->10
       |          |        |        ^    1
       v          |        |        |0
       1--------->2<-------4------->5
            0         1        1
      >>> g = AdjacencyList(11)
      >>> g.add_edge(0, 1, 0)
      >>> g.add_edge(0, 3, 1)
      >>> g.add_edge(1, 2, 0)
      >>> g.add_edge(2, 3, 0)
      >>> g.add_edge(4, 2, 1)
      >>> g.add_edge(4, 5, 1)
      >>> g.add_edge(4, 6, 1)
      >>> g.add_edge(5, 9, 0)
      >>> g.add_edge(6, 7, 1)
      >>> g.add_edge(7, 8, 1)
      >>> g.add_edge(8, 10, 1)
      >>> g.add_edge(9, 7, 0)
      >>> g.add_edge(9, 10, 1)
      >>> g.add_edge(1, 2, 2)
      Traceback (most recent call last):
          ...
      ValueError: Edge weight must be either 0 or 1.
      >>> g.get_shortest_path(0, 3)
      0
      >>> g.get_shortest_path(0, 4)
      Traceback (most recent call last):
          ...
      ValueError: No path from start_vertex to finish_vertex.
      >>> g.get_shortest_path(4, 10)
      2
      >>> g.get_shortest_path(4, 8)
      2
      >>> g.get_shortest_path(0, 1)
      0
      >>> g.get_shortest_path(1, 0)
      Traceback (most recent call last):
          ...
      ValueError: No path from start_vertex to finish_vertex.



   .. py:attribute:: _graph
      :type:  list[list[Edge]]


   .. py:attribute:: _size


   .. py:property:: size


.. py:class:: Edge

   Weighted directed graph edge.


   .. py:attribute:: destination_vertex
      :type:  int


   .. py:attribute:: weight
      :type:  int