COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/groups.dox @ 2376:0ed45a6c74b1

Last change on this file since 2376:0ed45a6c74b1 was 2376:0ed45a6c74b1, checked in by Balazs Dezso, 18 years ago

Reorganization of the modules and groups

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