COIN-OR::LEMON - Graph Library

source: lemon-1.0/doc/groups.dox @ 320:12626fc94ccf

1.0
Last change on this file since 320:12626fc94ccf was 320:12626fc94ccf, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge from trunk

File size: 9.4 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@ingroup algs
196/**
197@defgroup utils Tools and Utilities
198\brief Tools and utilities for programming in LEMON
199
200Tools and utilities for programming in LEMON.
201*/
202
203/**
204@defgroup gutils Basic Graph Utilities
205@ingroup utils
206\brief Simple basic graph utilities.
207
208This group describes some simple basic graph utilities.
209*/
210
211/**
212@defgroup misc Miscellaneous Tools
213@ingroup utils
214\brief Tools for development, debugging and testing.
215
216This group describes several useful tools for development,
217debugging and testing.
218*/
219
220/**
221@defgroup timecount Time Measuring and Counting
222@ingroup misc
223\brief Simple tools for measuring the performance of algorithms.
224
225This group describes simple tools for measuring the performance
226of algorithms.
227*/
228
229/**
230@defgroup exceptions Exceptions
231@ingroup utils
232\brief Exceptions defined in LEMON.
233
234This group describes the exceptions defined in LEMON.
235*/
236
237/**
238@defgroup io_group Input-Output
239\brief Graph Input-Output methods
240
241This group describes the tools for importing and exporting graphs
242and graph related data. Now it supports the LEMON format
243and the encapsulated postscript (EPS) format.
244postscript (EPS) format.
245*/
246
247/**
248@defgroup lemon_io LEMON Input-Output
249@ingroup io_group
250\brief Reading and writing LEMON Graph Format.
251
252This group describes methods for reading and writing
253\ref lgf-format "LEMON Graph Format".
254*/
255
256/**
257@defgroup eps_io Postscript Exporting
258@ingroup io_group
259\brief General \c EPS drawer and graph exporter
260
261This group describes general \c EPS drawing methods and special
262graph exporting tools.
263*/
264
265/**
266@defgroup concept Concepts
267\brief Skeleton classes and concept checking classes
268
269This group describes the data/algorithm skeletons and concept checking
270classes implemented in LEMON.
271
272The purpose of the classes in this group is fourfold.
273
274- These classes contain the documentations of the concepts. In order
275  to avoid document multiplications, an implementation of a concept
276  simply refers to the corresponding concept class.
277
278- These classes declare every functions, <tt>typedef</tt>s etc. an
279  implementation of the concepts should provide, however completely
280  without implementations and real data structures behind the
281  interface. On the other hand they should provide nothing else. All
282  the algorithms working on a data structure meeting a certain concept
283  should compile with these classes. (Though it will not run properly,
284  of course.) In this way it is easily to check if an algorithm
285  doesn't use any extra feature of a certain implementation.
286
287- The concept descriptor classes also provide a <em>checker class</em>
288  that makes it possible to check whether a certain implementation of a
289  concept indeed provides all the required features.
290
291- Finally, They can serve as a skeleton of a new implementation of a concept.
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
304This group describes the skeletons and concept checking classes of maps.
305/**
306\anchor demoprograms
307
308@defgroup demos Demo programs
309
310Some demo programs are listed here. Their full source codes can be found in
311the \c demo subdirectory of the source tree.
312
313It order to compile them, use <tt>--enable-demo</tt> configure option when
314build the library.
315*/
Note: See TracBrowser for help on using the repository browser.