
1 /* * C++ * 

2 * 

3 * This file is a part of LEMON, a generic C++ optimization library 

4 * 

5 * Copyright (C) 20032008 

6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 

7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 

8 * 

9 * Permission to use, modify and distribute this software is granted 

10 * provided that this copyright notice appears in all copies. For 

11 * precise terms see the accompanying LICENSE file. 

12 * 

13 * This software is provided "AS IS" with no warranty of any kind, 

14 * express or implied, and with no claim as to its suitability for any 

15 * purpose. 

16 * 

17 */ 

18 

19 /** 

20 @defgroup datas Data Structures 

21 This group describes the several graph structures implemented in LEMON. 

22 */ 

23 

24 /** 

25 @defgroup graphs Graph Structures 

26 @ingroup datas 

27 \brief Graph structures implemented in LEMON. 

28 

29 The implementation of combinatorial algorithms heavily relies on 

30 efficient graph implementations. LEMON offers data structures which are 

31 planned to be easily used in an experimental phase of implementation studies, 

32 and thereafter the program code can be made efficient by small modifications. 

33 

34 The most efficient implementation of diverse applications require the 

35 usage of different physical graph implementations. These differences 

36 appear in the size of graph we require to handle, memory or time usage 

37 limitations or in the set of operations through which the graph can be 

38 accessed. LEMON provides several physical graph structures to meet 

39 the diverging requirements of the possible users. In order to save on 

40 running time or on memory usage, some structures may fail to provide 

41 some graph features like edge or node deletion. 

42 

43 Alteration of standard containers need a very limited number of 

44 operations, these together satisfy the everyday requirements. 

45 In the case of graph structures, different operations are needed which do 

46 not alter the physical graph, but gives another view. If some nodes or 

47 edges have to be hidden or the reverse oriented graph have to be used, then 

48 this is the case. It also may happen that in a flow implementation 

49 the residual graph can be accessed by another algorithm, or a nodeset 

50 is to be shrunk for another algorithm. 

51 LEMON also provides a variety of graphs for these requirements called 

52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 

53 in conjunction with other graph representation. 

54 

55 You are free to use the graph structure that fit your requirements 

56 the best, most graph algorithms and auxiliary data structures can be used 

57 with any graph structures. 

58 */ 

59 

60 /** 

61 @defgroup semi_adaptors SemiAdaptors Classes for Graphs 

62 @ingroup graphs 

63 \brief Graph types between real graphs and graph adaptors. 

64 

65 Graph types between real graphs and graph adaptors. These classes wrap 

66 graphs to give new functionality as the adaptors do it. On the other 

67 hand they are not lightweight structures as the adaptors. 

68 */ 

69 

70 /** 

71 @defgroup maps Maps 

72 @ingroup datas 

73 \brief Some special purpose map to make life easier. 

74 

75 LEMON provides several special maps that e.g. combine 

76 new maps from existing ones. 

77 */ 

78 

79 /** 

80 @defgroup graph_maps Graph Maps 

81 @ingroup maps 

82 \brief Special GraphRelated Maps. 

83 

84 These maps are specifically designed to assign values to the nodes and edges of 

85 graphs. 

86 */ 

87 

88 

