graphs.minimum_spanning_tree_prims2
===================================

.. py:module:: graphs.minimum_spanning_tree_prims2

.. autoapi-nested-parse::

   Prim's (also known as Jarník's) algorithm is a greedy algorithm that finds a minimum
   spanning tree for a weighted undirected graph. This means it finds a subset of the
   edges that forms a tree that includes every vertex, where the total weight of all the
   edges in the tree is minimized. The algorithm operates by building this tree one vertex
   at a time, from an arbitrary starting vertex, at each step adding the cheapest possible
   connection from the tree to another vertex.



Attributes
----------

.. autoapisummary::

   graphs.minimum_spanning_tree_prims2.T


Classes
-------

.. autoapisummary::

   graphs.minimum_spanning_tree_prims2.GraphUndirectedWeighted
   graphs.minimum_spanning_tree_prims2.MinPriorityQueue


Functions
---------

.. autoapisummary::

   graphs.minimum_spanning_tree_prims2.get_child_left_position
   graphs.minimum_spanning_tree_prims2.get_child_right_position
   graphs.minimum_spanning_tree_prims2.get_parent_position
   graphs.minimum_spanning_tree_prims2.prims_algo


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

.. py:class:: GraphUndirectedWeighted

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ ]


   Graph Undirected Weighted Class

   Functions:
   add_node: function to add a node in the graph
   add_edge: function to add an edge between 2 nodes in the graph


   .. py:method:: __len__() -> int


   .. py:method:: __repr__() -> str


   .. py:method:: add_edge(node1: T, node2: T, weight: int) -> None


   .. py:method:: add_node(node: T) -> None


   .. py:attribute:: connections
      :type:  dict[T, dict[T, int]]


   .. py:attribute:: nodes
      :type:  int
      :value: 0



.. py:class:: MinPriorityQueue

   Bases: :py:obj:`Generic`\ [\ :py:obj:`T`\ ]


   Minimum Priority Queue Class

   Functions:
   is_empty: function to check if the priority queue is empty
   push: function to add an element with given priority to the queue
   extract_min: function to remove and return the element with lowest weight (highest
                priority)
   update_key: function to update the weight of the given key
   _bubble_up: helper function to place a node at the proper position (upward
               movement)
   _bubble_down: helper function to place a node at the proper position (downward
               movement)
   _swap_nodes: helper function to swap the nodes at the given positions

   >>> queue = MinPriorityQueue()

   >>> queue.push(1, 1000)
   >>> queue.push(2, 100)
   >>> queue.push(3, 4000)
   >>> queue.push(4, 3000)

   >>> queue.extract_min()
   2

   >>> queue.update_key(4, 50)

   >>> queue.extract_min()
   4
   >>> queue.extract_min()
   1
   >>> queue.extract_min()
   3


   .. py:method:: __len__() -> int


   .. py:method:: __repr__() -> str


   .. py:method:: _bubble_down(elem: T) -> None


   .. py:method:: _bubble_up(elem: T) -> None


   .. py:method:: _swap_nodes(node1_pos: int, node2_pos: int) -> None


   .. py:method:: extract_min() -> T


   .. py:method:: is_empty() -> bool


   .. py:method:: push(elem: T, weight: int) -> None


   .. py:method:: update_key(elem: T, weight: int) -> None


   .. py:attribute:: elements
      :type:  int
      :value: 0



   .. py:attribute:: heap
      :type:  list[tuple[T, int]]
      :value: []



   .. py:attribute:: position_map
      :type:  dict[T, int]


.. py:function:: get_child_left_position(position: int) -> int

   heap helper function get the position of the left child of the current node

   >>> get_child_left_position(0)
   1


.. py:function:: get_child_right_position(position: int) -> int

   heap helper function get the position of the right child of the current node

   >>> get_child_right_position(0)
   2


.. py:function:: get_parent_position(position: int) -> int

   heap helper function get the position of the parent of the current node

   >>> get_parent_position(1)
   0
   >>> get_parent_position(2)
   0


.. py:function:: prims_algo(graph: GraphUndirectedWeighted[T]) -> tuple[dict[T, int], dict[T, T | None]]

   >>> graph = GraphUndirectedWeighted()

   >>> graph.add_edge("a", "b", 3)
   >>> graph.add_edge("b", "c", 10)
   >>> graph.add_edge("c", "d", 5)
   >>> graph.add_edge("a", "c", 15)
   >>> graph.add_edge("b", "d", 100)

   >>> dist, parent = prims_algo(graph)

   >>> abs(dist["a"] - dist["b"])
   3
   >>> abs(dist["d"] - dist["b"])
   15
   >>> abs(dist["a"] - dist["c"])
   13


.. py:data:: T