224 class. We use the implicit minimum time map as the length map of the |
224 class. We use the implicit minimum time map as the length map of the |
225 \c Dijkstra algorithm. |
225 \c Dijkstra algorithm. |
226 */ |
226 */ |
227 |
227 |
228 /** |
228 /** |
229 @defgroup matrices Matrices |
|
230 @ingroup datas |
|
231 \brief Two dimensional data storages implemented in LEMON. |
|
232 |
|
233 This group contains two dimensional data storages implemented in LEMON. |
|
234 */ |
|
235 |
|
236 /** |
|
237 @defgroup paths Path Structures |
229 @defgroup paths Path Structures |
238 @ingroup datas |
230 @ingroup datas |
239 \brief %Path structures implemented in LEMON. |
231 \brief %Path structures implemented in LEMON. |
240 |
232 |
241 This group contains the path structures implemented in LEMON. |
233 This group contains the path structures implemented in LEMON. |
244 All of them have similar interfaces and they can be copied easily with |
236 All of them have similar interfaces and they can be copied easily with |
245 assignment operators and copy constructors. This makes it easy and |
237 assignment operators and copy constructors. This makes it easy and |
246 efficient to have e.g. the Dijkstra algorithm to store its result in |
238 efficient to have e.g. the Dijkstra algorithm to store its result in |
247 any kind of path structure. |
239 any kind of path structure. |
248 |
240 |
249 \sa lemon::concepts::Path |
241 \sa \ref concepts::Path "Path concept" |
|
242 */ |
|
243 |
|
244 /** |
|
245 @defgroup heaps Heap Structures |
|
246 @ingroup datas |
|
247 \brief %Heap structures implemented in LEMON. |
|
248 |
|
249 This group contains the heap structures implemented in LEMON. |
|
250 |
|
251 LEMON provides several heap classes. They are efficient implementations |
|
252 of the abstract data type \e priority \e queue. They store items with |
|
253 specified values called \e priorities in such a way that finding and |
|
254 removing the item with minimum priority are efficient. |
|
255 The basic operations are adding and erasing items, changing the priority |
|
256 of an item, etc. |
|
257 |
|
258 Heaps are crucial in several algorithms, such as Dijkstra and Prim. |
|
259 The heap implementations have the same interface, thus any of them can be |
|
260 used easily in such algorithms. |
|
261 |
|
262 \sa \ref concepts::Heap "Heap concept" |
|
263 */ |
|
264 |
|
265 /** |
|
266 @defgroup matrices Matrices |
|
267 @ingroup datas |
|
268 \brief Two dimensional data storages implemented in LEMON. |
|
269 |
|
270 This group contains two dimensional data storages implemented in LEMON. |
250 */ |
271 */ |
251 |
272 |
252 /** |
273 /** |
253 @defgroup auxdat Auxiliary Data Structures |
274 @defgroup auxdat Auxiliary Data Structures |
254 @ingroup datas |
275 @ingroup datas |
257 This group contains some data structures implemented in LEMON in |
278 This group contains some data structures implemented in LEMON in |
258 order to make it easier to implement combinatorial algorithms. |
279 order to make it easier to implement combinatorial algorithms. |
259 */ |
280 */ |
260 |
281 |
261 /** |
282 /** |
|
283 @defgroup geomdat Geometric Data Structures |
|
284 @ingroup auxdat |
|
285 \brief Geometric data structures implemented in LEMON. |
|
286 |
|
287 This group contains geometric data structures implemented in LEMON. |
|
288 |
|
289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional |
|
290 vector with the usual operations. |
|
291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the |
|
292 rectangular bounding box of a set of \ref lemon::dim2::Point |
|
293 "dim2::Point"'s. |
|
294 */ |
|
295 |
|
296 /** |
|
297 @defgroup matrices Matrices |
|
298 @ingroup auxdat |
|
299 \brief Two dimensional data storages implemented in LEMON. |
|
300 |
|
301 This group contains two dimensional data storages implemented in LEMON. |
|
302 */ |
|
303 |
|
304 /** |
262 @defgroup algs Algorithms |
305 @defgroup algs Algorithms |
263 \brief This group contains the several algorithms |
306 \brief This group contains the several algorithms |
264 implemented in LEMON. |
307 implemented in LEMON. |
265 |
308 |
266 This group contains the several algorithms |
309 This group contains the several algorithms |
271 @defgroup search Graph Search |
314 @defgroup search Graph Search |
272 @ingroup algs |
315 @ingroup algs |
273 \brief Common graph search algorithms. |
316 \brief Common graph search algorithms. |
274 |
317 |
275 This group contains the common graph search algorithms, namely |
318 This group contains the common graph search algorithms, namely |
276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). |
319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) |
|
320 \ref clrs01algorithms. |
277 */ |
321 */ |
278 |
322 |
279 /** |
323 /** |
280 @defgroup shortest_path Shortest Path Algorithms |
324 @defgroup shortest_path Shortest Path Algorithms |
281 @ingroup algs |
325 @ingroup algs |
282 \brief Algorithms for finding shortest paths. |
326 \brief Algorithms for finding shortest paths. |
283 |
327 |
284 This group contains the algorithms for finding shortest paths in digraphs. |
328 This group contains the algorithms for finding shortest paths in digraphs |
|
329 \ref clrs01algorithms. |
285 |
330 |
286 - \ref Dijkstra algorithm for finding shortest paths from a source node |
331 - \ref Dijkstra algorithm for finding shortest paths from a source node |
287 when all arc lengths are non-negative. |
332 when all arc lengths are non-negative. |
288 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
333 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
289 from a source node when arc lenghts can be either positive or negative, |
334 from a source node when arc lenghts can be either positive or negative, |
296 - \ref Suurballe A successive shortest path algorithm for finding |
341 - \ref Suurballe A successive shortest path algorithm for finding |
297 arc-disjoint paths between two nodes having minimum total length. |
342 arc-disjoint paths between two nodes having minimum total length. |
298 */ |
343 */ |
299 |
344 |
300 /** |
345 /** |
|
346 @defgroup spantree Minimum Spanning Tree Algorithms |
|
347 @ingroup algs |
|
348 \brief Algorithms for finding minimum cost spanning trees and arborescences. |
|
349 |
|
350 This group contains the algorithms for finding minimum cost spanning |
|
351 trees and arborescences \ref clrs01algorithms. |
|
352 */ |
|
353 |
|
354 /** |
301 @defgroup max_flow Maximum Flow Algorithms |
355 @defgroup max_flow Maximum Flow Algorithms |
302 @ingroup algs |
356 @ingroup algs |
303 \brief Algorithms for finding maximum flows. |
357 \brief Algorithms for finding maximum flows. |
304 |
358 |
305 This group contains the algorithms for finding maximum flows and |
359 This group contains the algorithms for finding maximum flows and |
306 feasible circulations. |
360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows. |
307 |
361 |
308 The \e maximum \e flow \e problem is to find a flow of maximum value between |
362 The \e maximum \e flow \e problem is to find a flow of maximum value between |
309 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ |
363 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ |
310 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and |
364 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and |
311 \f$s, t \in V\f$ source and target nodes. |
365 \f$s, t \in V\f$ source and target nodes. |
316 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) |
370 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) |
317 \quad \forall u\in V\setminus\{s,t\} \f] |
371 \quad \forall u\in V\setminus\{s,t\} \f] |
318 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
372 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
319 |
373 |
320 LEMON contains several algorithms for solving maximum flow problems: |
374 LEMON contains several algorithms for solving maximum flow problems: |
321 - \ref EdmondsKarp Edmonds-Karp algorithm. |
375 - \ref EdmondsKarp Edmonds-Karp algorithm |
322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. |
376 \ref edmondskarp72theoretical. |
323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. |
377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm |
324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. |
378 \ref goldberg88newapproach. |
325 |
379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees |
326 In most cases the \ref Preflow "Preflow" algorithm provides the |
380 \ref dinic70algorithm, \ref sleator83dynamic. |
|
381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees |
|
382 \ref goldberg88newapproach, \ref sleator83dynamic. |
|
383 |
|
384 In most cases the \ref Preflow algorithm provides the |
327 fastest method for computing a maximum flow. All implementations |
385 fastest method for computing a maximum flow. All implementations |
328 also provide functions to query the minimum cut, which is the dual |
386 also provide functions to query the minimum cut, which is the dual |
329 problem of maximum flow. |
387 problem of maximum flow. |
330 |
388 |
331 \ref Circulation is a preflow push-relabel algorithm implemented directly |
389 \ref Circulation is a preflow push-relabel algorithm implemented directly |
339 @ingroup algs |
397 @ingroup algs |
340 |
398 |
341 \brief Algorithms for finding minimum cost flows and circulations. |
399 \brief Algorithms for finding minimum cost flows and circulations. |
342 |
400 |
343 This group contains the algorithms for finding minimum cost flows and |
401 This group contains the algorithms for finding minimum cost flows and |
344 circulations. For more information about this problem and its dual |
402 circulations \ref amo93networkflows. For more information about this |
345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". |
403 problem and its dual solution, see \ref min_cost_flow |
|
404 "Minimum Cost Flow Problem". |
346 |
405 |
347 LEMON contains several algorithms for this problem. |
406 LEMON contains several algorithms for this problem. |
348 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
407 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
349 pivot strategies. |
408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. |
350 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on |
409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on |
351 cost scaling. |
410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, |
|
411 \ref bunnagel98efficient. |
352 - \ref CapacityScaling Successive Shortest %Path algorithm with optional |
412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional |
353 capacity scaling. |
413 capacity scaling \ref edmondskarp72theoretical. |
354 - \ref CancelAndTighten The Cancel and Tighten algorithm. |
414 - \ref CancelAndTighten The Cancel and Tighten algorithm |
355 - \ref CycleCanceling Cycle-Canceling algorithms. |
415 \ref goldberg89cyclecanceling. |
|
416 - \ref CycleCanceling Cycle-Canceling algorithms |
|
417 \ref klein67primal, \ref goldberg89cyclecanceling. |
356 |
418 |
357 In general NetworkSimplex is the most efficient implementation, |
419 In general NetworkSimplex is the most efficient implementation, |
358 but in special cases other algorithms could be faster. |
420 but in special cases other algorithms could be faster. |
359 For example, if the total supply and/or capacities are rather small, |
421 For example, if the total supply and/or capacities are rather small, |
360 CapacityScaling is usually the fastest algorithm (without effective scaling). |
422 CapacityScaling is usually the fastest algorithm (without effective scaling). |
373 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a |
435 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a |
374 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
436 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum |
375 cut is the \f$X\f$ solution of the next optimization problem: |
437 cut is the \f$X\f$ solution of the next optimization problem: |
376 |
438 |
377 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} |
439 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} |
378 \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] |
440 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] |
379 |
441 |
380 LEMON contains several algorithms related to minimum cut problems: |
442 LEMON contains several algorithms related to minimum cut problems: |
381 |
443 |
382 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
444 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
383 in directed graphs. |
445 in directed graphs. |
420 one, though the best known theoretical bound on its running time is |
482 one, though the best known theoretical bound on its running time is |
421 exponential. |
483 exponential. |
422 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
484 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space |
423 O(n<sup>2</sup>+e), but the latter one is typically faster due to the |
485 O(n<sup>2</sup>+e), but the latter one is typically faster due to the |
424 applied early termination scheme. |
486 applied early termination scheme. |
425 */ |
|
426 |
|
427 /** |
|
428 @defgroup graph_properties Connectivity and Other Graph Properties |
|
429 @ingroup algs |
|
430 \brief Algorithms for discovering the graph properties |
|
431 |
|
432 This group contains the algorithms for discovering the graph properties |
|
433 like connectivity, bipartiteness, euler property, simplicity etc. |
|
434 |
|
435 \image html edge_biconnected_components.png |
|
436 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
|
437 */ |
|
438 |
|
439 /** |
|
440 @defgroup planar Planarity Embedding and Drawing |
|
441 @ingroup algs |
|
442 \brief Algorithms for planarity checking, embedding and drawing |
|
443 |
|
444 This group contains the algorithms for planarity checking, |
|
445 embedding and drawing. |
|
446 |
|
447 \image html planar.png |
|
448 \image latex planar.eps "Plane graph" width=\textwidth |
|
449 */ |
487 */ |
450 |
488 |
451 /** |
489 /** |
452 @defgroup matching Matching Algorithms |
490 @defgroup matching Matching Algorithms |
453 @ingroup algs |
491 @ingroup algs |
487 \image html bipartite_matching.png |
525 \image html bipartite_matching.png |
488 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
526 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth |
489 */ |
527 */ |
490 |
528 |
491 /** |
529 /** |
492 @defgroup spantree Minimum Spanning Tree Algorithms |
530 @defgroup graph_properties Connectivity and Other Graph Properties |
493 @ingroup algs |
531 @ingroup algs |
494 \brief Algorithms for finding minimum cost spanning trees and arborescences. |
532 \brief Algorithms for discovering the graph properties |
495 |
533 |
496 This group contains the algorithms for finding minimum cost spanning |
534 This group contains the algorithms for discovering the graph properties |
497 trees and arborescences. |
535 like connectivity, bipartiteness, euler property, simplicity etc. |
|
536 |
|
537 \image html connected_components.png |
|
538 \image latex connected_components.eps "Connected components" width=\textwidth |
|
539 */ |
|
540 |
|
541 /** |
|
542 @defgroup planar Planarity Embedding and Drawing |
|
543 @ingroup algs |
|
544 \brief Algorithms for planarity checking, embedding and drawing |
|
545 |
|
546 This group contains the algorithms for planarity checking, |
|
547 embedding and drawing. |
|
548 |
|
549 \image html planar.png |
|
550 \image latex planar.eps "Plane graph" width=\textwidth |
|
551 */ |
|
552 |
|
553 /** |
|
554 @defgroup approx Approximation Algorithms |
|
555 @ingroup algs |
|
556 \brief Approximation algorithms. |
|
557 |
|
558 This group contains the approximation and heuristic algorithms |
|
559 implemented in LEMON. |
498 */ |
560 */ |
499 |
561 |
500 /** |
562 /** |
501 @defgroup auxalg Auxiliary Algorithms |
563 @defgroup auxalg Auxiliary Algorithms |
502 @ingroup algs |
564 @ingroup algs |
503 \brief Auxiliary algorithms implemented in LEMON. |
565 \brief Auxiliary algorithms implemented in LEMON. |
504 |
566 |
505 This group contains some algorithms implemented in LEMON |
567 This group contains some algorithms implemented in LEMON |
506 in order to make it easier to implement complex algorithms. |
568 in order to make it easier to implement complex algorithms. |
507 */ |
|
508 |
|
509 /** |
|
510 @defgroup approx Approximation Algorithms |
|
511 @ingroup algs |
|
512 \brief Approximation algorithms. |
|
513 |
|
514 This group contains the approximation and heuristic algorithms |
|
515 implemented in LEMON. |
|
516 */ |
569 */ |
517 |
570 |
518 /** |
571 /** |
519 @defgroup gen_opt_group General Optimization Tools |
572 @defgroup gen_opt_group General Optimization Tools |
520 \brief This group contains some general optimization frameworks |
573 \brief This group contains some general optimization frameworks |
523 This group contains some general optimization frameworks |
576 This group contains some general optimization frameworks |
524 implemented in LEMON. |
577 implemented in LEMON. |
525 */ |
578 */ |
526 |
579 |
527 /** |
580 /** |
528 @defgroup lp_group Lp and Mip Solvers |
581 @defgroup lp_group LP and MIP Solvers |
529 @ingroup gen_opt_group |
582 @ingroup gen_opt_group |
530 \brief Lp and Mip solver interfaces for LEMON. |
583 \brief LP and MIP solver interfaces for LEMON. |
531 |
584 |
532 This group contains Lp and Mip solver interfaces for LEMON. The |
585 This group contains LP and MIP solver interfaces for LEMON. |
533 various LP solvers could be used in the same manner with this |
586 Various LP solvers could be used in the same manner with this |
534 interface. |
587 high-level interface. |
|
588 |
|
589 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, |
|
590 \ref cplex, \ref soplex. |
535 */ |
591 */ |
536 |
592 |
537 /** |
593 /** |
538 @defgroup lp_utils Tools for Lp and Mip Solvers |
594 @defgroup lp_utils Tools for Lp and Mip Solvers |
539 @ingroup lp_group |
595 @ingroup lp_group |
619 This group contains general \c EPS drawing methods and special |
675 This group contains general \c EPS drawing methods and special |
620 graph exporting tools. |
676 graph exporting tools. |
621 */ |
677 */ |
622 |
678 |
623 /** |
679 /** |
624 @defgroup dimacs_group DIMACS format |
680 @defgroup dimacs_group DIMACS Format |
625 @ingroup io_group |
681 @ingroup io_group |
626 \brief Read and write files in DIMACS format |
682 \brief Read and write files in DIMACS format |
627 |
683 |
628 Tools to read a digraph from or write it to a file in DIMACS format data. |
684 Tools to read a digraph from or write it to a file in DIMACS format data. |
629 */ |
685 */ |
668 /** |
724 /** |
669 @defgroup graph_concepts Graph Structure Concepts |
725 @defgroup graph_concepts Graph Structure Concepts |
670 @ingroup concept |
726 @ingroup concept |
671 \brief Skeleton and concept checking classes for graph structures |
727 \brief Skeleton and concept checking classes for graph structures |
672 |
728 |
673 This group contains the skeletons and concept checking classes of LEMON's |
729 This group contains the skeletons and concept checking classes of |
674 graph structures and helper classes used to implement these. |
730 graph structures. |
675 */ |
731 */ |
676 |
732 |
677 /** |
733 /** |
678 @defgroup map_concepts Map Concepts |
734 @defgroup map_concepts Map Concepts |
679 @ingroup concept |
735 @ingroup concept |
681 |
737 |
682 This group contains the skeletons and concept checking classes of maps. |
738 This group contains the skeletons and concept checking classes of maps. |
683 */ |
739 */ |
684 |
740 |
685 /** |
741 /** |
|
742 @defgroup tools Standalone Utility Applications |
|
743 |
|
744 Some utility applications are listed here. |
|
745 |
|
746 The standard compilation procedure (<tt>./configure;make</tt>) will compile |
|
747 them, as well. |
|
748 */ |
|
749 |
|
750 /** |
686 \anchor demoprograms |
751 \anchor demoprograms |
687 |
752 |
688 @defgroup demos Demo Programs |
753 @defgroup demos Demo Programs |
689 |
754 |
690 Some demo programs are listed here. Their full source codes can be found in |
755 Some demo programs are listed here. Their full source codes can be found in |