COIN-OR::LEMON - Graph Library

source: lemon-1.1/doc/groups.dox @ 189:a63ed81c57ba

Last change on this file since 189:a63ed81c57ba was 156:e561aa7675de, checked in by Alpar Juttner <alpar@…>, 16 years ago

More flexible header names in .lgf + largely improved doc

File size: 17.6 KB
Line 
1/* -*- C++ -*-
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} \qquad \forall u \in V \setminus \{s,t\}\f]
231\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
232
233LEMON contains several algorithms for solving maximum flow problems:
234- \ref lemon::EdmondsKarp "Edmonds-Karp"
235- \ref lemon::Preflow "Goldberg's Preflow algorithm"
236- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
237- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
238
239In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
240fastest method to compute the maximum flow. All impelementations
241provides functions to query the minimum cut, which is the dual linear
242programming problem of the maximum flow.
243
244*/
245
246/**
247@defgroup min_cost_flow Minimum Cost Flow algorithms
248@ingroup algs
249
250\brief Algorithms for finding minimum cost flows and circulations.
251
252This group describes the algorithms for finding minimum cost flows and
253circulations. 
254*/
255
256/**
257@defgroup min_cut Minimum Cut algorithms
258@ingroup algs
259
260\brief Algorithms for finding minimum cut in graphs.
261
262This group describes the algorithms for finding minimum cut in graphs.
263
264The minimum cut problem is to find a non-empty and non-complete
265\f$X\f$ subset of the vertices with minimum overall capacity on
266outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
267\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
268cut is the \f$X\f$ solution of the next optimization problem:
269
270\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
271
272LEMON contains several algorithms related to minimum cut problems:
273
274- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
275  in directed graphs 
276- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
277  calculate minimum cut in undirected graphs
278- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
279  pairs minimum cut in undirected graphs
280
281If you want to find minimum cut just between two distinict nodes,
282please see the \ref max_flow "Maximum Flow page".
283
284*/
285
286/**
287@defgroup graph_prop Connectivity and other graph properties
288@ingroup algs
289\brief Algorithms for discovering the graph properties
290
291This group describes the algorithms for discovering the graph properties
292like connectivity, bipartiteness, euler property, simplicity etc.
293
294\image html edge_biconnected_components.png
295\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
296*/
297
298/**
299@defgroup planar Planarity embedding and drawing
300@ingroup algs
301\brief Algorithms for planarity checking, embedding and drawing
302
303This group describes the algorithms for planarity checking, embedding and drawing.
304
305\image html planar.png
306\image latex planar.eps "Plane graph" width=\textwidth
307*/
308
309/**
310@defgroup matching Matching algorithms
311@ingroup algs
312\brief Algorithms for finding matchings in graphs and bipartite graphs.
313
314This group contains algorithm objects and functions to calculate
315matchings in graphs and bipartite graphs. The general matching problem is
316finding a subset of the arcs which does not shares common endpoints.
317 
318There are several different algorithms for calculate matchings in
319graphs.  The matching problems in bipartite graphs are generally
320easier than in general graphs. The goal of the matching optimization
321can be the finding maximum cardinality, maximum weight or minimum cost
322matching. The search can be constrained to find perfect or
323maximum cardinality matching.
324
325Lemon contains the next algorithms:
326- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
327  augmenting path algorithm for calculate maximum cardinality matching in
328  bipartite graphs
329- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
330  algorithm for calculate maximum cardinality matching in bipartite graphs
331- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
332  Successive shortest path algorithm for calculate maximum weighted matching
333  and maximum weighted bipartite matching in bipartite graph
334- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
335  Successive shortest path algorithm for calculate minimum cost maximum
336  matching in bipartite graph
337- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
338  for calculate maximum cardinality matching in general graph
339- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
340  shrinking algorithm for calculate maximum weighted matching in general
341  graph
342- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
343  Edmond's blossom shrinking algorithm for calculate maximum weighted
344  perfect matching in general graph
345
346\image html bipartite_matching.png
347\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
348
349*/
350
351/**
352@defgroup spantree Minimum Spanning Tree algorithms
353@ingroup algs
354\brief Algorithms for finding a minimum cost spanning tree in a graph.
355
356This group describes the algorithms for finding a minimum cost spanning
357tree in a graph
358*/
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\brief Approximation algorithms.
373
374This group describes the approximation and heuristic algorithms
375implemented in LEMON.
376*/
377
378/**
379@defgroup gen_opt_group General Optimization Tools
380\brief This group describes some general optimization frameworks
381implemented in LEMON.
382
383This group describes some general optimization frameworks
384implemented in LEMON.
385
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/**
400@defgroup lp_utils Tools for Lp and Mip solvers
401@ingroup lp_group
402\brief Helper tools to the Lp and Mip solvers.
403
404This group adds some helper tools to general optimization framework
405implemented in LEMON.
406*/
407
408/**
409@defgroup metah Metaheuristics
410@ingroup gen_opt_group
411\brief Metaheuristics for LEMON library.
412
413This group describes some metaheuristic optimization tools.
414*/
415
416/**
417@defgroup utils Tools and Utilities
418\brief Tools and utilities for programming in LEMON
419
420Tools and utilities for programming in LEMON.
421*/
422
423/**
424@defgroup gutils Basic Graph Utilities
425@ingroup utils
426\brief Simple basic graph utilities.
427
428This group describes some simple basic graph utilities.
429*/
430
431/**
432@defgroup misc Miscellaneous Tools
433@ingroup utils
434\brief Tools for development, debugging and testing.
435
436This group describes several useful tools for development,
437debugging and testing.
438*/
439
440/**
441@defgroup timecount Time measuring and Counting
442@ingroup misc
443\brief Simple tools for measuring the performance of algorithms.
444
445This group describes simple tools for measuring the performance
446of algorithms.
447*/
448
449/**
450@defgroup graphbits Tools for Graph Implementation
451@ingroup utils
452\brief Tools to make it easier to create graphs.
453
454This group describes the tools that makes it easier to create graphs and
455the maps that dynamically update with the graph changes.
456*/
457
458/**
459@defgroup exceptions Exceptions
460@ingroup utils
461\brief Exceptions defined in LEMON.
462
463This group describes the exceptions defined in LEMON.
464*/
465
466/**
467@defgroup io_group Input-Output
468\brief Graph Input-Output methods
469
470This group describes the tools for importing and exporting graphs
471and graph related data. Now it supports the LEMON format, the
472\c DIMACS format and the encapsulated postscript (EPS) format.
473*/
474
475/**
476@defgroup lemon_io Lemon Input-Output
477@ingroup io_group
478\brief Reading and writing LEMON format
479
480This group describes methods for reading and writing LEMON format.
481You can find more about this format on the \ref graph-io-page "Graph Input-Output"
482tutorial pages.
483*/
484
485/**
486@defgroup eps_io Postscript exporting
487@ingroup io_group
488\brief General \c EPS drawer and graph exporter
489
490This group describes general \c EPS drawing methods and special
491graph exporting tools.
492*/
493
494
495/**
496@defgroup concept Concepts
497\brief Skeleton classes and concept checking classes
498
499This group describes the data/algorithm skeletons and concept checking
500classes implemented in LEMON.
501
502The purpose of the classes in this group is fourfold.
503 
504- These classes contain the documentations of the concepts. In order
505  to avoid document multiplications, an implementation of a concept
506  simply refers to the corresponding concept class.
507
508- These classes declare every functions, <tt>typedef</tt>s etc. an
509  implementation of the concepts should provide, however completely
510  without implementations and real data structures behind the
511  interface. On the other hand they should provide nothing else. All
512  the algorithms working on a data structure meeting a certain concept
513  should compile with these classes. (Though it will not run properly,
514  of course.) In this way it is easily to check if an algorithm
515  doesn't use any extra feature of a certain implementation.
516
517- The concept descriptor classes also provide a <em>checker class</em>
518  that makes it possible to check whether a certain implementation of a
519  concept indeed provides all the required features.
520
521- Finally, They can serve as a skeleton of a new implementation of a concept.
522
523*/
524
525
526/**
527@defgroup graph_concepts Graph Structure Concepts
528@ingroup concept
529\brief Skeleton and concept checking classes for graph structures
530
531This group describes the skeletons and concept checking classes of LEMON's
532graph structures and helper classes used to implement these.
533*/
534
535/* --- Unused group
536@defgroup experimental Experimental Structures and Algorithms
537This group describes some Experimental structures and algorithms.
538The stuff here is subject to change.
539*/
540
541/**
542\anchor demoprograms
543
544@defgroup demos Demo programs
545
546Some demo programs are listed here. Their full source codes can be found in
547the \c demo subdirectory of the source tree.
548
549It order to compile them, use <tt>--enable-demo</tt> configure option when
550build the library.
551*/
552
553/**
554@defgroup tools Standalone utility applications
555
556Some utility applications are listed here.
557
558The standard compilation procedure (<tt>./configure;make</tt>) will compile
559them, as well.
560*/
561
Note: See TracBrowser for help on using the repository browser.