COIN-OR::LEMON - Graph Library

Changeset 325:3a2e0692eaae in lemon


Ignore:
Timestamp:
10/09/08 13:47:26 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
1.0
Message:

Remove references to tools that have not been ported yet (ticket #119)

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r236 r325  
    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 
    5745with any graph structures. 
    58 */ 
    59  
    60 /** 
    61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs 
    62 @ingroup graphs 
    63 \brief Graph types between real graphs and graph adaptors. 
    64  
    65 This group describes some graph types between real graphs and graph adaptors. 
    66 These classes wrap graphs to give new functionality as the adaptors do it. 
    67 On the other hand they are not light-weight structures as the adaptors. 
    6846*/ 
    6947 
     
    153131 
    154132/** 
    155 @defgroup matrices Matrices 
    156 @ingroup datas 
    157 \brief Two dimensional data storages implemented in LEMON. 
    158  
    159 This group describes two dimensional data storages implemented in LEMON. 
    160 */ 
    161  
    162 /** 
    163133@defgroup paths Path Structures 
    164134@ingroup datas 
     
    214184 
    215185/** 
    216 @defgroup max_flow Maximum Flow algorithms 
    217 @ingroup algs 
    218 \brief Algorithms for finding maximum flows. 
    219  
    220 This group describes the algorithms for finding maximum flows and 
    221 feasible circulations. 
    222  
    223 The maximum flow problem is to find a flow between a single source and 
    224 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$ 
    225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity 
    226 function and given \f$s, t \in V\f$ source and target node. The 
    227 maximum flow is the \f$f_a\f$ solution of the next optimization problem: 
    228  
    229 \f[ 0 \le f_a \le c_a \f] 
    230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} 
    231 \qquad \forall u \in V \setminus \{s,t\}\f] 
    232 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f] 
    233  
    234 LEMON contains several algorithms for solving maximum flow problems: 
    235 - \ref lemon::EdmondsKarp "Edmonds-Karp" 
    236 - \ref lemon::Preflow "Goldberg's Preflow algorithm" 
    237 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees" 
    238 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees" 
    239  
    240 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the 
    241 fastest method to compute the maximum flow. All impelementations 
    242 provides functions to query the minimum cut, which is the dual linear 
    243 programming problem of the maximum flow. 
    244  
    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 /** 
    289 @defgroup graph_prop Connectivity and other graph properties 
    290 @ingroup algs 
    291 \brief Algorithms for discovering the graph properties 
    292  
    293 This group describes the algorithms for discovering the graph properties 
    294 like connectivity, bipartiteness, euler property, simplicity etc. 
    295  
    296 \image html edge_biconnected_components.png 
    297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 
    298 */ 
    299  
    300 /** 
    301 @defgroup planar Planarity embedding and drawing 
    302 @ingroup algs 
    303 \brief Algorithms for planarity checking, embedding and drawing 
    304  
    305 This group describes the algorithms for planarity checking, 
    306 embedding and drawing. 
    307  
    308 \image html planar.png 
    309 \image latex planar.eps "Plane graph" width=\textwidth 
    310 */ 
    311  
    312 /** 
    313 @defgroup matching Matching algorithms 
    314 @ingroup algs 
    315 \brief Algorithms for finding matchings in graphs and bipartite graphs. 
    316  
    317 This group contains algorithm objects and functions to calculate 
    318 matchings in graphs and bipartite graphs. The general matching problem is 
    319 finding a subset of the arcs which does not shares common endpoints. 
    320  
    321 There are several different algorithms for calculate matchings in 
    322 graphs.  The matching problems in bipartite graphs are generally 
    323 easier than in general graphs. The goal of the matching optimization 
    324 can be the finding maximum cardinality, maximum weight or minimum cost 
    325 matching. The search can be constrained to find perfect or 
    326 maximum cardinality matching. 
    327  
    328 LEMON contains the next algorithms: 
    329 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
    330   augmenting path algorithm for calculate maximum cardinality matching in 
    331   bipartite graphs 
    332 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
    333   algorithm for calculate maximum cardinality matching in bipartite graphs 
    334 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
    335   Successive shortest path algorithm for calculate maximum weighted matching 
    336   and maximum weighted bipartite matching in bipartite graph 
    337 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
    338   Successive shortest path algorithm for calculate minimum cost maximum 
    339   matching in bipartite graph 
    340 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm 
    341   for calculate maximum cardinality matching in general graph 
    342 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom 
    343   shrinking algorithm for calculate maximum weighted matching in general 
    344   graph 
    345 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching" 
    346   Edmond's blossom shrinking algorithm for calculate maximum weighted 
    347   perfect matching in general graph 
    348  
    349 \image html bipartite_matching.png 
    350 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 
    351  
    352 */ 
    353  
    354 /** 
    355186@defgroup spantree Minimum Spanning Tree algorithms 
    356187@ingroup algs 
     
    361192*/ 
    362193 
    363  
    364 /** 
    365 @defgroup auxalg Auxiliary algorithms 
    366 @ingroup algs 
    367 \brief Auxiliary algorithms implemented in LEMON. 
    368  
    369 This group describes some algorithms implemented in LEMON 
    370 in order to make it easier to implement complex algorithms. 
    371 */ 
    372  
    373 /** 
    374 @defgroup approx Approximation algorithms 
    375 \brief Approximation algorithms. 
    376  
    377 This group describes the approximation and heuristic algorithms 
    378 implemented in LEMON. 
    379 */ 
    380  
    381 /** 
    382 @defgroup gen_opt_group General Optimization Tools 
    383 \brief This group describes some general optimization frameworks 
    384 implemented in LEMON. 
    385  
    386 This group describes some general optimization frameworks 
    387 implemented in LEMON. 
    388  
    389 */ 
    390  
    391 /** 
    392 @defgroup lp_group Lp and Mip solvers 
    393 @ingroup gen_opt_group 
    394 \brief Lp and Mip solver interfaces for LEMON. 
    395  
    396 This group describes Lp and Mip solver interfaces for LEMON. The 
    397 various LP solvers could be used in the same manner with this 
    398 interface. 
    399  
    400 */ 
    401  
    402 /** 
    403 @defgroup lp_utils Tools for Lp and Mip solvers 
    404 @ingroup lp_group 
    405 \brief Helper tools to the Lp and Mip solvers. 
    406  
    407 This group adds some helper tools to general optimization framework 
    408 implemented in LEMON. 
    409 */ 
    410  
    411 /** 
    412 @defgroup metah Metaheuristics 
    413 @ingroup gen_opt_group 
    414 \brief Metaheuristics for LEMON library. 
    415  
    416 This group describes some metaheuristic optimization tools. 
    417 */ 
    418  
    419194/** 
    420195@defgroup utils Tools and Utilities 
     
    451226 
    452227/** 
    453 @defgroup graphbits Tools for Graph Implementation 
    454 @ingroup utils 
    455 \brief Tools to make it easier to create graphs. 
    456  
    457 This group describes the tools that makes it easier to create graphs and 
    458 the maps that dynamically update with the graph changes. 
    459 */ 
    460  
    461 /** 
    462228@defgroup exceptions Exceptions 
    463229@ingroup utils 
     
    472238 
    473239This group describes the tools for importing and exporting graphs 
    474 and graph related data. Now it supports the LEMON format, the 
    475 \c DIMACS format and the encapsulated postscript (EPS) format. 
     240and graph related data. Now it supports the LEMON format 
     241and the encapsulated postscript (EPS) format. 
    476242*/ 
    477243 
     
    535301*/ 
    536302 
    537 /* --- Unused group 
    538 @defgroup experimental Experimental Structures and Algorithms 
    539 This group describes some Experimental structures and algorithms. 
    540 The stuff here is subject to change. 
    541 */ 
    542  
    543303/** 
    544304\anchor demoprograms 
     
    552312build the library. 
    553313*/ 
    554  
    555 /** 
    556 @defgroup tools Standalone utility applications 
    557  
    558 Some utility applications are listed here. 
    559  
    560 The standard compilation procedure (<tt>./configure;make</tt>) will compile 
    561 them, as well. 
    562 */ 
    563  
  • doc/mainpage.dox

    r209 r325  
    4242\subsection howtoread How to read the documentation 
    4343 
    44 If you want to get a quick start and see the most important features then 
    45 take a look at our \ref quicktour 
    46 "Quick Tour to LEMON" which will guide you along. 
    47  
    48 If you already feel like using our library, see the page that tells you 
    49 \ref getstart "How to start using LEMON". 
    50  
    5144If you 
    5245want to see how LEMON works, see 
Note: See TracChangeset for help on using the changeset viewer.