lemon-project-template-glpk: 4fc6ad2fb8a6 deps/glpk/src/glpapi16.c

lemon-project-template-glpk

view deps/glpk/src/glpapi16.c @ 11:4fc6ad2fb8a6

Test GLPK in src/main.cc

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 21:43:29 +0100
parents
children

line source

1 /* glpapi16.c (graph and network analysis routines) */

3 /***********************************************************************

4 * This code is part of GLPK (GNU Linear Programming Kit).

5 *

7 * 2009, 2010, 2011 Andrew Makhorin, Department for Applied Informatics,

9 * E-mail: <mao@gnu.org>.

10 *

11 * GLPK is free software: you can redistribute it and/or modify it

12 * under the terms of the GNU General Public License as published by

13 * the Free Software Foundation, either version 3 of the License, or

14 * (at your option) any later version.

15 *

16 * GLPK is distributed in the hope that it will be useful, but WITHOUT

17 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

18 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

19 * License for more details.

20 *

21 * You should have received a copy of the GNU General Public License

22 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.

23 ***********************************************************************/

25 #include "glpapi.h"

26 #include "glpnet.h"

28 /***********************************************************************

29 * NAME

30 *

31 * glp_weak_comp - find all weakly connected components of graph

32 *

33 * SYNOPSIS

34 *

35 * int glp_weak_comp(glp_graph *G, int v_num);

36 *

37 * DESCRIPTION

38 *

39 * The routine glp_weak_comp finds all weakly connected components of

40 * the specified graph.

41 *

42 * The parameter v_num specifies an offset of the field of type int

43 * in the vertex data block, to which the routine stores the number of

44 * a (weakly) connected component containing that vertex. If v_num < 0,

45 * no component numbers are stored.

46 *

47 * The components are numbered in arbitrary order from 1 to nc, where

48 * nc is the total number of components found, 0 <= nc <= |V|.

49 *

50 * RETURNS

51 *

52 * The routine returns nc, the total number of components found. */

54 int glp_weak_comp(glp_graph *G, int v_num)

55 { glp_vertex *v;

56 glp_arc *a;

57 int f, i, j, nc, nv, pos1, pos2, *prev, *next, *list;

58 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))

59 xerror("glp_weak_comp: v_num = %d; invalid offset\n", v_num);

60 nv = G->nv;

61 if (nv == 0)

62 { nc = 0;

63 goto done;

64 }

65 /* allocate working arrays */

66 prev = xcalloc(1+nv, sizeof(int));

67 next = xcalloc(1+nv, sizeof(int));

68 list = xcalloc(1+nv, sizeof(int));

69 /* if vertex i is unlabelled, prev[i] is the index of previous

70 unlabelled vertex, and next[i] is the index of next unlabelled

71 vertex; if vertex i is labelled, then prev[i] < 0, and next[i]

72 is the connected component number */

73 /* initially all vertices are unlabelled */

74 f = 1;

75 for (i = 1; i <= nv; i++)

76 prev[i] = i - 1, next[i] = i + 1;

77 next[nv] = 0;

78 /* main loop (until all vertices have been labelled) */

79 nc = 0;

80 while (f != 0)

