3 @defgroup datas Data Structures
4 This group describes the several graph structures implemented in LEMON.
8 @defgroup graphs Graph Structures
10 \brief Graph structures implemented in LEMON.
12 The implementation of combinatorial algorithms heavily relies on
13 efficient graph implementations. LEMON offers data structures which are
14 planned to be easily used in an experimental phase of implementation studies,
15 and thereafter the program code can be made efficient by small modifications.
17 The most efficient implementation of diverse applications require the
18 usage of different physical graph implementations. These differences
19 appear in the size of graph we require to handle, memory or time usage
20 limitations or in the set of operations through which the graph can be
21 accessed. LEMON provides several physical graph structures to meet
22 the diverging requirements of the possible users. In order to save on
23 running time or on memory usage, some structures may fail to provide
24 some graph features like edge or node deletion.
26 Alteration of standard containers need a very limited number of
27 operations, these together satisfy the everyday requirements.
28 In the case of graph structures, different operations are needed which do
29 not alter the physical graph, but gives another view. If some nodes or
30 edges have to be hidden or the reverse oriented graph have to be used, then
31 this is the case. It also may happen that in a flow implementation
32 the residual graph can be accessed by another algorithm, or a node-set
33 is to be shrunk for another algorithm.
34 LEMON also provides a variety of graphs for these requirements called
35 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
36 in conjunction with other graph representation.
38 You are free to use the graph structure that fit your requirements
39 the best, most graph algorithms and auxiliary data structures can be used
40 with any graph structures.
44 @defgroup semi_adaptors Semi-Adaptors Classes for Graphs
46 \brief Graph types between real graphs and graph adaptors.
48 Graph types between real graphs and graph adaptors. These classes wrap
49 graphs to give new functionality as the adaptors do it. On the other
50 hand they are not light-weight structures as the adaptors.
56 \brief Some special purpose map to make life easier.
58 LEMON provides several special maps that e.g. combine
59 new maps from existing ones.
63 @defgroup graph_maps Graph Maps
65 \brief Special Graph-Related Maps.
67 These maps are specifically designed to assign values to the nodes and edges of
73 \defgroup map_adaptors Map Adaptors
75 \brief Tools to create new maps from existing ones
77 Map adaptors are used to create "implicit" maps from other maps.
79 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
80 make arithmetic operations between one or two maps (negation, scaling,
81 addition, multiplication etc.) or e.g. convert a map to another one
82 of different Value type.
86 @defgroup matrices Matrices
88 \brief Two dimensional data storages.
90 Two dimensional data storages.
94 @defgroup paths Path Structures
96 \brief Path structures implemented in LEMON.
98 LEMON provides flexible data structures
101 All of them have the same interface, especially they can be built or extended
102 using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
103 algorithm to store its result in any kind of path structure.
105 \sa lemon::concepts::Path
110 @defgroup auxdat Auxiliary Data Structures
112 \brief Some data structures implemented in LEMON.
114 This group describes the data structures implemented in LEMON in
115 order to make it easier to implement combinatorial algorithms.
120 @defgroup algs Algorithms
121 \brief This group describes the several algorithms
122 implemented in LEMON.
124 This group describes the several algorithms
125 implemented in LEMON.
129 @defgroup search Graph Search
131 \brief This group contains the common graph
134 This group contains the common graph
135 search algorithms like Bfs and Dfs.
139 @defgroup shortest_path Shortest Path algorithms
141 \brief This group describes the algorithms
142 for finding shortest paths.
144 This group describes the algorithms for finding shortest paths in
150 @defgroup max_flow Maximum Flow algorithms
152 \brief This group describes the algorithms for finding maximum flows.
154 This group describes the algorithms for finding maximum flows.
157 \image latex flow.eps "Graph flow" width=\textwidth
161 @defgroup min_cost_flow Minimum Cost Flow algorithms
164 \brief This group describes the algorithms
165 for finding minimum cost flows and circulations.
167 This group describes the algorithms for finding minimum cost flows and
172 @defgroup min_cut Minimum Cut algorithms
174 \brief This group describes the algorithms
175 for finding minimum cut in graphs.
177 This group describes the algorithms
178 for finding minimum cut in graphs.
182 @defgroup topology Topology related algorithms
184 \brief This group describes the algorithms
185 for discover the topology of the graphs.
187 This group describes the algorithms
188 for discover the topology of the graphs.
190 \image html edge_biconnected_components.png
191 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
195 @defgroup matching Matching algorithms
197 \brief This group describes the algorithms
198 for find matchings in graphs and bipartite graphs.
200 This group provides some algorithm objects and function
201 to calculate matchings in graphs and bipartite graphs.
203 \image html bipartite_matching.png
204 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
209 @defgroup spantree Minimum Spanning Tree algorithms
211 \brief This group contains the algorithms for finding a minimum cost spanning
214 This group contains the algorithms for finding a minimum cost spanning
220 @defgroup auxalg Auxiliary algorithms
222 \brief Some algorithms implemented in LEMON.
224 This group describes the algorithms in LEMON in order to make
225 it easier to implement complex algorithms.
229 @defgroup approx Approximation algorithms
230 \brief Approximation algorithms
232 Approximation and heuristic algorithms
236 @defgroup gen_opt_group General Optimization Tools
237 \brief This group describes some general optimization frameworks
238 implemented in LEMON.
240 This group describes some general optimization frameworks
241 implemented in LEMON.
246 @defgroup lp_group Lp and Mip solvers
247 @ingroup gen_opt_group
248 \brief Lp and Mip solver interfaces for LEMON.
250 This group describes Lp and Mip solver interfaces for LEMON. The
251 various LP solvers could be used in the same manner with this
257 @defgroup lp_utils Tools for Lp and Mip solvers
259 \brief This group adds some helper tools to the Lp and Mip solvers
260 implemented in LEMON.
262 This group adds some helper tools to general optimization framework
263 implemented in LEMON.
267 @defgroup metah Metaheuristics
268 @ingroup gen_opt_group
269 \brief Metaheuristics for LEMON library.
271 This group contains some metaheuristic optimization tools.
275 @defgroup utils Tools and Utilities
276 \brief Tools and Utilities for Programming in LEMON
278 Tools and Utilities for Programming in LEMON
282 @defgroup gutils Basic Graph Utilities
284 \brief This group describes some simple basic graph utilities.
286 This group describes some simple basic graph utilities.
290 @defgroup misc Miscellaneous Tools
292 Here you can find several useful tools for development,
293 debugging and testing.
298 @defgroup timecount Time measuring and Counting
300 Here you can find simple tools for measuring the performance
305 @defgroup graphbits Tools for Graph Implementation
307 \brief Tools to Make It Easier to Make Graphs.
309 This group describes the tools that makes it easier to make graphs and
310 the maps that dynamically update with the graph changes.
314 @defgroup exceptions Exceptions
316 This group contains the exceptions thrown by LEMON library
320 @defgroup io_group Input-Output
321 \brief Several Graph Input-Output methods
323 Here you can find tools for importing and exporting graphs
324 and graph related data. Now it supports the LEMON format, the
325 \c DIMACS format and the encapsulated postscript format.
329 @defgroup lemon_io Lemon Input-Output
331 \brief Reading and writing LEMON format
333 Methods for reading and writing LEMON format. More about this
334 format you can find on the \ref graph-io-page "Graph Input-Output"
339 @defgroup section_io Section readers and writers
341 \brief Section readers and writers for lemon Input-Output.
343 Here you can find which section readers and writers can attach to
344 the LemonReader and LemonWriter.
348 @defgroup item_io Item Readers and Writers
350 \brief Item readers and writers for lemon Input-Output.
352 The Input-Output classes can handle more data type by example
353 as map or attribute value. Each of these should be written and
354 read some way. The module make possible to do this.
358 @defgroup eps_io Postscript exporting
360 \brief General \c EPS drawer and graph exporter
362 This group contains general \c EPS drawing methods and special
363 graph exporting tools.
368 @defgroup concept Concepts
369 \brief Skeleton classes and concept checking classes
371 This group describes the data/algorithm skeletons and concept checking
372 classes implemented in LEMON.
374 The purpose of the classes in this group is fourfold.
376 - These classes contain the documentations of the concepts. In order
377 to avoid document multiplications, an implementation of a concept
378 simply refers to the corresponding concept class.
380 - These classes declare every functions, <tt>typedef</tt>s etc. an
381 implementation of the concepts should provide, however completely
382 without implementations and real data structures behind the
383 interface. On the other hand they should provide nothing else. All
384 the algorithms working on a data structure meeting a certain concept
385 should compile with these classes. (Though it will not run properly,
386 of course.) In this way it is easily to check if an algorithm
387 doesn't use any extra feature of a certain implementation.
389 - The concept descriptor classes also provide a <em>checker class</em>
390 that makes it possible check whether a certain implementation of a
391 concept indeed provides all the required features.
393 - Finally, They can serve as a skeleton of a new implementation of a concept.
399 @defgroup graph_concepts Graph Structure Concepts
401 \brief Skeleton and concept checking classes for graph structures
403 This group contains the skeletons and concept checking classes of LEMON's
404 graph structures and helper classes used to implement these.
408 @defgroup experimental Experimental Structures and Algorithms
409 This group contains some Experimental structures and algorithms.
410 The stuff here is subject to change.
416 @defgroup demos Demo programs
418 Some demo programs are listed here. Their full source codes can be found in
419 the \c demo subdirectory of the source tree.
421 The standard compilation procedure (<tt>./configure;make</tt>) will compile