graphs.edmonds_blossom_algorithm
================================

.. py:module:: graphs.edmonds_blossom_algorithm


Classes
-------

.. autoapisummary::

   graphs.edmonds_blossom_algorithm.BlossomAuxData
   graphs.edmonds_blossom_algorithm.BlossomData
   graphs.edmonds_blossom_algorithm.EdmondsBlossomAlgorithm


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

.. py:class:: BlossomAuxData(queue: collections.deque, parent: list[int], base: list[int], in_blossom: list[bool], match: list[int], in_queue: list[bool])

   Class to hold auxiliary data during the blossom algorithm's execution.


   .. py:attribute:: base


   .. py:attribute:: in_blossom


   .. py:attribute:: in_queue


   .. py:attribute:: match


   .. py:attribute:: parent


   .. py:attribute:: queue


.. py:class:: BlossomData(aux_data: BlossomAuxData, vertex_u: int, vertex_v: int, lowest_common_ancestor: int)

   Class to encapsulate data related to a blossom in the graph.


   .. py:attribute:: aux_data


   .. py:attribute:: lowest_common_ancestor


   .. py:attribute:: vertex_u


   .. py:attribute:: vertex_v


.. py:class:: EdmondsBlossomAlgorithm

   .. py:method:: contract_blossom(blossom_data: BlossomData) -> None
      :staticmethod:


      Contracts a blossom found during the matching process.

      Args:
          blossom_data: The data related to the blossom to be contracted.



   .. py:method:: find_base(base: list[int], parent: list[int], vertex_u: int, vertex_v: int) -> int
      :staticmethod:


      Finds the base of the blossom.

      Args:
          base: The base array for each vertex.
          parent: The parent array from BFS.
          vertex_u: One endpoint of the blossom.
          vertex_v: The other endpoint of the blossom.

      Returns:
          The lowest common ancestor of vertex_u and vertex_v in the blossom.



   .. py:method:: maximum_matching(edges: list[list[int]], vertex_count: int) -> list[list[int]]
      :staticmethod:


      Finds the maximum matching in a graph using the Edmonds Blossom Algorithm.

      Args:
          edges: A list of edges represented as pairs of vertices.
          vertex_count: The total number of vertices in the graph.

      Returns:
          A list of matched pairs in the form of a list of lists.



   .. py:method:: update_matching(match: list[int], parent: list[int], matched_vertex: int) -> None
      :staticmethod:


      Updates the matching based on the augmenting path found.

      Args:
          match: The current match list.
          parent: The parent list from BFS traversal.
          matched_vertex: The vertex where the augmenting path ends.



   .. py:attribute:: UNMATCHED
      :value: -1