PostgreSQL Source Code: src/backend/lib/bipartite_match.c Source File (original) (raw)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

18

19#include <limits.h>

20

23

24

25

26

27

28

29#define HK_INFINITY SHRT_MAX

30

33

34

35

36

37

40{

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

57 {

58 int u;

59

60 for (u = 1; u <= u_size; u++)

61 {

62 if (state->pair_uv[u] == 0)

64 state->matching++;

65 }

66

68 }

69

71}

72

73

74

75

76

77void

79{

80

86}

87

88

89

90

91

92static bool

94{

95 int usize = state->u_size;

96 short *queue = state->queue;

97 short *distance = state->distance;

98 int qhead = 0;

99 int qtail = 0;

100 int u;

101

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

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

129 {

130 distance[u_next] = 1 + distance[u];

131 Assert(qhead < usize + 2);

132 queue[qhead++] = u_next;

133 }

134 }

135 }

136 }

137

139}

140

141

142

143

144

145static bool

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;

158 return false;

159 nextdist = distance[u] + 1;

160

162

163 for (; i > 0; i--)

164 {

165 int v = u_adj[i];

166

167 if (distance[pair_vu[v]] == nextdist)

168 {

170 {

171 pair_vu[v] = u;

172 pair_uv[u] = v;

173 return true;

174 }

175 }

176 }

177

179 return false;

180}

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

static bool hk_depth_search(BipartiteMatchState *state, int u)

void BipartiteMatchFree(BipartiteMatchState *state)

static bool hk_breadth_search(BipartiteMatchState *state)

Assert(PointerIsAligned(start, uint64))

void pfree(void *pointer)

void * palloc0(Size size)

#define CHECK_FOR_INTERRUPTS()

void check_stack_depth(void)