COIN-OR::LEMON - Graph Library

source: lemon-1.0/doc/groups.dox @ 224:b246072978e8

Last change on this file since 224:b246072978e8 was 210:81cfc04531e8, checked in by Alpar Juttner <alpar@…>, 16 years ago

Remove long lines (from all but one file)

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