COIN-OR::LEMON - Graph Library

source: lemon-1.2/doc/groups.dox @ 347:85820a499b76

Last change on this file since 347:85820a499b76 was 318:1e2d6ca80793, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Doc improvements

File size: 17.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
43Alteration of standard containers need a very limited number of
44operations, these together satisfy the everyday requirements.
45In the case of graph structures, different operations are needed which do
46not alter the physical graph, but gives another view. If some nodes or
47arcs have to be hidden or the reverse oriented graph have to be used, then
48this is the case. It also may happen that in a flow implementation
49the residual graph can be accessed by another algorithm, or a node-set
50is to be shrunk for another algorithm.
51LEMON also provides a variety of graphs for these requirements called
52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
53in conjunction with other graph representations.
54
55You are free to use the graph structure that fit your requirements
56the best, most graph algorithms and auxiliary data structures can be used
57with any graph structure.
58
59<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
60*/
61
62/**
63@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
64@ingroup graphs
65\brief Graph types between real graphs and graph adaptors.
66
67This group describes some graph types between real graphs and graph adaptors.
68These classes wrap graphs to give new functionality as the adaptors do it.
69On the other hand they are not light-weight structures as the adaptors.
70*/
71
72/**
73@defgroup maps Maps
74@ingroup datas
75\brief Map structures implemented in LEMON.
76
77This group describes the map structures implemented in LEMON.
78
79LEMON provides several special purpose maps and map adaptors that e.g. combine
80new maps from existing ones.
81
82<b>See also:</b> \ref map_concepts "Map Concepts".
83*/
84
85/**
86@defgroup graph_maps Graph Maps
87@ingroup maps
88\brief Special graph-related maps.
89
90This group describes maps that are specifically designed to assign
91values to the nodes and arcs of graphs.
92*/
93
94/**
95\defgroup map_adaptors Map Adaptors
96\ingroup maps
97\brief Tools to create new maps from existing ones
98
99This group describes map adaptors that are used to create "implicit"
100maps from other maps.
101
102Most of them are \ref lemon::concepts::ReadMap "read-only maps".
103They can make arithmetic and logical operations between one or two maps
104(negation, shifting, addition, multiplication, logical 'and', 'or',
105'not' etc.) or e.g. convert a map to another one of different Value type.
106
107The typical usage of this classes is passing implicit maps to
108algorithms.  If a function type algorithm is called then the function
109type map adaptors can be used comfortable. For example let's see the
110usage of map adaptors with the \c graphToEps() function.
111\code
112  Color nodeColor(int deg) {
113    if (deg >= 2) {
114      return Color(0.5, 0.0, 0.5);
115    } else if (deg == 1) {
116      return Color(1.0, 0.5, 1.0);
117    } else {
118      return Color(0.0, 0.0, 0.0);
119    }
120  }
121
122  Digraph::NodeMap<int> degree_map(graph);
123
124  graphToEps(graph, "graph.eps")
125    .coords(coords).scaleToA4().undirected()
126    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
127    .run();
128\endcode
129The \c functorToMap() function makes an \c int to \c Color map from the
130\c nodeColor() function. The \c composeMap() compose the \c degree_map
131and the previously created map. The composed map is a proper function to
132get the color of each node.
133
134The usage with class type algorithms is little bit harder. In this
135case the function type map adaptors can not be used, because the
136function map adaptors give back temporary objects.
137\code
138  Digraph graph;
139
140  typedef Digraph::ArcMap<double> DoubleArcMap;
141  DoubleArcMap length(graph);
142  DoubleArcMap speed(graph);
143
144  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
145  TimeMap time(length, speed);
146
147  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
148  dijkstra.run(source, target);
149\endcode
150We have a length map and a maximum speed map on the arcs of a digraph.
151The minimum time to pass the arc can be calculated as the division of
152the two maps which can be done implicitly with the \c DivMap template
153class. We use the implicit minimum time map as the length map of the
154\c Dijkstra algorithm.
155*/
156
157/**
158@defgroup matrices Matrices
159@ingroup datas
160\brief Two dimensional data storages implemented in LEMON.
161
162This group describes two dimensional data storages implemented in LEMON.
163*/
164
165/**
166@defgroup paths Path Structures
167@ingroup datas
168\brief %Path structures implemented in LEMON.
169
170This group describes the path structures implemented in LEMON.
171
172LEMON provides flexible data structures to work with paths.
173All of them have similar interfaces and they can be copied easily with
174assignment operators and copy constructors. This makes it easy and
175efficient to have e.g. the Dijkstra algorithm to store its result in
176any kind of path structure.
177
178\sa lemon::concepts::Path
179*/
180
181/**
182@defgroup auxdat Auxiliary Data Structures
183@ingroup datas
184\brief Auxiliary data structures implemented in LEMON.
185
186This group describes some data structures implemented in LEMON in
187order to make it easier to implement combinatorial algorithms.
188*/
189
190/**
191@defgroup algs Algorithms
192\brief This group describes the several algorithms
193implemented in LEMON.
194
195This group describes the several algorithms
196implemented in LEMON.
197*/
198
199/**
200@defgroup search Graph Search
201@ingroup algs
202\brief Common graph search algorithms.
203
204This group describes the common graph search algorithms like
205Breadth-First Search (BFS) and Depth-First Search (DFS).
206*/
207
208/**
209@defgroup shortest_path Shortest Path Algorithms
210@ingroup algs
211\brief Algorithms for finding shortest paths.
212
213This group describes the algorithms for finding shortest paths in graphs.
214*/
215
216/**
217@defgroup max_flow Maximum Flow Algorithms
218@ingroup algs
219\brief Algorithms for finding maximum flows.
220
221This group describes the algorithms for finding maximum flows and
222feasible circulations.
223
224The maximum flow problem is to find a flow between a single source and
225a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
226directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
227function and given \f$s, t \in V\f$ source and target node. The
228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
229
230\f[ 0 \le f_a \le c_a \f]
231\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
232\qquad \forall u \in V \setminus \{s,t\}\f]
233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
234
235LEMON contains several algorithms for solving maximum flow problems:
236- \ref lemon::EdmondsKarp "Edmonds-Karp"
237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
240
241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
242fastest method to compute the maximum flow. All impelementations
243provides functions to query the minimum cut, which is the dual linear
244programming problem of the maximum flow.
245*/
246
247/**
248@defgroup min_cost_flow Minimum Cost Flow Algorithms
249@ingroup algs
250
251\brief Algorithms for finding minimum cost flows and circulations.
252
253This group describes the algorithms for finding minimum cost flows and
254circulations.
255*/
256
257/**
258@defgroup min_cut Minimum Cut Algorithms
259@ingroup algs
260
261\brief Algorithms for finding minimum cut in graphs.
262
263This group describes the algorithms for finding minimum cut in graphs.
264
265The minimum cut problem is to find a non-empty and non-complete
266\f$X\f$ subset of the vertices with minimum overall capacity on
267outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
268\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
269cut is the \f$X\f$ solution of the next optimization problem:
270
271\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
272\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
273
274LEMON contains several algorithms related to minimum cut problems:
275
276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
277  in directed graphs
278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
279  calculate minimum cut in undirected graphs
280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
281  pairs minimum cut in undirected graphs
282
283If you want to find minimum cut just between two distinict nodes,
284please see the \ref max_flow "Maximum Flow page".
285*/
286
287/**
288@defgroup graph_prop Connectivity and Other Graph Properties
289@ingroup algs
290\brief Algorithms for discovering the graph properties
291
292This group describes the algorithms for discovering the graph properties
293like connectivity, bipartiteness, euler property, simplicity etc.
294
295\image html edge_biconnected_components.png
296\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
297*/
298
299/**
300@defgroup planar Planarity Embedding and Drawing
301@ingroup algs
302\brief Algorithms for planarity checking, embedding and drawing
303
304This group describes the algorithms for planarity checking,
305embedding and drawing.
306
307\image html planar.png
308\image latex planar.eps "Plane graph" width=\textwidth
309*/
310
311/**
312@defgroup matching Matching Algorithms
313@ingroup algs
314\brief Algorithms for finding matchings in graphs and bipartite graphs.
315
316This group contains algorithm objects and functions to calculate
317matchings in graphs and bipartite graphs. The general matching problem is
318finding a subset of the arcs which does not shares common endpoints.
319
320There are several different algorithms for calculate matchings in
321graphs.  The matching problems in bipartite graphs are generally
322easier than in general graphs. The goal of the matching optimization
323can be the finding maximum cardinality, maximum weight or minimum cost
324matching. The search can be constrained to find perfect or
325maximum cardinality matching.
326
327LEMON contains the next algorithms:
328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
329  augmenting path algorithm for calculate maximum cardinality matching in
330  bipartite graphs
331- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
332  algorithm for calculate maximum cardinality matching in bipartite graphs
333- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
334  Successive shortest path algorithm for calculate maximum weighted matching
335  and maximum weighted bipartite matching in bipartite graph
336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
337  Successive shortest path algorithm for calculate minimum cost maximum
338  matching in bipartite graph
339- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
340  for calculate maximum cardinality matching in general graph
341- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
342  shrinking algorithm for calculate maximum weighted matching in general
343  graph
344- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
345  Edmond's blossom shrinking algorithm for calculate maximum weighted
346  perfect matching in general graph
347
348\image html bipartite_matching.png
349\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
350*/
351
352/**
353@defgroup spantree Minimum Spanning Tree Algorithms
354@ingroup algs
355\brief Algorithms for finding a minimum cost spanning tree in a graph.
356
357This group describes the algorithms for finding a minimum cost spanning
358tree in a graph
359*/
360
361/**
362@defgroup auxalg Auxiliary Algorithms
363@ingroup algs
364\brief Auxiliary algorithms implemented in LEMON.
365
366This group describes some algorithms implemented in LEMON
367in order to make it easier to implement complex algorithms.
368*/
369
370/**
371@defgroup approx Approximation Algorithms
372@ingroup algs
373\brief Approximation algorithms.
374
375This group describes the approximation and heuristic algorithms
376implemented in LEMON.
377*/
378
379/**
380@defgroup gen_opt_group General Optimization Tools
381\brief This group describes some general optimization frameworks
382implemented in LEMON.
383
384This group describes some general optimization frameworks
385implemented in LEMON.
386*/
387
388/**
389@defgroup lp_group Lp and Mip Solvers
390@ingroup gen_opt_group
391\brief Lp and Mip solver interfaces for LEMON.
392
393This group describes Lp and Mip solver interfaces for LEMON. The
394various LP solvers could be used in the same manner with this
395interface.
396*/
397
398/**
399@defgroup lp_utils Tools for Lp and Mip Solvers
400@ingroup lp_group
401\brief Helper tools to the Lp and Mip solvers.
402
403This group adds some helper tools to general optimization framework
404implemented in LEMON.
405*/
406
407/**
408@defgroup metah Metaheuristics
409@ingroup gen_opt_group
410\brief Metaheuristics for LEMON library.
411
412This group describes some metaheuristic optimization tools.
413*/
414
415/**
416@defgroup utils Tools and Utilities
417\brief Tools and utilities for programming in LEMON
418
419Tools and utilities for programming in LEMON.
420*/
421
422/**
423@defgroup gutils Basic Graph Utilities
424@ingroup utils
425\brief Simple basic graph utilities.
426
427This group describes some simple basic graph utilities.
428*/
429
430/**
431@defgroup misc Miscellaneous Tools
432@ingroup utils
433\brief Tools for development, debugging and testing.
434
435This group describes several useful tools for development,
436debugging and testing.
437*/
438
439/**
440@defgroup timecount Time Measuring and Counting
441@ingroup misc
442\brief Simple tools for measuring the performance of algorithms.
443
444This group describes simple tools for measuring the performance
445of algorithms.
446*/
447
448/**
449@defgroup exceptions Exceptions
450@ingroup utils
451\brief Exceptions defined in LEMON.
452
453This group describes the exceptions defined in LEMON.
454*/
455
456/**
457@defgroup io_group Input-Output
458\brief Graph Input-Output methods
459
460This group describes the tools for importing and exporting graphs
461and graph related data. Now it supports the \ref lgf-format
462"LEMON Graph Format", the \c DIMACS format and the encapsulated
463postscript (EPS) format.
464*/
465
466/**
467@defgroup lemon_io LEMON Input-Output
468@ingroup io_group
469\brief Reading and writing LEMON Graph Format.
470
471This group describes methods for reading and writing
472\ref lgf-format "LEMON Graph Format".
473*/
474
475/**
476@defgroup eps_io Postscript Exporting
477@ingroup io_group
478\brief General \c EPS drawer and graph exporter
479
480This group describes general \c EPS drawing methods and special
481graph exporting tools.
482*/
483
484/**
485@defgroup concept Concepts
486\brief Skeleton classes and concept checking classes
487
488This group describes the data/algorithm skeletons and concept checking
489classes implemented in LEMON.
490
491The purpose of the classes in this group is fourfold.
492
493- These classes contain the documentations of the %concepts. In order
494  to avoid document multiplications, an implementation of a concept
495  simply refers to the corresponding concept class.
496
497- These classes declare every functions, <tt>typedef</tt>s etc. an
498  implementation of the %concepts should provide, however completely
499  without implementations and real data structures behind the
500  interface. On the other hand they should provide nothing else. All
501  the algorithms working on a data structure meeting a certain concept
502  should compile with these classes. (Though it will not run properly,
503  of course.) In this way it is easily to check if an algorithm
504  doesn't use any extra feature of a certain implementation.
505
506- The concept descriptor classes also provide a <em>checker class</em>
507  that makes it possible to check whether a certain implementation of a
508  concept indeed provides all the required features.
509
510- Finally, They can serve as a skeleton of a new implementation of a concept.
511*/
512
513/**
514@defgroup graph_concepts Graph Structure Concepts
515@ingroup concept
516\brief Skeleton and concept checking classes for graph structures
517
518This group describes the skeletons and concept checking classes of LEMON's
519graph structures and helper classes used to implement these.
520*/
521
522/**
523@defgroup map_concepts Map Concepts
524@ingroup concept
525\brief Skeleton and concept checking classes for maps
526
527This group describes the skeletons and concept checking classes of maps.
528*/
529
530/**
531\anchor demoprograms
532
533@defgroup demos Demo programs
534
535Some demo programs are listed here. Their full source codes can be found in
536the \c demo subdirectory of the source tree.
537
538It order to compile them, use <tt>--enable-demo</tt> configure option when
539build the library.
540*/
541
542/**
543@defgroup tools Standalone utility applications
544
545Some utility applications are listed here.
546
547The standard compilation procedure (<tt>./configure;make</tt>) will compile
548them, as well.
549*/
550
Note: See TracBrowser for help on using the repository browser.