COIN-OR::LEMON - Graph Library

source: lemon-1.2/doc/groups.dox @ 406:a578265aa8a6

Last change on this file since 406:a578265aa8a6 was 406:a578265aa8a6, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Improvements in groups.dox (#188)

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