summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

doc/groups.dox

author | Alpar Juttner <alpar@cs.elte.hu> |

Sun, 12 Oct 2008 19:57:53 +0100 | |

changeset 320 | 34e185734b42 |

parent 209 | 765619b7cbb2 |

child 236 | da953e387d31 |

permissions | -rw-r--r-- |

AUTHORS file added

1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

2 *

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

4 *

5 * Copyright (C) 2003-2008

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 */

19 /**

20 @defgroup datas Data Structures

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

22 */

24 /**

25 @defgroup graphs Graph Structures

26 @ingroup datas

27 \brief Graph structures implemented in LEMON.

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.

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 arc/edge or node deletion.

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 arcs 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 node-set

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 representations.

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 */

60 /**

61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs

62 @ingroup graphs

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

65 This group describes some graph types between real graphs and graph adaptors.

66 These classes wrap graphs to give new functionality as the adaptors do it.

67 On the other hand they are not light-weight structures as the adaptors.

68 */

70 /**

71 @defgroup maps Maps

72 @ingroup datas

73 \brief Map structures implemented in LEMON.

75 This group describes the map structures implemented in LEMON.

77 LEMON provides several special purpose maps that e.g. combine

78 new maps from existing ones.

79 */

81 /**

82 @defgroup graph_maps Graph Maps

83 @ingroup maps

84 \brief Special graph-related maps.

86 This group describes maps that are specifically designed to assign

87 values to the nodes and arcs of graphs.

88 */

91 /**

92 \defgroup map_adaptors Map Adaptors

93 \ingroup maps

94 \brief Tools to create new maps from existing ones

96 This group describes map adaptors that are used to create "implicit"

97 maps from other maps.

99 Most of them are \ref lemon::concepts::ReadMap "read-only maps".

100 They can make arithmetic and logical operations between one or two maps

101 (negation, shifting, addition, multiplication, logical 'and', 'or',

102 'not' etc.) or e.g. convert a map to another one of different Value type.

104 The typical usage of this classes is passing implicit maps to

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

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

107 usage of map adaptors with the \c digraphToEps() function.

108 \code

109 Color nodeColor(int deg) {

110 if (deg >= 2) {

111 return Color(0.5, 0.0, 0.5);

112 } else if (deg == 1) {

113 return Color(1.0, 0.5, 1.0);

114 } else {

115 return Color(0.0, 0.0, 0.0);

116 }

117 }

119 Digraph::NodeMap<int> degree_map(graph);

121 digraphToEps(graph, "graph.eps")

122 .coords(coords).scaleToA4().undirected()

123 .nodeColors(composeMap(functorToMap(nodeColor), degree_map))

124 .run();

125 \endcode

126 The \c functorToMap() function makes an \c int to \c Color map from the

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

128 and the previously created map. The composed map is a proper function to

129 get the color of each node.

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

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

133 function map adaptors give back temporary objects.

134 \code

135 Digraph graph;

137 typedef Digraph::ArcMap<double> DoubleArcMap;

138 DoubleArcMap length(graph);

139 DoubleArcMap speed(graph);

141 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

142 TimeMap time(length, speed);

144 Dijkstra<Digraph, TimeMap> dijkstra(graph, time);

145 dijkstra.run(source, target);

146 \endcode

147 We have a length map and a maximum speed map on the arcs of a digraph.

148 The minimum time to pass the arc can be calculated as the division of

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

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

151 \c Dijkstra algorithm.

152 */

154 /**

155 @defgroup matrices Matrices

156 @ingroup datas

157 \brief Two dimensional data storages implemented in LEMON.

159 This group describes two dimensional data storages implemented in LEMON.

160 */

162 /**

163 @defgroup paths Path Structures

164 @ingroup datas

165 \brief Path structures implemented in LEMON.

167 This group describes the path structures implemented in LEMON.

169 LEMON provides flexible data structures to work with paths.

170 All of them have similar interfaces and they can be copied easily with

171 assignment operators and copy constructors. This makes it easy and

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

173 any kind of path structure.

175 \sa lemon::concepts::Path

177 */

179 /**

180 @defgroup auxdat Auxiliary Data Structures

181 @ingroup datas

182 \brief Auxiliary data structures implemented in LEMON.

184 This group describes some data structures implemented in LEMON in

185 order to make it easier to implement combinatorial algorithms.

186 */

