bipartite_match.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	BipartiteMatchState

Typedefs
typedef struct BipartiteMatchState	BipartiteMatchState

Functions
BipartiteMatchState *	BipartiteMatch (int u_size, int v_size, short **adjacency)
void	BipartiteMatchFree (BipartiteMatchState *state)

Typedef Documentation

BipartiteMatchState

typedef struct BipartiteMatchState BipartiteMatchState

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(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->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(), and palloc0().

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().