89 /** 

90 \defgroup map_adaptors Map Adaptors 

91 \ingroup maps 

92 \brief Tools to create new maps from existing ones 

93 

94 Map adaptors are used to create "implicit" maps from other maps. 

95 

96 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can 

97 make arithmetic operations between one or two maps (negation, scaling, 

98 addition, multiplication etc.) or e.g. convert a map to another one 

99 of different Value type. 

100 

101 The typical usage of this classes is the passing implicit maps to 

102 algorithms. If a function type algorithm is called then the function 

103 type map adaptors can be used comfortable. For example let's see the 

104 usage of map adaptors with the \c graphToEps() function: 

105 \code 

106 Color nodeColor(int deg) { 

107 if (deg >= 2) { 

108 return Color(0.5, 0.0, 0.5); 

109 } else if (deg == 1) { 

110 return Color(1.0, 0.5, 1.0); 

111 } else { 

112 return Color(0.0, 0.0, 0.0); 

113 } 

114 } 

115 

116 Graph::NodeMap<int> degree_map(graph); 

117 

118 graphToEps(graph, "graph.eps") 

119 .coords(coords).scaleToA4().undirected() 

120 .nodeColors(composeMap(functorMap(nodeColor), degree_map)) 

121 .run(); 

122 \endcode 

123 The \c functorMap() function makes an \c int to \c Color map from the 

124 \e nodeColor() function. The \c composeMap() compose the \e degree_map 

125 and the previous created map. The composed map is proper function to 

126 get color of each node. 

127 

128 The usage with class type algorithms is little bit harder. In this 

129 case the function type map adaptors can not be used, because the 

130 function map adaptors give back temporarly objects. 

131 \code 

132 Graph graph; 

133 

134 typedef Graph::EdgeMap<double> DoubleEdgeMap; 

135 DoubleEdgeMap length(graph); 

136 DoubleEdgeMap speed(graph); 

137 

138 typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap; 

139 

140 TimeMap time(length, speed); 

141 

142 Dijkstra<Graph, TimeMap> dijkstra(graph, time); 

143 dijkstra.run(source, target); 

144 \endcode 

145 

146 We have a length map and a maximum speed map on a graph. The minimum 

147 time to pass the edge can be calculated as the division of the two 

148 maps which can be done implicitly with the \c DivMap template 

149 class. We use the implicit minimum time map as the length map of the 

150 \c Dijkstra algorithm. 

151 */ 

152 

153 /** 

154 @defgroup matrices Matrices 

155 @ingroup datas 

156 \brief Two dimensional data storages. 

157 

158 Two dimensional data storages. 

159 */ 

160 

161 /** 

162 @defgroup paths Path Structures 

163 @ingroup datas 

164 \brief Path structures implemented in LEMON. 

165 

166 LEMON provides flexible data structures 

167 to work with paths. 

168 

169 All of them have similar interfaces, and it can be copied easily with 

170 assignment operator and copy constructor. This make it easy and 

171 efficient to have e.g. the Dijkstra algorithm to store its result in 

172 any kind of path structure. 

173 

174 \sa lemon::concepts::Path 

175 

176 */ 

177 

178 /** 

179 @defgroup auxdat Auxiliary Data Structures 

180 @ingroup datas 

181 \brief Some data structures implemented in LEMON. 

182 

183 This group describes the data structures implemented in LEMON in 

184 order to make it easier to implement combinatorial algorithms. 

185 */ 

186 

187 

188 /** 

189 @defgroup algs Algorithms 

190 \brief This group describes the several algorithms 

191 implemented in LEMON. 

192 

193 This group describes the several algorithms 

194 implemented in LEMON. 

195 */ 

196 

197 /** 

198 @defgroup search Graph Search 

199 @ingroup algs 

200 \brief This group contains the common graph 

201 search algorithms. 

202 

203 This group contains the common graph 

204 search algorithms like Bfs and Dfs. 

205 */ 

206 

207 /** 

208 @defgroup shortest_path Shortest Path algorithms 

209 @ingroup algs 

210 \brief This group describes the algorithms 

211 for finding shortest paths. 

212 

213 This group describes the algorithms for finding shortest paths in 

214 graphs. 

215 

216 */ 

217 

