COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/groups.dox @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 13 years ago

Happy New Year to all source files!

File size: 12.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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/**
20@defgroup datas Data Structures
21This group describes the several graph structures implemented in LEMON.
22*/
23
24/**
25@defgroup graphs Graph Structures
26@ingroup datas
27\brief Graph structures implemented in LEMON.
28
29The implementation of combinatorial algorithms heavily relies on
30efficient graph implementations. LEMON offers data structures which are
31planned to be easily used in an experimental phase of implementation studies,
32and thereafter the program code can be made efficient by small modifications.
33
34The most efficient implementation of diverse applications require the
35usage of different physical graph implementations. These differences
36appear in the size of graph we require to handle, memory or time usage
37limitations or in the set of operations through which the graph can be
38accessed.  LEMON provides several physical graph structures to meet
39the diverging requirements of the possible users.  In order to save on
40running time or on memory usage, some structures may fail to provide
41some graph features like edge or node deletion.
42
43Alteration of standard containers need a very limited number of
44operations, these together satisfy the everyday requirements.
45In the case of graph structures, different operations are needed which do
46not alter the physical graph, but gives another view. If some nodes or
47edges have to be hidden or the reverse oriented graph have to be used, then
48this is the case. It also may happen that in a flow implementation
49the residual graph can be accessed by another algorithm, or a node-set
50is to be shrunk for another algorithm.
51LEMON also provides a variety of graphs for these requirements called
52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
53in conjunction with other graph representation.
54
55You are free to use the graph structure that fit your requirements
56the best, most graph algorithms and auxiliary data structures can be used
57with any graph structures.
58*/
59
60/**
61@defgroup semi_adaptors Semi-Adaptors Classes for Graphs
62@ingroup graphs
63\brief Graph types between real graphs and graph adaptors.
64
65Graph types between real graphs and graph adaptors. These classes wrap
66graphs to give new functionality as the adaptors do it. On the other
67hand they are not light-weight structures as the adaptors.
68*/
69
70/**
71@defgroup maps Maps
72@ingroup datas
73\brief Some special purpose map to make life easier.
74
75LEMON provides several special maps that e.g. combine
76new maps from existing ones.
77*/
78
79/**
80@defgroup graph_maps Graph Maps
81@ingroup maps
82\brief Special Graph-Related Maps.
83
84These maps are specifically designed to assign values to the nodes and edges of
85graphs.
86*/
87
88
89/**
90\defgroup map_adaptors Map Adaptors
91\ingroup maps
92\brief Tools to create new maps from existing ones
93
94Map adaptors are used to create "implicit" maps from other maps.
95
96Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can
97make arithmetic operations between one or two maps (negation, scaling,
98addition, multiplication etc.) or e.g. convert a map to another one
99of different Value type.
100*/
101
102/**
103@defgroup matrices Matrices
104@ingroup datas
105\brief Two dimensional data storages.
106
107Two dimensional data storages.
108*/
109
110/**
111@defgroup paths Path Structures
112@ingroup datas
113\brief Path structures implemented in LEMON.
114
115LEMON provides flexible data structures
116to work with paths.
117
118All of them have the same interface, especially they can be built or extended
119using a standard Builder subclass. This make is easy to have e.g. the Dijkstra
120algorithm to store its result in any kind of path structure.
121
122\sa lemon::concepts::Path
123
124*/
125
126/**
127@defgroup auxdat Auxiliary Data Structures
128@ingroup datas
129\brief Some data structures implemented in LEMON.
130
131This group describes the data structures implemented in LEMON in
132order to make it easier to implement combinatorial algorithms.
133*/
134
135
136/**
137@defgroup algs Algorithms
138\brief This group describes the several algorithms
139implemented in LEMON.
140
141This group describes the several algorithms
142implemented in LEMON.
143*/
144
145/**
146@defgroup search Graph Search
147@ingroup algs
148\brief This group contains the common graph
149search algorithms.
150
151This group contains the common graph
152search algorithms like Bfs and Dfs.
153*/
154
155/**
156@defgroup shortest_path Shortest Path algorithms
157@ingroup algs
158\brief This group describes the algorithms
159for finding shortest paths.
160
161This group describes the algorithms for finding shortest paths in
162graphs.
163
164*/
165
166/**
167@defgroup max_flow Maximum Flow algorithms
168@ingroup algs
169\brief This group describes the algorithms for finding maximum flows.
170
171This group describes the algorithms for finding maximum flows and
172feasible circulations.
173
174\image html flow.png
175\image latex flow.eps "Graph flow" width=\textwidth
176*/
177
178/**
179@defgroup min_cost_flow Minimum Cost Flow algorithms
180@ingroup algs
181
182\brief This group describes the algorithms
183for finding minimum cost flows and circulations.
184
185This group describes the algorithms for finding minimum cost flows and
186circulations. 
187*/
188
189/**
190@defgroup min_cut Minimum Cut algorithms
191@ingroup algs
192\brief This group describes the algorithms
193for finding minimum cut in graphs.
194
195This group describes the algorithms
196for finding minimum cut in graphs.
197*/
198
199/**
200@defgroup topology Topology related algorithms
201@ingroup algs
202\brief This group describes the algorithms
203for discover the topology of the graphs.
204
205This group describes the algorithms
206for discover the topology of the graphs.
207
208\image html edge_biconnected_components.png
209\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
210*/
211
212/**
213@defgroup matching Matching algorithms
214@ingroup algs
215\brief This group describes the algorithms
216for find matchings in graphs and bipartite graphs.
217
218This group provides some algorithm objects and function
219to calculate matchings in graphs and bipartite graphs.
220
221\image html bipartite_matching.png
222\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
223
224*/
225
226/**
227@defgroup spantree Minimum Spanning Tree algorithms
228@ingroup algs
229\brief This group contains the algorithms for finding a minimum cost spanning
230tree in a graph
231
232This group contains the algorithms for finding a minimum cost spanning
233tree in a graph
234*/
235
236
237/**
238@defgroup auxalg Auxiliary algorithms
239@ingroup algs
240\brief Some algorithms implemented in LEMON.
241
242This group describes the algorithms in LEMON in order to make
243it easier to implement complex algorithms.
244*/
245
246/**
247@defgroup approx Approximation algorithms
248\brief Approximation algorithms
249
250Approximation and heuristic algorithms
251*/
252
253/**
254@defgroup gen_opt_group General Optimization Tools
255\brief This group describes some general optimization frameworks
256implemented in LEMON.
257
258This group describes some general optimization frameworks
259implemented in LEMON.
260
261*/
262
263/**
264@defgroup lp_group Lp and Mip solvers
265@ingroup gen_opt_group
266\brief Lp and Mip solver interfaces for LEMON.
267
268This group describes Lp and Mip solver interfaces for LEMON. The
269various LP solvers could be used in the same manner with this
270interface.
271
272*/
273
274/**
275@defgroup lp_utils Tools for Lp and Mip solvers
276@ingroup lp_group
277\brief This group adds some helper tools to the Lp and Mip solvers
278implemented in LEMON.
279
280This group adds some helper tools to general optimization framework
281implemented in LEMON.
282*/
283
284/**
285@defgroup metah Metaheuristics
286@ingroup gen_opt_group
287\brief Metaheuristics for LEMON library.
288
289This group contains some metaheuristic optimization tools.
290*/
291
292/**
293@defgroup utils Tools and Utilities
294\brief Tools and Utilities for Programming in LEMON
295
296Tools and Utilities for Programming in LEMON
297*/
298
299/**
300@defgroup gutils Basic Graph Utilities
301@ingroup utils
302\brief This group describes some simple basic graph utilities.
303
304This group describes some simple basic graph utilities.
305*/
306
307/**
308@defgroup misc Miscellaneous Tools
309@ingroup utils
310Here you can find several useful tools for development,
311debugging and testing.
312*/
313
314
315/**
316@defgroup timecount Time measuring and Counting
317@ingroup misc
318Here you can find simple tools for measuring the performance
319of algorithms.
320*/
321
322/**
323@defgroup graphbits Tools for Graph Implementation
324@ingroup utils
325\brief Tools to Make It Easier to Make Graphs.
326
327This group describes the tools that makes it easier to make graphs and
328the maps that dynamically update with the graph changes.
329*/
330
331/**
332@defgroup exceptions Exceptions
333@ingroup utils
334This group contains the exceptions thrown by LEMON library
335*/
336
337/**
338@defgroup io_group Input-Output
339\brief Several Graph Input-Output methods
340
341Here you can find tools for importing and exporting graphs
342and graph related data. Now it supports the LEMON format, the
343\c DIMACS format and the encapsulated postscript format.
344*/
345
346/**
347@defgroup lemon_io Lemon Input-Output
348@ingroup io_group
349\brief Reading and writing LEMON format
350
351Methods for reading and writing LEMON format. More about this
352format you can find on the \ref graph-io-page "Graph Input-Output"
353tutorial pages.
354*/
355
356/**
357@defgroup section_io Section readers and writers
358@ingroup lemon_io
359\brief Section readers and writers for lemon Input-Output.
360
361Here you can find which section readers and writers can attach to
362the LemonReader and LemonWriter.
363*/
364
365/**
366@defgroup item_io Item Readers and Writers
367@ingroup lemon_io
368\brief Item readers and writers for lemon Input-Output.
369
370The Input-Output classes can handle more data type by example
371as map or attribute value. Each of these should be written and
372read some way. The module make possible to do this. 
373*/
374
375/**
376@defgroup eps_io Postscript exporting
377@ingroup io_group
378\brief General \c EPS drawer and graph exporter
379
380This group contains general \c EPS drawing methods and special
381graph exporting tools.
382*/
383
384
385/**
386@defgroup concept Concepts
387\brief Skeleton classes and concept checking classes
388
389This group describes the data/algorithm skeletons and concept checking
390classes implemented in LEMON.
391
392The purpose of the classes in this group is fourfold.
393 
394- These classes contain the documentations of the concepts. In order
395  to avoid document multiplications, an implementation of a concept
396  simply refers to the corresponding concept class.
397
398- These classes declare every functions, <tt>typedef</tt>s etc. an
399  implementation of the concepts should provide, however completely
400  without implementations and real data structures behind the
401  interface. On the other hand they should provide nothing else. All
402  the algorithms working on a data structure meeting a certain concept
403  should compile with these classes. (Though it will not run properly,
404  of course.) In this way it is easily to check if an algorithm
405  doesn't use any extra feature of a certain implementation.
406
407- The concept descriptor classes also provide a <em>checker class</em>
408  that makes it possible check whether a certain implementation of a
409  concept indeed provides all the required features.
410
411- Finally, They can serve as a skeleton of a new implementation of a concept.
412
413*/
414
415
416/**
417@defgroup graph_concepts Graph Structure Concepts
418@ingroup concept
419\brief Skeleton and concept checking classes for graph structures
420
421This group contains the skeletons and concept checking classes of LEMON's
422graph structures and helper classes used to implement these.
423*/
424
425/* --- Unused group
426@defgroup experimental Experimental Structures and Algorithms
427This group contains some Experimental structures and algorithms.
428The stuff here is subject to change.
429*/
430
431/**
432\anchor demoprograms
433
434@defgroup demos Demo programs
435
436Some demo programs are listed here. Their full source codes can be found in
437the \c demo subdirectory of the source tree.
438
439The standard compilation procedure (<tt>./configure;make</tt>) will compile
440them, as well.
441
442*/
443
Note: See TracBrowser for help on using the repository browser.