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, 30 Mar 2008 22:16:35 +0100 | |

changeset 119 | 82a2639a05bb |

parent 71 | 9df0fe5e5109 |

child 156 | e561aa7675de |

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

Port time and counter utilities from svn -r3482

The mingw support has been removed

The mingw support has been removed

1 /* -*- C++ -*-

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} \qquad \forall u \in V \setminus \{s,t\}\f]

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

233 LEMON contains several algorithms for solving maximum flow problems:

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

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

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

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

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

240 fastest method to compute the maximum flow. All impelementations

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

242 programming problem of the maximum flow.

244 */

246 /**

247 @defgroup min_cost_flow Minimum Cost Flow algorithms

248 @ingroup algs

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

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

253 circulations.

254 */

256 /**

257 @defgroup min_cut Minimum Cut algorithms

258 @ingroup algs

260 \brief Algorithms for finding minimum cut in graphs.

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

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

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

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

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

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

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

272 LEMON contains several algorithms related to minimum cut problems:

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

275 in directed graphs

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

277 calculate minimum cut in undirected graphs

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

279 pairs minimum cut in undirected graphs

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

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

284 */

286 /**

287 @defgroup graph_prop Connectivity and other graph properties

288 @ingroup algs

289 \brief Algorithms for discovering the graph properties

291 This group describes the algorithms for discovering the graph properties

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

294 \image html edge_biconnected_components.png

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

296 */

298 /**

299 @defgroup planar Planarity embedding and drawing

300 @ingroup algs

301 \brief Algorithms for planarity checking, embedding and drawing

303 This group describes the algorithms for planarity checking, embedding and drawing.

305 \image html planar.png

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

307 */

309 /**

310 @defgroup matching Matching algorithms

311 @ingroup algs

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

314 This group contains algorithm objects and functions to calculate

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

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

318 There are several different algorithms for calculate matchings in

319 graphs. The matching problems in bipartite graphs are generally

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

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

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

323 maximum cardinality matching.

325 Lemon contains the next algorithms:

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

327 augmenting path algorithm for calculate maximum cardinality matching in

328 bipartite graphs

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

330 algorithm for calculate maximum cardinality matching in bipartite graphs

331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"

332 Successive shortest path algorithm for calculate maximum weighted matching

333 and maximum weighted bipartite matching in bipartite graph

334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"

335 Successive shortest path algorithm for calculate minimum cost maximum

336 matching in bipartite graph

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

338 for calculate maximum cardinality matching in general graph

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

340 shrinking algorithm for calculate maximum weighted matching in general

341 graph

342 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"

343 Edmond's blossom shrinking algorithm for calculate maximum weighted

344 perfect matching in general graph

346 \image html bipartite_matching.png

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

349 */

351 /**

352 @defgroup spantree Minimum Spanning Tree algorithms

353 @ingroup algs

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

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

357 tree in a graph

358 */

361 /**

362 @defgroup auxalg Auxiliary algorithms

363 @ingroup algs

364 \brief Auxiliary algorithms implemented in LEMON.

366 This group describes some algorithms implemented in LEMON

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

368 */

370 /**

371 @defgroup approx Approximation algorithms

372 \brief Approximation algorithms.

374 This group describes the approximation and heuristic algorithms

375 implemented in LEMON.

376 */

378 /**

379 @defgroup gen_opt_group General Optimization Tools

380 \brief This group describes some general optimization frameworks

381 implemented in LEMON.

383 This group describes some general optimization frameworks

384 implemented in LEMON.

386 */

388 /**

389 @defgroup lp_group Lp and Mip solvers

390 @ingroup gen_opt_group

391 \brief Lp and Mip solver interfaces for LEMON.

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

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

395 interface.

397 */

399 /**

400 @defgroup lp_utils Tools for Lp and Mip solvers

401 @ingroup lp_group

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

404 This group adds some helper tools to general optimization framework

405 implemented in LEMON.

406 */

408 /**

409 @defgroup metah Metaheuristics

410 @ingroup gen_opt_group

411 \brief Metaheuristics for LEMON library.

413 This group describes some metaheuristic optimization tools.

414 */

416 /**

417 @defgroup utils Tools and Utilities

418 \brief Tools and utilities for programming in LEMON

420 Tools and utilities for programming in LEMON.

421 */

423 /**

424 @defgroup gutils Basic Graph Utilities

425 @ingroup utils

426 \brief Simple basic graph utilities.

428 This group describes some simple basic graph utilities.

429 */

431 /**

432 @defgroup misc Miscellaneous Tools

433 @ingroup utils

434 \brief Tools for development, debugging and testing.

436 This group describes several useful tools for development,

437 debugging and testing.

438 */

440 /**

441 @defgroup timecount Time measuring and Counting

442 @ingroup misc

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

445 This group describes simple tools for measuring the performance

446 of algorithms.

447 */

449 /**

450 @defgroup graphbits Tools for Graph Implementation

451 @ingroup utils

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

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

455 the maps that dynamically update with the graph changes.

456 */

458 /**

459 @defgroup exceptions Exceptions

460 @ingroup utils

461 \brief Exceptions defined in LEMON.

463 This group describes the exceptions defined in LEMON.

464 */

466 /**

467 @defgroup io_group Input-Output

468 \brief Graph Input-Output methods

470 This group describes the tools for importing and exporting graphs

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

472 \c DIMACS format and the encapsulated postscript (EPS) format.

473 */

475 /**

476 @defgroup lemon_io Lemon Input-Output

477 @ingroup io_group

478 \brief Reading and writing LEMON format

480 This group describes methods for reading and writing LEMON format.

481 You can find more about this format on the \ref graph-io-page "Graph Input-Output"

482 tutorial pages.

483 */

485 /**

486 @defgroup section_io Section readers and writers

487 @ingroup lemon_io

488 \brief Section readers and writers for LEMON Input-Output.

490 This group describes section reader and writer classes that can be

491 attached to \ref LemonReader and \ref LemonWriter.

492 */

494 /**

495 @defgroup item_io Item readers and writers

496 @ingroup lemon_io

497 \brief Item readers and writers for LEMON Input-Output.

499 This group describes reader and writer classes for various data types

500 (e.g. map or attribute values). These classes can be attached to

501 \ref LemonReader and \ref LemonWriter.

502 */

504 /**

505 @defgroup eps_io Postscript exporting

506 @ingroup io_group

507 \brief General \c EPS drawer and graph exporter

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

510 graph exporting tools.

511 */

514 /**

515 @defgroup concept Concepts

516 \brief Skeleton classes and concept checking classes

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

519 classes implemented in LEMON.

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

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

524 to avoid document multiplications, an implementation of a concept

525 simply refers to the corresponding concept class.

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

528 implementation of the concepts should provide, however completely

529 without implementations and real data structures behind the

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

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

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

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

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

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

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

538 concept indeed provides all the required features.

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

542 */

545 /**

546 @defgroup graph_concepts Graph Structure Concepts

547 @ingroup concept

548 \brief Skeleton and concept checking classes for graph structures

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

551 graph structures and helper classes used to implement these.

552 */

554 /* --- Unused group

555 @defgroup experimental Experimental Structures and Algorithms

556 This group describes some Experimental structures and algorithms.

557 The stuff here is subject to change.

558 */

560 /**

561 \anchor demoprograms

563 @defgroup demos Demo programs

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

566 the \c demo subdirectory of the source tree.

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

569 build the library.

570 */

572 /**

573 @defgroup tools Standalone utility applications

575 Some utility applications are listed here.

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

578 them, as well.

579 */