lemon-project-template-glpk: 33de93886c88 deps/glpk/src/glpapi15.c

lemon-project-template-glpk

view deps/glpk/src/glpapi15.c @ 9:33de93886c88

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

line source

1 /* glpapi15.c (basic graph and network 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"

27 /* CAUTION: DO NOT CHANGE THE LIMITS BELOW */

29 #define NV_MAX 100000000 /* = 100*10^6 */

30 /* maximal number of vertices in the graph */

32 #define NA_MAX 500000000 /* = 500*10^6 */

33 /* maximal number of arcs in the graph */

35 /***********************************************************************

36 * NAME

37 *

38 * glp_create_graph - create graph

39 *

40 * SYNOPSIS

41 *

42 * glp_graph *glp_create_graph(int v_size, int a_size);

43 *

44 * DESCRIPTION

45 *

46 * The routine creates a new graph, which initially is empty, i.e. has

47 * no vertices and arcs.

48 *

49 * The parameter v_size specifies the size of data associated with each

50 * vertex of the graph (0 to 256 bytes).

51 *

52 * The parameter a_size specifies the size of data associated with each

53 * arc of the graph (0 to 256 bytes).

54 *

55 * RETURNS

56 *

57 * The routine returns a pointer to the graph created. */

59 static void create_graph(glp_graph *G, int v_size, int a_size)

60 { G->pool = dmp_create_pool();

61 G->name = NULL;

62 G->nv_max = 50;

63 G->nv = G->na = 0;

64 G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));

65 G->index = NULL;

66 G->v_size = v_size;

67 G->a_size = a_size;

68 return;

69 }

71 glp_graph *glp_create_graph(int v_size, int a_size)

72 { glp_graph *G;

73 if (!(0 <= v_size && v_size <= 256))

74 xerror("glp_create_graph: v_size = %d; invalid size of vertex "

75 "data\n", v_size);

76 if (!(0 <= a_size && a_size <= 256))

77 xerror("glp_create_graph: a_size = %d; invalid size of arc dat"

78 "a\n", a_size);

79 G = xmalloc(sizeof(glp_graph));

80 create_graph(G, v_size, a_size);

81 return G;

82 }

84 /***********************************************************************

85 * NAME

86 *

87 * glp_set_graph_name - assign (change) graph name

88 *

89 * SYNOPSIS

90 *

91 * void glp_set_graph_name(glp_graph *G, const char *name);

92 *

93 * DESCRIPTION

94 *

95 * The routine glp_set_graph_name assigns a symbolic name specified by

96 * the character string name (1 to 255 chars) to the graph.

97 *

98 * If the parameter name is NULL or an empty string, the routine erases

99 * the existing symbolic name of the graph. */

100

101 void glp_set_graph_name(glp_graph *G, const char *name)

102 { if (G->name != NULL)

103 { dmp_free_atom(G->pool, G->name, strlen(G->name)+1);

104 G->name = NULL;

105 }

106 if (!(name == NULL || name[0] == '\0'))

107 { int j;

108 for (j = 0; name[j] != '\0'; j++)

109 { if (j == 256)

110 xerror("glp_set_graph_name: graph name too long\n");

111 if (iscntrl((unsigned char)name[j]))

112 xerror("glp_set_graph_name: graph name contains invalid "

113 "character(s)\n");

114 }

115 G->name = dmp_get_atom(G->pool, strlen(name)+1);

116 strcpy(G->name, name);

117 }

118 return;

119 }

120

121 /***********************************************************************

122 * NAME

123 *

124 * glp_add_vertices - add new vertices to graph

125 *

126 * SYNOPSIS

127 *

128 * int glp_add_vertices(glp_graph *G, int nadd);

129 *

130 * DESCRIPTION

131 *

132 * The routine glp_add_vertices adds nadd vertices to the specified

133 * graph. New vertices are always added to the end of the vertex list,

134 * so ordinal numbers of existing vertices remain unchanged.

135 *

136 * Being added each new vertex is isolated (has no incident arcs).

137 *

138 * RETURNS

139 *

140 * The routine glp_add_vertices returns an ordinal number of the first

141 * new vertex added to the graph. */

142

