COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/groups.dox @ 2371:d2a2cb26ecbb

Last change on this file since 2371:d2a2cb26ecbb was 2371:d2a2cb26ecbb, checked in by Balazs Dezso, 13 years ago

Minor fix

File size: 10.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@defgroup graphbits Tools to Make It Easier to Make Graphs
120@ingroup auxdat
121\brief Tools to Make It Easier to Make Graphs.
122
123This group describes the tools that makes it easier to make graphs and
124the maps that dynamically update with the graph changes.
125*/
126
127/**
128@defgroup algs Algorithms
129\brief This group describes the several algorithms
130implemented in LEMON.
131
132This group describes the several algorithms
133implemented in LEMON.
134*/
135
136/**
137@defgroup gutils Basic Graph Utilities
138@ingroup algs
139\brief This group describes some simple basic graph utilities.
140
141This group describes some simple basic graph utilities.
142*/
143
144/**
145@defgroup flowalgs Path and Flow Algorithms
146@ingroup algs
147\brief This group describes the algorithms
148for finding paths and flows in graphs.
149
150This group describes the algorithms
151for finding paths and flows in graphs.
152
153\image html flow.png
154\image latex flow.eps "Graph flow" width=\textwidth
155*/
156
157/**
158@defgroup topology Topology related algorithms
159@ingroup algs
160\brief This group describes the algorithms
161for discover the topology of the graphs.
162
163This group describes the algorithms
164for discover the topology of the graphs.
165
166\image html edge_biconnected_components.png
167\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
168*/
169
170/**
171@defgroup matching Matching algorithms in graphs and bipartite graphs
172@ingroup algs
173\brief This group describes the algorithms
174for find matchings in graphs and bipartite graphs.
175
176This group provides some algorithm objects and function
177to calculate matchings in graphs and bipartite graphs.
178
179\image html bipartite_matching.png
180\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
181
182*/
183
184/**
185@defgroup spantree Minimum Cost Spanning Tree Algorithms
186@ingroup algs
187\brief This group contains the algorithms for finding a minimum cost spanning
188tree in a graph
189
190This group contains the algorithms for finding a minimum cost spanning
191tree in a graph
192*/
193
194
195/**
196@defgroup auxalg Auxiliary Algorithms
197@ingroup algs
198\brief Some algorithms implemented in LEMON.
199
200This group describes the algorithms in LEMON in order to make
201it easier to implement complex algorithms.
202
203*/
204
205/**
206@defgroup gen_opt_group General Optimization Tools
207\brief This group describes some general optimization frameworks
208implemented in LEMON.
209
210This group describes some general optimization frameworks
211implemented in LEMON.
212
213*/
214
215/**
216@defgroup lp_group Lp and Mip solvers
217@ingroup gen_opt_group
218\brief Lp and Mip solver interfaces for LEMON.
219
220This group describes Lp and Mip solver interfaces for LEMON. The
221various LP solvers could be used in the same manner with this
222interface.
223
224*/
225
226/**
227@defgroup lp_utils Tools for Lp and Mip solvers
228@ingroup lp_group
229\brief This group adds some helper tools to the Lp and Mip solvers
230implemented in LEMON.
231
232This group adds some helper tools to general optimization framework
233implemented in LEMON.
234
235*/
236
237/**
238@defgroup metah Metaheuristics
239@ingroup gen_opt_group
240\brief Metaheuristics for LEMON library.
241
242This group contains some metaheuristic optimization tools.
243*/
244
245/**
246@defgroup misc Miscellaneous Tools
247Here you can find several useful tools for development,
248debugging and testing.
249*/
250
251/**
252@defgroup timecount Time measuring and Counting
253@ingroup misc
254Here you can find simple tools for measuring the performance
255of algorithms.
256*/
257
258/**
259@defgroup io_group Input-Output
260\brief Several Graph Input-Output methods
261
262Here you can find tools for importing and exporting graphs
263and graph related data. Now it supports the LEMON format, the
264\c DIMACS format and the encapsulated postscript format.
265*/
266
267/**
268@defgroup lemon_io Lemon Input-Output
269@ingroup io_group
270\brief Reading and writing LEMON format
271
272Methods for reading and writing LEMON format. More about this
273format you can find on the \ref graph-io-page "Graph Input-Output"
274tutorial pages.
275*/
276
277/**
278@defgroup section_io Section readers and writers
279@ingroup lemon_io
280\brief Section readers and writers for lemon Input-Output.
281
282Here you can find which section readers and writers can attach to
283the LemonReader and LemonWriter.
284*/
285
286/**
287@defgroup item_io Item Readers and Writers
288@ingroup lemon_io
289\brief Item readers and writers for lemon Input-Output.
290
291The Input-Output classes can handle more data type by example
292as map or attribute value. Each of these should be written and
293read some way. The module make possible to do this. 
294*/
295
296/**
297@defgroup eps_io Postscript exporting
298@ingroup io_group
299\brief General \c EPS drawer and graph exporter
300
301This group contains general \c EPS drawing methods and special
302graph exporting tools.
303*/
304
305/**
306@defgroup exceptions Exceptions
307This group contains the exceptions thrown by LEMON library
308*/
309
310/**
311@defgroup concept Concepts
312\brief Skeleton classes and concept checking classes
313
314This group describes the data/algorithm skeletons and concept checking
315classes implemented in LEMON.
316
317The purpose of the classes in this group is fourfold.
318 
319- These classes contain the documentations of the concepts. In order
320  to avoid document multiplications, an implementation of a concept
321  simply refers to the corresponding concept class.
322
323- These classes declare every functions, <tt>typedef</tt>s etc. an
324  implementation of the concepts should provide, however completely
325  without implementations and real data structures behind the
326  interface. On the other hand they should provide nothing else. All
327  the algorithms working on a data structure meeting a certain concept
328  should compile with these classes. (Though it will not run properly,
329  of course.) In this way it is easily to check if an algorithm
330  doesn't use any extra feature of a certain implementation.
331
332- The concept descriptor classes also provide a <em>checker class</em>
333  that makes it possible check whether a certain implementation of a
334  concept indeed provides all the required features.
335
336- Finally, They can serve as a skeleton of a new implementation of a concept.
337
338*/
339
340
341/**
342@defgroup graph_concepts Graph Structure Concepts
343@ingroup concept
344\brief Skeleton and concept checking classes for graph structures
345
346This group contains the skeletons and concept checking classes of LEMON's
347graph structures and helper classes used to implement these.
348*/
349
350/* --- Unused group
351@defgroup experimental Experimental Structures and Algorithms
352This group contains some Experimental structures and algorithms.
353The stuff here is subject to change.
354*/
355
356/**
357\anchor demoprograms
358
359@defgroup demos Demo programs
360
361Some demo programs are listed here. Their full source codes can be found in
362the \c demo subdirectory of the source tree.
363
364The standard compilation procedure (<tt>./configure;make</tt>) will compile
365them, as well.
366
367*/
368
Note: See TracBrowser for help on using the repository browser.