218 /** 

219 @defgroup max_flow Maximum Flow algorithms 

220 @ingroup algs 

221 \brief This group describes the algorithms for finding maximum flows. 

222 

223 This group describes the algorithms for finding maximum flows and 

224 feasible circulations. 

225 

226 The maximum flow problem is to find a flow between a singlesource and 

227 singletarget that is maximum. Formally, there is \f$G=(V,A)\f$ 

228 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity 

229 function and given \f$s, t \in V\f$ source and target node. The 

230 maximum flow is the solution of the next optimization problem: 

231 

232 \f[ 0 \le f_a \le c_a \f] 

233 \f[ \sum_{v\in\delta^{}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \quad u \in V \setminus \{s,t\}\f] 

234 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv}  \sum_{v\in\delta^{}(s)}f_{vu}\f] 

235 

236 The lemon contains several algorithms for solve maximum flow problems: 

237  \ref lemon::EdmondsKarp "EdmondsKarp" 

238  \ref lemon::Preflow "Goldberg's Preflow algorithm" 

239  \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic tree" 

240  \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" 

241 

242 In most cases the \ref lemon::Preflow "preflow" algorithm provides the 

243 fastest method to compute the maximum flow. All impelementations 

244 provides functions for query the minimum cut, which is the dual linear 

245 programming probelm of the maximum flow. 

246 

247 */ 

248 

249 /** 

250 @defgroup min_cost_flow Minimum Cost Flow algorithms 

251 @ingroup algs 

252 

253 \brief This group describes the algorithms 

254 for finding minimum cost flows and circulations. 

255 

256 This group describes the algorithms for finding minimum cost flows and 

257 circulations. 

258 */ 

259 

260 /** 

261 @defgroup min_cut Minimum Cut algorithms 

262 @ingroup algs 

263 

264 \brief This group describes the algorithms for finding minimum cut in 

265 graphs. 

266 

267 This group describes the algorithms for finding minimum cut in graphs. 

268 

269 The minimum cut problem is to find a nonempty and noncomplete 

270 \f$X\f$ subset of the vertices with minimum overall capacity on 

271 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an 

272 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum 

273 cut is the solution of the next optimization problem: 

274 

275 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f] 

276 

277 The lemon contains several algorithms related to minimum cut problems: 

278 

279  \ref lemon::HaoOrlin "HaoOrlin algorithm" for calculate minimum cut 

280 in directed graphs 

281  \ref lemon::NagamochiIbaraki "NagamochiIbaraki algorithm" for 

282 calculate minimum cut in undirected graphs 

283  \ref lemon::GomoryHuTree "GomoryHu tree computation" for calculate all 

284 pairs minimum cut in undirected graphs 

285 

286 If you want to find minimum cut just between two distinict nodes, 

287 please see the \ref max_flow "Maximum Flow page". 

288 

289 */ 

290 

291 /** 

292 @defgroup graph_prop Connectivity and other graph properties 

293 @ingroup algs 

294 \brief This group describes the algorithms 

295 for discover the graph properties 

296 

297 This group describes the algorithms for discover the graph properties 

298 like connectivity, bipartiteness, euler property, simplicity, etc... 

299 

300 \image html edge_biconnected_components.png 

301 \image latex edge_biconnected_components.eps "biedgeconnected components" width=\textwidth 

302 */ 

303 

304 /** 

305 @defgroup planar Planarity embedding and drawing 

306 @ingroup algs 

307 \brief This group contains algorithms for planarity embedding and drawing 

308 

309 This group contains algorithms for planarity checking, embedding and drawing. 

310 

311 \image html planar.png 

312 \image latex planar.eps "Plane graph" width=\textwidth 

313 */ 

314 