143 int glp_add_vertices(glp_graph *G, int nadd)

144 { int i, nv_new;

145 if (nadd < 1)

146 xerror("glp_add_vertices: nadd = %d; invalid number of vertice"

147 "s\n", nadd);

148 if (nadd > NV_MAX - G->nv)

149 xerror("glp_add_vertices: nadd = %d; too many vertices\n",

150 nadd);

151 /* determine new number of vertices */

152 nv_new = G->nv + nadd;

153 /* increase the room, if necessary */

154 if (G->nv_max < nv_new)

155 { glp_vertex **save = G->v;

156 while (G->nv_max < nv_new)

157 { G->nv_max += G->nv_max;

158 xassert(G->nv_max > 0);

159 }

160 G->v = xcalloc(1+G->nv_max, sizeof(glp_vertex *));

161 memcpy(&G->v[1], &save[1], G->nv * sizeof(glp_vertex *));

162 xfree(save);

163 }

164 /* add new vertices to the end of the vertex list */

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

166 { glp_vertex *v;

167 G->v[i] = v = dmp_get_atom(G->pool, sizeof(glp_vertex));

168 v->i = i;

169 v->name = NULL;

170 v->entry = NULL;

171 if (G->v_size == 0)

172 v->data = NULL;

173 else

174 { v->data = dmp_get_atom(G->pool, G->v_size);

175 memset(v->data, 0, G->v_size);

176 }

177 v->temp = NULL;

178 v->in = v->out = NULL;

179 }

180 /* set new number of vertices */

181 G->nv = nv_new;

182 /* return the ordinal number of the first vertex added */

183 return nv_new - nadd + 1;

184 }

185

186 /**********************************************************************/

187

188 void glp_set_vertex_name(glp_graph *G, int i, const char *name)

189 { /* assign (change) vertex name */

190 glp_vertex *v;

191 if (!(1 <= i && i <= G->nv))

192 xerror("glp_set_vertex_name: i = %d; vertex number out of rang"

193 "e\n", i);

194 v = G->v[i];

195 if (v->name != NULL)

196 { if (v->entry != NULL)

197 { xassert(G->index != NULL);

198 avl_delete_node(G->index, v->entry);

199 v->entry = NULL;

200 }

201 dmp_free_atom(G->pool, v->name, strlen(v->name)+1);

202 v->name = NULL;

203 }

204 if (!(name == NULL || name[0] == '\0'))

205 { int k;

206 for (k = 0; name[k] != '\0'; k++)

207 { if (k == 256)

208 xerror("glp_set_vertex_name: i = %d; vertex name too lon"

209 "g\n", i);

210 if (iscntrl((unsigned char)name[k]))

211 xerror("glp_set_vertex_name: i = %d; vertex name contain"

212 "s invalid character(s)\n", i);

213 }

214 v->name = dmp_get_atom(G->pool, strlen(name)+1);

215 strcpy(v->name, name);

216 if (G->index != NULL)

217 { xassert(v->entry == NULL);

218 v->entry = avl_insert_node(G->index, v->name);

219 avl_set_node_link(v->entry, v);

220 }

221 }

222 return;

223 }

224

225 /***********************************************************************

226 * NAME

227 *

228 * glp_add_arc - add new arc to graph

229 *

230 * SYNOPSIS

231 *

232 * glp_arc *glp_add_arc(glp_graph *G, int i, int j);

233 *

234 * DESCRIPTION

235 *

236 * The routine glp_add_arc adds a new arc to the specified graph.

237 *

238 * The parameters i and j specify the ordinal numbers of, resp., tail

239 * and head vertices of the arc. Note that self-loops and multiple arcs

240 * are allowed.

241 *

242 * RETURNS

243 *

244 * The routine glp_add_arc returns a pointer to the arc added. */

245

246 glp_arc *glp_add_arc(glp_graph *G, int i, int j)