81 { /* take an unlabelled vertex */

82 i = f;

83 /* and remove it from the list of unlabelled vertices */

84 f = next[i];

85 if (f != 0) prev[f] = 0;

86 /* label the vertex; it begins a new component */

87 prev[i] = -1, next[i] = ++nc;

88 /* breadth first search */

89 list[1] = i, pos1 = pos2 = 1;

90 while (pos1 <= pos2)

91 { /* dequeue vertex i */

92 i = list[pos1++];

93 /* consider all arcs incoming to vertex i */

94 for (a = G->v[i]->in; a != NULL; a = a->h_next)

95 { /* vertex j is adjacent to vertex i */

96 j = a->tail->i;

97 if (prev[j] >= 0)

98 { /* vertex j is unlabelled */

99 /* remove it from the list of unlabelled vertices */

100 if (prev[j] == 0)

101 f = next[j];

102 else

103 next[prev[j]] = next[j];

104 if (next[j] == 0)

105 ;

106 else

107 prev[next[j]] = prev[j];

108 /* label the vertex */

109 prev[j] = -1, next[j] = nc;

110 /* and enqueue it for further consideration */

111 list[++pos2] = j;

112 }

113 }

114 /* consider all arcs outgoing from vertex i */

115 for (a = G->v[i]->out; a != NULL; a = a->t_next)

116 { /* vertex j is adjacent to vertex i */

117 j = a->head->i;

118 if (prev[j] >= 0)

119 { /* vertex j is unlabelled */

120 /* remove it from the list of unlabelled vertices */

121 if (prev[j] == 0)

122 f = next[j];

123 else

124 next[prev[j]] = next[j];

125 if (next[j] == 0)

126 ;

127 else

128 prev[next[j]] = prev[j];

129 /* label the vertex */

130 prev[j] = -1, next[j] = nc;

131 /* and enqueue it for further consideration */

132 list[++pos2] = j;

133 }

134 }

135 }

136 }

137 /* store component numbers */

138 if (v_num >= 0)

139 { for (i = 1; i <= nv; i++)

140 { v = G->v[i];

141 memcpy((char *)v->data + v_num, &next[i], sizeof(int));

142 }

143 }

144 /* free working arrays */

145 xfree(prev);

146 xfree(next);

147 xfree(list);

148 done: return nc;

149 }

150

151 /***********************************************************************

152 * NAME

153 *

154 * glp_strong_comp - find all strongly connected components of graph

155 *

156 * SYNOPSIS

157 *

158 * int glp_strong_comp(glp_graph *G, int v_num);

159 *

160 * DESCRIPTION

161 *

162 * The routine glp_strong_comp finds all strongly connected components

163 * of the specified graph.

164 *

165 * The parameter v_num specifies an offset of the field of type int

166 * in the vertex data block, to which the routine stores the number of

167 * a strongly connected component containing that vertex. If v_num < 0,

168 * no component numbers are stored.

169 *

170 * The components are numbered in arbitrary order from 1 to nc, where

171 * nc is the total number of components found, 0 <= nc <= |V|. However,

172 * the component numbering has the property that for every arc (i->j)

173 * in the graph the condition num(i) >= num(j) holds.

174 *

175 * RETURNS

176 *

177 * The routine returns nc, the total number of components found. */

178

179 int glp_strong_comp(glp_graph *G, int v_num)

180 { glp_vertex *v;

181 glp_arc *a;

182 int i, k, last, n, na, nc, *icn, *ip, *lenr, *ior, *ib, *lowl,

183 *numb, *prev;

184 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))

185 xerror("glp_strong_comp: v_num = %d; invalid offset\n",

186 v_num);

187 n = G->nv;

188 if (n == 0)

189 { nc = 0;

190 goto done;

191 }

192 na = G->na;

193 icn = xcalloc(1+na, sizeof(int));

194 ip = xcalloc(1+n, sizeof(int));

195 lenr = xcalloc(1+n, sizeof(int));

196 ior = xcalloc(1+n, sizeof(int));

197 ib = xcalloc(1+n, sizeof(int));

198 lowl = xcalloc(1+n, sizeof(int));

199 numb = xcalloc(1+n, sizeof(int));

200 prev = xcalloc(1+n, sizeof(int));

201 k = 1;

202 for (i = 1; i <= n; i++)

203 { v = G->v[i];

204 ip[i] = k;

205 for (a = v->out; a != NULL; a = a->t_next)

206 icn[k++] = a->head->i;

207 lenr[i] = k - ip[i];

208 }

209 xassert(na == k-1);

210 nc = mc13d(n, icn, ip, lenr, ior, ib, lowl, numb, prev);

211 if (v_num >= 0)

212 { xassert(ib[1] == 1);

213 for (k = 1; k <= nc; k++)

214 { last = (k < nc ? ib[k+1] : n+1);

215 xassert(ib[k] < last);

216 for (i = ib[k]; i < last; i++)

217 { v = G->v[ior[i]];

218 memcpy((char *)v->data + v_num, &k, sizeof(int));

219 }

220 }

221 }

