COIN-OR::LEMON - Graph Library

Changeset 320:12626fc94ccf in lemon-1.0 for doc/groups.dox


Ignore:
Timestamp:
10/09/08 15:37:44 (11 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.0
Parents:
303:de38fca76780 (diff), 319:c175e387da19 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge from trunk

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r302 r320  
    4343You are free to use the graph structure that fit your requirements
    4444the best, most graph algorithms and auxiliary data structures can be used
    45 with any graph structures.
     45with any graph structure.
     46
     47<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    4648*/
    4749
     
    5355This group describes the map structures implemented in LEMON.
    5456
    55 LEMON provides several special purpose maps that e.g. combine
     57LEMON provides several special purpose maps and map adaptors that e.g. combine
    5658new maps from existing ones.
     59
     60<b>See also:</b> \ref map_concepts "Map Concepts".
    5761*/
    5862
     
    6569values to the nodes and arcs of graphs.
    6670*/
    67 
    6871
    6972/**
     
    8386algorithms.  If a function type algorithm is called then the function
    8487type map adaptors can be used comfortable. For example let's see the
    85 usage of map adaptors with the \c digraphToEps() function.
     88usage of map adaptors with the \c graphToEps() function.
    8689\code
    8790  Color nodeColor(int deg) {
     
    97100  Digraph::NodeMap<int> degree_map(graph);
    98101
    99   digraphToEps(graph, "graph.eps")
     102  graphToEps(graph, "graph.eps")
    100103    .coords(coords).scaleToA4().undirected()
    101104    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
     
    103106\endcode
    104107The \c functorToMap() function makes an \c int to \c Color map from the
    105 \e nodeColor() function. The \c composeMap() compose the \e degree_map
     108\c nodeColor() function. The \c composeMap() compose the \c degree_map
    106109and the previously created map. The composed map is a proper function to
    107110get the color of each node.
     
    144147
    145148\sa lemon::concepts::Path
    146 
    147149*/
    148150
     
    156158*/
    157159
    158 
    159160/**
    160161@defgroup algs Algorithms
     
    172173
    173174This group describes the common graph search algorithms like
    174 Breadth-first search (Bfs) and Depth-first search (Dfs).
    175 */
    176 
    177 /**
    178 @defgroup shortest_path Shortest Path algorithms
     175Breadth-First Search (BFS) and Depth-First Search (DFS).
     176*/
     177
     178/**
     179@defgroup shortest_path Shortest Path Algorithms
    179180@ingroup algs
    180181\brief Algorithms for finding shortest paths.
     
    184185
    185186/**
    186 @defgroup spantree Minimum Spanning Tree algorithms
     187@defgroup spantree Minimum Spanning Tree Algorithms
    187188@ingroup algs
    188189\brief Algorithms for finding a minimum cost spanning tree in a graph.
     
    192193*/
    193194
     195@ingroup algs
    194196/**
    195197@defgroup utils Tools and Utilities
     
    217219
    218220/**
    219 @defgroup timecount Time measuring and Counting
     221@defgroup timecount Time Measuring and Counting
    220222@ingroup misc
    221223\brief Simple tools for measuring the performance of algorithms.
     
    240242and graph related data. Now it supports the LEMON format
    241243and the encapsulated postscript (EPS) format.
     244postscript (EPS) format.
    242245*/
    243246
     
    245248@defgroup lemon_io LEMON Input-Output
    246249@ingroup io_group
    247 \brief Reading and writing \ref lgf-format "LEMON Graph Format".
     250\brief Reading and writing LEMON Graph Format.
    248251
    249252This group describes methods for reading and writing
     
    252255
    253256/**
    254 @defgroup eps_io Postscript exporting
     257@defgroup eps_io Postscript Exporting
    255258@ingroup io_group
    256259\brief General \c EPS drawer and graph exporter
     
    259262graph exporting tools.
    260263*/
    261 
    262264
    263265/**
     
    288290
    289291- Finally, They can serve as a skeleton of a new implementation of a concept.
    290 
    291 */
    292 
     292*/
    293293
    294294/**
     
    301301*/
    302302
     303
     304This group describes the skeletons and concept checking classes of maps.
    303305/**
    304306\anchor demoprograms
  • doc/groups.dox

    r318 r320  
    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
     
    359193*/
    360194
    361 /**
    362 @defgroup auxalg Auxiliary Algorithms
    363195@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 
    415196/**
    416197@defgroup utils Tools and Utilities
     
    459240
    460241This 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
     242and graph related data. Now it supports the LEMON format
     243and the encapsulated postscript (EPS) format.
    463244postscript (EPS) format.
    464245*/
     
    520301*/
    521302
    522 /**
    523 @defgroup map_concepts Map Concepts
    524 @ingroup concept
    525 \brief Skeleton and concept checking classes for maps
    526303
    527304This group describes the skeletons and concept checking classes of maps.
    528 */
    529 
    530305/**
    531306\anchor demoprograms
     
    539314build the library.
    540315*/
    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.