315 /** 

316 @defgroup matching Matching algorithms 

317 @ingroup algs 

318 \brief This group describes the algorithms 

319 for find matchings in graphs and bipartite graphs. 

320 

321 This group provides some algorithm objects and function to calculate 

322 matchings in graphs and bipartite graphs. The general matching problem is 

323 finding a subset of the edges which does not shares common endpoints. 

324 

325 There are several different algorithms for calculate matchings in 

326 graphs. The matching problems in bipartite graphs are generally 

327 easier than in general graphs. The goal of the matching optimization 

328 can be the finding maximum cardinality, maximum weight or minimum cost 

329 matching. The search can be constrained to find perfect or 

330 maximum cardinality matching. 

331 

332 Lemon contains the next algorithms: 

333  \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" HopcroftKarp 

334 augmenting path algorithm for calculate maximum cardinality matching in 

335 bipartite graphs 

336  \ref lemon::PrBipartiteMatching "PrBipartiteMatching" PushRelabel 

337 algorithm for calculate maximum cardinality matching in bipartite graphs 

338  \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 

339 Successive shortest path algorithm for calculate maximum weighted matching 

340 and maximum weighted bipartite matching in bipartite graph 

341  \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 

342 Successive shortest path algorithm for calculate minimum cost maximum 

343 matching in bipartite graph 

344  \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm 

345 for calculate maximum cardinality matching in general graph 

346  \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom 

347 shrinking algorithm for calculate maximum weighted matching in general 

348 graph 

349  \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" 

350 Edmond's blossom shrinking algorithm for calculate maximum weighted 

351 perfect matching in general graph 

352 

353 \image html bipartite_matching.png 

354 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 

355 

356 */ 

357 

358 /** 

359 @defgroup spantree Minimum Spanning Tree algorithms 

360 @ingroup algs 

361 \brief This group contains the algorithms for finding a minimum cost spanning 

362 tree in a graph 

363 

364 This group contains the algorithms for finding a minimum cost spanning 

365 tree in a graph 

366 */ 

367 

368 

369 /** 

370 @defgroup auxalg Auxiliary algorithms 

371 @ingroup algs 

372 \brief Some algorithms implemented in LEMON. 

373 

374 This group describes the algorithms in LEMON in order to make 

375 it easier to implement complex algorithms. 

376 */ 

377 

378 /** 

379 @defgroup approx Approximation algorithms 

380 \brief Approximation algorithms 

381 

382 Approximation and heuristic algorithms 

383 */ 

384 

385 /** 

386 @defgroup gen_opt_group General Optimization Tools 

387 \brief This group describes some general optimization frameworks 

388 implemented in LEMON. 

389 

390 This group describes some general optimization frameworks 

391 implemented in LEMON. 

392 

393 */ 

394 

395 /** 

396 @defgroup lp_group Lp and Mip solvers 

397 @ingroup gen_opt_group 

398 \brief Lp and Mip solver interfaces for LEMON. 

399 

400 This group describes Lp and Mip solver interfaces for LEMON. The 

401 various LP solvers could be used in the same manner with this 

402 interface. 

403 

404 */ 

405 

406 /** 

407 @defgroup lp_utils Tools for Lp and Mip solvers 

408 @ingroup lp_group 

409 \brief This group adds some helper tools to the Lp and Mip solvers 

410 implemented in LEMON. 

411 

412 This group adds some helper tools to general optimization framework 

413 implemented in LEMON. 

414 */ 

415 

416 /** 

417 @defgroup metah Metaheuristics 

418 @ingroup gen_opt_group 

419 \brief Metaheuristics for LEMON library. 

420 

421 This group contains some metaheuristic optimization tools. 

422 */ 

423 

424 /** 

425 @defgroup utils Tools and Utilities 

426 \brief Tools and Utilities for Programming in LEMON 

427 

428 Tools and Utilities for Programming in LEMON 

429 */ 

430 

431 /** 

432 @defgroup gutils Basic Graph Utilities 

433 @ingroup utils 

434 \brief This group describes some simple basic graph utilities. 

435 

436 This group describes some simple basic graph utilities. 

437 */ 

438 

439 /** 

440 @defgroup misc Miscellaneous Tools 

441 @ingroup utils 

442 Here you can find several useful tools for development, 

443 debugging and testing. 

444 */ 

445 

446 

447 /** 

448 @defgroup timecount Time measuring and Counting 

449 @ingroup misc 

450 Here you can find simple tools for measuring the performance 

451 of algorithms. 

452 */ 

453 

454 /** 

455 @defgroup graphbits Tools for Graph Implementation 

456 @ingroup utils 

457 \brief Tools to Make It Easier to Make Graphs. 

458 

459 This group describes the tools that makes it easier to make graphs and 

460 the maps that dynamically update with the graph changes. 

461 */ 

462 

