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-2024, 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         800 : BipartiteMatch(int u_size, int v_size, short **adjacency)
      40             : {
      41         800 :     BipartiteMatchState *state = palloc(sizeof(BipartiteMatchState));
      42             : 
      43         800 :     if (u_size < 0 || u_size >= SHRT_MAX ||
      44         800 :         v_size < 0 || v_size >= SHRT_MAX)
      45           0 :         elog(ERROR, "invalid set size for BipartiteMatch");
      46             : 
      47         800 :     state->u_size = u_size;
      48         800 :     state->v_size = v_size;
      49         800 :     state->adjacency = adjacency;
      50         800 :     state->matching = 0;
      51         800 :     state->pair_uv = (short *) palloc0((u_size + 1) * sizeof(short));
      52         800 :     state->pair_vu = (short *) palloc0((v_size + 1) * sizeof(short));
      53         800 :     state->distance = (short *) palloc((u_size + 1) * sizeof(short));
      54         800 :     state->queue = (short *) palloc((u_size + 2) * sizeof(short));
      55             : 
      56        1198 :     while (hk_breadth_search(state))
      57             :     {
      58             :         int         u;
      59             : 
      60        1592 :         for (u = 1; u <= u_size; u++)
      61             :         {
      62        1194 :             if (state->pair_uv[u] == 0)
      63        1194 :                 if (hk_depth_search(state, u))
      64         570 :                     state->matching++;
      65             :         }
      66             : 
      67         398 :         CHECK_FOR_INTERRUPTS(); /* just in case */
      68             :     }
      69             : 
      70         800 :     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         800 : BipartiteMatchFree(BipartiteMatchState *state)
      79             : {
      80             :     /* adjacency matrix is treated as owned by the caller */
      81         800 :     pfree(state->pair_uv);
      82         800 :     pfree(state->pair_vu);
      83         800 :     pfree(state->distance);
      84         800 :     pfree(state->queue);
      85         800 :     pfree(state);
      86         800 : }
      87             : 
      88             : /*
      89             :  * Perform the breadth-first search step of H-K matching.
      90             :  * Returns true if successful.
      91             :  */
      92             : static bool
      93        1198 : hk_breadth_search(BipartiteMatchState *state)
      94             : {
      95        1198 :     int         usize = state->u_size;
      96        1198 :     short      *queue = state->queue;
      97        1198 :     short      *distance = state->distance;
      98        1198 :     int         qhead = 0;      /* we never enqueue any node more than once */
      99        1198 :     int         qtail = 0;      /* so don't have to worry about wrapping */
     100             :     int         u;
     101             : 
     102        1198 :     distance[0] = HK_INFINITY;
     103             : 
     104        4274 :     for (u = 1; u <= usize; u++)
     105             :     {
     106        3076 :         if (state->pair_uv[u] == 0)
     107             :         {
     108        2506 :             distance[u] = 0;
     109        2506 :             queue[qhead++] = u;
     110             :         }
     111             :         else
     112         570 :             distance[u] = HK_INFINITY;
     113             :     }
     114             : 
     115        4130 :     while (qtail < qhead)
     116             :     {
     117        2932 :         u = queue[qtail++];
     118             : 
     119        2932 :         if (distance[u] < distance[0])
     120             :         {
     121        2534 :             short      *u_adj = state->adjacency[u];
     122        2534 :             int         i = u_adj ? u_adj[0] : 0;
     123             : 
     124        3700 :             for (; i > 0; i--)
     125             :             {
     126        1166 :                 int         u_next = state->pair_vu[u_adj[i]];
     127             : 
     128        1166 :                 if (distance[u_next] == HK_INFINITY)
     129             :                 {
     130         426 :                     distance[u_next] = 1 + distance[u];
     131             :                     Assert(qhead < usize + 2);
     132         426 :                     queue[qhead++] = u_next;
     133             :                 }
     134             :             }
     135             :         }
     136             :     }
     137             : 
     138        1198 :     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        1764 : hk_depth_search(BipartiteMatchState *state, int u)
     147             : {
     148        1764 :     short      *distance = state->distance;
     149        1764 :     short      *pair_uv = state->pair_uv;
     150        1764 :     short      *pair_vu = state->pair_vu;
     151        1764 :     short      *u_adj = state->adjacency[u];
     152        1764 :     int         i = u_adj ? u_adj[0] : 0;
     153             :     short       nextdist;
     154             : 
     155        1764 :     if (u == 0)
     156         570 :         return true;
     157        1194 :     if (distance[u] == HK_INFINITY)
     158           0 :         return false;
     159        1194 :     nextdist = distance[u] + 1;
     160             : 
     161        1194 :     check_stack_depth();
     162             : 
     163        1430 :     for (; i > 0; i--)
     164             :     {
     165         806 :         int         v = u_adj[i];
     166             : 
     167         806 :         if (distance[pair_vu[v]] == nextdist)
     168             :         {
     169         570 :             if (hk_depth_search(state, pair_vu[v]))
     170             :             {
     171         570 :                 pair_vu[v] = u;
     172         570 :                 pair_uv[u] = v;
     173         570 :                 return true;
     174             :             }
     175             :         }
     176             :     }
     177             : 
     178         624 :     distance[u] = HK_INFINITY;
     179         624 :     return false;
     180             : }