Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit44ed65a

Browse files
committed
Avoid use of float arithmetic in bipartite_match.c.
Since the distances used in this algorithm are small integers (not morethan the size of the U set, in fact), there is no good reason to use floatarithmetic for them. Use short ints instead: they're smaller, faster, andrequire no special portability assumptions.Per testing by Greg Stark, which disclosed that the code got into aninfinite loop on VAX for lack of IEEE-style float infinities. We don'treally care all that much whether Postgres can run on a VAX anymore,but there seems sufficient reason to change this code anyway.In passing, make a few other small adjustments to make the code matchusual Postgres coding style a bit better.
1 parent5956b7f commit44ed65a

File tree

2 files changed

+55
-36
lines changed

2 files changed

+55
-36
lines changed

‎src/backend/lib/bipartite_match.c‎

Lines changed: 46 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -16,17 +16,20 @@
1616
*/
1717
#include"postgres.h"
1818

19-
#include<float.h>
20-
#include<math.h>
2119
#include<limits.h>
2220

2321
#include"lib/bipartite_match.h"
2422
#include"miscadmin.h"
25-
#include"utils/builtins.h"
2623

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+
#defineHK_INFINITY SHRT_MAX
2730

2831
staticboolhk_breadth_search(BipartiteMatchState*state);
29-
staticboolhk_depth_search(BipartiteMatchState*state,intu,intdepth);
32+
staticboolhk_depth_search(BipartiteMatchState*state,intu);
3033

3134
/*
3235
* Given the size of U and V, where each is indexed 1..size, and an adjacency
@@ -37,26 +40,29 @@ BipartiteMatch(int u_size, int v_size, short **adjacency)
3740
{
3841
BipartiteMatchState*state=palloc(sizeof(BipartiteMatchState));
3942

40-
Assert(u_size<SHRT_MAX);
41-
Assert(v_size<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");
4246

4347
state->u_size=u_size;
4448
state->v_size=v_size;
45-
state->matching=0;
4649
state->adjacency=adjacency;
47-
state->pair_uv=palloc0((u_size+1)*sizeof(short));
48-
state->pair_vu=palloc0((v_size+1)*sizeof(short));
49-
state->distance=palloc((u_size+1)*sizeof(float));
50-
state->queue=palloc((u_size+2)*sizeof(short));
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));
5155

5256
while (hk_breadth_search(state))
5357
{
5458
intu;
5559

56-
for (u=1;u <=u_size;++u)
60+
for (u=1;u <=u_size;u++)
61+
{
5762
if (state->pair_uv[u]==0)
58-
if (hk_depth_search(state,u,1))
63+
if (hk_depth_search(state,u))
5964
state->matching++;
65+
}
6066

6167
CHECK_FOR_INTERRUPTS();/* just in case */
6268
}
@@ -79,27 +85,31 @@ BipartiteMatchFree(BipartiteMatchState *state)
7985
pfree(state);
8086
}
8187

88+
/*
89+
* Perform the breadth-first search step of H-K matching.
90+
* Returns true if successful.
91+
*/
8292
staticbool
8393
hk_breadth_search(BipartiteMatchState*state)
8494
{
8595
intusize=state->u_size;
8696
short*queue=state->queue;
87-
float*distance=state->distance;
97+
short*distance=state->distance;
8898
intqhead=0;/* we never enqueue any node more than once */
8999
intqtail=0;/* so don't have to worry about wrapping */
90100
intu;
91101

92-
distance[0]=get_float4_infinity();
102+
distance[0]=HK_INFINITY;
93103

94-
for (u=1;u <=usize;++u)
104+
for (u=1;u <=usize;u++)
95105
{
96106
if (state->pair_uv[u]==0)
97107
{
98108
distance[u]=0;
99109
queue[qhead++]=u;
100110
}
101111
else
102-
distance[u]=get_float4_infinity();
112+
distance[u]=HK_INFINITY;
103113
}
104114

105115
while (qtail<qhead)
@@ -111,45 +121,52 @@ hk_breadth_search(BipartiteMatchState *state)
111121
short*u_adj=state->adjacency[u];
112122
inti=u_adj ?u_adj[0] :0;
113123

114-
for (;i>0;--i)
124+
for (;i>0;i--)
115125
{
116126
intu_next=state->pair_vu[u_adj[i]];
117127

118-
if (isinf(distance[u_next]))
128+
if (distance[u_next]==HK_INFINITY)
119129
{
120130
distance[u_next]=1+distance[u];
131+
Assert(qhead<usize+2);
121132
queue[qhead++]=u_next;
122-
Assert(qhead <=usize+2);
123133
}
124134
}
125135
}
126136
}
127137

