graphs.hopcroft_karp
====================

.. py:module:: graphs.hopcroft_karp

.. autoapi-nested-parse::

   Hopcroft-Karp algorithm for finding maximum cardinality matching in bipartite graphs.

   Reference:
       https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

   The Hopcroft-Karp algorithm finds a maximum cardinality matching in an unweighted
   bipartite graph in O(|E| * sqrt(|V|)) time.

   Key Concepts and Conditions:
   1. Bipartite Condition:
      A graph G = (U union V, E) is bipartite if its vertices can be partitioned into
      two disjoint sets U (left partition) and V (right partition) such that every
      edge connects a vertex in U to a vertex in V. No edges may exist between two
      vertices within the same partition (U intersect V = empty set). Vertices cannot
      be None.

   2. Matching Condition:
      A matching M is a subset of edges such that no two edges share a common vertex.
      A vertex is 'free' (unmatched) if it is not incident to any edge in M.

   3. Alternating and Augmenting Paths:
      - Alternating path: A path whose edges alternate between unmatched edges
        (not in M) and matched edges (in M).
      - Augmenting path: An alternating path that starts and ends at distinct free
        vertices.
      - Berge's Lemma: A matching is of maximum cardinality if and only if no
        augmenting paths exist.

   4. Hopcroft-Karp Layering and Augmentation Conditions:
      Instead of searching for augmenting paths one-by-one (O(|V| * |E|)), Hopcroft-Karp
      operates in phases:
      - BFS Phase (Layering): Simultaneously searches from all free vertices in U to
        find the length of the shortest augmenting paths. It builds a layered DAG of
        alternating levels. If no free vertex in V is reachable, the algorithm terminates.
      - DFS Phase (Augmentation): Discovers a maximal set of vertex-disjoint augmenting
        paths of the shortest length found by BFS. It only traverses edges satisfying:
        distance_map[matched_left] == distance_map[curr_left] + 1.
      - Symmetric Difference: Matching edges along each augmenting path are flipped
        (unmatched becomes matched, matched becomes unmatched).
      - Iterative DFS: The DFS phase is implemented iteratively using an explicit stack
        to prevent RecursionError on graphs with large alternating path diameters.

   Complexity:
       Time Complexity:  O(|E| * sqrt(|V|))
       Space Complexity: O(|V| + |E|)



Attributes
----------

.. autoapisummary::

   graphs.hopcroft_karp._NIL


Classes
-------

.. autoapisummary::

   graphs.hopcroft_karp.HopcroftKarp


Functions
---------

.. autoapisummary::

   graphs.hopcroft_karp.hopcroft_karp
   graphs.hopcroft_karp.test_hopcroft_karp


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

.. py:class:: HopcroftKarp[T](graph: dict[T, list[T]])

   Class implementing the Hopcroft-Karp maximum bipartite matching algorithm.

   >>> hk = HopcroftKarp({"u1": ["v1", "v2"], "u2": ["v1"], "u3": ["v2", "v3"]})
   >>> hk.maximum_matching()
   {'u1': 'v2', 'u2': 'v1', 'u3': 'v3'}


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

      BFS Phase: Layer the graph and find shortest augmenting path length.

      Returns:
          True if at least one augmenting path to a free vertex in V exists,
          False otherwise (termination condition).

      >>> hk = HopcroftKarp({"u1": ["v1"]})
      >>> hk.breadth_first_search()
      True
      >>> hk.pair_left["u1"] = "v1"
      >>> hk.pair_right["v1"] = "u1"
      >>> hk.breadth_first_search()
      False



   .. py:method:: depth_first_search(start_left: T) -> bool

      DFS Phase: Find and augment along shortest augmenting paths iteratively.

      Implemented iteratively with an explicit stack to prevent RecursionError
      on graphs with deep alternating paths (diameter > 1000).

      Parameters:
          start_left: The free vertex in the left partition to start the search from.

      Returns:
          True if an augmenting path was found and augmented, False otherwise.

      >>> hk = HopcroftKarp({"u1": ["v1"]})
      >>> _ = hk.breadth_first_search()
      >>> hk.depth_first_search("u1")
      True
      >>> hk.pair_left["u1"]
      'v1'
      >>> hk.depth_first_search("u1")
      False



   .. py:method:: maximum_matching() -> dict[T, T]

      Compute and return the maximum cardinality matching.

      >>> hk = HopcroftKarp({"u1": ["v1"], "u2": ["v1"]})
      >>> hk.maximum_matching()
      {'u1': 'v1'}



   .. py:attribute:: distance_map
      :type:  dict[T | object, float]


   .. py:attribute:: graph


   .. py:attribute:: left_vertices


   .. py:attribute:: pair_left
      :type:  dict[T, T | object]


   .. py:attribute:: pair_right
      :type:  dict[T, T | object]


   .. py:attribute:: right_vertices


.. py:function:: hopcroft_karp[T](graph: dict[T, list[T]]) -> dict[T, T]

   Find a maximum cardinality matching in a bipartite graph using Hopcroft-Karp.

   Parameters:
       graph: An adjacency list mapping each vertex in the left partition (U) to
           a list of adjacent vertices in the right partition (V). The two
           partitions must be disjoint, and vertices cannot be None.

   Returns:
       A dictionary representing the matching, mapping each matched vertex in
       the left partition to its matched partner in the right partition.

   Raises:
       ValueError: If any vertex appears in both partitions or if any vertex is None.

   Examples:
       >>> # Standard bipartite matching
       >>> graph = {"u1": ["v1", "v2"], "u2": ["v1"], "u3": ["v2", "v3"]}
       >>> hopcroft_karp(graph)
       {'u1': 'v2', 'u2': 'v1', 'u3': 'v3'}

       >>> # Empty graph condition
       >>> hopcroft_karp({})
       {}

       >>> # Isolated vertices (no incident edges)
       >>> hopcroft_karp({"u1": []})
       {}

       >>> # Competing vertices (more left vertices than right vertices)
       >>> hopcroft_karp({"u1": ["v1"], "u2": ["v1"]})
       {'u1': 'v1'}

       >>> # Bipartite cycle (6 vertices)
       >>> cycle_graph = {
       ...     "u1": ["v1", "v2"],
       ...     "u2": ["v2", "v3"],
       ...     "u3": ["v3", "v1"],
       ... }
       >>> hopcroft_karp(cycle_graph)
       {'u1': 'v1', 'u2': 'v2', 'u3': 'v3'}

       >>> # Error condition: Overlapping partitions (not a valid bipartite graph)
       >>> hopcroft_karp({"A": ["A"]})
       Traceback (most recent call last):
           ...
       ValueError: Partitions must be disjoint: found vertices in both sets: ['A']

       >>> # Error condition: None vertex
       >>> hopcroft_karp({"u": [None]})
       Traceback (most recent call last):
           ...
       ValueError: Vertices cannot be None


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

   Pytest test function to verify maximum bipartite matching functionality.

   >>> test_hopcroft_karp()


.. py:data:: _NIL