doc/groups.dox
branch1.1
changeset 644 189760a7cdd0
parent 636 6c408d864fa1
child 664 c01a98ce01fd
equal deleted inserted replaced
26:18297b9fca6a 27:b6e4f7d1e3a3
   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