COIN-OR::LEMON - Graph Library

source: lemon-1.0/doc/groups.dox @ 420:e24922c56bc2

Last change on this file since 420:e24922c56bc2 was 325:1e2d6ca80793, checked in by Peter Kovacs <kpeter@…>, 15 years ago

Doc improvements

File size: 17.4 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[40]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[40]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
[50]21This group describes the several data structures implemented in LEMON.
[40]22*/
23
24/**
25@defgroup graphs Graph Structures
26@ingroup datas
27\brief Graph structures implemented in LEMON.
28
[209]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.
[40]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
[83]41some graph features like arc/edge or node deletion.
[40]42
[209]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
[83]47arcs have to be hidden or the reverse oriented graph have to be used, then
[209]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.
[40]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
[318]57with any graph structure.
58
59<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
[40]60*/
61
62/**
[50]63@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
[40]64@ingroup graphs
65\brief Graph types between real graphs and graph adaptors.
66
[50]67This group describes some graph types between real graphs and graph adaptors.
[209]68These classes wrap graphs to give new functionality as the adaptors do it.
[50]69On the other hand they are not light-weight structures as the adaptors.
[40]70*/
71
72/**
[209]73@defgroup maps Maps
[40]74@ingroup datas
[50]75\brief Map structures implemented in LEMON.
[40]76
[50]77This group describes the map structures implemented in LEMON.
78
[318]79LEMON provides several special purpose maps and map adaptors that e.g. combine
[40]80new maps from existing ones.
[318]81
82<b>See also:</b> \ref map_concepts "Map Concepts".
[40]83*/
84
85/**
[209]86@defgroup graph_maps Graph Maps
[40]87@ingroup maps
[83]88\brief Special graph-related maps.
[40]89
[50]90This group describes maps that are specifically designed to assign
[83]91values to the nodes and arcs of graphs.
[40]92*/
93
94/**
95\defgroup map_adaptors Map Adaptors
96\ingroup maps
97\brief Tools to create new maps from existing ones
98
[50]99This group describes map adaptors that are used to create "implicit"
100maps from other maps.
[40]101
[83]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.
[40]106
[50]107The typical usage of this classes is passing implicit maps to
[40]108algorithms.  If a function type algorithm is called then the function
109type map adaptors can be used comfortable. For example let's see the
[318]110usage of map adaptors with the \c graphToEps() function.
[40]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  }
[209]121
[83]122  Digraph::NodeMap<int> degree_map(graph);
[209]123
[318]124  graphToEps(graph, "graph.eps")
[40]125    .coords(coords).scaleToA4().undirected()
[83]126    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
[40]127    .run();
[209]128\endcode
[83]129The \c functorToMap() function makes an \c int to \c Color map from the
[318]130\c nodeColor() function. The \c composeMap() compose the \c degree_map
[83]131and the previously created map. The composed map is a proper function to
132get the color of each node.
[40]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
[50]136function map adaptors give back temporary objects.
[40]137\code
[83]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;
[40]145  TimeMap time(length, speed);
[209]146
[83]147  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
[40]148  dijkstra.run(source, target);
149\endcode
[83]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
[40]153class. We use the implicit minimum time map as the length map of the
154\c Dijkstra algorithm.
155*/
156
157/**
[209]158@defgroup matrices Matrices
[40]159@ingroup datas
[50]160\brief Two dimensional data storages implemented in LEMON.
[40]161
[50]162This group describes two dimensional data storages implemented in LEMON.
[40]163*/
164
165/**
166@defgroup paths Path Structures
167@ingroup datas
[325]168\brief %Path structures implemented in LEMON.
[40]169
[50]170This group describes the path structures implemented in LEMON.
[40]171
[50]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
[40]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
[50]184\brief Auxiliary data structures implemented in LEMON.
[40]185
[50]186This group describes some data structures implemented in LEMON in
[40]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
[50]202\brief Common graph search algorithms.
[40]203
[209]204This group describes the common graph search algorithms like
[318]205Breadth-First Search (BFS) and Depth-First Search (DFS).
[40]206*/
207
208/**
[318]209@defgroup shortest_path Shortest Path Algorithms
[40]210@ingroup algs
[50]211\brief Algorithms for finding shortest paths.
[40]212
[50]213This group describes the algorithms for finding shortest paths in graphs.
[40]214*/
215
[209]216/**
[318]217@defgroup max_flow Maximum Flow Algorithms
[209]218@ingroup algs
[50]219\brief Algorithms for finding maximum flows.
[40]220
221This group describes the algorithms for finding maximum flows and
222feasible circulations.
223
[50]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$
[40]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
[50]228maximum flow is the \f$f_a\f$ solution of the next optimization problem:
[40]229
230\f[ 0 \le f_a \le c_a \f]
[210]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]
[40]233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
234
[50]235LEMON contains several algorithms for solving maximum flow problems:
[209]236- \ref lemon::EdmondsKarp "Edmonds-Karp"
[40]237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
[50]238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
[40]239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
240
[50]241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
[40]242fastest method to compute the maximum flow. All impelementations
[50]243provides functions to query the minimum cut, which is the dual linear
244programming problem of the maximum flow.
[40]245*/
246
247/**
[318]248@defgroup min_cost_flow Minimum Cost Flow Algorithms
[40]249@ingroup algs
250
[50]251\brief Algorithms for finding minimum cost flows and circulations.
[40]252
253This group describes the algorithms for finding minimum cost flows and
[209]254circulations.
[40]255*/
256
257/**
[318]258@defgroup min_cut Minimum Cut Algorithms
[209]259@ingroup algs
[40]260
[50]261\brief Algorithms for finding minimum cut in graphs.
[40]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
[50]269cut is the \f$X\f$ solution of the next optimization problem:
[40]270
[210]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]
[40]273
[50]274LEMON contains several algorithms related to minimum cut problems:
[40]275
[50]276- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
[209]277  in directed graphs
[50]278- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
[40]279  calculate minimum cut in undirected graphs
[50]280- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
[40]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/**
[318]288@defgroup graph_prop Connectivity and Other Graph Properties
[40]289@ingroup algs
[50]290\brief Algorithms for discovering the graph properties
[40]291
[50]292This group describes the algorithms for discovering the graph properties
293like connectivity, bipartiteness, euler property, simplicity etc.
[40]294
295\image html edge_biconnected_components.png
296\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
297*/
298
299/**
[318]300@defgroup planar Planarity Embedding and Drawing
[40]301@ingroup algs
[50]302\brief Algorithms for planarity checking, embedding and drawing
[40]303
[210]304This group describes the algorithms for planarity checking,
305embedding and drawing.
[40]306
307\image html planar.png
308\image latex planar.eps "Plane graph" width=\textwidth
309*/
310
311/**
[318]312@defgroup matching Matching Algorithms
[40]313@ingroup algs
[50]314\brief Algorithms for finding matchings in graphs and bipartite graphs.
[40]315
[50]316This group contains algorithm objects and functions to calculate
[40]317matchings in graphs and bipartite graphs. The general matching problem is
[83]318finding a subset of the arcs which does not shares common endpoints.
[209]319
[40]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
[236]327LEMON contains the next algorithms:
[209]328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
329  augmenting path algorithm for calculate maximum cardinality matching in
[40]330  bipartite graphs
[209]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
[40]335  and maximum weighted bipartite matching in bipartite graph
[209]336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
337  Successive shortest path algorithm for calculate minimum cost maximum
[40]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/**
[318]353@defgroup spantree Minimum Spanning Tree Algorithms
[40]354@ingroup algs
[50]355\brief Algorithms for finding a minimum cost spanning tree in a graph.
[40]356
[50]357This group describes the algorithms for finding a minimum cost spanning
[40]358tree in a graph
359*/
360
361/**
[318]362@defgroup auxalg Auxiliary Algorithms
[40]363@ingroup algs
[50]364\brief Auxiliary algorithms implemented in LEMON.
[40]365
[50]366This group describes some algorithms implemented in LEMON
367in order to make it easier to implement complex algorithms.
[40]368*/
369
370/**
[318]371@defgroup approx Approximation Algorithms
372@ingroup algs
[50]373\brief Approximation algorithms.
[40]374
[50]375This group describes the approximation and heuristic algorithms
376implemented in LEMON.
[40]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/**
[318]389@defgroup lp_group Lp and Mip Solvers
[40]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
[209]398/**
[318]399@defgroup lp_utils Tools for Lp and Mip Solvers
[40]400@ingroup lp_group
[50]401\brief Helper tools to the Lp and Mip solvers.
[40]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
[50]412This group describes some metaheuristic optimization tools.
[40]413*/
414
415/**
[209]416@defgroup utils Tools and Utilities
[50]417\brief Tools and utilities for programming in LEMON
[40]418
[50]419Tools and utilities for programming in LEMON.
[40]420*/
421
422/**
423@defgroup gutils Basic Graph Utilities
424@ingroup utils
[50]425\brief Simple basic graph utilities.
[40]426
427This group describes some simple basic graph utilities.
428*/
429
430/**
431@defgroup misc Miscellaneous Tools
432@ingroup utils
[50]433\brief Tools for development, debugging and testing.
434
435This group describes several useful tools for development,
[40]436debugging and testing.
437*/
438
439/**
[318]440@defgroup timecount Time Measuring and Counting
[40]441@ingroup misc
[50]442\brief Simple tools for measuring the performance of algorithms.
443
444This group describes simple tools for measuring the performance
[40]445of algorithms.
446*/
447
448/**
449@defgroup exceptions Exceptions
450@ingroup utils
[50]451\brief Exceptions defined in LEMON.
452
453This group describes the exceptions defined in LEMON.
[40]454*/
455
456/**
457@defgroup io_group Input-Output
[50]458\brief Graph Input-Output methods
[40]459
[209]460This group describes the tools for importing and exporting graphs
[318]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.
[40]464*/
465
466/**
[236]467@defgroup lemon_io LEMON Input-Output
[40]468@ingroup io_group
[318]469\brief Reading and writing LEMON Graph Format.
[40]470
[210]471This group describes methods for reading and writing
[236]472\ref lgf-format "LEMON Graph Format".
[40]473*/
474
475/**
[318]476@defgroup eps_io Postscript Exporting
[40]477@ingroup io_group
478\brief General \c EPS drawer and graph exporter
479
[50]480This group describes general \c EPS drawing methods and special
[209]481graph exporting tools.
[40]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.
[209]492
[325]493- These classes contain the documentations of the %concepts. In order
[40]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
[325]498  implementation of the %concepts should provide, however completely
[40]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>
[50]507  that makes it possible to check whether a certain implementation of a
[40]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
[50]518This group describes the skeletons and concept checking classes of LEMON's
[40]519graph structures and helper classes used to implement these.
520*/
521
[318]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.
[40]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
[41]538It order to compile them, use <tt>--enable-demo</tt> configure option when
539build the library.
[40]540*/
541
542/**
543@defgroup tools Standalone utility applications
544
[209]545Some utility applications are listed here.
[40]546
547The standard compilation procedure (<tt>./configure;make</tt>) will compile
[209]548them, as well.
[40]549*/
550
Note: See TracBrowser for help on using the repository browser.