COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r710 r963  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2009
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    227227
    228228/**
    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 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    247239any kind of path structure.
    248240
    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
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
    250263*/
    251264
     
    260273
    261274/**
     275@defgroup geomdat Geometric Data Structures
     276@ingroup auxdat
     277\brief Geometric data structures implemented in LEMON.
     278
     279This group contains geometric data structures implemented in LEMON.
     280
     281 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
     282   vector with the usual operations.
     283 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
     284   rectangular bounding box of a set of \ref lemon::dim2::Point
     285   "dim2::Point"'s.
     286*/
     287
     288/**
    262289@defgroup algs Algorithms
    263290\brief This group contains the several algorithms
     
    274301
    275302This group contains the common graph search algorithms, namely
    276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
     303\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
     304\ref clrs01algorithms.
    277305*/
    278306
     
    282310\brief Algorithms for finding shortest paths.
    283311
    284 This group contains the algorithms for finding shortest paths in digraphs.
     312This group contains the algorithms for finding shortest paths in digraphs
     313\ref clrs01algorithms.
    285314
    286315 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    290319   but the digraph should not contain directed cycles with negative total
    291320   length.
    292  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    293    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    294    lenghts can be either positive or negative, but the digraph should
    295    not contain directed cycles with negative total length.
    296321 - \ref Suurballe A successive shortest path algorithm for finding
    297322   arc-disjoint paths between two nodes having minimum total length.
     
    299324
    300325/**
     326@defgroup spantree Minimum Spanning Tree Algorithms
     327@ingroup algs
     328\brief Algorithms for finding minimum cost spanning trees and arborescences.
     329
     330This group contains the algorithms for finding minimum cost spanning
     331trees and arborescences \ref clrs01algorithms.
     332*/
     333
     334/**
    301335@defgroup max_flow Maximum Flow Algorithms
    302336@ingroup algs
     
    304338
    305339This group contains the algorithms for finding maximum flows and
    306 feasible circulations.
     340feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    307341
    308342The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    318352\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319353
    320 LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
    327 fastest method for computing a maximum flow. All implementations
    328 also provide functions to query the minimum cut, which is the dual
    329 problem of maximum flow.
    330 
    331 \ref Circulation is a preflow push-relabel algorithm implemented directly
     354\ref Preflow is an efficient implementation of Goldberg-Tarjan's
     355preflow push-relabel algorithm \ref goldberg88newapproach for finding
     356maximum flows. It also provides functions to query the minimum cut,
     357which is the dual problem of maximum flow.
     358
     359\ref Circulation is a preflow push-relabel algorithm implemented directly
    332360for finding feasible circulations, which is a somewhat different problem,
    333361but it is strongly related to maximum flow.
     
    342370
    343371This group contains the algorithms for finding minimum cost flows and
    344 circulations. For more information about this problem and its dual
    345 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     372circulations \ref amo93networkflows. For more information about this
     373problem and its dual solution, see \ref min_cost_flow
     374"Minimum Cost Flow Problem".
    346375
    347376LEMON contains several algorithms for this problem.
    348377 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
     378   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     379 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     380   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     381   \ref bunnagel98efficient.
     382 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     383   shortest path method \ref edmondskarp72theoretical.
     384 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     385   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    356386
    357387In general NetworkSimplex is the most efficient implementation,
     
    376406
    377407\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]
     408    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379409
    380410LEMON contains several algorithms related to minimum cut problems:
     
    382412- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383413  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386414- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387415  all-pairs minimum cut in undirected graphs.
     
    392420
    393421/**
    394 @defgroup graph_properties Connectivity and Other Graph Properties
    395 @ingroup algs
    396 \brief Algorithms for discovering the graph properties
    397 
    398 This group contains the algorithms for discovering the graph properties
    399 like connectivity, bipartiteness, euler property, simplicity etc.
    400 
    401 \image html edge_biconnected_components.png
    402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    403 */
    404 
    405 /**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
     422@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     423@ingroup algs
     424\brief Algorithms for finding minimum mean cycles.
     425
     426This group contains the algorithms for finding minimum mean cycles
     427\ref clrs01algorithms, \ref amo93networkflows.
     428
     429The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     430of minimum mean length (cost) in a digraph.
     431The mean length of a cycle is the average length of its arcs, i.e. the
     432ratio between the total length of the cycle and the number of arcs on it.
     433
     434This problem has an important connection to \e conservative \e length
     435\e functions, too. A length function on the arcs of a digraph is called
     436conservative if and only if there is no directed cycle of negative total
     437length. For an arbitrary length function, the negative of the minimum
     438cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     439arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     440function.
     441
     442LEMON contains three algorithms for solving the minimum mean cycle problem:
     443- \ref KarpMmc Karp's original algorithm \ref amo93networkflows,
     444  \ref dasdan98minmeancycle.
     445- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved
     446  version of Karp's algorithm \ref dasdan98minmeancycle.
     447- \ref HowardMmc Howard's policy iteration algorithm
     448  \ref dasdan98minmeancycle.
     449
     450In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
     451most efficient one, though the best known theoretical bound on its running
     452time is exponential.
     453Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
     454run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is
     455typically faster due to the applied early termination scheme.
    415456*/
    416457
     
    433474
    434475The matching algorithms implemented in LEMON:
    435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    436   for calculating maximum cardinality matching in bipartite graphs.
    437 - \ref PrBipartiteMatching Push-relabel algorithm
    438   for calculating maximum cardinality matching in bipartite graphs.
    439 - \ref MaxWeightedBipartiteMatching
    440   Successive shortest path algorithm for calculating maximum weighted
    441   matching and maximum weighted bipartite matching in bipartite graphs.
    442 - \ref MinCostMaxBipartiteMatching
    443   Successive shortest path algorithm for calculating minimum cost maximum
    444   matching in bipartite graphs.
    445476- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446477  maximum cardinality matching in general graphs.
     
    450481  Edmond's blossom shrinking algorithm for calculating maximum weighted
    451482  perfect matching in general graphs.
    452 
    453 \image html bipartite_matching.png
    454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    455 */
    456 
    457 /**
    458 @defgroup spantree Minimum Spanning Tree Algorithms
    459 @ingroup algs
    460 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    461 
    462 This group contains the algorithms for finding minimum cost spanning
    463 trees and arborescences.
     483- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     484  maximum cardinality fractional matching in general graphs.
     485- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     486  maximum weighted fractional matching in general graphs.
     487- \ref MaxWeightedPerfectFractionalMatching
     488  Augmenting path algorithm for calculating maximum weighted
     489  perfect fractional matching in general graphs.
     490
     491\image html matching.png
     492\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     493*/
     494
     495/**
     496@defgroup graph_properties Connectivity and Other Graph Properties
     497@ingroup algs
     498\brief Algorithms for discovering the graph properties
     499
     500This group contains the algorithms for discovering the graph properties
     501like connectivity, bipartiteness, euler property, simplicity etc.
     502
     503\image html connected_components.png
     504\image latex connected_components.eps "Connected components" width=\textwidth
     505*/
     506
     507/**
     508@defgroup planar Planarity Embedding and Drawing
     509@ingroup algs
     510\brief Algorithms for planarity checking, embedding and drawing
     511
     512This group contains the algorithms for planarity checking,
     513embedding and drawing.
     514
     515\image html planar.png
     516\image latex planar.eps "Plane graph" width=\textwidth
    464517*/
    465518
     
    471524This group contains some algorithms implemented in LEMON
    472525in order to make it easier to implement complex algorithms.
    473 */
    474 
    475 /**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482526*/
    483527
     
    492536
    493537/**
    494 @defgroup lp_group Lp and Mip Solvers
     538@defgroup lp_group LP and MIP Solvers
    495539@ingroup gen_opt_group
    496 \brief Lp and Mip solver interfaces for LEMON.
    497 
    498 This group contains Lp and Mip solver interfaces for LEMON. The
    499 various LP solvers could be used in the same manner with this
    500 interface.
    501 */
    502 
    503 /**
    504 @defgroup lp_utils Tools for Lp and Mip Solvers
    505 @ingroup lp_group
    506 \brief Helper tools to the Lp and Mip solvers.
    507 
    508 This group adds some helper tools to general optimization framework
    509 implemented in LEMON.
    510 */
    511 
    512 /**
    513 @defgroup metah Metaheuristics
    514 @ingroup gen_opt_group
    515 \brief Metaheuristics for LEMON library.
    516 
    517 This group contains some metaheuristic optimization tools.
     540\brief LP and MIP solver interfaces for LEMON.
     541
     542This group contains LP and MIP solver interfaces for LEMON.
     543Various LP solvers could be used in the same manner with this
     544high-level interface.
     545
     546The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     547\ref cplex, \ref soplex.
    518548*/
    519549
     
    588618
    589619/**
    590 @defgroup dimacs_group DIMACS format
     620@defgroup dimacs_group DIMACS Format
    591621@ingroup io_group
    592622\brief Read and write files in DIMACS format
     
    637667\brief Skeleton and concept checking classes for graph structures
    638668
    639 This group contains the skeletons and concept checking classes of LEMON's
    640 graph structures and helper classes used to implement these.
     669This group contains the skeletons and concept checking classes of
     670graph structures.
    641671*/
    642672
     
    650680
    651681/**
     682@defgroup tools Standalone Utility Applications
     683
     684Some utility applications are listed here.
     685
     686The standard compilation procedure (<tt>./configure;make</tt>) will compile
     687them, as well.
     688*/
     689
     690/**
    652691\anchor demoprograms
    653692
     
    661700*/
    662701
    663 /**
    664 @defgroup tools Standalone Utility Applications
    665 
    666 Some utility applications are listed here.
    667 
    668 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    669 them, as well.
    670 */
    671 
    672702}
Note: See TracChangeset for help on using the changeset viewer.