# greenplumn bipartite_match 源码

• 2022-08-18
• 浏览 (47)

## greenplumn bipartite_match 代码

``````/*-------------------------------------------------------------------------
*
* 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-2019, PostgreSQL Global Development Group
*
* IDENTIFICATION
*	  src/backend/lib/bipartite_match.c
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"

#include <limits.h>

#include "lib/bipartite_match.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_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->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));

{
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
{
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 = HK_INFINITY;

for (u = 1; u <= usize; u++)
{
if (state->pair_uv[u] == 0)
{
distance[u] = 0;
}
else
distance[u] = HK_INFINITY;
}

{
u = queue[qtail++];

if (distance[u] < distance)
{

for (; i > 0; i--)
{

if (distance[u_next] == HK_INFINITY)
{
distance[u_next] = 1 + distance[u];
}
}
}
}

return (distance != 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		nextdist;

if (u == 0)
return true;
if (distance[u] == HK_INFINITY)
return false;
nextdist = distance[u] + 1;

check_stack_depth();

for (; i > 0; 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;
}
``````

greenplumn 源码目录

## 相关文章

greenplumn binaryheap 源码

greenplumn bloomfilter 源码

greenplumn dshash 源码

greenplumn hyperloglog 源码

greenplumn ilist 源码

greenplumn integerset 源码

greenplumn knapsack 源码

greenplumn pairingheap 源码

greenplumn rbtree 源码

0