COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r318 r844  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2009
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    1717 */
    1818
     19namespace lemon {
     20
    1921/**
    2022@defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
     23This group contains the several data structures implemented in LEMON.
    2224*/
    2325
     
    6163
    6264/**
    63 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
     65@defgroup graph_adaptors Adaptor Classes for Graphs
    6466@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.
     67\brief Adaptor classes for digraphs and graphs
     68
     69This group contains several useful adaptor classes for digraphs and graphs.
     70
     71The main parts of LEMON are the different graph structures, generic
     72graph algorithms, graph concepts, which couple them, and graph
     73adaptors. While the previous notions are more or less clear, the
     74latter one needs further explanation. Graph adaptors are graph classes
     75which serve for considering graph structures in different ways.
     76
     77A short example makes this much clearer.  Suppose that we have an
     78instance \c g of a directed graph type, say ListDigraph and an algorithm
     79\code
     80template <typename Digraph>
     81int algorithm(const Digraph&);
     82\endcode
     83is needed to run on the reverse oriented graph.  It may be expensive
     84(in time or in memory usage) to copy \c g with the reversed
     85arcs.  In this case, an adaptor class is used, which (according
     86to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
     87The adaptor uses the original digraph structure and digraph operations when
     88methods of the reversed oriented graph are called.  This means that the adaptor
     89have minor memory usage, and do not perform sophisticated algorithmic
     90actions.  The purpose of it is to give a tool for the cases when a
     91graph have to be used in a specific alteration.  If this alteration is
     92obtained by a usual construction like filtering the node or the arc set or
     93considering a new orientation, then an adaptor is worthwhile to use.
     94To come back to the reverse oriented graph, in this situation
     95\code
     96template<typename Digraph> class ReverseDigraph;
     97\endcode
     98template class can be used. The code looks as follows
     99\code
     100ListDigraph g;
     101ReverseDigraph<ListDigraph> rg(g);
     102int result = algorithm(rg);
     103\endcode
     104During running the algorithm, the original digraph \c g is untouched.
     105This techniques give rise to an elegant code, and based on stable
     106graph adaptors, complex algorithms can be implemented easily.
     107
     108In flow, circulation and matching problems, the residual
     109graph is of particular importance. Combining an adaptor implementing
     110this with shortest path algorithms or minimum mean cycle algorithms,
     111a range of weighted and cardinality optimization algorithms can be
     112obtained. For other examples, the interested user is referred to the
     113detailed documentation of particular adaptors.
     114
     115The behavior of graph adaptors can be very different. Some of them keep
     116capabilities of the original graph while in other cases this would be
     117meaningless. This means that the concepts that they meet depend
     118on the graph adaptor, and the wrapped graph.
     119For example, if an arc of a reversed digraph is deleted, this is carried
     120out by deleting the corresponding arc of the original digraph, thus the
     121adaptor modifies the original digraph.
     122However in case of a residual digraph, this operation has no sense.
     123
     124Let us stand one more example here to simplify your work.
     125ReverseDigraph has constructor
     126\code
     127ReverseDigraph(Digraph& digraph);
     128\endcode
     129This means that in a situation, when a <tt>const %ListDigraph&</tt>
     130reference to a graph is given, then it have to be instantiated with
     131<tt>Digraph=const %ListDigraph</tt>.
     132\code
     133int algorithm1(const ListDigraph& g) {
     134  ReverseDigraph<const ListDigraph> rg(g);
     135  return algorithm2(rg);
     136}
     137\endcode
    70138*/
    71139
     
    75143\brief Map structures implemented in LEMON.
    76144
    77 This group describes the map structures implemented in LEMON.
     145This group contains the map structures implemented in LEMON.
    78146
    79147LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    88156\brief Special graph-related maps.
    89157
    90 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     158This group contains maps that are specifically designed to assign
     159values to the nodes and arcs/edges of graphs.
     160
     161If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     162\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92163*/
    93164
     
    97168\brief Tools to create new maps from existing ones
    98169
    99 This group describes map adaptors that are used to create "implicit"
     170This group contains map adaptors that are used to create "implicit"
    100171maps from other maps.
    101172
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     173Most of them are \ref concepts::ReadMap "read-only maps".
    103174They can make arithmetic and logical operations between one or two maps
    104175(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    156227
    157228/**
    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 /**
    166229@defgroup paths Path Structures
    167230@ingroup datas
    168231\brief %Path structures implemented in LEMON.
    169232
    170 This group describes the path structures implemented in LEMON.
     233This group contains the path structures implemented in LEMON.
    171234
    172235LEMON provides flexible data structures to work with paths.
     
    184247\brief Auxiliary data structures implemented in LEMON.
    185248
    186 This group describes some data structures implemented in LEMON in
     249This group contains some data structures implemented in LEMON in
    187250order to make it easier to implement combinatorial algorithms.
    188251*/
     
    190253/**
    191254@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     255\brief This group contains the several algorithms
    193256implemented in LEMON.
    194257
    195 This group describes the several algorithms
     258This group contains the several algorithms
    196259implemented in LEMON.
    197260*/
     
    202265\brief Common graph search algorithms.
    203266
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     267This group contains the common graph search algorithms, namely
     268\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206269*/
    207270
     
    211274\brief Algorithms for finding shortest paths.
    212275
    213 This group describes the algorithms for finding shortest paths in graphs.
     276This group contains the algorithms for finding shortest paths in digraphs.
     277
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
     280 - \ref Suurballe A successive shortest path algorithm for finding
     281   arc-disjoint paths between two nodes having minimum total length.
    214282*/
    215283
     
    219287\brief Algorithms for finding maximum flows.
    220288
    221 This group describes the algorithms for finding maximum flows and
     289This group contains the algorithms for finding maximum flows and
    222290feasible circulations.
    223291
    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
     292The \e maximum \e flow \e problem is to find a flow of maximum value between
     293a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     294digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     295\f$s, t \in V\f$ source and target nodes.
     296A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     297following optimization problem.
     298
     299\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     300\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     301    \quad \forall u\in V\setminus\{s,t\} \f]
     302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
     303
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
     308
     309\ref Circulation is a preflow push-relabel algorithm implemented directly
     310for finding feasible circulations, which is a somewhat different problem,
     311but it is strongly related to maximum flow.
     312For more information, see \ref Circulation.
     313*/
     314
     315/**
     316@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    249317@ingroup algs
    250318
    251319\brief Algorithms for finding minimum cost flows and circulations.
    252320
    253 This group describes the algorithms for finding minimum cost flows and
    254 circulations.
     321This group contains the algorithms for finding minimum cost flows and
     322circulations. For more information about this problem and its dual
     323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     324
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    255328*/
    256329
     
    261334\brief Algorithms for finding minimum cut in graphs.
    262335
    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
     336This group contains the algorithms for finding minimum cut in graphs.
     337
     338The \e minimum \e cut \e problem is to find a non-empty and non-complete
     339\f$X\f$ subset of the nodes with minimum overall capacity on
     340outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     341\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269342cut is the \f$X\f$ solution of the next optimization problem:
    270343
    271344\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]
     345    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273346
    274347LEMON contains several algorithms related to minimum cut problems:
    275348
    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
     349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     350  in directed graphs.
     351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     352  all-pairs minimum cut in undirected graphs.
    282353
    283354If 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
     355see the \ref max_flow "maximum flow problem".
     356*/
     357
     358/**
     359@defgroup graph_properties Connectivity and Other Graph Properties
    289360@ingroup algs
    290361\brief Algorithms for discovering the graph properties
    291362
    292 This group describes the algorithms for discovering the graph properties
     363This group contains the algorithms for discovering the graph properties
    293364like connectivity, bipartiteness, euler property, simplicity etc.
    294365
     
    298369
    299370/**
    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 /**
    312371@defgroup matching Matching Algorithms
    313372@ingroup algs
    314373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315374
    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.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    319378
    320379There 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
     380graphs. The goal of the matching optimization
     381can be finding maximum cardinality, maximum weight or minimum cost
    324382matching. The search can be constrained to find perfect or
    325383maximum cardinality matching.
    326384
    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
     385The matching algorithms implemented in LEMON:
     386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     387  maximum cardinality matching in general graphs.
     388- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     389  maximum weighted matching in general graphs.
     390- \ref MaxWeightedPerfectMatching
     391  Edmond's blossom shrinking algorithm for calculating maximum weighted
     392  perfect matching in general graphs.
    347393
    348394\image html bipartite_matching.png
     
    353399@defgroup spantree Minimum Spanning Tree Algorithms
    354400@ingroup algs
    355 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    356 
    357 This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     401\brief Algorithms for finding minimum cost spanning trees and arborescences.
     402
     403This group contains the algorithms for finding minimum cost spanning
     404trees and arborescences.
    359405*/
    360406
     
    364410\brief Auxiliary algorithms implemented in LEMON.
    365411
    366 This group describes some algorithms implemented in LEMON
     412This group contains some algorithms implemented in LEMON
    367413in order to make it easier to implement complex algorithms.
    368414*/
    369415
    370416/**
    371 @defgroup approx Approximation Algorithms
    372 @ingroup algs
    373 \brief Approximation algorithms.
    374 
    375 This group describes the approximation and heuristic algorithms
     417@defgroup gen_opt_group General Optimization Tools
     418\brief This group contains some general optimization frameworks
    376419implemented 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
     420
     421This group contains some general optimization frameworks
    385422implemented in LEMON.
    386423*/
     
    391428\brief Lp and Mip solver interfaces for LEMON.
    392429
    393 This group describes Lp and Mip solver interfaces for LEMON. The
     430This group contains Lp and Mip solver interfaces for LEMON. The
    394431various LP solvers could be used in the same manner with this
    395432interface.
    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.
    413433*/
    414434
     
    425445\brief Simple basic graph utilities.
    426446
    427 This group describes some simple basic graph utilities.
     447This group contains some simple basic graph utilities.
    428448*/
    429449
     
    433453\brief Tools for development, debugging and testing.
    434454
    435 This group describes several useful tools for development,
     455This group contains several useful tools for development,
    436456debugging and testing.
    437457*/
     
    442462\brief Simple tools for measuring the performance of algorithms.
    443463
    444 This group describes simple tools for measuring the performance
     464This group contains simple tools for measuring the performance
    445465of algorithms.
    446466*/
     
    451471\brief Exceptions defined in LEMON.
    452472
    453 This group describes the exceptions defined in LEMON.
     473This group contains the exceptions defined in LEMON.
    454474*/
    455475
     
    458478\brief Graph Input-Output methods
    459479
    460 This group describes the tools for importing and exporting graphs
     480This group contains the tools for importing and exporting graphs
    461481and graph related data. Now it supports the \ref lgf-format
    462482"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    465485
    466486/**
    467 @defgroup lemon_io LEMON Input-Output
     487@defgroup lemon_io LEMON Graph Format
    468488@ingroup io_group
    469489\brief Reading and writing LEMON Graph Format.
    470490
    471 This group describes methods for reading and writing
     491This group contains methods for reading and writing
    472492\ref lgf-format "LEMON Graph Format".
    473493*/
     
    478498\brief General \c EPS drawer and graph exporter
    479499
    480 This group describes general \c EPS drawing methods and special
     500This group contains general \c EPS drawing methods and special
    481501graph exporting tools.
     502*/
     503
     504/**
     505@defgroup dimacs_group DIMACS format
     506@ingroup io_group
     507\brief Read and write files in DIMACS format
     508
     509Tools to read a digraph from or write it to a file in DIMACS format data.
     510*/
     511
     512/**
     513@defgroup nauty_group NAUTY Format
     514@ingroup io_group
     515\brief Read \e Nauty format
     516
     517Tool to read graphs from \e Nauty format data.
    482518*/
    483519
     
    486522\brief Skeleton classes and concept checking classes
    487523
    488 This group describes the data/algorithm skeletons and concept checking
     524This group contains the data/algorithm skeletons and concept checking
    489525classes implemented in LEMON.
    490526
     
    516552\brief Skeleton and concept checking classes for graph structures
    517553
    518 This group describes the skeletons and concept checking classes of LEMON's
     554This group contains the skeletons and concept checking classes of LEMON's
    519555graph structures and helper classes used to implement these.
    520556*/
     
    525561\brief Skeleton and concept checking classes for maps
    526562
    527 This group describes the skeletons and concept checking classes of maps.
     563This group contains the skeletons and concept checking classes of maps.
    528564*/
    529565
     
    531567\anchor demoprograms
    532568
    533 @defgroup demos Demo programs
     569@defgroup demos Demo Programs
    534570
    535571Some demo programs are listed here. Their full source codes can be found in
    536572the \c demo subdirectory of the source tree.
    537573
    538 It order to compile them, use <tt>--enable-demo</tt> configure option when
    539 build the library.
    540 */
    541 
    542 /**
    543 @defgroup tools Standalone utility applications
     574In order to compile them, use the <tt>make demo</tt> or the
     575<tt>make check</tt> commands.
     576*/
     577
     578/**
     579@defgroup tools Standalone Utility Applications
    544580
    545581Some utility applications are listed here.
     
    549585*/
    550586
     587}
Note: See TracChangeset for help on using the changeset viewer.