189 /**

190 @defgroup algs Algorithms

191 \brief This group describes the several algorithms

192 implemented in LEMON.

194 This group describes the several algorithms

195 implemented in LEMON.

196 */

198 /**

199 @defgroup search Graph Search

200 @ingroup algs

201 \brief Common graph search algorithms.

203 This group describes the common graph search algorithms like

204 Breadth-first search (Bfs) and Depth-first search (Dfs).

205 */

207 /**

208 @defgroup shortest_path Shortest Path algorithms

209 @ingroup algs

210 \brief Algorithms for finding shortest paths.

212 This group describes the algorithms for finding shortest paths in graphs.

213 */

215 /**

216 @defgroup max_flow Maximum Flow algorithms

217 @ingroup algs

218 \brief Algorithms for finding maximum flows.

220 This group describes the algorithms for finding maximum flows and

221 feasible circulations.

223 The maximum flow problem is to find a flow between a single source and

224 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$

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

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

227 maximum flow is the \f$f_a\f$ solution of the next optimization problem:

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

230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}

231 \qquad \forall u \in V \setminus \{s,t\}\f]

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

234 LEMON contains several algorithms for solving maximum flow problems:

235 - \ref lemon::EdmondsKarp "Edmonds-Karp"

236 - \ref lemon::Preflow "Goldberg's Preflow algorithm"

237 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

238 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

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

241 fastest method to compute the maximum flow. All impelementations

242 provides functions to query the minimum cut, which is the dual linear

243 programming problem of the maximum flow.

245 */

247 /**

248 @defgroup min_cost_flow Minimum Cost Flow algorithms

249 @ingroup algs

251 \brief Algorithms for finding minimum cost flows and circulations.

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

254 circulations.

255 */

257 /**

258 @defgroup min_cut Minimum Cut algorithms

259 @ingroup algs

261 \brief Algorithms for finding minimum cut in graphs.

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

265 The minimum cut problem is to find a non-empty and non-complete

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

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

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

269 cut is the \f$X\f$ solution of the next optimization problem:

271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}

272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]

274 LEMON contains several algorithms related to minimum cut problems:

276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut

277 in directed graphs

278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to

279 calculate minimum cut in undirected graphs

280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all

281 pairs minimum cut in undirected graphs

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

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

286 */

288 /**

289 @defgroup graph_prop Connectivity and other graph properties

290 @ingroup algs

291 \brief Algorithms for discovering the graph properties

293 This group describes the algorithms for discovering the graph properties

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

296 \image html edge_biconnected_components.png

297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

298 */

300 /**

301 @defgroup planar Planarity embedding and drawing

302 @ingroup algs

303 \brief Algorithms for planarity checking, embedding and drawing

305 This group describes the algorithms for planarity checking,

306 embedding and drawing.

308 \image html planar.png

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

310 */

312 /**

313 @defgroup matching Matching algorithms

314 @ingroup algs

315 \brief Algorithms for finding matchings in graphs and bipartite graphs.

317 This group contains algorithm objects and functions to calculate

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

319 finding a subset of the arcs which does not shares common endpoints.

321 There are several different algorithms for calculate matchings in

322 graphs. The matching problems in bipartite graphs are generally

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

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

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

326 maximum cardinality matching.

328 Lemon contains the next algorithms:

329 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp

330 augmenting path algorithm for calculate maximum cardinality matching in

331 bipartite graphs

332 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel

333 algorithm for calculate maximum cardinality matching in bipartite graphs

334 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"

335 Successive shortest path algorithm for calculate maximum weighted matching

336 and maximum weighted bipartite matching in bipartite graph

337 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"

338 Successive shortest path algorithm for calculate minimum cost maximum

339 matching in bipartite graph

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

341 for calculate maximum cardinality matching in general graph

342 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom

343 shrinking algorithm for calculate maximum weighted matching in general

344 graph

345 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"

346 Edmond's blossom shrinking algorithm for calculate maximum weighted

347 perfect matching in general graph

349 \image html bipartite_matching.png

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

352 */

354 /**

355 @defgroup spantree Minimum Spanning Tree algorithms

356 @ingroup algs

357 \brief Algorithms for finding a minimum cost spanning tree in a graph.

359 This group describes the algorithms for finding a minimum cost spanning

360 tree in a graph

361 */

364 /**

365 @defgroup auxalg Auxiliary algorithms

366 @ingroup algs

367 \brief Auxiliary algorithms implemented in LEMON.

369 This group describes some algorithms implemented in LEMON

370 in order to make it easier to implement complex algorithms.

371 */

