Include CMake related files in the tarball.
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
20 @defgroup datas Data Structures
21 This group describes the several data structures implemented in LEMON.
25 @defgroup graphs Graph Structures
27 \brief Graph structures implemented in LEMON.
29 The implementation of combinatorial algorithms heavily relies on
30 efficient graph implementations. LEMON offers data structures which are
31 planned to be easily used in an experimental phase of implementation studies,
32 and thereafter the program code can be made efficient by small modifications.
34 The most efficient implementation of diverse applications require the
35 usage of different physical graph implementations. These differences
36 appear in the size of graph we require to handle, memory or time usage
37 limitations or in the set of operations through which the graph can be
38 accessed. LEMON provides several physical graph structures to meet
39 the diverging requirements of the possible users. In order to save on
40 running time or on memory usage, some structures may fail to provide
41 some graph features like arc/edge or node deletion.
43 Alteration of standard containers need a very limited number of
44 operations, these together satisfy the everyday requirements.
45 In the case of graph structures, different operations are needed which do
46 not alter the physical graph, but gives another view. If some nodes or
47 arcs have to be hidden or the reverse oriented graph have to be used, then
48 this is the case. It also may happen that in a flow implementation
49 the residual graph can be accessed by another algorithm, or a node-set
50 is to be shrunk for another algorithm.
51 LEMON also provides a variety of graphs for these requirements called
52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
53 in conjunction with other graph representations.
55 You are free to use the graph structure that fit your requirements
56 the best, most graph algorithms and auxiliary data structures can be used
57 with any graph structures.
61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
63 \brief Graph types between real graphs and graph adaptors.
65 This group describes some graph types between real graphs and graph adaptors.
66 These classes wrap graphs to give new functionality as the adaptors do it.
67 On the other hand they are not light-weight structures as the adaptors.
73 \brief Map structures implemented in LEMON.
75 This group describes the map structures implemented in LEMON.
77 LEMON provides several special purpose maps that e.g. combine
78 new maps from existing ones.
82 @defgroup graph_maps Graph Maps
84 \brief Special graph-related maps.
86 This group describes maps that are specifically designed to assign
87 values to the nodes and arcs of graphs.
92 \defgroup map_adaptors Map Adaptors
94 \brief Tools to create new maps from existing ones
96 This group describes map adaptors that are used to create "implicit"
99 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
100 They can make arithmetic and logical operations between one or two maps
101 (negation, shifting, addition, multiplication, logical 'and', 'or',
102 'not' etc.) or e.g. convert a map to another one of different Value type.
104 The typical usage of this classes is passing implicit maps to
105 algorithms. If a function type algorithm is called then the function
106 type map adaptors can be used comfortable. For example let's see the
107 usage of map adaptors with the \c digraphToEps() function.
109 Color nodeColor(int deg) {
111 return Color(0.5, 0.0, 0.5);
112 } else if (deg == 1) {
113 return Color(1.0, 0.5, 1.0);
115 return Color(0.0, 0.0, 0.0);
119 Digraph::NodeMap<int> degree_map(graph);
121 digraphToEps(graph, "graph.eps")
122 .coords(coords).scaleToA4().undirected()
123 .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
126 The \c functorToMap() function makes an \c int to \c Color map from the
127 \e nodeColor() function. The \c composeMap() compose the \e degree_map
128 and the previously created map. The composed map is a proper function to
129 get the color of each node.
131 The usage with class type algorithms is little bit harder. In this
132 case the function type map adaptors can not be used, because the
133 function map adaptors give back temporary objects.
137 typedef Digraph::ArcMap<double> DoubleArcMap;
138 DoubleArcMap length(graph);
139 DoubleArcMap speed(graph);
141 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
142 TimeMap time(length, speed);
144 Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
145 dijkstra.run(source, target);
147 We have a length map and a maximum speed map on the arcs of a digraph.
148 The minimum time to pass the arc can be calculated as the division of
149 the two maps which can be done implicitly with the \c DivMap template
150 class. We use the implicit minimum time map as the length map of the
151 \c Dijkstra algorithm.
155 @defgroup matrices Matrices
157 \brief Two dimensional data storages implemented in LEMON.
159 This group describes two dimensional data storages implemented in LEMON.
163 @defgroup paths Path Structures
165 \brief Path structures implemented in LEMON.
167 This group describes the path structures implemented in LEMON.
169 LEMON provides flexible data structures to work with paths.
170 All of them have similar interfaces and they can be copied easily with
171 assignment operators and copy constructors. This makes it easy and
172 efficient to have e.g. the Dijkstra algorithm to store its result in
173 any kind of path structure.
175 \sa lemon::concepts::Path
180 @defgroup auxdat Auxiliary Data Structures
182 \brief Auxiliary data structures implemented in LEMON.
184 This group describes some data structures implemented in LEMON in
185 order to make it easier to implement combinatorial algorithms.
190 @defgroup algs Algorithms
191 \brief This group describes the several algorithms
192 implemented in LEMON.
194 This group describes the several algorithms
195 implemented in LEMON.
199 @defgroup search Graph Search
201 \brief Common graph search algorithms.
203 This group describes the common graph search algorithms like
204 Breadth-first search (Bfs) and Depth-first search (Dfs).
208 @defgroup shortest_path Shortest Path algorithms
210 \brief Algorithms for finding shortest paths.
212 This group describes the algorithms for finding shortest paths in graphs.
216 @defgroup max_flow Maximum Flow algorithms
218 \brief Algorithms for finding maximum flows.
220 This group describes the algorithms for finding maximum flows and
221 feasible circulations.
223 The maximum flow problem is to find a flow between a single source and
224 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
226 function and given \f$s, t \in V\f$ source and target node. The
227 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
229 \f[ 0 \le f_a \le c_a \f]
230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
231 \qquad \forall u \in V \setminus \{s,t\}\f]
232 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
234 LEMON contains several algorithms for solving maximum flow problems:
235 - \ref lemon::EdmondsKarp "Edmonds-Karp"
236 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
237 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
238 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
240 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
241 fastest method to compute the maximum flow. All impelementations
242 provides functions to query the minimum cut, which is the dual linear
243 programming problem of the maximum flow.
248 @defgroup min_cost_flow Minimum Cost Flow algorithms
251 \brief Algorithms for finding minimum cost flows and circulations.
253 This group describes the algorithms for finding minimum cost flows and
258 @defgroup min_cut Minimum Cut algorithms
261 \brief Algorithms for finding minimum cut in graphs.
263 This group describes the algorithms for finding minimum cut in graphs.
265 The minimum cut problem is to find a non-empty and non-complete
266 \f$X\f$ subset of the vertices with minimum overall capacity on
267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
269 cut is the \f$X\f$ solution of the next optimization problem:
271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
274 LEMON contains several algorithms related to minimum cut problems:
276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
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
283 If you want to find minimum cut just between two distinict nodes,
284 please see the \ref max_flow "Maximum Flow page".
289 @defgroup graph_prop Connectivity and other graph properties
291 \brief Algorithms for discovering the graph properties
293 This group describes the algorithms for discovering the graph properties
294 like connectivity, bipartiteness, euler property, simplicity etc.
296 \image html edge_biconnected_components.png
297 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
301 @defgroup planar Planarity embedding and drawing
303 \brief Algorithms for planarity checking, embedding and drawing
305 This group describes the algorithms for planarity checking,
306 embedding and drawing.
308 \image html planar.png
309 \image latex planar.eps "Plane graph" width=\textwidth
313 @defgroup matching Matching algorithms
315 \brief Algorithms for finding matchings in graphs and bipartite graphs.
317 This group contains algorithm objects and functions to calculate
318 matchings in graphs and bipartite graphs. The general matching problem is
319 finding a subset of the arcs which does not shares common endpoints.
321 There are several different algorithms for calculate matchings in
322 graphs. The matching problems in bipartite graphs are generally
323 easier than in general graphs. The goal of the matching optimization
324 can be the finding maximum cardinality, maximum weight or minimum cost
325 matching. The search can be constrained to find perfect or
326 maximum cardinality matching.
328 Lemon contains the next algorithms:
329 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
330 augmenting path algorithm for calculate maximum cardinality matching in
332 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
333 algorithm for calculate maximum cardinality matching in bipartite graphs
334 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
335 Successive shortest path algorithm for calculate maximum weighted matching
336 and maximum weighted bipartite matching in bipartite graph
337 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
338 Successive shortest path algorithm for calculate minimum cost maximum
339 matching in bipartite graph
340 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
341 for calculate maximum cardinality matching in general graph
342 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
343 shrinking algorithm for calculate maximum weighted matching in general
345 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
346 Edmond's blossom shrinking algorithm for calculate maximum weighted
347 perfect matching in general graph
349 \image html bipartite_matching.png
350 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
355 @defgroup spantree Minimum Spanning Tree algorithms
357 \brief Algorithms for finding a minimum cost spanning tree in a graph.
359 This group describes the algorithms for finding a minimum cost spanning
365 @defgroup auxalg Auxiliary algorithms
367 \brief Auxiliary algorithms implemented in LEMON.
369 This group describes some algorithms implemented in LEMON
370 in order to make it easier to implement complex algorithms.
374 @defgroup approx Approximation algorithms
375 \brief Approximation algorithms.
377 This group describes the approximation and heuristic algorithms
378 implemented in LEMON.
382 @defgroup gen_opt_group General Optimization Tools
383 \brief This group describes some general optimization frameworks
384 implemented in LEMON.
386 This group describes some general optimization frameworks
387 implemented in LEMON.
392 @defgroup lp_group Lp and Mip solvers
393 @ingroup gen_opt_group
394 \brief Lp and Mip solver interfaces for LEMON.
396 This group describes Lp and Mip solver interfaces for LEMON. The
397 various LP solvers could be used in the same manner with this
403 @defgroup lp_utils Tools for Lp and Mip solvers
405 \brief Helper tools to the Lp and Mip solvers.
407 This group adds some helper tools to general optimization framework
408 implemented in LEMON.
412 @defgroup metah Metaheuristics
413 @ingroup gen_opt_group
414 \brief Metaheuristics for LEMON library.
416 This group describes some metaheuristic optimization tools.
420 @defgroup utils Tools and Utilities
421 \brief Tools and utilities for programming in LEMON
423 Tools and utilities for programming in LEMON.
427 @defgroup gutils Basic Graph Utilities
429 \brief Simple basic graph utilities.
431 This group describes some simple basic graph utilities.
435 @defgroup misc Miscellaneous Tools
437 \brief Tools for development, debugging and testing.
439 This group describes several useful tools for development,
440 debugging and testing.
444 @defgroup timecount Time measuring and Counting
446 \brief Simple tools for measuring the performance of algorithms.
448 This group describes simple tools for measuring the performance
453 @defgroup graphbits Tools for Graph Implementation
455 \brief Tools to make it easier to create graphs.
457 This group describes the tools that makes it easier to create graphs and
458 the maps that dynamically update with the graph changes.
462 @defgroup exceptions Exceptions
464 \brief Exceptions defined in LEMON.
466 This group describes the exceptions defined in LEMON.
470 @defgroup io_group Input-Output
471 \brief Graph Input-Output methods
473 This group describes the tools for importing and exporting graphs
474 and graph related data. Now it supports the LEMON format, the
475 \c DIMACS format and the encapsulated postscript (EPS) format.
479 @defgroup lemon_io Lemon Input-Output
481 \brief Reading and writing \ref lgf-format "Lemon Graph Format".
483 This group describes methods for reading and writing
484 \ref lgf-format "Lemon Graph Format".
488 @defgroup eps_io Postscript exporting
490 \brief General \c EPS drawer and graph exporter
492 This group describes general \c EPS drawing methods and special
493 graph exporting tools.
498 @defgroup concept Concepts
499 \brief Skeleton classes and concept checking classes
501 This group describes the data/algorithm skeletons and concept checking
502 classes implemented in LEMON.
504 The purpose of the classes in this group is fourfold.
506 - These classes contain the documentations of the concepts. In order
507 to avoid document multiplications, an implementation of a concept
508 simply refers to the corresponding concept class.
510 - These classes declare every functions, <tt>typedef</tt>s etc. an
511 implementation of the concepts should provide, however completely
512 without implementations and real data structures behind the
513 interface. On the other hand they should provide nothing else. All
514 the algorithms working on a data structure meeting a certain concept
515 should compile with these classes. (Though it will not run properly,
516 of course.) In this way it is easily to check if an algorithm
517 doesn't use any extra feature of a certain implementation.
519 - The concept descriptor classes also provide a <em>checker class</em>
520 that makes it possible to check whether a certain implementation of a
521 concept indeed provides all the required features.
523 - Finally, They can serve as a skeleton of a new implementation of a concept.
529 @defgroup graph_concepts Graph Structure Concepts
531 \brief Skeleton and concept checking classes for graph structures
533 This group describes the skeletons and concept checking classes of LEMON's
534 graph structures and helper classes used to implement these.
538 @defgroup experimental Experimental Structures and Algorithms
539 This group describes some Experimental structures and algorithms.
540 The stuff here is subject to change.
546 @defgroup demos Demo programs
548 Some demo programs are listed here. Their full source codes can be found in
549 the \c demo subdirectory of the source tree.
551 It order to compile them, use <tt>--enable-demo</tt> configure option when
556 @defgroup tools Standalone utility applications
558 Some utility applications are listed here.
560 The standard compilation procedure (<tt>./configure;make</tt>) will compile