247 { glp_arc *a;

248 if (!(1 <= i && i <= G->nv))

249 xerror("glp_add_arc: i = %d; tail vertex number out of range\n"

250 , i);

251 if (!(1 <= j && j <= G->nv))

252 xerror("glp_add_arc: j = %d; head vertex number out of range\n"

253 , j);

254 if (G->na == NA_MAX)

255 xerror("glp_add_arc: too many arcs\n");

256 a = dmp_get_atom(G->pool, sizeof(glp_arc));

257 a->tail = G->v[i];

258 a->head = G->v[j];

259 if (G->a_size == 0)

260 a->data = NULL;

261 else

262 { a->data = dmp_get_atom(G->pool, G->a_size);

263 memset(a->data, 0, G->a_size);

264 }

265 a->temp = NULL;

266 a->t_prev = NULL;

267 a->t_next = G->v[i]->out;

268 if (a->t_next != NULL) a->t_next->t_prev = a;

269 a->h_prev = NULL;

270 a->h_next = G->v[j]->in;

271 if (a->h_next != NULL) a->h_next->h_prev = a;

272 G->v[i]->out = G->v[j]->in = a;

273 G->na++;

274 return a;

275 }

276

277 /***********************************************************************

278 * NAME

279 *

280 * glp_del_vertices - delete vertices from graph

281 *

282 * SYNOPSIS

283 *

284 * void glp_del_vertices(glp_graph *G, int ndel, const int num[]);

285 *

286 * DESCRIPTION

287 *

288 * The routine glp_del_vertices deletes vertices along with all

289 * incident arcs from the specified graph. Ordinal numbers of vertices

290 * to be deleted should be placed in locations num[1], ..., num[ndel],

291 * ndel > 0.

292 *

293 * Note that deleting vertices involves changing ordinal numbers of

294 * other vertices remaining in the graph. New ordinal numbers of the

295 * remaining vertices are assigned under the assumption that the

296 * original order of vertices is not changed. */

297

298 void glp_del_vertices(glp_graph *G, int ndel, const int num[])

299 { glp_vertex *v;

300 int i, k, nv_new;

301 /* scan the list of vertices to be deleted */

302 if (!(1 <= ndel && ndel <= G->nv))

303 xerror("glp_del_vertices: ndel = %d; invalid number of vertice"

304 "s\n", ndel);

305 for (k = 1; k <= ndel; k++)

306 { /* take the number of vertex to be deleted */

307 i = num[k];

308 /* obtain pointer to i-th vertex */

309 if (!(1 <= i && i <= G->nv))

310 xerror("glp_del_vertices: num[%d] = %d; vertex number out o"

311 "f range\n", k, i);

312 v = G->v[i];

313 /* check that the vertex is not marked yet */

314 if (v->i == 0)

315 xerror("glp_del_vertices: num[%d] = %d; duplicate vertex nu"

316 "mbers not allowed\n", k, i);

317 /* erase symbolic name assigned to the vertex */

318 glp_set_vertex_name(G, i, NULL);

319 xassert(v->name == NULL);

320 xassert(v->entry == NULL);

321 /* free vertex data, if allocated */

322 if (v->data != NULL)

323 dmp_free_atom(G->pool, v->data, G->v_size);

324 /* delete all incoming arcs */

325 while (v->in != NULL)

326 glp_del_arc(G, v->in);

327 /* delete all outgoing arcs */

328 while (v->out != NULL)

329 glp_del_arc(G, v->out);

330 /* mark the vertex to be deleted */

331 v->i = 0;

332 }

333 /* delete all marked vertices from the vertex list */

334 nv_new = 0;

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

336 { /* obtain pointer to i-th vertex */

337 v = G->v[i];

338 /* check if the vertex is marked */

339 if (v->i == 0)

340 { /* it is marked, delete it */

341 dmp_free_atom(G->pool, v, sizeof(glp_vertex));

342 }

343 else

344 { /* it is not marked, keep it */

345 v->i = ++nv_new;

346 G->v[v->i] = v;

347 }

348 }

349 /* set new number of vertices in the graph */

350 G->nv = nv_new;

351 return;

352 }

353

354 /***********************************************************************

355 * NAME

356 *

357 * glp_del_arc - delete arc from graph

358 *

359 * SYNOPSIS

360 *

361 * void glp_del_arc(glp_graph *G, glp_arc *a);

362 *

363 * DESCRIPTION

364 *

365 * The routine glp_del_arc deletes an arc from the specified graph.

366 * The arc to be deleted must exist. */

