COIN-OR::LEMON - Graph Library

Ignore:
File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r318 r611  
    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/**
     65@defgroup graph_adaptors Adaptor Classes for Graphs
     66@ingroup graphs
     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
     138*/
     139
     140/**
    63141@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    64142@ingroup graphs
    65143\brief Graph types between real graphs and graph adaptors.
    66144
    67 This group describes some graph types between real graphs and graph adaptors.
     145This group contains some graph types between real graphs and graph adaptors.
    68146These classes wrap graphs to give new functionality as the adaptors do it.
    69147On the other hand they are not light-weight structures as the adaptors.
     
    75153\brief Map structures implemented in LEMON.
    76154
    77 This group describes the map structures implemented in LEMON.
     155This group contains the map structures implemented in LEMON.
    78156
    79157LEMON provides several special purpose maps and map adaptors that e.g. combine
     
    88166\brief Special graph-related maps.
    89167
    90 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
     168This group contains maps that are specifically designed to assign
     169values to the nodes and arcs/edges of graphs.
     170
     171If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
     172\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92173*/
    93174
     
    97178\brief Tools to create new maps from existing ones
    98179
    99 This group describes map adaptors that are used to create "implicit"
     180This group contains map adaptors that are used to create "implicit"
    100181maps from other maps.
    101182
    102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
     183Most of them are \ref concepts::ReadMap "read-only maps".
    103184They can make arithmetic and logical operations between one or two maps
    104185(negation, shifting, addition, multiplication, logical 'and', 'or',
     
    160241\brief Two dimensional data storages implemented in LEMON.
    161242
    162 This group describes two dimensional data storages implemented in LEMON.
     243This group contains two dimensional data storages implemented in LEMON.
    163244*/
    164245
     
    168249\brief %Path structures implemented in LEMON.
    169250
    170 This group describes the path structures implemented in LEMON.
     251This group contains the path structures implemented in LEMON.
    171252
    172253LEMON provides flexible data structures to work with paths.
     
    184265\brief Auxiliary data structures implemented in LEMON.
    185266
    186 This group describes some data structures implemented in LEMON in
     267This group contains some data structures implemented in LEMON in
    187268order to make it easier to implement combinatorial algorithms.
    188269*/
     
    190271/**
    191272@defgroup algs Algorithms
    192 \brief This group describes the several algorithms
     273\brief This group contains the several algorithms
    193274implemented in LEMON.
    194275
    195 This group describes the several algorithms
     276This group contains the several algorithms
    196277implemented in LEMON.
    197278*/
     
    202283\brief Common graph search algorithms.
    203284
    204 This group describes the common graph search algorithms like
    205 Breadth-First Search (BFS) and Depth-First Search (DFS).
     285This group contains the common graph search algorithms, namely
     286\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
    206287*/
    207288
     
    211292\brief Algorithms for finding shortest paths.
    212293
    213 This group describes the algorithms for finding shortest paths in graphs.
     294This group contains the algorithms for finding shortest paths in digraphs.
     295
     296 - \ref Dijkstra algorithm for finding shortest paths from a source node
     297   when all arc lengths are non-negative.
     298 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
     299   from a source node when arc lenghts can be either positive or negative,
     300   but the digraph should not contain directed cycles with negative total
     301   length.
     302 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
     303   for solving the \e all-pairs \e shortest \e paths \e problem when arc
     304   lenghts can be either positive or negative, but the digraph should
     305   not contain directed cycles with negative total length.
     306 - \ref Suurballe A successive shortest path algorithm for finding
     307   arc-disjoint paths between two nodes having minimum total length.
    214308*/
    215309
     
    219313\brief Algorithms for finding maximum flows.
    220314
    221 This group describes the algorithms for finding maximum flows and
     315This group contains the algorithms for finding maximum flows and
    222316feasible circulations.
    223317
    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]
     318The \e maximum \e flow \e problem is to find a flow of maximum value between
     319a single source and a single target. Formally, there is a \f$G=(V,A)\f$
     320digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and
     321\f$s, t \in V\f$ source and target nodes.
     322A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the
     323following optimization problem.
     324
     325\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]
     326\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)
     327    \quad \forall u\in V\setminus\{s,t\} \f]
     328\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    234329
    235330LEMON 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.
     331- \ref EdmondsKarp Edmonds-Karp algorithm.
     332- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
     333- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
     334- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
     335
     336In most cases the \ref Preflow "Preflow" algorithm provides the
     337fastest method for computing a maximum flow. All implementations
     338provides functions to also query the minimum cut, which is the dual
     339problem of the maximum flow.
    245340*/
    246341
     
    251346\brief Algorithms for finding minimum cost flows and circulations.
    252347
    253 This group describes the algorithms for finding minimum cost flows and
     348This group contains the algorithms for finding minimum cost flows and
    254349circulations.
     350
     351The \e minimum \e cost \e flow \e problem is to find a feasible flow of
     352minimum total cost from a set of supply nodes to a set of demand nodes
     353in a network with capacity constraints (lower and upper bounds)
     354and arc costs.
     355Formally, let \f$G=(V,A)\f$ be a digraph,
     356\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     357upper bounds for the flow values on the arcs, for which
     358\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
     359\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
     360on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
     361signed supply values of the nodes.
     362If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
     363supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
     364\f$-sup(u)\f$ demand.
     365A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
     366of the following optimization problem.
     367
     368\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
     369\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
     370    sup(u) \quad \forall u\in V \f]
     371\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
     372
     373The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
     374zero or negative in order to have a feasible solution (since the sum
     375of the expressions on the left-hand side of the inequalities is zero).
     376It means that the total demand must be greater or equal to the total
     377supply and all the supplies have to be carried out from the supply nodes,
     378but there could be demands that are not satisfied.
     379If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
     380constraints have to be satisfied with equality, i.e. all demands
     381have to be satisfied and all supplies have to be used.
     382
     383If you need the opposite inequalities in the supply/demand constraints
     384(i.e. the total demand is less than the total supply and all the demands
     385have to be satisfied while there could be supplies that are not used),
     386then you could easily transform the problem to the above form by reversing
     387the direction of the arcs and taking the negative of the supply values
     388(e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
     389However \ref NetworkSimplex algorithm also supports this form directly
     390for the sake of convenience.
     391
     392A feasible solution for this problem can be found using \ref Circulation.
     393
     394Note that the above formulation is actually more general than the usual
     395definition of the minimum cost flow problem, in which strict equalities
     396are required in the supply/demand contraints, i.e.
     397
     398\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
     399    sup(u) \quad \forall u\in V. \f]
     400
     401However if the sum of the supply values is zero, then these two problems
     402are equivalent. So if you need the equality form, you have to ensure this
     403additional contraint for the algorithms.
     404
     405The dual solution of the minimum cost flow problem is represented by node
     406potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
     407An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
     408is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
     409node potentials the following \e complementary \e slackness optimality
     410conditions hold.
     411
     412 - For all \f$uv\in A\f$ arcs:
     413   - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
     414   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
     415   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
     416 - For all \f$u\in V\f$:
     417   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
     418     then \f$\pi(u)=0\f$.
     419 
     420Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
     421\f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
     422\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
     423
     424All algorithms provide dual solution (node potentials) as well
     425if an optimal flow is found.
     426
     427LEMON contains several algorithms for solving minimum cost flow problems.
     428 - \ref NetworkSimplex Primal Network Simplex algorithm with various
     429   pivot strategies.
     430 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
     431   cost scaling.
     432 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
     433   capacity scaling.
     434 - \ref CancelAndTighten The Cancel and Tighten algorithm.
     435 - \ref CycleCanceling Cycle-Canceling algorithms.
     436
     437Most of these implementations support the general inequality form of the
     438minimum cost flow problem, but CancelAndTighten and CycleCanceling
     439only support the equality form due to the primal method they use.
     440
     441In general NetworkSimplex is the most efficient implementation,
     442but in special cases other algorithms could be faster.
     443For example, if the total supply and/or capacities are rather small,
     444CapacityScaling is usually the fastest algorithm (without effective scaling).
    255445*/
    256446
     
    261451\brief Algorithms for finding minimum cut in graphs.
    262452
    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
     453This group contains the algorithms for finding minimum cut in graphs.
     454
     455The \e minimum \e cut \e problem is to find a non-empty and non-complete
     456\f$X\f$ subset of the nodes with minimum overall capacity on
     457outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
     458\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
    269459cut is the \f$X\f$ solution of the next optimization problem:
    270460
    271461\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]
     462    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
    273463
    274464LEMON contains several algorithms related to minimum cut problems:
    275465
    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
     466- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
     467  in directed graphs.
     468- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
     469  calculating minimum cut in undirected graphs.
     470- \ref GomoryHu "Gomory-Hu tree computation" for calculating
     471  all-pairs minimum cut in undirected graphs.
    282472
    283473If 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
     474see the \ref max_flow "maximum flow problem".
     475*/
     476
     477/**
     478@defgroup graph_properties Connectivity and Other Graph Properties
    289479@ingroup algs
    290480\brief Algorithms for discovering the graph properties
    291481
    292 This group describes the algorithms for discovering the graph properties
     482This group contains the algorithms for discovering the graph properties
    293483like connectivity, bipartiteness, euler property, simplicity etc.
    294484
     
    302492\brief Algorithms for planarity checking, embedding and drawing
    303493
    304 This group describes the algorithms for planarity checking,
     494This group contains the algorithms for planarity checking,
    305495embedding and drawing.
    306496
     
    314504\brief Algorithms for finding matchings in graphs and bipartite graphs.
    315505
    316 This group contains algorithm objects and functions to calculate
     506This group contains the algorithms for calculating
    317507matchings in graphs and bipartite graphs. The general matching problem is
    318 finding a subset of the arcs which does not shares common endpoints.
     508finding a subset of the edges for which each node has at most one incident
     509edge.
    319510
    320511There are several different algorithms for calculate matchings in
    321512graphs.  The matching problems in bipartite graphs are generally
    322513easier than in general graphs. The goal of the matching optimization
    323 can be the finding maximum cardinality, maximum weight or minimum cost
     514can be finding maximum cardinality, maximum weight or minimum cost
    324515matching. The search can be constrained to find perfect or
    325516maximum cardinality matching.
    326517
    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
     518The matching algorithms implemented in LEMON:
     519- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
     520  for calculating maximum cardinality matching in bipartite graphs.
     521- \ref PrBipartiteMatching Push-relabel algorithm
     522  for calculating maximum cardinality matching in bipartite graphs.
     523- \ref MaxWeightedBipartiteMatching
     524  Successive shortest path algorithm for calculating maximum weighted
     525  matching and maximum weighted bipartite matching in bipartite graphs.
     526- \ref MinCostMaxBipartiteMatching
     527  Successive shortest path algorithm for calculating minimum cost maximum
     528  matching in bipartite graphs.
     529- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
     530  maximum cardinality matching in general graphs.
     531- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
     532  maximum weighted matching in general graphs.
     533- \ref MaxWeightedPerfectMatching
     534  Edmond's blossom shrinking algorithm for calculating maximum weighted
     535  perfect matching in general graphs.
    347536
    348537\image html bipartite_matching.png
     
    355544\brief Algorithms for finding a minimum cost spanning tree in a graph.
    356545
    357 This group describes the algorithms for finding a minimum cost spanning
    358 tree in a graph
     546This group contains the algorithms for finding a minimum cost spanning
     547tree in a graph.
    359548*/
    360549
     
    364553\brief Auxiliary algorithms implemented in LEMON.
    365554
    366 This group describes some algorithms implemented in LEMON
     555This group contains some algorithms implemented in LEMON
    367556in order to make it easier to implement complex algorithms.
    368557*/
     
    373562\brief Approximation algorithms.
    374563
    375 This group describes the approximation and heuristic algorithms
     564This group contains the approximation and heuristic algorithms
    376565implemented in LEMON.
    377566*/
     
    379568/**
    380569@defgroup gen_opt_group General Optimization Tools
    381 \brief This group describes some general optimization frameworks
     570\brief This group contains some general optimization frameworks
    382571implemented in LEMON.
    383572
    384 This group describes some general optimization frameworks
     573This group contains some general optimization frameworks
    385574implemented in LEMON.
    386575*/
     
    391580\brief Lp and Mip solver interfaces for LEMON.
    392581
    393 This group describes Lp and Mip solver interfaces for LEMON. The
     582This group contains Lp and Mip solver interfaces for LEMON. The
    394583various LP solvers could be used in the same manner with this
    395584interface.
     
    410599\brief Metaheuristics for LEMON library.
    411600
    412 This group describes some metaheuristic optimization tools.
     601This group contains some metaheuristic optimization tools.
    413602*/
    414603
     
    425614\brief Simple basic graph utilities.
    426615
    427 This group describes some simple basic graph utilities.
     616This group contains some simple basic graph utilities.
    428617*/
    429618
     
    433622\brief Tools for development, debugging and testing.
    434623
    435 This group describes several useful tools for development,
     624This group contains several useful tools for development,
    436625debugging and testing.
    437626*/
     
    442631\brief Simple tools for measuring the performance of algorithms.
    443632
    444 This group describes simple tools for measuring the performance
     633This group contains simple tools for measuring the performance
    445634of algorithms.
    446635*/
     
    451640\brief Exceptions defined in LEMON.
    452641
    453 This group describes the exceptions defined in LEMON.
     642This group contains the exceptions defined in LEMON.
    454643*/
    455644
     
    458647\brief Graph Input-Output methods
    459648
    460 This group describes the tools for importing and exporting graphs
     649This group contains the tools for importing and exporting graphs
    461650and graph related data. Now it supports the \ref lgf-format
    462651"LEMON Graph Format", the \c DIMACS format and the encapsulated
     
    465654
    466655/**
    467 @defgroup lemon_io LEMON Input-Output
     656@defgroup lemon_io LEMON Graph Format
    468657@ingroup io_group
    469658\brief Reading and writing LEMON Graph Format.
    470659
    471 This group describes methods for reading and writing
     660This group contains methods for reading and writing
    472661\ref lgf-format "LEMON Graph Format".
    473662*/
     
    478667\brief General \c EPS drawer and graph exporter
    479668
    480 This group describes general \c EPS drawing methods and special
     669This group contains general \c EPS drawing methods and special
    481670graph exporting tools.
     671*/
     672
     673/**
     674@defgroup dimacs_group DIMACS format
     675@ingroup io_group
     676\brief Read and write files in DIMACS format
     677
     678Tools to read a digraph from or write it to a file in DIMACS format data.
     679*/
     680
     681/**
     682@defgroup nauty_group NAUTY Format
     683@ingroup io_group
     684\brief Read \e Nauty format
     685
     686Tool to read graphs from \e Nauty format data.
    482687*/
    483688
     
    486691\brief Skeleton classes and concept checking classes
    487692
    488 This group describes the data/algorithm skeletons and concept checking
     693This group contains the data/algorithm skeletons and concept checking
    489694classes implemented in LEMON.
    490695
     
    516721\brief Skeleton and concept checking classes for graph structures
    517722
    518 This group describes the skeletons and concept checking classes of LEMON's
     723This group contains the skeletons and concept checking classes of LEMON's
    519724graph structures and helper classes used to implement these.
    520725*/
     
    525730\brief Skeleton and concept checking classes for maps
    526731
    527 This group describes the skeletons and concept checking classes of maps.
     732This group contains the skeletons and concept checking classes of maps.
    528733*/
    529734
     
    531736\anchor demoprograms
    532737
    533 @defgroup demos Demo programs
     738@defgroup demos Demo Programs
    534739
    535740Some demo programs are listed here. Their full source codes can be found in
    536741the \c demo subdirectory of the source tree.
    537742
    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
     743In order to compile them, use the <tt>make demo</tt> or the
     744<tt>make check</tt> commands.
     745*/
     746
     747/**
     748@defgroup tools Standalone Utility Applications
    544749
    545750Some utility applications are listed here.
     
    549754*/
    550755
     756}
Note: See TracChangeset for help on using the changeset viewer.