graphs.dijkstra_algorithm
=========================

.. py:module:: graphs.dijkstra_algorithm


Attributes
----------

.. autoapisummary::

   graphs.dijkstra_algorithm.graph


Classes
-------

.. autoapisummary::

   graphs.dijkstra_algorithm.Graph
   graphs.dijkstra_algorithm.PriorityQueue


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

.. py:class:: Graph(num)

   .. py:method:: add_edge(u, v, w)

      Add edge going from node u to v and v to u with weight w: u (w)-> v, v (w) -> u

      Examples:
      >>> graph_test = Graph(1)
      >>> graph_test.add_edge(1, 2, 1)
      >>> graph_test.add_edge(2, 3, 2)
      >>> graph_test.adjList
      {1: [(2, 1)], 2: [(1, 1), (3, 2)], 3: [(2, 2)]}



   .. py:method:: dijkstra(src)

      Dijkstra algorithm

      Examples:
      >>> graph_test = Graph(3)
      >>> graph_test.add_edge(0, 1, 2)
      >>> graph_test.add_edge(1, 2, 2)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 2
      Node 2 has distance: 4
      >>> graph_test.dist
      [0, 2, 4]

      >>> graph_test = Graph(2)
      >>> graph_test.add_edge(0, 1, 2)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 2
      >>> graph_test.dist
      [0, 2]

      >>> graph_test = Graph(3)
      >>> graph_test.add_edge(0, 1, 2)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 2
      Node 2 has distance: 0
      >>> graph_test.dist
      [0, 2, 0]

      >>> graph_test = Graph(3)
      >>> graph_test.add_edge(0, 1, 2)
      >>> graph_test.add_edge(1, 2, 2)
      >>> graph_test.add_edge(0, 2, 1)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 2
      Node 2 has distance: 1
      >>> graph_test.dist
      [0, 2, 1]

      >>> graph_test = Graph(4)
      >>> graph_test.add_edge(0, 1, 4)
      >>> graph_test.add_edge(1, 2, 2)
      >>> graph_test.add_edge(2, 3, 1)
      >>> graph_test.add_edge(0, 2, 3)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 4
      Node 2 has distance: 3
      Node 3 has distance: 4
      >>> graph_test.dist
      [0, 4, 3, 4]

      >>> graph_test = Graph(4)
      >>> graph_test.add_edge(0, 1, 4)
      >>> graph_test.add_edge(1, 2, 2)
      >>> graph_test.add_edge(2, 3, 1)
      >>> graph_test.add_edge(0, 2, 7)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 4
      Node 2 has distance: 6
      Node 3 has distance: 7
      >>> graph_test.dist
      [0, 4, 6, 7]



   .. py:method:: show_distances(src)

      Show the distances from src to all other nodes in a graph

      Examples:
      >>> graph_test = Graph(1)
      >>> graph_test.show_distances(0)
      Distance from node: 0
      Node 0 has distance: 0



   .. py:method:: show_graph()

      Show the graph: u -> v(w)

      Examples:
      >>> graph_test = Graph(1)
      >>> graph_test.add_edge(1, 2, 1)
      >>> graph_test.show_graph()
      1 -> 2(1)
      2 -> 1(1)
      >>> graph_test.add_edge(2, 3, 2)
      >>> graph_test.show_graph()
      1 -> 2(1)
      2 -> 1(1) -> 3(2)
      3 -> 2(2)



   .. py:method:: show_path(src, dest)

      Shows the shortest path from src to dest.
      WARNING: Use it *after* calling dijkstra.

      Examples:
      >>> graph_test = Graph(4)
      >>> graph_test.add_edge(0, 1, 1)
      >>> graph_test.add_edge(1, 2, 2)
      >>> graph_test.add_edge(2, 3, 3)
      >>> graph_test.dijkstra(0)
      Distance from node: 0
      Node 0 has distance: 0
      Node 1 has distance: 1
      Node 2 has distance: 3
      Node 3 has distance: 6
      >>> graph_test.show_path(0, 3)  # doctest: +NORMALIZE_WHITESPACE
      ----Path to reach 3 from 0----
      0 -> 1 -> 2 -> 3
      Total cost of path:  6



   .. py:attribute:: adjList


   .. py:attribute:: dist


   .. py:attribute:: num_nodes


   .. py:attribute:: par