373 /**

374 @defgroup approx Approximation algorithms

375 \brief Approximation algorithms.

377 This group describes the approximation and heuristic algorithms

378 implemented in LEMON.

379 */

381 /**

382 @defgroup gen_opt_group General Optimization Tools

383 \brief This group describes some general optimization frameworks

384 implemented in LEMON.

386 This group describes some general optimization frameworks

387 implemented in LEMON.

389 */

391 /**

392 @defgroup lp_group Lp and Mip solvers

393 @ingroup gen_opt_group

394 \brief Lp and Mip solver interfaces for LEMON.

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

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

398 interface.

400 */

402 /**

403 @defgroup lp_utils Tools for Lp and Mip solvers

404 @ingroup lp_group

405 \brief Helper tools to the Lp and Mip solvers.

407 This group adds some helper tools to general optimization framework

408 implemented in LEMON.

409 */

411 /**

412 @defgroup metah Metaheuristics

413 @ingroup gen_opt_group

414 \brief Metaheuristics for LEMON library.

416 This group describes some metaheuristic optimization tools.

417 */

419 /**

420 @defgroup utils Tools and Utilities

421 \brief Tools and utilities for programming in LEMON

423 Tools and utilities for programming in LEMON.

424 */

426 /**

427 @defgroup gutils Basic Graph Utilities

428 @ingroup utils

429 \brief Simple basic graph utilities.

431 This group describes some simple basic graph utilities.

432 */

434 /**

435 @defgroup misc Miscellaneous Tools

436 @ingroup utils

437 \brief Tools for development, debugging and testing.

439 This group describes several useful tools for development,

440 debugging and testing.

441 */

443 /**

444 @defgroup timecount Time measuring and Counting

445 @ingroup misc

446 \brief Simple tools for measuring the performance of algorithms.

448 This group describes simple tools for measuring the performance

449 of algorithms.

450 */

452 /**

453 @defgroup graphbits Tools for Graph Implementation

454 @ingroup utils

455 \brief Tools to make it easier to create graphs.

457 This group describes the tools that makes it easier to create graphs and

458 the maps that dynamically update with the graph changes.

459 */

461 /**

462 @defgroup exceptions Exceptions

463 @ingroup utils

464 \brief Exceptions defined in LEMON.

466 This group describes the exceptions defined in LEMON.

467 */

469 /**

470 @defgroup io_group Input-Output

471 \brief Graph Input-Output methods

473 This group describes the 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 (EPS) format.

476 */

478 /**

479 @defgroup lemon_io Lemon Input-Output

480 @ingroup io_group

481 \brief Reading and writing \ref lgf-format "Lemon Graph Format".

483 This group describes methods for reading and writing

484 \ref lgf-format "Lemon Graph Format".

485 */

487 /**

488 @defgroup eps_io Postscript exporting

489 @ingroup io_group

490 \brief General \c EPS drawer and graph exporter

492 This group describes general \c EPS drawing methods and special

493 graph exporting tools.

494 */

497 /**

498 @defgroup concept Concepts

499 \brief Skeleton classes and concept checking classes

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

502 classes implemented in LEMON.

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

506 - These classes contain the documentations of the concepts. In order

507 to avoid document multiplications, an implementation of a concept

508 simply refers to the corresponding concept class.

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

511 implementation of the concepts should provide, however completely

512 without implementations and real data structures behind the

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

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

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

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

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

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

520 that makes it possible to check whether a certain implementation of a

521 concept indeed provides all the required features.

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

525 */

528 /**

529 @defgroup graph_concepts Graph Structure Concepts

530 @ingroup concept

531 \brief Skeleton and concept checking classes for graph structures

533 This group describes the skeletons and concept checking classes of LEMON's

534 graph structures and helper classes used to implement these.

535 */

537 /* --- Unused group

538 @defgroup experimental Experimental Structures and Algorithms

539 This group describes some Experimental structures and algorithms.

540 The stuff here is subject to change.

541 */

543 /**

544 \anchor demoprograms

546 @defgroup demos Demo programs

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

549 the \c demo subdirectory of the source tree.

551 It order to compile them, use <tt>--enable-demo</tt> configure option when

552 build the library.

553 */

555 /**

556 @defgroup tools Standalone utility applications

558 Some utility applications are listed here.

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

561 them, as well.

562 */