234 class. We use the implicit minimum time map as the length map of the |
234 class. We use the implicit minimum time map as the length map of the |
235 \c Dijkstra algorithm. |
235 \c Dijkstra algorithm. |
236 */ |
236 */ |
237 |
237 |
238 /** |
238 /** |
239 @defgroup matrices Matrices |
|
240 @ingroup datas |
|
241 \brief Two dimensional data storages implemented in LEMON. |
|
242 |
|
243 This group contains two dimensional data storages implemented in LEMON. |
|
244 */ |
|
245 |
|
246 /** |
|
247 @defgroup paths Path Structures |
239 @defgroup paths Path Structures |
248 @ingroup datas |
240 @ingroup datas |
249 \brief %Path structures implemented in LEMON. |
241 \brief %Path structures implemented in LEMON. |
250 |
242 |
251 This group contains the path structures implemented in LEMON. |
243 This group contains the path structures implemented in LEMON. |
291 @ingroup algs |
283 @ingroup algs |
292 \brief Algorithms for finding shortest paths. |
284 \brief Algorithms for finding shortest paths. |
293 |
285 |
294 This group contains the algorithms for finding shortest paths in digraphs. |
286 This group contains the algorithms for finding shortest paths in digraphs. |
295 |
287 |
296 - \ref Dijkstra algorithm for finding shortest paths from a source node |
288 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a |
297 when all arc lengths are non-negative. |
289 source node when all arc lengths are non-negative. |
298 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths |
|
299 from a source node when arc lenghts can be either positive or negative, |
|
300 but the digraph should not contain directed cycles with negative total |
|
301 length. |
|
302 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms |
|
303 for solving the \e all-pairs \e shortest \e paths \e problem when arc |
|
304 lenghts can be either positive or negative, but the digraph should |
|
305 not contain directed cycles with negative total length. |
|
306 - \ref Suurballe A successive shortest path algorithm for finding |
290 - \ref Suurballe A successive shortest path algorithm for finding |
307 arc-disjoint paths between two nodes having minimum total length. |
291 arc-disjoint paths between two nodes having minimum total length. |
308 */ |
292 */ |
309 |
293 |
310 /** |
294 /** |
325 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] |
309 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] |
326 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) |
310 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) |
327 \quad \forall u\in V\setminus\{s,t\} \f] |
311 \quad \forall u\in V\setminus\{s,t\} \f] |
328 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
312 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] |
329 |
313 |
330 LEMON contains several algorithms for solving maximum flow problems: |
314 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and |
331 - \ref EdmondsKarp Edmonds-Karp algorithm. |
315 Tarjan for solving this problem. It also provides functions to query the |
332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. |
316 minimum cut, which is the dual problem of maximum flow. |
333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. |
317 |
334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. |
318 \ref Circulation is a preflow push-relabel algorithm implemented directly |
335 |
319 for finding feasible circulations, which is a somewhat different problem, |
336 In most cases the \ref Preflow "Preflow" algorithm provides the |
320 but it is strongly related to maximum flow. |
337 fastest method for computing a maximum flow. All implementations |
321 For more information, see \ref Circulation. |
338 provides functions to also query the minimum cut, which is the dual |
|
339 problem of the maximum flow. |
|
340 */ |
322 */ |
341 |
323 |
342 /** |
324 /** |
343 @defgroup min_cost_flow Minimum Cost Flow Algorithms |
325 @defgroup min_cost_flow Minimum Cost Flow Algorithms |
344 @ingroup algs |
326 @ingroup algs |
419 |
401 |
420 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc |
402 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc |
421 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. |
403 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e. |
422 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] |
404 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f] |
423 |
405 |
424 All algorithms provide dual solution (node potentials) as well, |
406 \ref NetworkSimplex is an efficient implementation of the primal Network |
425 if an optimal flow is found. |
407 Simplex algorithm for finding minimum cost flows. It also provides dual |
426 |
408 solution (node potentials), if an optimal flow is found. |
427 LEMON contains several algorithms for solving minimum cost flow problems. |
|
428 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
|
429 pivot strategies. |
|
430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on |
|
431 cost scaling. |
|
432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional |
|
433 capacity scaling. |
|
434 - \ref CancelAndTighten The Cancel and Tighten algorithm. |
|
435 - \ref CycleCanceling Cycle-Canceling algorithms. |
|
436 |
|
437 Most of these implementations support the general inequality form of the |
|
438 minimum cost flow problem, but CancelAndTighten and CycleCanceling |
|
439 only support the equality form due to the primal method they use. |
|
440 |
|
441 In general NetworkSimplex is the most efficient implementation, |
|
442 but in special cases other algorithms could be faster. |
|
443 For example, if the total supply and/or capacities are rather small, |
|
444 CapacityScaling is usually the fastest algorithm (without effective scaling). |
|
445 */ |
409 */ |
446 |
410 |
447 /** |
411 /** |
448 @defgroup min_cut Minimum Cut Algorithms |
412 @defgroup min_cut Minimum Cut Algorithms |
449 @ingroup algs |
413 @ingroup algs |
463 |
427 |
464 LEMON contains several algorithms related to minimum cut problems: |
428 LEMON contains several algorithms related to minimum cut problems: |
465 |
429 |
466 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
430 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut |
467 in directed graphs. |
431 in directed graphs. |
468 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for |
|
469 calculating minimum cut in undirected graphs. |
|
470 - \ref GomoryHu "Gomory-Hu tree computation" for calculating |
432 - \ref GomoryHu "Gomory-Hu tree computation" for calculating |
471 all-pairs minimum cut in undirected graphs. |
433 all-pairs minimum cut in undirected graphs. |
472 |
434 |
473 If you want to find minimum cut just between two distinict nodes, |
435 If you want to find minimum cut just between two distinict nodes, |
474 see the \ref max_flow "maximum flow problem". |
436 see the \ref max_flow "maximum flow problem". |
485 \image html edge_biconnected_components.png |
447 \image html edge_biconnected_components.png |
486 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
448 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth |
487 */ |
449 */ |
488 |
450 |
489 /** |
451 /** |
490 @defgroup planar Planarity Embedding and Drawing |
|
491 @ingroup algs |
|
492 \brief Algorithms for planarity checking, embedding and drawing |
|
493 |
|
494 This group contains the algorithms for planarity checking, |
|
495 embedding and drawing. |
|
496 |
|
497 \image html planar.png |
|
498 \image latex planar.eps "Plane graph" width=\textwidth |
|
499 */ |
|
500 |
|
501 /** |
|
502 @defgroup matching Matching Algorithms |
452 @defgroup matching Matching Algorithms |
503 @ingroup algs |
453 @ingroup algs |
504 \brief Algorithms for finding matchings in graphs and bipartite graphs. |
454 \brief Algorithms for finding matchings in graphs and bipartite graphs. |
505 |
455 |
506 This group contains the algorithms for calculating |
456 This group contains the algorithms for calculating matchings in graphs. |
507 matchings in graphs and bipartite graphs. The general matching problem is |
457 The general matching problem is finding a subset of the edges for which |
508 finding a subset of the edges for which each node has at most one incident |
458 each node has at most one incident edge. |
509 edge. |
|
510 |
459 |
511 There are several different algorithms for calculate matchings in |
460 There are several different algorithms for calculate matchings in |
512 graphs. The matching problems in bipartite graphs are generally |
461 graphs. The goal of the matching optimization |
513 easier than in general graphs. The goal of the matching optimization |
|
514 can be finding maximum cardinality, maximum weight or minimum cost |
462 can be finding maximum cardinality, maximum weight or minimum cost |
515 matching. The search can be constrained to find perfect or |
463 matching. The search can be constrained to find perfect or |
516 maximum cardinality matching. |
464 maximum cardinality matching. |
517 |
465 |
518 The matching algorithms implemented in LEMON: |
466 The matching algorithms implemented in LEMON: |
519 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm |
|
520 for calculating maximum cardinality matching in bipartite graphs. |
|
521 - \ref PrBipartiteMatching Push-relabel algorithm |
|
522 for calculating maximum cardinality matching in bipartite graphs. |
|
523 - \ref MaxWeightedBipartiteMatching |
|
524 Successive shortest path algorithm for calculating maximum weighted |
|
525 matching and maximum weighted bipartite matching in bipartite graphs. |
|
526 - \ref MinCostMaxBipartiteMatching |
|
527 Successive shortest path algorithm for calculating minimum cost maximum |
|
528 matching in bipartite graphs. |
|
529 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
467 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating |
530 maximum cardinality matching in general graphs. |
468 maximum cardinality matching in general graphs. |
531 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
469 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating |
532 maximum weighted matching in general graphs. |
470 maximum weighted matching in general graphs. |
533 - \ref MaxWeightedPerfectMatching |
471 - \ref MaxWeightedPerfectMatching |
555 This group contains some algorithms implemented in LEMON |
493 This group contains some algorithms implemented in LEMON |
556 in order to make it easier to implement complex algorithms. |
494 in order to make it easier to implement complex algorithms. |
557 */ |
495 */ |
558 |
496 |
559 /** |
497 /** |
560 @defgroup approx Approximation Algorithms |
|
561 @ingroup algs |
|
562 \brief Approximation algorithms. |
|
563 |
|
564 This group contains the approximation and heuristic algorithms |
|
565 implemented in LEMON. |
|
566 */ |
|
567 |
|
568 /** |
|
569 @defgroup gen_opt_group General Optimization Tools |
498 @defgroup gen_opt_group General Optimization Tools |
570 \brief This group contains some general optimization frameworks |
499 \brief This group contains some general optimization frameworks |
571 implemented in LEMON. |
500 implemented in LEMON. |
572 |
501 |
573 This group contains some general optimization frameworks |
502 This group contains some general optimization frameworks |
580 \brief Lp and Mip solver interfaces for LEMON. |
509 \brief Lp and Mip solver interfaces for LEMON. |
581 |
510 |
582 This group contains Lp and Mip solver interfaces for LEMON. The |
511 This group contains Lp and Mip solver interfaces for LEMON. The |
583 various LP solvers could be used in the same manner with this |
512 various LP solvers could be used in the same manner with this |
584 interface. |
513 interface. |
585 */ |
|
586 |
|
587 /** |
|
588 @defgroup lp_utils Tools for Lp and Mip Solvers |
|
589 @ingroup lp_group |
|
590 \brief Helper tools to the Lp and Mip solvers. |
|
591 |
|
592 This group adds some helper tools to general optimization framework |
|
593 implemented in LEMON. |
|
594 */ |
|
595 |
|
596 /** |
|
597 @defgroup metah Metaheuristics |
|
598 @ingroup gen_opt_group |
|
599 \brief Metaheuristics for LEMON library. |
|
600 |
|
601 This group contains some metaheuristic optimization tools. |
|
602 */ |
514 */ |
603 |
515 |
604 /** |
516 /** |
605 @defgroup utils Tools and Utilities |
517 @defgroup utils Tools and Utilities |
606 \brief Tools and utilities for programming in LEMON |
518 \brief Tools and utilities for programming in LEMON |