367

368 void glp_del_arc(glp_graph *G, glp_arc *a)

369 { /* some sanity checks */

370 xassert(G->na > 0);

371 xassert(1 <= a->tail->i && a->tail->i <= G->nv);

372 xassert(a->tail == G->v[a->tail->i]);

373 xassert(1 <= a->head->i && a->head->i <= G->nv);

374 xassert(a->head == G->v[a->head->i]);

375 /* remove the arc from the list of incoming arcs */

376 if (a->h_prev == NULL)

377 a->head->in = a->h_next;

378 else

379 a->h_prev->h_next = a->h_next;

380 if (a->h_next == NULL)

381 ;

382 else

383 a->h_next->h_prev = a->h_prev;

384 /* remove the arc from the list of outgoing arcs */

385 if (a->t_prev == NULL)

386 a->tail->out = a->t_next;

387 else

388 a->t_prev->t_next = a->t_next;

389 if (a->t_next == NULL)

390 ;

391 else

392 a->t_next->t_prev = a->t_prev;

393 /* free arc data, if allocated */

394 if (a->data != NULL)

395 dmp_free_atom(G->pool, a->data, G->a_size);

396 /* delete the arc from the graph */

397 dmp_free_atom(G->pool, a, sizeof(glp_arc));

398 G->na--;

399 return;

400 }

401

402 /***********************************************************************

403 * NAME

404 *

405 * glp_erase_graph - erase graph content

406 *

407 * SYNOPSIS

408 *

409 * void glp_erase_graph(glp_graph *G, int v_size, int a_size);

410 *

411 * DESCRIPTION

412 *

413 * The routine glp_erase_graph erases the content of the specified

414 * graph. The effect of this operation is the same as if the graph

415 * would be deleted with the routine glp_delete_graph and then created

416 * anew with the routine glp_create_graph, with exception that the

417 * handle (pointer) to the graph remains valid. */

418

419 static void delete_graph(glp_graph *G)

420 { dmp_delete_pool(G->pool);

421 xfree(G->v);

422 if (G->index != NULL) avl_delete_tree(G->index);

423 return;

424 }

425

426 void glp_erase_graph(glp_graph *G, int v_size, int a_size)

427 { if (!(0 <= v_size && v_size <= 256))

428 xerror("glp_erase_graph: v_size = %d; invalid size of vertex d"

429 "ata\n", v_size);

430 if (!(0 <= a_size && a_size <= 256))

431 xerror("glp_erase_graph: a_size = %d; invalid size of arc data"

432 "\n", a_size);

433 delete_graph(G);

434 create_graph(G, v_size, a_size);

435 return;

436 }

437

438 /***********************************************************************

439 * NAME

440 *

441 * glp_delete_graph - delete graph

442 *

443 * SYNOPSIS

444 *

445 * void glp_delete_graph(glp_graph *G);

446 *

447 * DESCRIPTION

448 *

449 * The routine glp_delete_graph deletes the specified graph and frees

450 * all the memory allocated to this program object. */

451

452 void glp_delete_graph(glp_graph *G)

453 { delete_graph(G);

454 xfree(G);

455 return;

456 }

457

458 /**********************************************************************/

459

460 void glp_create_v_index(glp_graph *G)

461 { /* create vertex name index */

462 glp_vertex *v;

463 int i;

464 if (G->index == NULL)

465 { G->index = avl_create_tree(avl_strcmp, NULL);

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

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

468 xassert(v->entry == NULL);

469 if (v->name != NULL)

470 { v->entry = avl_insert_node(G->index, v->name);

471 avl_set_node_link(v->entry, v);

472 }

473 }

474 }

475 return;

476 }

477

478 int glp_find_vertex(glp_graph *G, const char *name)

479 { /* find vertex by its name */

480 AVLNODE *node;

481 int i = 0;

482 if (G->index == NULL)

483 xerror("glp_find_vertex: vertex name index does not exist\n");

484 if (!(name == NULL || name[0] == '\0' || strlen(name) > 255))

485 { node = avl_find_node(G->index, name);

486 if (node != NULL)

487 i = ((glp_vertex *)avl_get_node_link(node))->i;

488 }

489 return i;

490 }

