COIN-OR::LEMON - Graph Library

source: lemon-1.0/doc/groups.dox @ 326:d3a7603026a2

1.0
Last change on this file since 326:d3a7603026a2 was 326:d3a7603026a2, checked in by Alpar Juttner <alpar@…>, 16 years ago

Merge from trunk

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