doc/groups.dox
 author Peter Kovacs Wed, 29 Apr 2009 03:15:24 +0200 changeset 687 6c408d864fa1 parent 658 85cb3aa71cce child 698 3adf5e2d1e62 child 843 189760a7cdd0 permissions -rw-r--r--
Support negative costs and bounds in NetworkSimplex (#270)

* The interface is reworked to support negative costs and bounds.
- ProblemType and problemType() are renamed to
- ProblemType type is introduced similarly to the LP interface.
- 'bool run()' is replaced by 'ProblemType run()' to handle
unbounded problem instances, as well.
- Add INF public member constant similarly to the LP interface.
 alpar@209  1 /* -*- mode: C++; indent-tabs-mode: nil; -*-  alpar@40  2  *  alpar@209  3  * This file is a part of LEMON, a generic C++ optimization library.  alpar@40  4  *  alpar@463  5  * Copyright (C) 2003-2009  alpar@40  6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport  alpar@40  7  * (Egervary Research Group on Combinatorial Optimization, EGRES).  alpar@40  8  *  alpar@40  9  * Permission to use, modify and distribute this software is granted  alpar@40  10  * provided that this copyright notice appears in all copies. For  alpar@40  11  * precise terms see the accompanying LICENSE file.  alpar@40  12  *  alpar@40  13  * This software is provided "AS IS" with no warranty of any kind,  alpar@40  14  * express or implied, and with no claim as to its suitability for any  alpar@40  15  * purpose.  alpar@40  16  *  alpar@40  17  */  alpar@40  18 kpeter@422  19 namespace lemon {  kpeter@422  20 alpar@40  21 /**  alpar@40  22 @defgroup datas Data Structures  kpeter@606  23 This group contains the several data structures implemented in LEMON.  alpar@40  24 */  alpar@40  25 alpar@40  26 /**  alpar@40  27 @defgroup graphs Graph Structures  alpar@40  28 @ingroup datas  alpar@40  29 \brief Graph structures implemented in LEMON.  alpar@40  30 alpar@209  31 The implementation of combinatorial algorithms heavily relies on  alpar@209  32 efficient graph implementations. LEMON offers data structures which are  alpar@209  33 planned to be easily used in an experimental phase of implementation studies,  alpar@209  34 and thereafter the program code can be made efficient by small modifications.  alpar@40  35 alpar@40  36 The most efficient implementation of diverse applications require the  alpar@40  37 usage of different physical graph implementations. These differences  alpar@40  38 appear in the size of graph we require to handle, memory or time usage  alpar@40  39 limitations or in the set of operations through which the graph can be  alpar@40  40 accessed. LEMON provides several physical graph structures to meet  alpar@40  41 the diverging requirements of the possible users. In order to save on  alpar@40  42 running time or on memory usage, some structures may fail to provide  kpeter@83  43 some graph features like arc/edge or node deletion.  alpar@40  44 alpar@209  45 Alteration of standard containers need a very limited number of  alpar@209  46 operations, these together satisfy the everyday requirements.  alpar@209  47 In the case of graph structures, different operations are needed which do  alpar@209  48 not alter the physical graph, but gives another view. If some nodes or  kpeter@83  49 arcs have to be hidden or the reverse oriented graph have to be used, then  alpar@209  50 this is the case. It also may happen that in a flow implementation  alpar@209  51 the residual graph can be accessed by another algorithm, or a node-set  alpar@209  52 is to be shrunk for another algorithm.  alpar@209  53 LEMON also provides a variety of graphs for these requirements called  alpar@209  54 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only  alpar@209  55 in conjunction with other graph representations.  alpar@40  56 alpar@40  57 You are free to use the graph structure that fit your requirements  alpar@40  58 the best, most graph algorithms and auxiliary data structures can be used  kpeter@314  59 with any graph structure.  kpeter@314  60 kpeter@314  61 See also: \ref graph_concepts "Graph Structure Concepts".  alpar@40  62 */  alpar@40  63 alpar@40  64 /**  kpeter@474  65 @defgroup graph_adaptors Adaptor Classes for Graphs  deba@432  66 @ingroup graphs  kpeter@474  67 \brief Adaptor classes for digraphs and graphs  kpeter@474  68 kpeter@474  69 This group contains several useful adaptor classes for digraphs and graphs.  deba@432  70 deba@432  71 The main parts of LEMON are the different graph structures, generic  kpeter@474  72 graph algorithms, graph concepts, which couple them, and graph  deba@432  73 adaptors. While the previous notions are more or less clear, the  deba@432  74 latter one needs further explanation. Graph adaptors are graph classes  deba@432  75 which serve for considering graph structures in different ways.  deba@432  76 deba@432  77 A short example makes this much clearer. Suppose that we have an  kpeter@474  78 instance \c g of a directed graph type, say ListDigraph and an algorithm  deba@432  79 \code  deba@432  80 template  deba@432  81 int algorithm(const Digraph&);  deba@432  82 \endcode  deba@432  83 is needed to run on the reverse oriented graph. It may be expensive  deba@432  84 (in time or in memory usage) to copy \c g with the reversed  deba@432  85 arcs. In this case, an adaptor class is used, which (according  kpeter@474  86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.  kpeter@474  87 The adaptor uses the original digraph structure and digraph operations when  kpeter@474  88 methods of the reversed oriented graph are called. This means that the adaptor  kpeter@474  89 have minor memory usage, and do not perform sophisticated algorithmic  deba@432  90 actions. The purpose of it is to give a tool for the cases when a  deba@432  91 graph have to be used in a specific alteration. If this alteration is  kpeter@474  92 obtained by a usual construction like filtering the node or the arc set or  deba@432  93 considering a new orientation, then an adaptor is worthwhile to use.  deba@432  94 To come back to the reverse oriented graph, in this situation  deba@432  95 \code  deba@432  96 template class ReverseDigraph;  deba@432  97 \endcode  deba@432  98 template class can be used. The code looks as follows  deba@432  99 \code  deba@432  100 ListDigraph g;  kpeter@474  101 ReverseDigraph rg(g);  deba@432  102 int result = algorithm(rg);  deba@432  103 \endcode  kpeter@474  104 During running the algorithm, the original digraph \c g is untouched.  kpeter@474  105 This techniques give rise to an elegant code, and based on stable  deba@432  106 graph adaptors, complex algorithms can be implemented easily.  deba@432  107 kpeter@474  108 In flow, circulation and matching problems, the residual  deba@432  109 graph is of particular importance. Combining an adaptor implementing  kpeter@474  110 this with shortest path algorithms or minimum mean cycle algorithms,  deba@432  111 a range of weighted and cardinality optimization algorithms can be  deba@432  112 obtained. For other examples, the interested user is referred to the  deba@432  113 detailed documentation of particular adaptors.  deba@432  114 deba@432  115 The behavior of graph adaptors can be very different. Some of them keep  deba@432  116 capabilities of the original graph while in other cases this would be  kpeter@474  117 meaningless. This means that the concepts that they meet depend  kpeter@474  118 on the graph adaptor, and the wrapped graph.  kpeter@474  119 For example, if an arc of a reversed digraph is deleted, this is carried  kpeter@474  120 out by deleting the corresponding arc of the original digraph, thus the  kpeter@474  121 adaptor modifies the original digraph.  kpeter@474  122 However in case of a residual digraph, this operation has no sense.  deba@432  123 deba@432  124 Let us stand one more example here to simplify your work.  kpeter@474  125 ReverseDigraph has constructor  deba@432  126 \code  deba@432  127 ReverseDigraph(Digraph& digraph);  deba@432  128 \endcode  kpeter@474  129 This means that in a situation, when a const %ListDigraph&  deba@432  130 reference to a graph is given, then it have to be instantiated with  kpeter@474  131 Digraph=const %ListDigraph.  deba@432  132 \code  deba@432  133 int algorithm1(const ListDigraph& g) {  kpeter@474  134  ReverseDigraph rg(g);  deba@432  135  return algorithm2(rg);  deba@432  136 }  deba@432  137 \endcode  deba@432  138 */  deba@432  139 deba@432  140 /**  kpeter@50  141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs  alpar@40  142 @ingroup graphs  alpar@40  143 \brief Graph types between real graphs and graph adaptors.  alpar@40  144 kpeter@606  145 This group contains some graph types between real graphs and graph adaptors.  alpar@209  146 These classes wrap graphs to give new functionality as the adaptors do it.  kpeter@50  147 On the other hand they are not light-weight structures as the adaptors.  alpar@40  148 */  alpar@40  149 alpar@40  150 /**  alpar@209  151 @defgroup maps Maps  alpar@40  152 @ingroup datas  kpeter@50  153 \brief Map structures implemented in LEMON.  alpar@40  154 kpeter@606  155 This group contains the map structures implemented in LEMON.  kpeter@50  156 kpeter@314  157 LEMON provides several special purpose maps and map adaptors that e.g. combine  alpar@40  158 new maps from existing ones.  kpeter@314  159 kpeter@314  160 See also: \ref map_concepts "Map Concepts".  alpar@40  161 */  alpar@40  162 alpar@40  163 /**  alpar@209  164 @defgroup graph_maps Graph Maps  alpar@40  165 @ingroup maps  kpeter@83  166 \brief Special graph-related maps.  alpar@40  167 kpeter@606  168 This group contains maps that are specifically designed to assign  kpeter@422  169 values to the nodes and arcs/edges of graphs.  kpeter@422  170 kpeter@422  171 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,  kpeter@422  172 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".  alpar@40  173 */  alpar@40  174 alpar@40  175 /**  alpar@40  176 \defgroup map_adaptors Map Adaptors  alpar@40  177 \ingroup maps  alpar@40  178 \brief Tools to create new maps from existing ones  alpar@40  179 kpeter@606  180 This group contains map adaptors that are used to create "implicit"  kpeter@50  181 maps from other maps.  alpar@40  182 kpeter@422  183 Most of them are \ref concepts::ReadMap "read-only maps".  kpeter@83  184 They can make arithmetic and logical operations between one or two maps  kpeter@83  185 (negation, shifting, addition, multiplication, logical 'and', 'or',  kpeter@83  186 'not' etc.) or e.g. convert a map to another one of different Value type.  alpar@40  187 kpeter@50  188 The typical usage of this classes is passing implicit maps to  alpar@40  189 algorithms. If a function type algorithm is called then the function  alpar@40  190 type map adaptors can be used comfortable. For example let's see the  kpeter@314  191 usage of map adaptors with the \c graphToEps() function.  alpar@40  192 \code  alpar@40  193  Color nodeColor(int deg) {  alpar@40  194  if (deg >= 2) {  alpar@40  195  return Color(0.5, 0.0, 0.5);  alpar@40  196  } else if (deg == 1) {  alpar@40  197  return Color(1.0, 0.5, 1.0);  alpar@40  198  } else {  alpar@40  199  return Color(0.0, 0.0, 0.0);  alpar@40  200  }  alpar@40  201  }  alpar@209  202 kpeter@83  203  Digraph::NodeMap degree_map(graph);  alpar@209  204 kpeter@314  205  graphToEps(graph, "graph.eps")  alpar@40  206  .coords(coords).scaleToA4().undirected()  kpeter@83  207  .nodeColors(composeMap(functorToMap(nodeColor), degree_map))  alpar@40  208  .run();  alpar@209  209 \endcode  kpeter@83  210 The \c functorToMap() function makes an \c int to \c Color map from the  kpeter@314  211 \c nodeColor() function. The \c composeMap() compose the \c degree_map  kpeter@83  212 and the previously created map. The composed map is a proper function to  kpeter@83  213 get the color of each node.  alpar@40  214 alpar@40  215 The usage with class type algorithms is little bit harder. In this  alpar@40  216 case the function type map adaptors can not be used, because the  kpeter@50  217 function map adaptors give back temporary objects.  alpar@40  218 \code  kpeter@83  219  Digraph graph;  kpeter@83  220 kpeter@83  221  typedef Digraph::ArcMap DoubleArcMap;  kpeter@83  222  DoubleArcMap length(graph);  kpeter@83  223  DoubleArcMap speed(graph);  kpeter@83  224 kpeter@83  225  typedef DivMap TimeMap;  alpar@40  226  TimeMap time(length, speed);  alpar@209  227 kpeter@83  228  Dijkstra dijkstra(graph, time);  alpar@40  229  dijkstra.run(source, target);  alpar@40  230 \endcode  kpeter@83  231 We have a length map and a maximum speed map on the arcs of a digraph.  kpeter@83  232 The minimum time to pass the arc can be calculated as the division of  kpeter@83  233 the two maps which can be done implicitly with the \c DivMap template  alpar@40  234 class. We use the implicit minimum time map as the length map of the  alpar@40  235 \c Dijkstra algorithm.  alpar@40  236 */  alpar@40  237 alpar@40  238 /**  alpar@209  239 @defgroup matrices Matrices  alpar@40  240 @ingroup datas  kpeter@50  241 \brief Two dimensional data storages implemented in LEMON.  alpar@40  242 kpeter@606  243 This group contains two dimensional data storages implemented in LEMON.  alpar@40  244 */  alpar@40  245 alpar@40  246 /**  alpar@40  247 @defgroup paths Path Structures  alpar@40  248 @ingroup datas  kpeter@318  249 \brief %Path structures implemented in LEMON.  alpar@40  250 kpeter@606  251 This group contains the path structures implemented in LEMON.  alpar@40  252 kpeter@50  253 LEMON provides flexible data structures to work with paths.  kpeter@50  254 All of them have similar interfaces and they can be copied easily with  kpeter@50  255 assignment operators and copy constructors. This makes it easy and  alpar@40  256 efficient to have e.g. the Dijkstra algorithm to store its result in  alpar@40  257 any kind of path structure.  alpar@40  258 alpar@40  259 \sa lemon::concepts::Path  alpar@40  260 */  alpar@40  261 alpar@40  262 /**  alpar@40  263 @defgroup auxdat Auxiliary Data Structures  alpar@40  264 @ingroup datas  kpeter@50  265 \brief Auxiliary data structures implemented in LEMON.  alpar@40  266 kpeter@606  267 This group contains some data structures implemented in LEMON in  alpar@40  268 order to make it easier to implement combinatorial algorithms.  alpar@40  269 */  alpar@40  270 alpar@40  271 /**  alpar@40  272 @defgroup algs Algorithms  kpeter@606  273 \brief This group contains the several algorithms  alpar@40  274 implemented in LEMON.  alpar@40  275 kpeter@606  276 This group contains the several algorithms  alpar@40  277 implemented in LEMON.  alpar@40  278 */  alpar@40  279 alpar@40  280 /**  alpar@40  281 @defgroup search Graph Search  alpar@40  282 @ingroup algs  kpeter@50  283 \brief Common graph search algorithms.  alpar@40  284 kpeter@606  285 This group contains the common graph search algorithms, namely  kpeter@422  286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).  alpar@40  287 */  alpar@40  288 alpar@40  289 /**  kpeter@314  290 @defgroup shortest_path Shortest Path Algorithms  alpar@40  291 @ingroup algs  kpeter@50  292 \brief Algorithms for finding shortest paths.  alpar@40  293 kpeter@606  294 This group contains the algorithms for finding shortest paths in digraphs.  kpeter@422  295 kpeter@422  296  - \ref Dijkstra algorithm for finding shortest paths from a source node  kpeter@422  297  when all arc lengths are non-negative.  kpeter@422  298  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths  kpeter@422  299  from a source node when arc lenghts can be either positive or negative,  kpeter@422  300  but the digraph should not contain directed cycles with negative total  kpeter@422  301  length.  kpeter@422  302  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms  kpeter@422  303  for solving the \e all-pairs \e shortest \e paths \e problem when arc  kpeter@422  304  lenghts can be either positive or negative, but the digraph should  kpeter@422  305  not contain directed cycles with negative total length.  kpeter@422  306  - \ref Suurballe A successive shortest path algorithm for finding  kpeter@422  307  arc-disjoint paths between two nodes having minimum total length.  alpar@40  308 */  alpar@40  309 alpar@209  310 /**  kpeter@314  311 @defgroup max_flow Maximum Flow Algorithms  alpar@209  312 @ingroup algs  kpeter@50  313 \brief Algorithms for finding maximum flows.  alpar@40  314 kpeter@606  315 This group contains the algorithms for finding maximum flows and  alpar@40  316 feasible circulations.  alpar@40  317 kpeter@422  318 The \e maximum \e flow \e problem is to find a flow of maximum value between  kpeter@422  319 a single source and a single target. Formally, there is a \f$G=(V,A)\f$  kpeter@656  320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and  kpeter@422  321 \f$s, t \in V\f$ source and target nodes.  kpeter@656  322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the  kpeter@422  323 following optimization problem.  alpar@40  324 kpeter@656  325 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]  kpeter@656  326 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)  kpeter@656  327  \quad \forall u\in V\setminus\{s,t\} \f]  kpeter@656  328 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]  alpar@40  329 kpeter@50  330 LEMON contains several algorithms for solving maximum flow problems:  kpeter@422  331 - \ref EdmondsKarp Edmonds-Karp algorithm.  kpeter@422  332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.  kpeter@422  333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.  kpeter@422  334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.  alpar@40  335 kpeter@422  336 In most cases the \ref Preflow "Preflow" algorithm provides the  kpeter@422  337 fastest method for computing a maximum flow. All implementations  kpeter@422  338 provides functions to also query the minimum cut, which is the dual  kpeter@422  339 problem of the maximum flow.  alpar@40  340 */  alpar@40  341 alpar@40  342 /**  kpeter@314  343 @defgroup min_cost_flow Minimum Cost Flow Algorithms  alpar@40  344 @ingroup algs  alpar@40  345 kpeter@50  346 \brief Algorithms for finding minimum cost flows and circulations.  alpar@40  347 kpeter@656  348 This group contains the algorithms for finding minimum cost flows and  alpar@209  349 circulations.  kpeter@422  350 kpeter@422  351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of  kpeter@422  352 minimum total cost from a set of supply nodes to a set of demand nodes  kpeter@656  353 in a network with capacity constraints (lower and upper bounds)  kpeter@656  354 and arc costs.  kpeter@687  355 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,  kpeter@687  356 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and  kpeter@656  357 upper bounds for the flow values on the arcs, for which  kpeter@687  358 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,  kpeter@687  359 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow  kpeter@687  360 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the  kpeter@656  361 signed supply values of the nodes.  kpeter@656  362 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$  kpeter@656  363 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with  kpeter@656  364 \f$-sup(u)\f$ demand.  kpeter@687  365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution  kpeter@656  366 of the following optimization problem.  kpeter@422  367 kpeter@656  368 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]  kpeter@656  369 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq  kpeter@656  370  sup(u) \quad \forall u\in V \f]  kpeter@656  371 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]  kpeter@422  372 kpeter@656  373 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be  kpeter@656  374 zero or negative in order to have a feasible solution (since the sum  kpeter@656  375 of the expressions on the left-hand side of the inequalities is zero).  kpeter@656  376 It means that the total demand must be greater or equal to the total  kpeter@656  377 supply and all the supplies have to be carried out from the supply nodes,  kpeter@656  378 but there could be demands that are not satisfied.  kpeter@656  379 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand  kpeter@656  380 constraints have to be satisfied with equality, i.e. all demands  kpeter@656  381 have to be satisfied and all supplies have to be used.  kpeter@656  382 kpeter@656  383 If you need the opposite inequalities in the supply/demand constraints  kpeter@656  384 (i.e. the total demand is less than the total supply and all the demands  kpeter@656  385 have to be satisfied while there could be supplies that are not used),  kpeter@656  386 then you could easily transform the problem to the above form by reversing  kpeter@656  387 the direction of the arcs and taking the negative of the supply values  kpeter@656  388 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).  kpeter@656  389 However \ref NetworkSimplex algorithm also supports this form directly  kpeter@656  390 for the sake of convenience.  kpeter@656  391 kpeter@656  392 A feasible solution for this problem can be found using \ref Circulation.  kpeter@656  393 kpeter@656  394 Note that the above formulation is actually more general than the usual  kpeter@656  395 definition of the minimum cost flow problem, in which strict equalities  kpeter@656  396 are required in the supply/demand contraints, i.e.  kpeter@656  397 kpeter@656  398 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =  kpeter@656  399  sup(u) \quad \forall u\in V. \f]  kpeter@656  400 kpeter@656  401 However if the sum of the supply values is zero, then these two problems  kpeter@656  402 are equivalent. So if you need the equality form, you have to ensure this  kpeter@656  403 additional contraint for the algorithms.  kpeter@656  404 kpeter@656  405 The dual solution of the minimum cost flow problem is represented by node  kpeter@656  406 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.  kpeter@687  407 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem  kpeter@656  408 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$  kpeter@656  409 node potentials the following \e complementary \e slackness optimality  kpeter@656  410 conditions hold.  kpeter@656  411 kpeter@656  412  - For all \f$uv\in A\f$ arcs:  kpeter@656  413  - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;  kpeter@656  414  - if \f\$lower(uv)typedefs etc. an  kpeter@318  703  implementation of the %concepts should provide, however completely  alpar@40  704  without implementations and real data structures behind the  alpar@40  705  interface. On the other hand they should provide nothing else. All  alpar@40  706  the algorithms working on a data structure meeting a certain concept  alpar@40  707  should compile with these classes. (Though it will not run properly,  alpar@40  708  of course.) In this way it is easily to check if an algorithm  alpar@40  709  doesn't use any extra feature of a certain implementation.  alpar@40  710 alpar@40  711 - The concept descriptor classes also provide a checker class  kpeter@50  712  that makes it possible to check whether a certain implementation of a  alpar@40  713  concept indeed provides all the required features.  alpar@40  714 alpar@40  715 - Finally, They can serve as a skeleton of a new implementation of a concept.  alpar@40  716 */  alpar@40  717 alpar@40  718 /**  alpar@40  719 @defgroup graph_concepts Graph Structure Concepts  alpar@40  720 @ingroup concept  alpar@40  721 \brief Skeleton and concept checking classes for graph structures  alpar@40  722 kpeter@606  723 This group contains the skeletons and concept checking classes of LEMON's  alpar@40  724 graph structures and helper classes used to implement these.  alpar@40  725 */  alpar@40  726 kpeter@314  727 /**  kpeter@314  728 @defgroup map_concepts Map Concepts  kpeter@314  729 @ingroup concept  kpeter@314  730 \brief Skeleton and concept checking classes for maps  kpeter@314  731 kpeter@606  732 This group contains the skeletons and concept checking classes of maps.  alpar@40  733 */  alpar@40  734 alpar@40  735 /**  alpar@40  736 \anchor demoprograms  alpar@40  737 kpeter@422  738 @defgroup demos Demo Programs  alpar@40  739 alpar@40  740 Some demo programs are listed here. Their full source codes can be found in  alpar@40  741 the \c demo subdirectory of the source tree.  alpar@40  742 ladanyi@611  743 In order to compile them, use the make demo or the  ladanyi@611  744 make check commands.  alpar@40  745 */  alpar@40  746 alpar@40  747 /**  kpeter@422  748 @defgroup tools Standalone Utility Applications  alpar@40  749 alpar@209  750 Some utility applications are listed here.  alpar@40  751 alpar@40  752 The standard compilation procedure (./configure;make) will compile  alpar@209  753 them, as well.  alpar@40  754 */  alpar@40  755 kpeter@422  756 }