128-
return!isinf(distance[0]);
138+
return (distance[0]!=HK_INFINITY);
129139
}
130140

141+
/*
142+
* Perform the depth-first search step of H-K matching.
143+
* Returns true if successful.
144+
*/
131145
staticbool
132-
hk_depth_search(BipartiteMatchState*state,intu,intdepth)
146+
hk_depth_search(BipartiteMatchState*state,intu)
133147
{
134-
float*distance=state->distance;
148+
short*distance=state->distance;
135149
short*pair_uv=state->pair_uv;
136150
short*pair_vu=state->pair_vu;
137151
short*u_adj=state->adjacency[u];
138152
inti=u_adj ?u_adj[0] :0;
153+
shortnextdist;
139154

140155
if (u==0)
141156
return true;
157+
if (distance[u]==HK_INFINITY)
158+
return false;
159+
nextdist=distance[u]+1;
142160

143-
if ((depth %8)==0)
144-
check_stack_depth();
161+
check_stack_depth();
145162

146-
for (;i>0;--i)
163+
for (;i>0;i--)
147164
{
148165
intv=u_adj[i];
149166

150-
if (distance[pair_vu[v]]==distance[u]+1)
167+
if (distance[pair_vu[v]]==nextdist)
151168
{
152-
if (hk_depth_search(state,pair_vu[v],depth+1))
169+
if (hk_depth_search(state,pair_vu[v]))
153170
{
154171
pair_vu[v]=u;
155172
pair_uv[u]=v;
@@ -158,6 +175,6 @@ hk_depth_search(BipartiteMatchState *state, int u, int depth)
158175
}
159176
}
160177

161-
distance[u]=get_float4_infinity();
178+
distance[u]=HK_INFINITY;
162179
return false;
163180
}

‎src/include/lib/bipartite_match.h‎

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
/*
1212
* Given a bipartite graph consisting of nodes U numbered 1..nU, nodes V
1313
* numbered 1..nV, and an adjacency map of undirected edges in the form
14-
* adjacency[u] = [n, v1, v2, v3, ...vn], we wish to find a "maximum
14+
* adjacency[u] = [k, v1, v2, v3, ...vk], we wish to find a "maximum
1515
* cardinality matching", which is defined as follows: a matching is a subset
1616
* of the original edges such that no node has more than one edge, and a
1717
* matching has maximum cardinality if there exists no other matching with a
@@ -24,21 +24,23 @@
2424
* the problem of planning a collection of grouping sets with the provably
2525
* minimal number of sort operations.
2626
*/
27-
typedefstructbipartite_match_state
27+
typedefstructBipartiteMatchState
2828
{
29+
/* inputs: */
2930
intu_size;/* size of U */
3031
intv_size;/* size of V */
32+
short**adjacency;/* adjacency[u] = [k, v1,v2,v3,...,vk] */
33+
/* outputs: */
3134
intmatching;/* number of edges in matching */
32-
short**adjacency;/* adjacency[u] = [n, v1,v2,v3,...,vn] */
3335
short*pair_uv;/* pair_uv[u] -> v */
3436
short*pair_vu;/* pair_vu[v] -> u */
35-
36-
float*distance;/* distance[u], float so we can have +inf */
37+
/* private state for matching algorithm: */
38+
short*distance;/* distance[u] */
3739
short*queue;/* queue storage for breadth search */
3840
}BipartiteMatchState;
3941

40-
BipartiteMatchState*BipartiteMatch(intu_size,intv_size,short**adjacency);
42+
externBipartiteMatchState*BipartiteMatch(intu_size,intv_size,short**adjacency);
4143

42-
voidBipartiteMatchFree(BipartiteMatchState*state);
44+
externvoidBipartiteMatchFree(BipartiteMatchState*state);
4345

4446
#endif/* BIPARTITE_MATCH_H */

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp