graphs.prim
===========

.. py:module:: graphs.prim

.. autoapi-nested-parse::

   Prim's Algorithm.

   Determines the minimum spanning tree(MST) of a graph using the Prim's Algorithm.

   Details: https://en.wikipedia.org/wiki/Prim%27s_algorithm



Classes
-------

.. autoapisummary::

   graphs.prim.Vertex


Functions
---------

.. autoapisummary::

   graphs.prim.connect
   graphs.prim.prim
   graphs.prim.prim_heap
   graphs.prim.test_vector


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

.. py:class:: Vertex(id_)

   Class Vertex.


   .. py:method:: __lt__(other)

      Comparison rule to < operator.



   .. py:method:: __repr__()

      Return the vertex id.



   .. py:method:: add_edge(vertex, weight)

      Destination vertex and weight.



   .. py:method:: add_neighbor(vertex)

      Add a pointer to a vertex at neighbor's list.



   .. py:attribute:: edges


   .. py:attribute:: id
      :value: ''



   .. py:attribute:: key
      :value: None



   .. py:attribute:: neighbors
      :value: []



   .. py:attribute:: pi
      :value: None



.. py:function:: connect(graph, a, b, edge)

.. py:function:: prim(graph: list, root: Vertex) -> list

   Prim's Algorithm.

   Runtime:
       O(mn) with `m` edges and `n` vertices

   Return:
       List with the edges of a Minimum Spanning Tree

   Usage:
       prim(graph, graph[0])


.. py:function:: prim_heap(graph: list, root: Vertex) -> collections.abc.Iterator[tuple]

   Prim's Algorithm with min heap.

   Runtime:
       O((m + n)log n) with `m` edges and `n` vertices

   Yield:
       Edges of a Minimum Spanning Tree

   Usage:
       prim(graph, graph[0])


.. py:function:: test_vector() -> None

   # Creates a list to store x vertices.
   >>> x = 5
   >>> G = [Vertex(n) for n in range(x)]

   >>> connect(G, 1, 2, 15)
   >>> connect(G, 1, 3, 12)
   >>> connect(G, 2, 4, 13)
   >>> connect(G, 2, 5, 5)
   >>> connect(G, 3, 2, 6)
   >>> connect(G, 3, 4, 6)
   >>> connect(G, 0, 0, 0)  # Generate the minimum spanning tree:
   >>> G_heap = G[:]
   >>> MST = prim(G, G[0])
   >>> MST_heap = prim_heap(G, G[0])
   >>> for i in MST:
   ...     print(i)
   (2, 3)
   (3, 1)
   (4, 3)
   (5, 2)
   >>> for i in MST_heap:
   ...     print(i)
   (2, 3)
   (3, 1)
   (4, 3)
   (5, 2)