491

492 void glp_delete_v_index(glp_graph *G)

493 { /* delete vertex name index */

494 int i;

495 if (G->index != NULL)

496 { avl_delete_tree(G->index), G->index = NULL;

497 for (i = 1; i <= G->nv; i++) G->v[i]->entry = NULL;

498 }

499 return;

500 }

501

502 /***********************************************************************

503 * NAME

504 *

505 * glp_read_graph - read graph from plain text file

506 *

507 * SYNOPSIS

508 *

509 * int glp_read_graph(glp_graph *G, const char *fname);

510 *

511 * DESCRIPTION

512 *

513 * The routine glp_read_graph reads a graph from a plain text file.

514 *

515 * RETURNS

516 *

517 * If the operation was successful, the routine returns zero. Otherwise

518 * it prints an error message and returns non-zero. */

519

520 int glp_read_graph(glp_graph *G, const char *fname)

521 { glp_data *data;

522 jmp_buf jump;

523 int nv, na, i, j, k, ret;

524 glp_erase_graph(G, G->v_size, G->a_size);

525 xprintf("Reading graph from `%s'...\n", fname);

526 data = glp_sdf_open_file(fname);

527 if (data == NULL)

528 { ret = 1;

529 goto done;

530 }

531 if (setjmp(jump))

532 { ret = 1;

533 goto done;

534 }

535 glp_sdf_set_jump(data, jump);

536 nv = glp_sdf_read_int(data);

537 if (nv < 0)

538 glp_sdf_error(data, "invalid number of vertices\n");

539 na = glp_sdf_read_int(data);

540 if (na < 0)

541 glp_sdf_error(data, "invalid number of arcs\n");

542 xprintf("Graph has %d vert%s and %d arc%s\n",

543 nv, nv == 1 ? "ex" : "ices", na, na == 1 ? "" : "s");

544 if (nv > 0) glp_add_vertices(G, nv);

545 for (k = 1; k <= na; k++)

546 { i = glp_sdf_read_int(data);

547 if (!(1 <= i && i <= nv))

548 glp_sdf_error(data, "tail vertex number out of range\n");

549 j = glp_sdf_read_int(data);

550 if (!(1 <= j && j <= nv))

551 glp_sdf_error(data, "head vertex number out of range\n");

552 glp_add_arc(G, i, j);

553 }

554 xprintf("%d lines were read\n", glp_sdf_line(data));

555 ret = 0;

556 done: if (data != NULL) glp_sdf_close_file(data);

557 return ret;

558 }

559

560 /***********************************************************************

561 * NAME

562 *

563 * glp_write_graph - write graph to plain text file

564 *

565 * SYNOPSIS

566 *

567 * int glp_write_graph(glp_graph *G, const char *fname).

568 *

569 * DESCRIPTION

570 *

571 * The routine glp_write_graph writes the specified graph to a plain

572 * text file.

573 *

574 * RETURNS

575 *

576 * If the operation was successful, the routine returns zero. Otherwise

577 * it prints an error message and returns non-zero. */

578

579 int glp_write_graph(glp_graph *G, const char *fname)

580 { XFILE *fp;

581 glp_vertex *v;

582 glp_arc *a;

583 int i, count, ret;

584 xprintf("Writing graph to `%s'...\n", fname);

585 fp = xfopen(fname, "w"), count = 0;

586 if (fp == NULL)

587 { xprintf("Unable to create `%s' - %s\n", fname, xerrmsg());

588 ret = 1;

589 goto done;

590 }

591 xfprintf(fp, "%d %d\n", G->nv, G->na), count++;

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

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

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

595 xfprintf(fp, "%d %d\n", a->tail->i, a->head->i), count++;

596 }

597 xfflush(fp);

598 if (xferror(fp))

599 { xprintf("Write error on `%s' - %s\n", fname, xerrmsg());

600 ret = 1;

601 goto done;

602 }

603 xprintf("%d lines were written\n", count);

604 ret = 0;

605 done: if (fp != NULL) xfclose(fp);

606 return ret;

607 }

608

609 /* eof */