29 #define HK_INFINITY SHRT_MAX
43 if (u_size < 0 || u_size >= SHRT_MAX ||
44 v_size < 0 || v_size >= SHRT_MAX)
45 elog(
ERROR,
"invalid set size for BipartiteMatch");
47 state->u_size = u_size;
48 state->v_size = v_size;
49 state->adjacency = adjacency;
51 state->pair_uv = (
short *)
palloc0((u_size + 1) *
sizeof(short));
52 state->pair_vu = (
short *)
palloc0((v_size + 1) *
sizeof(short));
53 state->distance = (
short *)
palloc((u_size + 1) *
sizeof(short));
54 state->queue = (
short *)
palloc((u_size + 2) *
sizeof(short));
60 for (u = 1; u <= u_size; u++)
62 if (
state->pair_uv[u] == 0)
95 int usize =
state->u_size;
96 short *queue =
state->queue;
97 short *distance =
state->distance;
104 for (u = 1; u <= usize; u++)
106 if (
state->pair_uv[u] == 0)
115 while (qtail < qhead)
119 if (distance[u] < distance[0])
121 short *u_adj =
state->adjacency[u];
122 int i = u_adj ? u_adj[0] : 0;
126 int u_next =
state->pair_vu[u_adj[
i]];
130 distance[u_next] = 1 + distance[u];
131 Assert(qhead < usize + 2);
132 queue[qhead++] = u_next;
148 short *distance =
state->distance;
149 short *pair_uv =
state->pair_uv;
150 short *pair_vu =
state->pair_vu;
151 short *u_adj =
state->adjacency[u];
152 int i = u_adj ? u_adj[0] : 0;
159 nextdist = distance[u] + 1;
167 if (distance[pair_vu[v]] == nextdist)
static bool hk_depth_search(BipartiteMatchState *state, int u)
void BipartiteMatchFree(BipartiteMatchState *state)
static bool hk_breadth_search(BipartiteMatchState *state)
BipartiteMatchState * BipartiteMatch(int u_size, int v_size, short **adjacency)
#define Assert(condition)
void pfree(void *pointer)
void * palloc0(Size size)
#define CHECK_FOR_INTERRUPTS()
void check_stack_depth(void)