222 xfree(icn);

223 xfree(ip);

224 xfree(lenr);

225 xfree(ior);

226 xfree(ib);

227 xfree(lowl);

228 xfree(numb);

229 xfree(prev);

230 done: return nc;

231 }

232

233 /***********************************************************************

234 * NAME

235 *

236 * glp_top_sort - topological sorting of acyclic digraph

237 *

238 * SYNOPSIS

239 *

240 * int glp_top_sort(glp_graph *G, int v_num);

241 *

242 * DESCRIPTION

243 *

244 * The routine glp_top_sort performs topological sorting of vertices of

245 * the specified acyclic digraph.

246 *

247 * The parameter v_num specifies an offset of the field of type int in

248 * the vertex data block, to which the routine stores the vertex number

249 * assigned. If v_num < 0, vertex numbers are not stored.

250 *

251 * The vertices are numbered from 1 to n, where n is the total number

252 * of vertices in the graph. The vertex numbering has the property that

253 * for every arc (i->j) in the graph the condition num(i) < num(j)

254 * holds. Special case num(i) = 0 means that vertex i is not assigned a

255 * number, because the graph is *not* acyclic.

256 *

257 * RETURNS

258 *

259 * If the graph is acyclic and therefore all the vertices have been

260 * assigned numbers, the routine glp_top_sort returns zero. Otherwise,

261 * if the graph is not acyclic, the routine returns the number of

262 * vertices which have not been numbered, i.e. for which num(i) = 0. */

263

264 static int top_sort(glp_graph *G, int num[])

265 { glp_arc *a;

266 int i, j, cnt, top, *stack, *indeg;

267 /* allocate working arrays */

268 indeg = xcalloc(1+G->nv, sizeof(int));

269 stack = xcalloc(1+G->nv, sizeof(int));

270 /* determine initial indegree of each vertex; push into the stack

271 the vertices having zero indegree */

272 top = 0;

273 for (i = 1; i <= G->nv; i++)

274 { num[i] = indeg[i] = 0;

275 for (a = G->v[i]->in; a != NULL; a = a->h_next)

276 indeg[i]++;

277 if (indeg[i] == 0)

278 stack[++top] = i;

279 }

280 /* assign numbers to vertices in the sorted order */

281 cnt = 0;

282 while (top > 0)

283 { /* pull vertex i from the stack */

284 i = stack[top--];

285 /* it has zero indegree in the current graph */

286 xassert(indeg[i] == 0);

287 /* so assign it a next number */

288 xassert(num[i] == 0);

289 num[i] = ++cnt;

290 /* remove vertex i from the current graph, update indegree of

291 its adjacent vertices, and push into the stack new vertices

292 whose indegree becomes zero */

293 for (a = G->v[i]->out; a != NULL; a = a->t_next)

294 { j = a->head->i;

295 /* there exists arc (i->j) in the graph */

296 xassert(indeg[j] > 0);

297 indeg[j]--;

298 if (indeg[j] == 0)

299 stack[++top] = j;

300 }

301 }

302 /* free working arrays */

303 xfree(indeg);

304 xfree(stack);

305 return G->nv - cnt;

306 }

307

308 int glp_top_sort(glp_graph *G, int v_num)

309 { glp_vertex *v;

310 int i, cnt, *num;

311 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))

312 xerror("glp_top_sort: v_num = %d; invalid offset\n", v_num);

313 if (G->nv == 0)

314 { cnt = 0;

315 goto done;

316 }

317 num = xcalloc(1+G->nv, sizeof(int));

318 cnt = top_sort(G, num);

319 if (v_num >= 0)

320 { for (i = 1; i <= G->nv; i++)

321 { v = G->v[i];

322 memcpy((char *)v->data + v_num, &num[i], sizeof(int));

323 }

324 }

325 xfree(num);

326 done: return cnt;

327 }

328

329 /* eof */