bipartite_match.c File Reference

#include "postgres.h"
#include <limits.h>
#include "lib/bipartite_match.h"
#include "miscadmin.h"

Include dependency graph for bipartite_match.c:

Go to the source code of this file.

Macros
#define	HK_INFINITY   SHRT_MAX

Functions
static bool	hk_breadth_search (BipartiteMatchState *state)
static bool	hk_depth_search (BipartiteMatchState *state, int u)
BipartiteMatchState *	BipartiteMatch (int u_size, int v_size, short **adjacency)
void	BipartiteMatchFree (BipartiteMatchState *state)

Macro Definition Documentation

HK_INFINITY

#define HK_INFINITY   SHRT_MAX

Definition at line 29 of file bipartite_match.c.

Function Documentation

BipartiteMatch()

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

Definition at line 39 of file bipartite_match.c.

{
    BipartiteMatchState *state = palloc_object(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;
}

References CHECK_FOR_INTERRUPTS, elog, ERROR, hk_breadth_search(), hk_depth_search(), palloc(), palloc0(), and palloc_object.

Referenced by extract_rollup_sets().

BipartiteMatchFree()

void BipartiteMatchFree

(

BipartiteMatchState *

state

)

Definition at line 78 of file bipartite_match.c.

{
    /* 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);
}

References pfree().

Referenced by extract_rollup_sets().

hk_breadth_search()

static bool hk_breadth_search ( BipartiteMatchState *  state )

static

Definition at line 93 of file bipartite_match.c.

{
    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);
}

References Assert(), HK_INFINITY, and i.

Referenced by BipartiteMatch().

hk_depth_search()

static bool hk_depth_search ( BipartiteMatchState *  state, int  u  )

static

Definition at line 146 of file bipartite_match.c.

{
    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;
}

References check_stack_depth(), hk_depth_search(), HK_INFINITY, and i.

Referenced by BipartiteMatch(), and hk_depth_search().