doc/groups.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 12 Dec 2008 22:59:17 +0100
changeset 449 91fcb8ed4cdc
parent 406 a578265aa8a6
parent 416 76287c8caa26
child 440 88ed40ad0d4f
child 451 fbd6e04acf44
permissions -rw-r--r--
Various bug fixes and code improvements in adaptors.h (#67)

- Fix UndirectorBase::nodeNum().
- Fix UndirectorBase::findEdge().
- Fix OrienterBase::addArc().
- Fix OrienterBase::findArc().
- Improve SplitNodesBase::findArc().
- Add missing notifier() function in UndirectorBase.
- Add missing typedefs for maps (conform to the ReferenceMap concept).
- Add some useful typedefs for graph adaptors.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon {
    20 
    21 /**
    22 @defgroup datas Data Structures
    23 This group describes the several data structures implemented in LEMON.
    24 */
    25 
    26 /**
    27 @defgroup graphs Graph Structures
    28 @ingroup datas
    29 \brief Graph structures implemented in LEMON.
    30 
    31 The implementation of combinatorial algorithms heavily relies on
    32 efficient graph implementations. LEMON offers data structures which are
    33 planned to be easily used in an experimental phase of implementation studies,
    34 and thereafter the program code can be made efficient by small modifications.
    35 
    36 The most efficient implementation of diverse applications require the
    37 usage of different physical graph implementations. These differences
    38 appear in the size of graph we require to handle, memory or time usage
    39 limitations or in the set of operations through which the graph can be
    40 accessed.  LEMON provides several physical graph structures to meet
    41 the diverging requirements of the possible users.  In order to save on
    42 running time or on memory usage, some structures may fail to provide
    43 some graph features like arc/edge or node deletion.
    44 
    45 Alteration of standard containers need a very limited number of
    46 operations, these together satisfy the everyday requirements.
    47 In the case of graph structures, different operations are needed which do
    48 not alter the physical graph, but gives another view. If some nodes or
    49 arcs have to be hidden or the reverse oriented graph have to be used, then
    50 this is the case. It also may happen that in a flow implementation
    51 the residual graph can be accessed by another algorithm, or a node-set
    52 is to be shrunk for another algorithm.
    53 LEMON also provides a variety of graphs for these requirements called
    54 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
    55 in conjunction with other graph representations.
    56 
    57 You are free to use the graph structure that fit your requirements
    58 the best, most graph algorithms and auxiliary data structures can be used
    59 with any graph structure.
    60 
    61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
    62 */
    63 
    64 /**
    65 @defgroup graph_adaptors Adaptor Classes for graphs
    66 @ingroup graphs
    67 \brief This group contains several adaptor classes for digraphs and graphs
    68 
    69 The main parts of LEMON are the different graph structures, generic
    70 graph algorithms, graph concepts which couple these, and graph
    71 adaptors. While the previous notions are more or less clear, the
    72 latter one needs further explanation. Graph adaptors are graph classes
    73 which serve for considering graph structures in different ways.
    74 
    75 A short example makes this much clearer.  Suppose that we have an
    76 instance \c g of a directed graph type say ListDigraph and an algorithm
    77 \code
    78 template <typename Digraph>
    79 int algorithm(const Digraph&);
    80 \endcode
    81 is needed to run on the reverse oriented graph.  It may be expensive
    82 (in time or in memory usage) to copy \c g with the reversed
    83 arcs.  In this case, an adaptor class is used, which (according
    84 to LEMON digraph concepts) works as a digraph.  The adaptor uses the
    85 original digraph structure and digraph operations when methods of the
    86 reversed oriented graph are called.  This means that the adaptor have
    87 minor memory usage, and do not perform sophisticated algorithmic
    88 actions.  The purpose of it is to give a tool for the cases when a
    89 graph have to be used in a specific alteration.  If this alteration is
    90 obtained by a usual construction like filtering the arc-set or
    91 considering a new orientation, then an adaptor is worthwhile to use.
    92 To come back to the reverse oriented graph, in this situation
    93 \code
    94 template<typename Digraph> class ReverseDigraph;
    95 \endcode
    96 template class can be used. The code looks as follows
    97 \code
    98 ListDigraph g;
    99 ReverseDigraph<ListGraph> rg(g);
   100 int result = algorithm(rg);
   101 \endcode
   102 After running the algorithm, the original graph \c g is untouched.
   103 This techniques gives rise to an elegant code, and based on stable
   104 graph adaptors, complex algorithms can be implemented easily.
   105 
   106 In flow, circulation and bipartite matching problems, the residual
   107 graph is of particular importance. Combining an adaptor implementing
   108 this, shortest path algorithms and minimum mean cycle algorithms,
   109 a range of weighted and cardinality optimization algorithms can be
   110 obtained. For other examples, the interested user is referred to the
   111 detailed documentation of particular adaptors.
   112 
   113 The behavior of graph adaptors can be very different. Some of them keep
   114 capabilities of the original graph while in other cases this would be
   115 meaningless. This means that the concepts that they are models of depend
   116 on the graph adaptor, and the wrapped graph(s).
   117 If an arc of \c rg is deleted, this is carried out by deleting the
   118 corresponding arc of \c g, thus the adaptor modifies the original graph.
   119 
   120 But for a residual graph, this operation has no sense.
   121 Let us stand one more example here to simplify your work.
   122 RevGraphAdaptor has constructor
   123 \code
   124 ReverseDigraph(Digraph& digraph);
   125 \endcode
   126 This means that in a situation, when a <tt>const ListDigraph&</tt>
   127 reference to a graph is given, then it have to be instantiated with
   128 <tt>Digraph=const ListDigraph</tt>.
   129 \code
   130 int algorithm1(const ListDigraph& g) {
   131   RevGraphAdaptor<const ListDigraph> rg(g);
   132   return algorithm2(rg);
   133 }
   134 \endcode
   135 */
   136 
   137 /**
   138 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
   139 @ingroup graphs
   140 \brief Graph types between real graphs and graph adaptors.
   141 
   142 This group describes some graph types between real graphs and graph adaptors.
   143 These classes wrap graphs to give new functionality as the adaptors do it.
   144 On the other hand they are not light-weight structures as the adaptors.
   145 */
   146 
   147 /**
   148 @defgroup maps Maps
   149 @ingroup datas
   150 \brief Map structures implemented in LEMON.
   151 
   152 This group describes the map structures implemented in LEMON.
   153 
   154 LEMON provides several special purpose maps and map adaptors that e.g. combine
   155 new maps from existing ones.
   156 
   157 <b>See also:</b> \ref map_concepts "Map Concepts".
   158 */
   159 
   160 /**
   161 @defgroup graph_maps Graph Maps
   162 @ingroup maps
   163 \brief Special graph-related maps.
   164 
   165 This group describes maps that are specifically designed to assign
   166 values to the nodes and arcs/edges of graphs.
   167 
   168 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
   169 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
   170 */
   171 
   172 /**
   173 \defgroup map_adaptors Map Adaptors
   174 \ingroup maps
   175 \brief Tools to create new maps from existing ones
   176 
   177 This group describes map adaptors that are used to create "implicit"
   178 maps from other maps.
   179 
   180 Most of them are \ref concepts::ReadMap "read-only maps".
   181 They can make arithmetic and logical operations between one or two maps
   182 (negation, shifting, addition, multiplication, logical 'and', 'or',
   183 'not' etc.) or e.g. convert a map to another one of different Value type.
   184 
   185 The typical usage of this classes is passing implicit maps to
   186 algorithms.  If a function type algorithm is called then the function
   187 type map adaptors can be used comfortable. For example let's see the
   188 usage of map adaptors with the \c graphToEps() function.
   189 \code
   190   Color nodeColor(int deg) {
   191     if (deg >= 2) {
   192       return Color(0.5, 0.0, 0.5);
   193     } else if (deg == 1) {
   194       return Color(1.0, 0.5, 1.0);
   195     } else {
   196       return Color(0.0, 0.0, 0.0);
   197     }
   198   }
   199 
   200   Digraph::NodeMap<int> degree_map(graph);
   201 
   202   graphToEps(graph, "graph.eps")
   203     .coords(coords).scaleToA4().undirected()
   204     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
   205     .run();
   206 \endcode
   207 The \c functorToMap() function makes an \c int to \c Color map from the
   208 \c nodeColor() function. The \c composeMap() compose the \c degree_map
   209 and the previously created map. The composed map is a proper function to
   210 get the color of each node.
   211 
   212 The usage with class type algorithms is little bit harder. In this
   213 case the function type map adaptors can not be used, because the
   214 function map adaptors give back temporary objects.
   215 \code
   216   Digraph graph;
   217 
   218   typedef Digraph::ArcMap<double> DoubleArcMap;
   219   DoubleArcMap length(graph);
   220   DoubleArcMap speed(graph);
   221 
   222   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
   223   TimeMap time(length, speed);
   224 
   225   Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
   226   dijkstra.run(source, target);
   227 \endcode
   228 We have a length map and a maximum speed map on the arcs of a digraph.
   229 The minimum time to pass the arc can be calculated as the division of
   230 the two maps which can be done implicitly with the \c DivMap template
   231 class. We use the implicit minimum time map as the length map of the
   232 \c Dijkstra algorithm.
   233 */
   234 
   235 /**
   236 @defgroup matrices Matrices
   237 @ingroup datas
   238 \brief Two dimensional data storages implemented in LEMON.
   239 
   240 This group describes two dimensional data storages implemented in LEMON.
   241 */
   242 
   243 /**
   244 @defgroup paths Path Structures
   245 @ingroup datas
   246 \brief %Path structures implemented in LEMON.
   247 
   248 This group describes the path structures implemented in LEMON.
   249 
   250 LEMON provides flexible data structures to work with paths.
   251 All of them have similar interfaces and they can be copied easily with
   252 assignment operators and copy constructors. This makes it easy and
   253 efficient to have e.g. the Dijkstra algorithm to store its result in
   254 any kind of path structure.
   255 
   256 \sa lemon::concepts::Path
   257 */
   258 
   259 /**
   260 @defgroup auxdat Auxiliary Data Structures
   261 @ingroup datas
   262 \brief Auxiliary data structures implemented in LEMON.
   263 
   264 This group describes some data structures implemented in LEMON in
   265 order to make it easier to implement combinatorial algorithms.
   266 */
   267 
   268 /**
   269 @defgroup algs Algorithms
   270 \brief This group describes the several algorithms
   271 implemented in LEMON.
   272 
   273 This group describes the several algorithms
   274 implemented in LEMON.
   275 */
   276 
   277 /**
   278 @defgroup search Graph Search
   279 @ingroup algs
   280 \brief Common graph search algorithms.
   281 
   282 This group describes the common graph search algorithms, namely
   283 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
   284 */
   285 
   286 /**
   287 @defgroup shortest_path Shortest Path Algorithms
   288 @ingroup algs
   289 \brief Algorithms for finding shortest paths.
   290 
   291 This group describes the algorithms for finding shortest paths in digraphs.
   292 
   293  - \ref Dijkstra algorithm for finding shortest paths from a source node
   294    when all arc lengths are non-negative.
   295  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
   296    from a source node when arc lenghts can be either positive or negative,
   297    but the digraph should not contain directed cycles with negative total
   298    length.
   299  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
   300    for solving the \e all-pairs \e shortest \e paths \e problem when arc
   301    lenghts can be either positive or negative, but the digraph should
   302    not contain directed cycles with negative total length.
   303  - \ref Suurballe A successive shortest path algorithm for finding
   304    arc-disjoint paths between two nodes having minimum total length.
   305 */
   306 
   307 /**
   308 @defgroup max_flow Maximum Flow Algorithms
   309 @ingroup algs
   310 \brief Algorithms for finding maximum flows.
   311 
   312 This group describes the algorithms for finding maximum flows and
   313 feasible circulations.
   314 
   315 The \e maximum \e flow \e problem is to find a flow of maximum value between
   316 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
   317 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
   318 \f$s, t \in V\f$ source and target nodes.
   319 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
   320 following optimization problem.
   321 
   322 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
   323 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
   324     \qquad \forall v\in V\setminus\{s,t\} \f]
   325 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
   326 
   327 LEMON contains several algorithms for solving maximum flow problems:
   328 - \ref EdmondsKarp Edmonds-Karp algorithm.
   329 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
   330 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
   331 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
   332 
   333 In most cases the \ref Preflow "Preflow" algorithm provides the
   334 fastest method for computing a maximum flow. All implementations
   335 provides functions to also query the minimum cut, which is the dual
   336 problem of the maximum flow.
   337 */
   338 
   339 /**
   340 @defgroup min_cost_flow Minimum Cost Flow Algorithms
   341 @ingroup algs
   342 
   343 \brief Algorithms for finding minimum cost flows and circulations.
   344 
   345 This group describes the algorithms for finding minimum cost flows and
   346 circulations.
   347 
   348 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
   349 minimum total cost from a set of supply nodes to a set of demand nodes
   350 in a network with capacity constraints and arc costs.
   351 Formally, let \f$G=(V,A)\f$ be a digraph,
   352 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
   353 upper bounds for the flow values on the arcs,
   354 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
   355 on the arcs, and
   356 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
   357 of the nodes.
   358 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
   359 the following optimization problem.
   360 
   361 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
   362 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
   363     supply(v) \qquad \forall v\in V \f]
   364 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
   365 
   366 LEMON contains several algorithms for solving minimum cost flow problems:
   367  - \ref CycleCanceling Cycle-canceling algorithms.
   368  - \ref CapacityScaling Successive shortest path algorithm with optional
   369    capacity scaling.
   370  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
   371    cost scaling.
   372  - \ref NetworkSimplex Primal network simplex algorithm with various
   373    pivot strategies.
   374 */
   375 
   376 /**
   377 @defgroup min_cut Minimum Cut Algorithms
   378 @ingroup algs
   379 
   380 \brief Algorithms for finding minimum cut in graphs.
   381 
   382 This group describes the algorithms for finding minimum cut in graphs.
   383 
   384 The \e minimum \e cut \e problem is to find a non-empty and non-complete
   385 \f$X\f$ subset of the nodes with minimum overall capacity on
   386 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
   387 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   388 cut is the \f$X\f$ solution of the next optimization problem:
   389 
   390 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
   391     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
   392 
   393 LEMON contains several algorithms related to minimum cut problems:
   394 
   395 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   396   in directed graphs.
   397 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
   398   calculating minimum cut in undirected graphs.
   399 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
   400   all-pairs minimum cut in undirected graphs.
   401 
   402 If you want to find minimum cut just between two distinict nodes,
   403 see the \ref max_flow "maximum flow problem".
   404 */
   405 
   406 /**
   407 @defgroup graph_prop Connectivity and Other Graph Properties
   408 @ingroup algs
   409 \brief Algorithms for discovering the graph properties
   410 
   411 This group describes the algorithms for discovering the graph properties
   412 like connectivity, bipartiteness, euler property, simplicity etc.
   413 
   414 \image html edge_biconnected_components.png
   415 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
   416 */
   417 
   418 /**
   419 @defgroup planar Planarity Embedding and Drawing
   420 @ingroup algs
   421 \brief Algorithms for planarity checking, embedding and drawing
   422 
   423 This group describes the algorithms for planarity checking,
   424 embedding and drawing.
   425 
   426 \image html planar.png
   427 \image latex planar.eps "Plane graph" width=\textwidth
   428 */
   429 
   430 /**
   431 @defgroup matching Matching Algorithms
   432 @ingroup algs
   433 \brief Algorithms for finding matchings in graphs and bipartite graphs.
   434 
   435 This group contains algorithm objects and functions to calculate
   436 matchings in graphs and bipartite graphs. The general matching problem is
   437 finding a subset of the arcs which does not shares common endpoints.
   438 
   439 There are several different algorithms for calculate matchings in
   440 graphs.  The matching problems in bipartite graphs are generally
   441 easier than in general graphs. The goal of the matching optimization
   442 can be finding maximum cardinality, maximum weight or minimum cost
   443 matching. The search can be constrained to find perfect or
   444 maximum cardinality matching.
   445 
   446 The matching algorithms implemented in LEMON:
   447 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
   448   for calculating maximum cardinality matching in bipartite graphs.
   449 - \ref PrBipartiteMatching Push-relabel algorithm
   450   for calculating maximum cardinality matching in bipartite graphs.
   451 - \ref MaxWeightedBipartiteMatching
   452   Successive shortest path algorithm for calculating maximum weighted
   453   matching and maximum weighted bipartite matching in bipartite graphs.
   454 - \ref MinCostMaxBipartiteMatching
   455   Successive shortest path algorithm for calculating minimum cost maximum
   456   matching in bipartite graphs.
   457 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
   458   maximum cardinality matching in general graphs.
   459 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
   460   maximum weighted matching in general graphs.
   461 - \ref MaxWeightedPerfectMatching
   462   Edmond's blossom shrinking algorithm for calculating maximum weighted
   463   perfect matching in general graphs.
   464 
   465 \image html bipartite_matching.png
   466 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   467 */
   468 
   469 /**
   470 @defgroup spantree Minimum Spanning Tree Algorithms
   471 @ingroup algs
   472 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   473 
   474 This group describes the algorithms for finding a minimum cost spanning
   475 tree in a graph.
   476 */
   477 
   478 /**
   479 @defgroup auxalg Auxiliary Algorithms
   480 @ingroup algs
   481 \brief Auxiliary algorithms implemented in LEMON.
   482 
   483 This group describes some algorithms implemented in LEMON
   484 in order to make it easier to implement complex algorithms.
   485 */
   486 
   487 /**
   488 @defgroup approx Approximation Algorithms
   489 @ingroup algs
   490 \brief Approximation algorithms.
   491 
   492 This group describes the approximation and heuristic algorithms
   493 implemented in LEMON.
   494 */
   495 
   496 /**
   497 @defgroup gen_opt_group General Optimization Tools
   498 \brief This group describes some general optimization frameworks
   499 implemented in LEMON.
   500 
   501 This group describes some general optimization frameworks
   502 implemented in LEMON.
   503 */
   504 
   505 /**
   506 @defgroup lp_group Lp and Mip Solvers
   507 @ingroup gen_opt_group
   508 \brief Lp and Mip solver interfaces for LEMON.
   509 
   510 This group describes Lp and Mip solver interfaces for LEMON. The
   511 various LP solvers could be used in the same manner with this
   512 interface.
   513 */
   514 
   515 /**
   516 @defgroup lp_utils Tools for Lp and Mip Solvers
   517 @ingroup lp_group
   518 \brief Helper tools to the Lp and Mip solvers.
   519 
   520 This group adds some helper tools to general optimization framework
   521 implemented in LEMON.
   522 */
   523 
   524 /**
   525 @defgroup metah Metaheuristics
   526 @ingroup gen_opt_group
   527 \brief Metaheuristics for LEMON library.
   528 
   529 This group describes some metaheuristic optimization tools.
   530 */
   531 
   532 /**
   533 @defgroup utils Tools and Utilities
   534 \brief Tools and utilities for programming in LEMON
   535 
   536 Tools and utilities for programming in LEMON.
   537 */
   538 
   539 /**
   540 @defgroup gutils Basic Graph Utilities
   541 @ingroup utils
   542 \brief Simple basic graph utilities.
   543 
   544 This group describes some simple basic graph utilities.
   545 */
   546 
   547 /**
   548 @defgroup misc Miscellaneous Tools
   549 @ingroup utils
   550 \brief Tools for development, debugging and testing.
   551 
   552 This group describes several useful tools for development,
   553 debugging and testing.
   554 */
   555 
   556 /**
   557 @defgroup timecount Time Measuring and Counting
   558 @ingroup misc
   559 \brief Simple tools for measuring the performance of algorithms.
   560 
   561 This group describes simple tools for measuring the performance
   562 of algorithms.
   563 */
   564 
   565 /**
   566 @defgroup exceptions Exceptions
   567 @ingroup utils
   568 \brief Exceptions defined in LEMON.
   569 
   570 This group describes the exceptions defined in LEMON.
   571 */
   572 
   573 /**
   574 @defgroup io_group Input-Output
   575 \brief Graph Input-Output methods
   576 
   577 This group describes the tools for importing and exporting graphs
   578 and graph related data. Now it supports the \ref lgf-format
   579 "LEMON Graph Format", the \c DIMACS format and the encapsulated
   580 postscript (EPS) format.
   581 */
   582 
   583 /**
   584 @defgroup lemon_io LEMON Graph Format
   585 @ingroup io_group
   586 \brief Reading and writing LEMON Graph Format.
   587 
   588 This group describes methods for reading and writing
   589 \ref lgf-format "LEMON Graph Format".
   590 */
   591 
   592 /**
   593 @defgroup eps_io Postscript Exporting
   594 @ingroup io_group
   595 \brief General \c EPS drawer and graph exporter
   596 
   597 This group describes general \c EPS drawing methods and special
   598 graph exporting tools.
   599 */
   600 
   601 /**
   602 @defgroup dimacs_group DIMACS format
   603 @ingroup io_group
   604 \brief Read and write files in DIMACS format
   605 
   606 Tools to read a digraph from or write it to a file in DIMACS format data.
   607 */
   608 
   609 /**
   610 @defgroup nauty_group NAUTY Format
   611 @ingroup io_group
   612 \brief Read \e Nauty format
   613 
   614 Tool to read graphs from \e Nauty format data.
   615 */
   616 
   617 /**
   618 @defgroup concept Concepts
   619 \brief Skeleton classes and concept checking classes
   620 
   621 This group describes the data/algorithm skeletons and concept checking
   622 classes implemented in LEMON.
   623 
   624 The purpose of the classes in this group is fourfold.
   625 
   626 - These classes contain the documentations of the %concepts. In order
   627   to avoid document multiplications, an implementation of a concept
   628   simply refers to the corresponding concept class.
   629 
   630 - These classes declare every functions, <tt>typedef</tt>s etc. an
   631   implementation of the %concepts should provide, however completely
   632   without implementations and real data structures behind the
   633   interface. On the other hand they should provide nothing else. All
   634   the algorithms working on a data structure meeting a certain concept
   635   should compile with these classes. (Though it will not run properly,
   636   of course.) In this way it is easily to check if an algorithm
   637   doesn't use any extra feature of a certain implementation.
   638 
   639 - The concept descriptor classes also provide a <em>checker class</em>
   640   that makes it possible to check whether a certain implementation of a
   641   concept indeed provides all the required features.
   642 
   643 - Finally, They can serve as a skeleton of a new implementation of a concept.
   644 */
   645 
   646 /**
   647 @defgroup graph_concepts Graph Structure Concepts
   648 @ingroup concept
   649 \brief Skeleton and concept checking classes for graph structures
   650 
   651 This group describes the skeletons and concept checking classes of LEMON's
   652 graph structures and helper classes used to implement these.
   653 */
   654 
   655 /**
   656 @defgroup map_concepts Map Concepts
   657 @ingroup concept
   658 \brief Skeleton and concept checking classes for maps
   659 
   660 This group describes the skeletons and concept checking classes of maps.
   661 */
   662 
   663 /**
   664 \anchor demoprograms
   665 
   666 @defgroup demos Demo Programs
   667 
   668 Some demo programs are listed here. Their full source codes can be found in
   669 the \c demo subdirectory of the source tree.
   670 
   671 It order to compile them, use <tt>--enable-demo</tt> configure option when
   672 build the library.
   673 */
   674 
   675 /**
   676 @defgroup tools Standalone Utility Applications
   677 
   678 Some utility applications are listed here.
   679 
   680 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   681 them, as well.
   682 */
   683 
   684 }