Line data    Source code

       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * bipartite_match.c
       4             :  *    Hopcroft-Karp maximum cardinality algorithm for bipartite graphs
       5             :  *
       6             :  * This implementation is based on pseudocode found at:
       7             :  *
       8             :  * https://en.wikipedia.org/w/index.php?title=Hopcroft%E2%80%93Karp_algorithm&oldid=593898016
       9             :  *
      10             :  * Copyright (c) 2015-2026, PostgreSQL Global Development Group
      11             :  *
      12             :  * IDENTIFICATION
      13             :  *    src/backend/lib/bipartite_match.c
      14             :  *
      15             :  *-------------------------------------------------------------------------
      16             :  */
      17             : #include "postgres.h"
      18             : 
      19             : #include <limits.h>
      20             : 
      21             : #include "lib/bipartite_match.h"
      22             : #include "miscadmin.h"
      23             : 
      24             : /*
      25             :  * The distances computed in hk_breadth_search can easily be seen to never
      26             :  * exceed u_size.  Since we restrict u_size to be less than SHRT_MAX, we
      27             :  * can therefore use SHRT_MAX as the "infinity" distance needed as a marker.
      28             :  */
      29             : #define HK_INFINITY  SHRT_MAX
      30             : 
      31             : static bool hk_breadth_search(BipartiteMatchState *state);
      32             : static bool hk_depth_search(BipartiteMatchState *state, int u);
      33             : 
      34             : /*
      35             :  * Given the size of U and V, where each is indexed 1..size, and an adjacency
      36             :  * list, perform the matching and return the resulting state.
      37             :  */
      38             : BipartiteMatchState *
      39         926 : BipartiteMatch(int u_size, int v_size, short **adjacency)
      40             : {
      41         926 :     BipartiteMatchState *state = palloc_object(BipartiteMatchState);
      42             : 
      43         926 :     if (u_size < 0 || u_size >= SHRT_MAX ||
      44         926 :         v_size < 0 || v_size >= SHRT_MAX)
      45           0 :         elog(ERROR, "invalid set size for BipartiteMatch");
      46             : 
      47         926 :     state->u_size = u_size;
      48         926 :     state->v_size = v_size;
      49         926 :     state->adjacency = adjacency;
      50         926 :     state->matching = 0;
      51         926 :     state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));
      52         926 :     state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));
      53         926 :     state->distance = (short *) palloc((u_size + 1) * sizeof(short));
      54         926 :     state->queue = (short *) palloc((u_size + 2) * sizeof(short));
      55             : 
      56        2274 :     while (hk_breadth_search(state))
      57             :     {
      58             :         int         u;
      59             : 
      60        1664 :         for (u = 1; u <= u_size; u++)
      61             :         {
      62        1242 :             if (state->pair_uv[u] == 0)
      63        1242 :                 if (hk_depth_search(state, u))
      64         594 :                     state->matching++;
      65             :         }
      66             : 
      67         422 :         CHECK_FOR_INTERRUPTS(); /* just in case */
      68             :     }
      69             : 
      70         926 :     return state;
      71             : }
      72             : 
      73             : /*
      74             :  * Free a state returned by BipartiteMatch, except for the original adjacency
      75             :  * list, which is owned by the caller. This only frees memory, so it's optional.
      76             :  */
      77             : void
      78         926 : BipartiteMatchFree(BipartiteMatchState *state)
      79             : {
      80             :     /* adjacency matrix is treated as owned by the caller */
      81         926 :     pfree(state->pair_uv);
      82         926 :     pfree(state->pair_vu);
      83         926 :     pfree(state->distance);
      84         926 :     pfree(state->queue);
      85         926 :     pfree(state);
      86         926 : }
      87             : 
      88             : /*
      89             :  * Perform the breadth-first search step of H-K matching.
      90             :  * Returns true if successful.
      91             :  */
      92             : static bool
      93        1348 : hk_breadth_search(BipartiteMatchState *state)
      94             : {
      95        1348 :     int         usize = state->u_size;
      96        1348 :     short      *queue = state->queue;
      97        1348 :     short      *distance = state->distance;
      98        1348 :     int         qhead = 0;      /* we never enqueue any node more than once */
      99        1348 :     int         qtail = 0;      /* so don't have to worry about wrapping */
     100             :     int         u;
     101             : 
     102        1348 :     distance[0] = HK_INFINITY;
     103             : 
     104        4742 :     for (u = 1; u <= usize; u++)
     105             :     {
     106        3394 :         if (state->pair_uv[u] == 0)
     107             :         {
     108        2800 :             distance[u] = 0;
     109        2800 :             queue[qhead++] = u;
     110             :         }
     111             :         else
     112         594 :             distance[u] = HK_INFINITY;
     113             :     }
     114             : 
     115        4598 :     while (qtail < qhead)
     116             :     {
     117        3250 :         u = queue[qtail++];
     118             : 
     119        3250 :         if (distance[u] < distance[0])
     120             :         {
     121        2828 :             short      *u_adj = state->adjacency[u];
     122        2828 :             int         i = u_adj ? u_adj[0] : 0;
     123             : 
     124        4018 :             for (; i > 0; i--)
     125             :             {
     126        1190 :                 int         u_next = state->pair_vu[u_adj[i]];
     127             : 
     128        1190 :                 if (distance[u_next] == HK_INFINITY)
     129             :                 {
     130         450 :                     distance[u_next] = 1 + distance[u];
     131             :                     Assert(qhead < usize + 2);
     132         450 :                     queue[qhead++] = u_next;
     133             :                 }
     134             :             }
     135             :         }
     136             :     }
     137             : 
     138        1348 :     return (distance[0] != HK_INFINITY);
     139             : }
     140             : 
     141             : /*
     142             :  * Perform the depth-first search step of H-K matching.
     143             :  * Returns true if successful.
     144             :  */
     145             : static bool
     146        1836 : hk_depth_search(BipartiteMatchState *state, int u)
     147             : {
     148        1836 :     short      *distance = state->distance;
     149        1836 :     short      *pair_uv = state->pair_uv;
     150        1836 :     short      *pair_vu = state->pair_vu;
     151        1836 :     short      *u_adj = state->adjacency[u];
     152        1836 :     int         i = u_adj ? u_adj[0] : 0;
     153             :     short       nextdist;
     154             : 
     155        1836 :     if (u == 0)
     156         594 :         return true;
     157        1242 :     if (distance[u] == HK_INFINITY)
     158           0 :         return false;
     159        1242 :     nextdist = distance[u] + 1;
     160             : 
     161        1242 :     check_stack_depth();
     162             : 
     163        1478 :     for (; i > 0; i--)
     164             :     {
     165         830 :         int         v = u_adj[i];
     166             : 
     167         830 :         if (distance[pair_vu[v]] == nextdist)
     168             :         {
     169         594 :             if (hk_depth_search(state, pair_vu[v]))
     170             :             {
     171         594 :                 pair_vu[v] = u;
     172         594 :                 pair_uv[u] = v;
     173         594 :                 return true;
     174             :             }
     175             :         }
     176             :     }
     177             : 
     178         648 :     distance[u] = HK_INFINITY;
     179         648 :     return false;
     180             : }