COIN-OR::LEMON - Graph Library

source: lemon/doc/groups.dox @ 325:3a2e0692eaae

1.0
Last change on this file since 325:3a2e0692eaae was 325:3a2e0692eaae, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Remove references to tools that have not been ported yet (ticket #119)

File size: 9.1 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2008
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 data 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 arc/edge or node deletion.
42
43You are free to use the graph structure that fit your requirements
44the best, most graph algorithms and auxiliary data structures can be used
45with any graph structures.
46*/
47
48/**
49@defgroup maps Maps
50@ingroup datas
51\brief Map structures implemented in LEMON.
52
53This group describes the map structures implemented in LEMON.
54
55LEMON provides several special purpose maps that e.g. combine
56new maps from existing ones.
57*/
58
59/**
60@defgroup graph_maps Graph Maps
61@ingroup maps
62\brief Special graph-related maps.
63
64This group describes maps that are specifically designed to assign
65values to the nodes and arcs of graphs.
66*/
67
68
69/**
70\defgroup map_adaptors Map Adaptors
71\ingroup maps
72\brief Tools to create new maps from existing ones
73
74This group describes map adaptors that are used to create "implicit"
75maps from other maps.
76
77Most of them are \ref lemon::concepts::ReadMap "read-only maps".
78They can make arithmetic and logical operations between one or two maps
79(negation, shifting, addition, multiplication, logical 'and', 'or',
80'not' etc.) or e.g. convert a map to another one of different Value type.
81
82The typical usage of this classes is passing implicit maps to
83algorithms.  If a function type algorithm is called then the function
84type map adaptors can be used comfortable. For example let's see the
85usage of map adaptors with the \c digraphToEps() function.
86\code
87  Color nodeColor(int deg) {
88    if (deg >= 2) {
89      return Color(0.5, 0.0, 0.5);
90    } else if (deg == 1) {
91      return Color(1.0, 0.5, 1.0);
92    } else {
93      return Color(0.0, 0.0, 0.0);
94    }
95  }
96
97  Digraph::NodeMap<int> degree_map(graph);
98
99  digraphToEps(graph, "graph.eps")
100    .coords(coords).scaleToA4().undirected()
101    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
102    .run();
103\endcode
104The \c functorToMap() function makes an \c int to \c Color map from the
105\e nodeColor() function. The \c composeMap() compose the \e degree_map
106and the previously created map. The composed map is a proper function to
107get the color of each node.
108
109The usage with class type algorithms is little bit harder. In this
110case the function type map adaptors can not be used, because the
111function map adaptors give back temporary objects.
112\code
113  Digraph graph;
114
115  typedef Digraph::ArcMap<double> DoubleArcMap;
116  DoubleArcMap length(graph);
117  DoubleArcMap speed(graph);
118
119  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
120  TimeMap time(length, speed);
121
122  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
123  dijkstra.run(source, target);
124\endcode
125We have a length map and a maximum speed map on the arcs of a digraph.
126The minimum time to pass the arc can be calculated as the division of
127the two maps which can be done implicitly with the \c DivMap template
128class. We use the implicit minimum time map as the length map of the
129\c Dijkstra algorithm.
130*/
131
132/**
133@defgroup paths Path Structures
134@ingroup datas
135\brief Path structures implemented in LEMON.
136
137This group describes the path structures implemented in LEMON.
138
139LEMON provides flexible data structures to work with paths.
140All of them have similar interfaces and they can be copied easily with
141assignment operators and copy constructors. This makes it easy and
142efficient to have e.g. the Dijkstra algorithm to store its result in
143any kind of path structure.
144
145\sa lemon::concepts::Path
146
147*/
148
149/**
150@defgroup auxdat Auxiliary Data Structures
151@ingroup datas
152\brief Auxiliary data structures implemented in LEMON.
153
154This group describes some data structures implemented in LEMON in
155order to make it easier to implement combinatorial algorithms.
156*/
157
158
159/**
160@defgroup algs Algorithms
161\brief This group describes the several algorithms
162implemented in LEMON.
163
164This group describes the several algorithms
165implemented in LEMON.
166*/
167
168/**
169@defgroup search Graph Search
170@ingroup algs
171\brief Common graph search algorithms.
172
173This group describes the common graph search algorithms like
174Breadth-first search (Bfs) and Depth-first search (Dfs).
175*/
176
177/**
178@defgroup shortest_path Shortest Path algorithms
179@ingroup algs
180\brief Algorithms for finding shortest paths.
181
182This group describes the algorithms for finding shortest paths in graphs.
183*/
184
185/**
186@defgroup spantree Minimum Spanning Tree algorithms
187@ingroup algs
188\brief Algorithms for finding a minimum cost spanning tree in a graph.
189
190This group describes the algorithms for finding a minimum cost spanning
191tree in a graph
192*/
193
194/**
195@defgroup utils Tools and Utilities
196\brief Tools and utilities for programming in LEMON
197
198Tools and utilities for programming in LEMON.
199*/
200
201/**
202@defgroup gutils Basic Graph Utilities
203@ingroup utils
204\brief Simple basic graph utilities.
205
206This group describes some simple basic graph utilities.
207*/
208
209/**
210@defgroup misc Miscellaneous Tools
211@ingroup utils
212\brief Tools for development, debugging and testing.
213
214This group describes several useful tools for development,
215debugging and testing.
216*/
217
218/**
219@defgroup timecount Time measuring and Counting
220@ingroup misc
221\brief Simple tools for measuring the performance of algorithms.
222
223This group describes simple tools for measuring the performance
224of algorithms.
225*/
226
227/**
228@defgroup exceptions Exceptions
229@ingroup utils
230\brief Exceptions defined in LEMON.
231
232This group describes the exceptions defined in LEMON.
233*/
234
235/**
236@defgroup io_group Input-Output
237\brief Graph Input-Output methods
238
239This group describes the tools for importing and exporting graphs
240and graph related data. Now it supports the LEMON format
241and the encapsulated postscript (EPS) format.
242*/
243
244/**
245@defgroup lemon_io LEMON Input-Output
246@ingroup io_group
247\brief Reading and writing \ref lgf-format "LEMON Graph Format".
248
249This group describes methods for reading and writing
250\ref lgf-format "LEMON Graph Format".
251*/
252
253/**
254@defgroup eps_io Postscript exporting
255@ingroup io_group
256\brief General \c EPS drawer and graph exporter
257
258This group describes general \c EPS drawing methods and special
259graph exporting tools.
260*/
261
262
263/**
264@defgroup concept Concepts
265\brief Skeleton classes and concept checking classes
266
267This group describes the data/algorithm skeletons and concept checking
268classes implemented in LEMON.
269
270The purpose of the classes in this group is fourfold.
271
272- These classes contain the documentations of the concepts. In order
273  to avoid document multiplications, an implementation of a concept
274  simply refers to the corresponding concept class.
275
276- These classes declare every functions, <tt>typedef</tt>s etc. an
277  implementation of the concepts should provide, however completely
278  without implementations and real data structures behind the
279  interface. On the other hand they should provide nothing else. All
280  the algorithms working on a data structure meeting a certain concept
281  should compile with these classes. (Though it will not run properly,
282  of course.) In this way it is easily to check if an algorithm
283  doesn't use any extra feature of a certain implementation.
284
285- The concept descriptor classes also provide a <em>checker class</em>
286  that makes it possible to check whether a certain implementation of a
287  concept indeed provides all the required features.
288
289- Finally, They can serve as a skeleton of a new implementation of a concept.
290
291*/
292
293
294/**
295@defgroup graph_concepts Graph Structure Concepts
296@ingroup concept
297\brief Skeleton and concept checking classes for graph structures
298
299This group describes the skeletons and concept checking classes of LEMON's
300graph structures and helper classes used to implement these.
301*/
302
303/**
304\anchor demoprograms
305
306@defgroup demos Demo programs
307
308Some demo programs are listed here. Their full source codes can be found in
309the \c demo subdirectory of the source tree.
310
311It order to compile them, use <tt>--enable-demo</tt> configure option when
312build the library.
313*/
Note: See TracBrowser for help on using the repository browser.