code: def hopcroft_karp_matching(G, top_nodes=None):
      """Returns the maximum cardinality matching of the bipartite graph `G`.
  
      A matching is a set of edges that do not share any nodes. A maximum
      cardinality matching is a matching with the most edges possible. It
      is not always unique. Finding a matching in a bipartite graph can be
      treated as a networkx flow problem.
  
      The functions ``hopcroft_karp_matching`` and ``maximum_matching``
      are aliases of the same function.
  
      Parameters
      ----------
      G : NetworkX graph
  
        Undirected bipartite graph
  
      top_nodes : container of nodes
  
        Container with all nodes in one bipartite node set. If not supplied
        it will be computed. But if more than one solution exists an exception
        will be raised.
  
      Returns
      -------
      matches : dictionary
  
        The matching is returned as a dictionary, `matches`, such that
        ``matches[v] == w`` if node `v` is matched to node `w`. Unmatched
        nodes do not occur as a key in `matches`.
  
      Raises
      ------
      AmbiguousSolution
        Raised if the input bipartite graph is disconnected and no container
        with all nodes in one bipartite set is provided. When determining
        the nodes in each bipartite set more than one valid solution is
        possible if the input graph is disconnected.
  
      Notes
      -----
      This function is implemented with the `Hopcroft--Karp matching algorithm
      <https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm>`_ for
      bipartite graphs.
  
      See :mod:`bipartite documentation <networkx.algorithms.bipartite>`
      for further details on how bipartite graphs are handled in NetworkX.
  
      See Also
      --------
      maximum_matching
      hopcroft_karp_matching
      eppstein_matching
  
      References
      ----------
      .. [1] John E. Hopcroft and Richard M. Karp. "An n^{5 / 2} Algorithm for
         Maximum Matchings in Bipartite Graphs" In: **SIAM Journal of Computing**
         2.4 (1973), pp. 225--231. <https://doi.org/10.1137/0202019>.
  
      """
  
      # First we define some auxiliary search functions.
      #
      # If you are a human reading these auxiliary search functions, the "global"
      # variables `leftmatches`, `rightmatches`, `distances`, etc. are defined
      # below the functions, so that they are initialized close to the initial
      # invocation of the search functions.
      def breadth_first_search():
          for v in left:
              if leftmatches[v] is None:
                  distances[v] = 0
                  queue.append(v)
              else:
                  distances[v] = INFINITY
          distances[None] = INFINITY
          while queue:
              v = queue.popleft()
              if distances[v] < distances[None]:
                  for u in G[v]:
                      if distances[rightmatches[u]] is INFINITY:
                          distances[rightmatches[u]] = distances[v] + 1
                          queue.append(rightmatches[u])
          return distances[None] is not INFINITY
  
      def depth_first_search(v):
          if v is not None:
              for u in G[v]:
                  if distances[rightmatches[u]] == distances[v] + 1:
                      if depth_first_search(rightmatches[u]):
                          rightmatches[u] = v
                          leftmatches[v] = u
                          return True
              distances[v] = INFINITY
              return False
          return True
  
      # Initialize the "global" variables that maintain state during the search.
      left, right = bipartite_sets(G, top_nodes)
      leftmatches = {v: None for v in left}
      rightmatches = {v: None for v in right}
      distances = {}
      queue = collections.deque()
  
      # Implementation note: this counter is incremented as pairs are matched but
      # it is currently not used elsewhere in the computation.
      num_matched_pairs = 0
      while breadth_first_search():
          for v in left:
              if leftmatches[v] is None:
                  if depth_first_search(v):
                      num_matched_pairs += 1
  
      # Strip the entries matched to `None`.
      leftmatches = {
          k: v for k, v in leftmatches.items() if v is not None
      }
      rightmatches = {
          k: v for k, v in rightmatches.items() if v is not None
      }
  
      # At this point, the left matches and the right matches are inverses of one
      # another. In other words,
      #
      #     leftmatches == {v, k for k, v in rightmatches.items()}
      #
      # Finally, we combine both the left matches and right matches.
      return dict(
          itertools.chain(leftmatches.items(), rightmatches.items())
      )
  
file_path: networkx/networkx/algorithms/bipartite/matching.py
imports: import collections
  import itertools
  import networkx
  from networkx.algorithms.bipartite import sets
  from networkx.algorithms.bipartite.matrix import biadjacency_matrix
label_desc: Use image node_id 1 for calling a global function with example usage: hopcroft_karp_matching(G, top_nodes) and returns: dict, unknown, True, False, True