LCOV - code coverage report
Current view: top level - src/backend/lib - bipartite_match.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 69 71 97.2 %
Date: 2019-06-19 14:06:47 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13