COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r325 r326  
    4141some graph features like arc/edge or node deletion.
    4242
    43 Alteration of standard containers need a very limited number of
    44 operations, these together satisfy the everyday requirements.
    45 In the case of graph structures, different operations are needed which do
    46 not alter the physical graph, but gives another view. If some nodes or
    47 arcs have to be hidden or the reverse oriented graph have to be used, then
    48 this is the case. It also may happen that in a flow implementation
    49 the residual graph can be accessed by another algorithm, or a node-set
    50 is to be shrunk for another algorithm.
    51 LEMON also provides a variety of graphs for these requirements called
    52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    53 in conjunction with other graph representations.
    54 
    5543You are free to use the graph structure that fit your requirements
    5644the best, most graph algorithms and auxiliary data structures can be used
     
    5846
    5947<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 
    67 This group describes some graph types between real graphs and graph adaptors.
    68 These classes wrap graphs to give new functionality as the adaptors do it.
    69 On the other hand they are not light-weight structures as the adaptors.
    7048*/
    7149
     
    156134
    157135/**
    158 @defgroup matrices Matrices
    159 @ingroup datas
    160 \brief Two dimensional data storages implemented in LEMON.
    161 
    162 This group describes two dimensional data storages implemented in LEMON.
    163 */
    164 
    165 /**
    166136@defgroup paths Path Structures
    167137@ingroup datas
     
    215185
    216186/**
    217 @defgroup max_flow Maximum Flow Algorithms
    218 @ingroup algs
    219 \brief Algorithms for finding maximum flows.
    220 
    221 This group describes the algorithms for finding maximum flows and
    222 feasible circulations.
    223 
    224 The maximum flow problem is to find a flow between a single source and
    225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
    226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
    227 function and given \f$s, t \in V\f$ source and target node. The
    228 maximum 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 
    235 LEMON 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 
    241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
    242 fastest method to compute the maximum flow. All impelementations
    243 provides functions to query the minimum cut, which is the dual linear
    244 programming 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 
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
    255 */
    256 
    257 /**
    258 @defgroup min_cut Minimum Cut Algorithms
    259 @ingroup algs
    260 
    261 \brief Algorithms for finding minimum cut in graphs.
    262 
    263 This group describes the algorithms for finding minimum cut in graphs.
    264 
    265 The 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
    267 outgoing 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
    269 cut 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 
    274 LEMON 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 
    283 If you want to find minimum cut just between two distinict nodes,
    284 please 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 
    292 This group describes the algorithms for discovering the graph properties
    293 like 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 
    304 This group describes the algorithms for planarity checking,
    305 embedding 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 
    316 This group contains algorithm objects and functions to calculate
    317 matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
    319 
    320 There are several different algorithms for calculate matchings in
    321 graphs.  The matching problems in bipartite graphs are generally
    322 easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
    324 matching. The search can be constrained to find perfect or
    325 maximum cardinality matching.
    326 
    327 LEMON 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 /**
    353187@defgroup spantree Minimum Spanning Tree Algorithms
    354188@ingroup algs
     
    360194
    361195/**
    362 @defgroup auxalg Auxiliary Algorithms
    363 @ingroup algs
    364 \brief Auxiliary algorithms implemented in LEMON.
    365 
    366 This group describes some algorithms implemented in LEMON
    367 in 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 
    375 This group describes the approximation and heuristic algorithms
    376 implemented in LEMON.
    377 */
    378 
    379 /**
    380 @defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
    382 implemented in LEMON.
    383 
    384 This group describes some general optimization frameworks
    385 implemented 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 
    393 This group describes Lp and Mip solver interfaces for LEMON. The
    394 various LP solvers could be used in the same manner with this
    395 interface.
    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 
    403 This group adds some helper tools to general optimization framework
    404 implemented in LEMON.
    405 */
    406 
    407 /**
    408 @defgroup metah Metaheuristics
    409 @ingroup gen_opt_group
    410 \brief Metaheuristics for LEMON library.
    411 
    412 This group describes some metaheuristic optimization tools.
    413 */
    414 
    415 /**
    416196@defgroup utils Tools and Utilities
    417197\brief Tools and utilities for programming in LEMON
     
    459239
    460240This group describes the tools for importing and exporting graphs
    461 and graph related data. Now it supports the \ref lgf-format
    462 "LEMON Graph Format", the \c DIMACS format and the encapsulated
     241and graph related data. Now it supports the LEMON format
     242and the encapsulated postscript (EPS) format.
    463243postscript (EPS) format.
    464244*/
     
    524304@ingroup concept
    525305\brief Skeleton and concept checking classes for maps
    526 
     306 
    527307This group describes the skeletons and concept checking classes of maps.
    528308*/
     
    539319build the library.
    540320*/
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
    544 
    545 Some utility applications are listed here.
    546 
    547 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    548 them, as well.
    549 */
    550 
Note: See TracChangeset for help on using the changeset viewer.