PostgreSQL Source Code
git master
bipartite_match.c
Go to the documentation of this file.
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
* http://en.wikipedia.org/w/index.php?title=Hopcroft%E2%80%93Karp_algorithm&oldid=593898016
9
*
10
* Copyright (c) 2015-2018, 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
BipartiteMatch
(
int
u_size,
int
v_size,
short
**adjacency)
40
{
41
BipartiteMatchState
*
state
=
palloc
(
sizeof
(
BipartiteMatchState
));
42
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"
);
46
47
state->
u_size
= u_size;
48
state->
v_size
= v_size;
49
state->
adjacency
= adjacency;
50
state->
matching
= 0;
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));
55
56
while
(
hk_breadth_search
(state))
57
{
58
int
u;
59
60
for
(u = 1; u <= u_size; u++)
61
{
62
if
(state->
pair_uv
[u] == 0)
63
if
(
hk_depth_search
(state, u))
64
state->
matching
++;
65
}
66
67
CHECK_FOR_INTERRUPTS
();
/* just in case */
68
}
69
70
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
BipartiteMatchFree
(
BipartiteMatchState
*
state
)
79
{
80
/* adjacency matrix is treated as owned by the caller */
81
pfree
(state->
pair_uv
);
82
pfree
(state->
pair_vu
);
83
pfree
(state->
distance
);
84
pfree
(state->
queue
);
85
pfree
(state);
86
}
87
88
/*
89
* Perform the breadth-first search step of H-K matching.
90
* Returns true if successful.
91
*/
92
static
bool
93
hk_breadth_search
(
BipartiteMatchState
*
state
)
94
{
95
int
usize = state->
u_size
;
96
short
*queue = state->
queue
;
97
short
*distance = state->
distance
;
98
int
qhead = 0;
/* we never enqueue any node more than once */
99
int
qtail = 0;
/* so don't have to worry about wrapping */
100
int
u;
101
102
distance[0] =
HK_INFINITY
;
103
104
for
(u = 1; u <= usize; u++)
105
{
106
if
(state->
pair_uv
[u] == 0)
107
{
108
distance[u] = 0;
109
queue[qhead++] = u;
110
}
111
else
112
distance[u] =
HK_INFINITY
;
113
}
114
115
while
(qtail < qhead)
116
{
117
u = queue[qtail++];
118
119
if
(distance[u] < distance[0])
120
{
121
short
*u_adj = state->
adjacency
[u];
122
int
i
= u_adj ? u_adj[0] : 0;
123
124
for
(; i > 0; i--)
125
{
126
int
u_next = state->
pair_vu
[u_adj[
i
]];
127
128
if
(distance[u_next] ==
HK_INFINITY
)
129
{
130
distance[u_next] = 1 + distance[u];
131
Assert
(qhead < usize + 2);
132
queue[qhead++] = u_next;
133
}
134
}
135
}
136
}
137
138
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
hk_depth_search
(
BipartiteMatchState
*
state
,
int
u)
147
{
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;
153
short
nextdist;
154
155
if
(u == 0)
156
return
true
;
157
if
(distance[u] ==
HK_INFINITY
)
158
return
false
;
159
nextdist = distance[u] + 1;
160
161
check_stack_depth
();
162
163
for
(; i > 0; i--)
164
{
165
int
v = u_adj[
i
];
166
167
if
(distance[pair_vu[v]] == nextdist)
168
{
169
if
(
hk_depth_search
(state, pair_vu[v]))
170
{
171
pair_vu[v] = u;
172
pair_uv[u] = v;
173
return
true
;
174
}
175
}
176
}
177
178
distance[u] =
HK_INFINITY
;
179
return
false
;
180
}
HK_INFINITY
#define HK_INFINITY
Definition:
bipartite_match.c:29
hk_depth_search
static bool hk_depth_search(BipartiteMatchState *state, int u)
Definition:
bipartite_match.c:146
BipartiteMatchFree
void BipartiteMatchFree(BipartiteMatchState *state)
Definition:
bipartite_match.c:78
pfree
void pfree(void *pointer)
Definition:
mcxt.c:1031
BipartiteMatchState::v_size
int v_size
Definition:
bipartite_match.h:31
ERROR
#define ERROR
Definition:
elog.h:43
miscadmin.h
check_stack_depth
void check_stack_depth(void)
Definition:
postgres.c:3155
hk_breadth_search
static bool hk_breadth_search(BipartiteMatchState *state)
Definition:
bipartite_match.c:93
BipartiteMatchState::adjacency
short ** adjacency
Definition:
bipartite_match.h:32
BipartiteMatchState::queue
short * queue
Definition:
bipartite_match.h:39
BipartiteMatchState::u_size
int u_size
Definition:
bipartite_match.h:30
palloc0
void * palloc0(Size size)
Definition:
mcxt.c:955
postgres.h
BipartiteMatch
BipartiteMatchState * BipartiteMatch(int u_size, int v_size, short **adjacency)
Definition:
bipartite_match.c:39
Assert
#define Assert(condition)
Definition:
c.h:699
state
Definition:
regguts.h:298
BipartiteMatchState::pair_uv
short * pair_uv
Definition:
bipartite_match.h:35
bipartite_match.h
BipartiteMatchState::matching
int matching
Definition:
bipartite_match.h:34
palloc
void * palloc(Size size)
Definition:
mcxt.c:924
BipartiteMatchState
Definition:
bipartite_match.h:27
i
int i
Definition:
preproc-comment.c:23
CHECK_FOR_INTERRUPTS
#define CHECK_FOR_INTERRUPTS()
Definition:
miscadmin.h:98
elog
#define elog
Definition:
elog.h:219
BipartiteMatchState::pair_vu
short * pair_vu
Definition:
bipartite_match.h:36
BipartiteMatchState::distance
short * distance
Definition:
bipartite_match.h:38
src
backend
lib
bipartite_match.c
Generated on Thu Apr 26 2018 00:13:16 for PostgreSQL Source Code by
1.8.13