.. py:class:: PriorityQueue

   .. py:method:: decrease_key(tup, new_d)

      Decrease the key value for a given tuple, assuming the new_d is at most old_d.

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.array = [(10, 'A'), (15, 'B')]
      >>> priority_queue_test.cur_size = len(priority_queue_test.array)
      >>> priority_queue_test.pos = {'A': 0, 'B': 1}
      >>> priority_queue_test.decrease_key((10, 'A'), 5)
      >>> priority_queue_test.array
      [(5, 'A'), (15, 'B')]



   .. py:method:: extract_min()

      Removes and returns the min element at top of priority queue.

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.array = [(10, 'A'), (15, 'B')]
      >>> priority_queue_test.cur_size = len(priority_queue_test.array)
      >>> priority_queue_test.pos = {'A': 0, 'B': 1}
      >>> priority_queue_test.insert((5, 'C'))
      >>> priority_queue_test.extract_min()
      'C'
      >>> priority_queue_test.array[0]
      (15, 'B')



   .. py:method:: insert(tup)

      Inserts a node into the Priority Queue.

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.insert((10, 'A'))
      >>> priority_queue_test.array
      [(10, 'A')]
      >>> priority_queue_test.insert((15, 'B'))
      >>> priority_queue_test.array
      [(10, 'A'), (15, 'B')]
      >>> priority_queue_test.insert((5, 'C'))
      >>> priority_queue_test.array
      [(5, 'C'), (10, 'A'), (15, 'B')]



   .. py:method:: is_empty()

      Conditional boolean method to determine if the priority queue is empty or not.

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.is_empty()
      True
      >>> priority_queue_test.insert((2, 'A'))
      >>> priority_queue_test.is_empty()
      False



   .. py:method:: left(i)

      Returns the index of left child

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.left(0)
      1
      >>> priority_queue_test.left(1)
      3



   .. py:method:: min_heapify(idx)

      Sorts the queue array so that the minimum element is root.

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.cur_size = 3
      >>> priority_queue_test.pos = {'A': 0, 'B': 1, 'C': 2}

      >>> priority_queue_test.array = [(5, 'A'), (10, 'B'), (15, 'C')]
      >>> priority_queue_test.min_heapify(0)
      Traceback (most recent call last):
          ...
      TypeError: 'list' object is not callable
      >>> priority_queue_test.array
      [(5, 'A'), (10, 'B'), (15, 'C')]

      >>> priority_queue_test.array = [(10, 'A'), (5, 'B'), (15, 'C')]
      >>> priority_queue_test.min_heapify(0)
      Traceback (most recent call last):
          ...
      TypeError: 'list' object is not callable
      >>> priority_queue_test.array
      [(10, 'A'), (5, 'B'), (15, 'C')]

      >>> priority_queue_test.array = [(10, 'A'), (15, 'B'), (5, 'C')]
      >>> priority_queue_test.min_heapify(0)
      Traceback (most recent call last):
          ...
      TypeError: 'list' object is not callable
      >>> priority_queue_test.array
      [(10, 'A'), (15, 'B'), (5, 'C')]

      >>> priority_queue_test.array = [(10, 'A'), (5, 'B')]
      >>> priority_queue_test.cur_size = len(priority_queue_test.array)
      >>> priority_queue_test.pos = {'A': 0, 'B': 1}
      >>> priority_queue_test.min_heapify(0)
      Traceback (most recent call last):
          ...
      TypeError: 'list' object is not callable
      >>> priority_queue_test.array
      [(10, 'A'), (5, 'B')]



   .. py:method:: par(i)

      Returns the index of parent

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.par(1)
      0
      >>> priority_queue_test.par(2)
      1
      >>> priority_queue_test.par(4)
      2



   .. py:method:: right(i)

      Returns the index of right child

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.right(0)
      2
      >>> priority_queue_test.right(1)
      4



   .. py:method:: swap(i, j)

      Swaps array elements at indices i and j, update the pos{}

      Examples:
      >>> priority_queue_test = PriorityQueue()
      >>> priority_queue_test.array = [(10, 'A'), (15, 'B')]
      >>> priority_queue_test.cur_size = len(priority_queue_test.array)
      >>> priority_queue_test.pos = {'A': 0, 'B': 1}
      >>> priority_queue_test.swap(0, 1)
      >>> priority_queue_test.array
      [(15, 'B'), (10, 'A')]
      >>> priority_queue_test.pos
      {'A': 1, 'B': 0}



   .. py:attribute:: array
      :value: []



   .. py:attribute:: cur_size
      :value: 0



   .. py:attribute:: pos


.. py:data:: graph