463 /** 

464 @defgroup exceptions Exceptions 

465 @ingroup utils 

466 This group contains the exceptions thrown by LEMON library 

467 */ 

468 

469 /** 

470 @defgroup io_group InputOutput 

471 \brief Several Graph InputOutput methods 

472 

473 Here you can find tools for importing and exporting graphs 

474 and graph related data. Now it supports the LEMON format, the 

475 \c DIMACS format and the encapsulated postscript format. 

476 */ 

477 

478 /** 

479 @defgroup lemon_io Lemon InputOutput 

480 @ingroup io_group 

481 \brief Reading and writing LEMON format 

482 

483 Methods for reading and writing LEMON format. More about this 

484 format you can find on the \ref graphiopage "Graph InputOutput" 

485 tutorial pages. 

486 */ 

487 

488 /** 

489 @defgroup section_io Section readers and writers 

490 @ingroup lemon_io 

491 \brief Section readers and writers for lemon InputOutput. 

492 

493 Here you can find which section readers and writers can attach to 

494 the LemonReader and LemonWriter. 

495 */ 

496 

497 /** 

498 @defgroup item_io Item Readers and Writers 

499 @ingroup lemon_io 

500 \brief Item readers and writers for lemon InputOutput. 

501 

502 The InputOutput classes can handle more data type by example 

503 as map or attribute value. Each of these should be written and 

504 read some way. The module make possible to do this. 

505 */ 

506 

507 /** 

508 @defgroup eps_io Postscript exporting 

509 @ingroup io_group 

510 \brief General \c EPS drawer and graph exporter 

511 

512 This group contains general \c EPS drawing methods and special 

513 graph exporting tools. 

514 */ 

515 

516 

517 /** 

518 @defgroup concept Concepts 

519 \brief Skeleton classes and concept checking classes 

520 

521 This group describes the data/algorithm skeletons and concept checking 

522 classes implemented in LEMON. 

523 

524 The purpose of the classes in this group is fourfold. 

525 

526  These classes contain the documentations of the concepts. In order 

527 to avoid document multiplications, an implementation of a concept 

528 simply refers to the corresponding concept class. 

529 

530  These classes declare every functions, <tt>typedef</tt>s etc. an 

531 implementation of the concepts should provide, however completely 

532 without implementations and real data structures behind the 

533 interface. On the other hand they should provide nothing else. All 

534 the algorithms working on a data structure meeting a certain concept 

535 should compile with these classes. (Though it will not run properly, 

536 of course.) In this way it is easily to check if an algorithm 

537 doesn't use any extra feature of a certain implementation. 

538 

539  The concept descriptor classes also provide a <em>checker class</em> 

540 that makes it possible check whether a certain implementation of a 

541 concept indeed provides all the required features. 

542 

543  Finally, They can serve as a skeleton of a new implementation of a concept. 

544 

545 */ 

546 

547 

548 /** 

549 @defgroup graph_concepts Graph Structure Concepts 

550 @ingroup concept 

551 \brief Skeleton and concept checking classes for graph structures 

552 

553 This group contains the skeletons and concept checking classes of LEMON's 

554 graph structures and helper classes used to implement these. 

555 */ 

556 

557 /*  Unused group 

558 @defgroup experimental Experimental Structures and Algorithms 

559 This group contains some Experimental structures and algorithms. 

560 The stuff here is subject to change. 

561 */ 

562 

563 /** 

564 \anchor demoprograms 

565 

566 @defgroup demos Demo programs 

567 

568 Some demo programs are listed here. Their full source codes can be found in 

569 the \c demo subdirectory of the source tree. 

570 

571 The standard compilation procedure (<tt>./configure;make</tt>) will compile 

572 them, as well. 

573 

574 */ 

575 

576 /** 

577 @defgroup tools Standalone utility applications 

578 

579 Some utility applications are listed here. 

580 

581 The standard compilation procedure (<tt>./configure;make</tt>) will compile 

582 them, as well. 

583 

584 */ 

585 