1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2011
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 You are free to use the graph structure that fit your requirements
44 the best, most graph algorithms and auxiliary data structures can be used
45 with any graph structure.
47 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
53 \brief Map structures implemented in LEMON.
55 This group describes the map structures implemented in LEMON.
57 LEMON provides several special purpose maps and map adaptors that e.g. combine
58 new maps from existing ones.
60 <b>See also:</b> \ref map_concepts "Map Concepts".
64 @defgroup graph_maps Graph Maps
66 \brief Special graph-related maps.
68 This group describes maps that are specifically designed to assign
69 values to the nodes and arcs of graphs.
73 \defgroup map_adaptors Map Adaptors
75 \brief Tools to create new maps from existing ones
77 This group describes map adaptors that are used to create "implicit"
80 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
81 They can make arithmetic and logical operations between one or two maps
82 (negation, shifting, addition, multiplication, logical 'and', 'or',
83 'not' etc.) or e.g. convert a map to another one of different Value type.
85 The typical usage of this classes is passing implicit maps to
86 algorithms. If a function type algorithm is called then the function
87 type map adaptors can be used comfortable. For example let's see the
88 usage of map adaptors with the \c graphToEps() function.
90 Color nodeColor(int deg) {
92 return Color(0.5, 0.0, 0.5);
93 } else if (deg == 1) {
94 return Color(1.0, 0.5, 1.0);
96 return Color(0.0, 0.0, 0.0);
100 Digraph::NodeMap<int> degree_map(graph);
102 graphToEps(graph, "graph.eps")
103 .coords(coords).scaleToA4().undirected()
104 .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
107 The \c functorToMap() function makes an \c int to \c Color map from the
108 \c nodeColor() function. The \c composeMap() compose the \c degree_map
109 and the previously created map. The composed map is a proper function to
110 get the color of each node.
112 The usage with class type algorithms is little bit harder. In this
113 case the function type map adaptors can not be used, because the
114 function map adaptors give back temporary objects.
118 typedef Digraph::ArcMap<double> DoubleArcMap;
119 DoubleArcMap length(graph);
120 DoubleArcMap speed(graph);
122 typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
123 TimeMap time(length, speed);
125 Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
126 dijkstra.run(source, target);
128 We have a length map and a maximum speed map on the arcs of a digraph.
129 The minimum time to pass the arc can be calculated as the division of
130 the two maps which can be done implicitly with the \c DivMap template
131 class. We use the implicit minimum time map as the length map of the
132 \c Dijkstra algorithm.
136 @defgroup paths Path Structures
138 \brief %Path structures implemented in LEMON.
140 This group describes the path structures implemented in LEMON.
142 LEMON provides flexible data structures to work with paths.
143 All of them have similar interfaces and they can be copied easily with
144 assignment operators and copy constructors. This makes it easy and
145 efficient to have e.g. the Dijkstra algorithm to store its result in
146 any kind of path structure.
148 \sa lemon::concepts::Path
152 @defgroup auxdat Auxiliary Data Structures
154 \brief Auxiliary data structures implemented in LEMON.
156 This group describes some data structures implemented in LEMON in
157 order to make it easier to implement combinatorial algorithms.
161 @defgroup algs Algorithms
162 \brief This group describes the several algorithms
163 implemented in LEMON.
165 This group describes the several algorithms
166 implemented in LEMON.
170 @defgroup search Graph Search
172 \brief Common graph search algorithms.
174 This group describes the common graph search algorithms like
175 Breadth-First Search (BFS) and Depth-First Search (DFS).
179 @defgroup shortest_path Shortest Path Algorithms
181 \brief Algorithms for finding shortest paths.
183 This group describes the algorithms for finding shortest paths in graphs.
187 @defgroup spantree Minimum Spanning Tree Algorithms
189 \brief Algorithms for finding a minimum cost spanning tree in a graph.
191 This group describes the algorithms for finding a minimum cost spanning
196 @defgroup utils Tools and Utilities
197 \brief Tools and utilities for programming in LEMON
199 Tools and utilities for programming in LEMON.
203 @defgroup gutils Basic Graph Utilities
205 \brief Simple basic graph utilities.
207 This group describes some simple basic graph utilities.
211 @defgroup misc Miscellaneous Tools
213 \brief Tools for development, debugging and testing.
215 This group describes several useful tools for development,
216 debugging and testing.
220 @defgroup timecount Time Measuring and Counting
222 \brief Simple tools for measuring the performance of algorithms.
224 This group describes simple tools for measuring the performance
229 @defgroup exceptions Exceptions
231 \brief Exceptions defined in LEMON.
233 This group describes the exceptions defined in LEMON.
237 @defgroup io_group Input-Output
238 \brief Graph Input-Output methods
240 This group describes the tools for importing and exporting graphs
241 and graph related data. Now it supports the LEMON format
242 and the encapsulated postscript (EPS) format.
243 postscript (EPS) format.
247 @defgroup lemon_io LEMON Input-Output
249 \brief Reading and writing LEMON Graph Format.
251 This group describes methods for reading and writing
252 \ref lgf-format "LEMON Graph Format".
256 @defgroup eps_io Postscript Exporting
258 \brief General \c EPS drawer and graph exporter
260 This group describes general \c EPS drawing methods and special
261 graph exporting tools.
265 @defgroup concept Concepts
266 \brief Skeleton classes and concept checking classes
268 This group describes the data/algorithm skeletons and concept checking
269 classes implemented in LEMON.
271 The purpose of the classes in this group is fourfold.
273 - These classes contain the documentations of the %concepts. In order
274 to avoid document multiplications, an implementation of a concept
275 simply refers to the corresponding concept class.
277 - These classes declare every functions, <tt>typedef</tt>s etc. an
278 implementation of the %concepts should provide, however completely
279 without implementations and real data structures behind the
280 interface. On the other hand they should provide nothing else. All
281 the algorithms working on a data structure meeting a certain concept
282 should compile with these classes. (Though it will not run properly,
283 of course.) In this way it is easily to check if an algorithm
284 doesn't use any extra feature of a certain implementation.
286 - The concept descriptor classes also provide a <em>checker class</em>
287 that makes it possible to check whether a certain implementation of a
288 concept indeed provides all the required features.
290 - Finally, They can serve as a skeleton of a new implementation of a concept.
294 @defgroup graph_concepts Graph Structure Concepts
296 \brief Skeleton and concept checking classes for graph structures
298 This group describes the skeletons and concept checking classes of LEMON's
299 graph structures and helper classes used to implement these.
303 @defgroup map_concepts Map Concepts
305 \brief Skeleton and concept checking classes for maps
307 This group describes the skeletons and concept checking classes of maps.
313 @defgroup demos Demo programs
315 Some demo programs are listed here. Their full source codes can be found in
316 the \c demo subdirectory of the source tree.
318 It order to compile them, use <tt>--enable-demo</tt> configure option when