COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r326 r325  
    4141some graph features like arc/edge or node deletion.
    4242
     43Alteration of standard containers need a very limited number of
     44operations, these together satisfy the everyday requirements.
     45In the case of graph structures, different operations are needed which do
     46not alter the physical graph, but gives another view. If some nodes or
     47arcs have to be hidden or the reverse oriented graph have to be used, then
     48this is the case. It also may happen that in a flow implementation
     49the residual graph can be accessed by another algorithm, or a node-set
     50is to be shrunk for another algorithm.
     51LEMON also provides a variety of graphs for these requirements called
     52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
     53in conjunction with other graph representations.
     54
    4355You are free to use the graph structure that fit your requirements
    4456the best, most graph algorithms and auxiliary data structures can be used
     
    4658
    4759<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
     60*/
     61
     62/**
     63@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
     64@ingroup graphs
     65\brief Graph types between real graphs and graph adaptors.
     66
     67This group describes some graph types between real graphs and graph adaptors.
     68These classes wrap graphs to give new functionality as the adaptors do it.
     69On the other hand they are not light-weight structures as the adaptors.
    4870*/
    4971
     
    134156
    135157/**
     158@defgroup matrices Matrices
     159@ingroup datas
     160\brief Two dimensional data storages implemented in LEMON.
     161
     162This group describes two dimensional data storages implemented in LEMON.
     163*/
     164
     165/**
    136166@defgroup paths Path Structures
    137167@ingroup datas
     
    185215
    186216/**
     217@defgroup max_flow Maximum Flow Algorithms
     218@ingroup algs
     219\brief Algorithms for finding maximum flows.
     220
     221This group describes the algorithms for finding maximum flows and
     222feasible circulations.
     223
     224The maximum flow problem is to find a flow between a single source and
     225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
     226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
     227function and given \f$s, t \in V\f$ source and target node. The
     228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
     229
     230\f[ 0 \le f_a \le c_a \f]
     231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
     232\qquad \forall u \in V \setminus \{s,t\}\f]
     233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
     234
     235LEMON contains several algorithms for solving maximum flow problems:
     236- \ref lemon::EdmondsKarp "Edmonds-Karp"
     237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
     238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
     239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
     240
     241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
     242fastest method to compute the maximum flow. All impelementations
     243provides functions to query the minimum cut, which is the dual linear
     244programming problem of the maximum flow.
     245*/
     246
     247/**
     248@defgroup min_cost_flow Minimum Cost Flow Algorithms
     249@ingroup algs
     250
     251\brief Algorithms for finding minimum cost flows and circulations.
     252
     253This group describes the algorithms for finding minimum cost flows and
     254circulations.
     255*/
     256
     257/**
     258@defgroup min_cut Minimum Cut Algorithms
     259@ingroup algs
     260
     261\brief Algorithms for finding minimum cut in graphs.
     262
     263This group describes the algorithms for finding minimum cut in graphs.
     264
     265The minimum cut problem is to find a non-empty and non-complete
     266\f$X\f$ subset of the vertices with minimum overall capacity on
     267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
     268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
     269cut is the \f$X\f$ solution of the next optimization problem:
     270
     271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
     272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
     273
     274LEMON contains several algorithms related to minimum cut problems:
     275
     276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
     277  in directed graphs
     278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
     279  calculate minimum cut in undirected graphs
     280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
     281  pairs minimum cut in undirected graphs
     282
     283If you want to find minimum cut just between two distinict nodes,
     284please see the \ref max_flow "Maximum Flow page".
     285*/
     286
     287/**
     288@defgroup graph_prop Connectivity and Other Graph Properties
     289@ingroup algs
     290\brief Algorithms for discovering the graph properties
     291
     292This group describes the algorithms for discovering the graph properties
     293like connectivity, bipartiteness, euler property, simplicity etc.
     294
     295\image html edge_biconnected_components.png
     296\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
     297*/
     298
     299/**
     300@defgroup planar Planarity Embedding and Drawing
     301@ingroup algs
     302\brief Algorithms for planarity checking, embedding and drawing
     303
     304This group describes the algorithms for planarity checking,
     305embedding and drawing.
     306
     307\image html planar.png
     308\image latex planar.eps "Plane graph" width=\textwidth
     309*/
     310
     311/**
     312@defgroup matching Matching Algorithms
     313@ingroup algs
     314\brief Algorithms for finding matchings in graphs and bipartite graphs.
     315
     316This group contains algorithm objects and functions to calculate
     317matchings in graphs and bipartite graphs. The general matching problem is
     318finding a subset of the arcs which does not shares common endpoints.
     319
     320There are several different algorithms for calculate matchings in
     321graphs.  The matching problems in bipartite graphs are generally
     322easier than in general graphs. The goal of the matching optimization
     323can be the finding maximum cardinality, maximum weight or minimum cost
     324matching. The search can be constrained to find perfect or
     325maximum cardinality matching.
     326
     327LEMON contains the next algorithms:
     328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     329  augmenting path algorithm for calculate maximum cardinality matching in
     330  bipartite graphs
     331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     332  algorithm for calculate maximum cardinality matching in bipartite graphs
     333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     334  Successive shortest path algorithm for calculate maximum weighted matching
     335  and maximum weighted bipartite matching in bipartite graph
     336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     337  Successive shortest path algorithm for calculate minimum cost maximum
     338  matching in bipartite graph
     339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
     340  for calculate maximum cardinality matching in general graph
     341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
     342  shrinking algorithm for calculate maximum weighted matching in general
     343  graph
     344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
     345  Edmond's blossom shrinking algorithm for calculate maximum weighted
     346  perfect matching in general graph
     347
     348\image html bipartite_matching.png
     349\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
     350*/
     351
     352/**
    187353@defgroup spantree Minimum Spanning Tree Algorithms
    188354@ingroup algs
     
    191357This group describes the algorithms for finding a minimum cost spanning
    192358tree in a graph
     359*/
     360
     361/**
     362@defgroup auxalg Auxiliary Algorithms
     363@ingroup algs
     364\brief Auxiliary algorithms implemented in LEMON.
     365
     366This group describes some algorithms implemented in LEMON
     367in order to make it easier to implement complex algorithms.
     368*/
     369
     370/**
     371@defgroup approx Approximation Algorithms
     372@ingroup algs
     373\brief Approximation algorithms.
     374
     375This group describes the approximation and heuristic algorithms
     376implemented in LEMON.
     377*/
     378
     379/**
     380@defgroup gen_opt_group General Optimization Tools
     381\brief This group describes some general optimization frameworks
     382implemented in LEMON.
     383
     384This group describes some general optimization frameworks
     385implemented in LEMON.
     386*/
     387
     388/**
     389@defgroup lp_group Lp and Mip Solvers
     390@ingroup gen_opt_group
     391\brief Lp and Mip solver interfaces for LEMON.
     392
     393This group describes Lp and Mip solver interfaces for LEMON. The
     394various LP solvers could be used in the same manner with this
     395interface.
     396*/
     397
     398/**
     399@defgroup lp_utils Tools for Lp and Mip Solvers
     400@ingroup lp_group
     401\brief Helper tools to the Lp and Mip solvers.
     402
     403This group adds some helper tools to general optimization framework
     404implemented in LEMON.
     405*/
     406
     407/**
     408@defgroup metah Metaheuristics
     409@ingroup gen_opt_group
     410\brief Metaheuristics for LEMON library.
     411
     412This group describes some metaheuristic optimization tools.
    193413*/
    194414
     
    239459
    240460This group describes the tools for importing and exporting graphs
    241 and graph related data. Now it supports the LEMON format
    242 and the encapsulated postscript (EPS) format.
     461and graph related data. Now it supports the \ref lgf-format
     462"LEMON Graph Format", the \c DIMACS format and the encapsulated
    243463postscript (EPS) format.
    244464*/
     
    304524@ingroup concept
    305525\brief Skeleton and concept checking classes for maps
    306  
     526
    307527This group describes the skeletons and concept checking classes of maps.
    308528*/
     
    319539build the library.
    320540*/
     541
     542/**
     543@defgroup tools Standalone utility applications
     544
     545Some utility applications are listed here.
     546
     547The standard compilation procedure (<tt>./configure;make</tt>) will compile
     548them, as well.
     549*/
     550
Note: See TracChangeset for help on using the changeset viewer.