/*-------------------------------------------------------------------------

 *

 * bipartite_match.c

 *    Hopcroft-Karp maximum cardinality algorithm for bipartite graphs

 *

 * This implementation is based on pseudocode found at:

 *

 * https://en.wikipedia.org/w/index.php?title=Hopcroft%E2%80%93Karp_algorithm&oldid=593898016

 *

 * Copyright (c) 2015-2025, PostgreSQL Global Development Group

 *

 * IDENTIFICATION

 *    src/backend/lib/bipartite_match.c

 *

 *-------------------------------------------------------------------------

 */

#include "postgres.h"

#include <limits.h>

#include "lib/bipartite_match.h"

#include "miscadmin.h"

/*

 * The distances computed in hk_breadth_search can easily be seen to never

 * exceed u_size.  Since we restrict u_size to be less than SHRT_MAX, we

 * can therefore use SHRT_MAX as the "infinity" distance needed as a marker.

 */

#define HK_INFINITY  SHRT_MAX

static bool hk_breadth_search(BipartiteMatchState *state);

static bool hk_depth_search(BipartiteMatchState *state, int u);

/*

 * Given the size of U and V, where each is indexed 1..size, and an adjacency

 * list, perform the matching and return the resulting state.

 */

BipartiteMatchState *

BipartiteMatch(int u_size, int v_size, short **adjacency)

{

  BipartiteMatchState *state = palloc(sizeof(BipartiteMatchState));

  if (u_size < 0 || u_size >= SHRT_MAX ||

    v_size < 0 || v_size >= SHRT_MAX)

    elog(ERROR, "invalid set size for BipartiteMatch");

  state->u_size = u_size;

  state->v_size = v_size;

  state->adjacency = adjacency;

  state->matching = 0;

  state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));

  state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));

  state->distance = (short *) palloc((u_size + 1) * sizeof(short));

  state->queue = (short *) palloc((u_size + 2) * sizeof(short));

  while (hk_breadth_search(state))

  {

    int     u;

    for (u = 1; u <= u_size; u++)

    {

      if (state->pair_uv[u] == 0)

        if (hk_depth_search(state, u))

          state->matching++;

    }

    CHECK_FOR_INTERRUPTS(); /* just in case */

  }

  return state;

}

/*

 * Free a state returned by BipartiteMatch, except for the original adjacency

 * list, which is owned by the caller. This only frees memory, so it's optional.

 */

void

BipartiteMatchFree(BipartiteMatchState *state)

{

  /* adjacency matrix is treated as owned by the caller */

  pfree(state->pair_uv);

  pfree(state->pair_vu);

  pfree(state->distance);

  pfree(state->queue);

  pfree(state);

}

/*

 * Perform the breadth-first search step of H-K matching.

 * Returns true if successful.

 */

static bool

hk_breadth_search(BipartiteMatchState *state)

{

  int     usize = state->u_size;

  short    *queue = state->queue;

  short    *distance = state->distance;

  int     qhead = 0;    /* we never enqueue any node more than once */

  int     qtail = 0;    /* so don't have to worry about wrapping */

  int     u;

  distance[0] = HK_INFINITY;

  for (u = 1; u <= usize; u++)

  {

    if (state->pair_uv[u] == 0)

    {

      distance[u] = 0;

      queue[qhead++] = u;

    }

    else

      distance[u] = HK_INFINITY;

  }

  while (qtail < qhead)

  {

    u = queue[qtail++];

    if (distance[u] < distance[0])

    {

      short    *u_adj = state->adjacency[u];

      int     i = u_adj ? u_adj[0] : 0;

      for (; i > 0; i--)

      {

        int     u_next = state->pair_vu[u_adj[i]];

        if (distance[u_next] == HK_INFINITY)

        {

          distance[u_next] = 1 + distance[u];

          Assert(qhead < usize + 2);

          queue[qhead++] = u_next;

        }

      }

    }

  }

  return (distance[0] != HK_INFINITY);

}

/*

 * Perform the depth-first search step of H-K matching.

 * Returns true if successful.

 */

static bool

hk_depth_search(BipartiteMatchState *state, int u)

{

  short    *distance = state->distance;

  short    *pair_uv = state->pair_uv;

  short    *pair_vu = state->pair_vu;

  short    *u_adj = state->adjacency[u];

  int     i = u_adj ? u_adj[0] : 0;

  short   nextdist;

  if (u == 0)

    return true;

  if (distance[u] == HK_INFINITY)

    return false;

  nextdist = distance[u] + 1;

  check_stack_depth();

  for (; i > 0; i--)

  {

    int     v = u_adj[i];

    if (distance[pair_vu[v]] == nextdist)

    {

      if (hk_depth_search(state, pair_vu[v]))

      {

        pair_vu[v] = u;

        pair_uv[u] = v;

        return true;

      }

    }

  }

  distance[u] = HK_INFINITY;

  return false;

}