COIN-OR::LEMON - Graph Library

source: lemon-main/doc/groups.dox @ 278:931190050520

Last change on this file since 278:931190050520 was 236:da953e387d31, checked in by Akos Ladanyi <ladanyi@…>, 16 years ago

Unify the spelling of LEMON (#103).

File size: 17.5 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
[209]57with any graph structures.
[40]58*/
59
60/**
[50]61@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
[40]62@ingroup graphs
63\brief Graph types between real graphs and graph adaptors.
64
[50]65This group describes some graph types between real graphs and graph adaptors.
[209]66These classes wrap graphs to give new functionality as the adaptors do it.
[50]67On the other hand they are not light-weight structures as the adaptors.
[40]68*/
69
70/**
[209]71@defgroup maps Maps
[40]72@ingroup datas
[50]73\brief Map structures implemented in LEMON.
[40]74
[50]75This group describes the map structures implemented in LEMON.
76
77LEMON provides several special purpose maps that e.g. combine
[40]78new maps from existing ones.
79*/
80
81/**
[209]82@defgroup graph_maps Graph Maps
[40]83@ingroup maps
[83]84\brief Special graph-related maps.
[40]85
[50]86This group describes maps that are specifically designed to assign
[83]87values to the nodes and arcs of graphs.
[40]88*/
89
90
91/**
92\defgroup map_adaptors Map Adaptors
93\ingroup maps
94\brief Tools to create new maps from existing ones
95
[50]96This group describes map adaptors that are used to create "implicit"
97maps from other maps.
[40]98
[83]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.
[40]103
[50]104The typical usage of this classes is passing implicit maps to
[40]105algorithms.  If a function type algorithm is called then the function
106type map adaptors can be used comfortable. For example let's see the
[83]107usage of map adaptors with the \c digraphToEps() function.
[40]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  }
[209]118
[83]119  Digraph::NodeMap<int> degree_map(graph);
[209]120
[83]121  digraphToEps(graph, "graph.eps")
[40]122    .coords(coords).scaleToA4().undirected()
[83]123    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
[40]124    .run();
[209]125\endcode
[83]126The \c functorToMap() function makes an \c int to \c Color map from the
[40]127\e nodeColor() function. The \c composeMap() compose the \e degree_map
[83]128and the previously created map. The composed map is a proper function to
129get the color of each node.
[40]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
[50]133function map adaptors give back temporary objects.
[40]134\code
[83]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;
[40]142  TimeMap time(length, speed);
[209]143
[83]144  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
[40]145  dijkstra.run(source, target);
146\endcode
[83]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
[40]150class. We use the implicit minimum time map as the length map of the
151\c Dijkstra algorithm.
152*/
153
154/**
[209]155@defgroup matrices Matrices
[40]156@ingroup datas
[50]157\brief Two dimensional data storages implemented in LEMON.
[40]158
[50]159This group describes two dimensional data storages implemented in LEMON.
[40]160*/
161
162/**
163@defgroup paths Path Structures
164@ingroup datas
165\brief Path structures implemented in LEMON.
166
[50]167This group describes the path structures implemented in LEMON.
[40]168
[50]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
[40]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
[50]182\brief Auxiliary data structures implemented in LEMON.
[40]183
[50]184This group describes some data structures implemented in LEMON in
[40]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
[50]201\brief Common graph search algorithms.
[40]202
[209]203This group describes the common graph search algorithms like
[50]204Breadth-first search (Bfs) and Depth-first search (Dfs).
[40]205*/
206
207/**
208@defgroup shortest_path Shortest Path algorithms
209@ingroup algs
[50]210\brief Algorithms for finding shortest paths.
[40]211
[50]212This group describes the algorithms for finding shortest paths in graphs.
[40]213*/
214
[209]215/**
216@defgroup max_flow Maximum Flow algorithms
217@ingroup algs
[50]218\brief Algorithms for finding maximum flows.
[40]219
220This group describes the algorithms for finding maximum flows and
221feasible circulations.
222
[50]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$
[40]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
[50]227maximum flow is the \f$f_a\f$ solution of the next optimization problem:
[40]228
229\f[ 0 \le f_a \le c_a \f]
[210]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]
[40]232\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
233
[50]234LEMON contains several algorithms for solving maximum flow problems:
[209]235- \ref lemon::EdmondsKarp "Edmonds-Karp"
[40]236- \ref lemon::Preflow "Goldberg's Preflow algorithm"
[50]237- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
[40]238- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
239
[50]240In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
[40]241fastest method to compute the maximum flow. All impelementations
[50]242provides functions to query the minimum cut, which is the dual linear
243programming problem of the maximum flow.
[40]244
245*/
246
247/**
248@defgroup min_cost_flow Minimum Cost Flow algorithms
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/**
[209]258@defgroup min_cut Minimum Cut algorithms
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
288/**
289@defgroup graph_prop Connectivity and other graph properties
290@ingroup algs
[50]291\brief Algorithms for discovering the graph properties
[40]292
[50]293This group describes the algorithms for discovering the graph properties
294like connectivity, bipartiteness, euler property, simplicity etc.
[40]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
[50]303\brief Algorithms for planarity checking, embedding and drawing
[40]304
[210]305This group describes the algorithms for planarity checking,
306embedding and drawing.
[40]307
308\image html planar.png
309\image latex planar.eps "Plane graph" width=\textwidth
310*/
311
312/**
[209]313@defgroup matching Matching algorithms
[40]314@ingroup algs
[50]315\brief Algorithms for finding matchings in graphs and bipartite graphs.
[40]316
[50]317This group contains algorithm objects and functions to calculate
[40]318matchings in graphs and bipartite graphs. The general matching problem is
[83]319finding a subset of the arcs which does not shares common endpoints.
[209]320
[40]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
[236]328LEMON contains the next algorithms:
[209]329- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
330  augmenting path algorithm for calculate maximum cardinality matching in
[40]331  bipartite graphs
[209]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
[40]336  and maximum weighted bipartite matching in bipartite graph
[209]337- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
338  Successive shortest path algorithm for calculate minimum cost maximum
[40]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
[50]357\brief Algorithms for finding a minimum cost spanning tree in a graph.
[40]358
[50]359This group describes the algorithms for finding a minimum cost spanning
[40]360tree in a graph
361*/
362
363
364/**
365@defgroup auxalg Auxiliary algorithms
366@ingroup algs
[50]367\brief Auxiliary algorithms implemented in LEMON.
[40]368
[50]369This group describes some algorithms implemented in LEMON
370in order to make it easier to implement complex algorithms.
[40]371*/
372
373/**
374@defgroup approx Approximation algorithms
[50]375\brief Approximation algorithms.
[40]376
[50]377This group describes the approximation and heuristic algorithms
378implemented in LEMON.
[40]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
[209]402/**
403@defgroup lp_utils Tools for Lp and Mip solvers
[40]404@ingroup lp_group
[50]405\brief Helper tools to the Lp and Mip solvers.
[40]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
[50]416This group describes some metaheuristic optimization tools.
[40]417*/
418
419/**
[209]420@defgroup utils Tools and Utilities
[50]421\brief Tools and utilities for programming in LEMON
[40]422
[50]423Tools and utilities for programming in LEMON.
[40]424*/
425
426/**
427@defgroup gutils Basic Graph Utilities
428@ingroup utils
[50]429\brief Simple basic graph utilities.
[40]430
431This group describes some simple basic graph utilities.
432*/
433
434/**
435@defgroup misc Miscellaneous Tools
436@ingroup utils
[50]437\brief Tools for development, debugging and testing.
438
439This group describes several useful tools for development,
[40]440debugging and testing.
441*/
442
443/**
444@defgroup timecount Time measuring and Counting
445@ingroup misc
[50]446\brief Simple tools for measuring the performance of algorithms.
447
448This group describes simple tools for measuring the performance
[40]449of algorithms.
450*/
451
452/**
453@defgroup graphbits Tools for Graph Implementation
454@ingroup utils
[50]455\brief Tools to make it easier to create graphs.
[40]456
[50]457This group describes the tools that makes it easier to create graphs and
[40]458the maps that dynamically update with the graph changes.
459*/
460
461/**
462@defgroup exceptions Exceptions
463@ingroup utils
[50]464\brief Exceptions defined in LEMON.
465
466This group describes the exceptions defined in LEMON.
[40]467*/
468
469/**
470@defgroup io_group Input-Output
[50]471\brief Graph Input-Output methods
[40]472
[209]473This group describes the tools for importing and exporting graphs
[40]474and graph related data. Now it supports the LEMON format, the
[50]475\c DIMACS format and the encapsulated postscript (EPS) format.
[40]476*/
477
478/**
[236]479@defgroup lemon_io LEMON Input-Output
[40]480@ingroup io_group
[236]481\brief Reading and writing \ref lgf-format "LEMON Graph Format".
[40]482
[210]483This group describes methods for reading and writing
[236]484\ref lgf-format "LEMON Graph Format".
[40]485*/
486
487/**
488@defgroup eps_io Postscript exporting
489@ingroup io_group
490\brief General \c EPS drawer and graph exporter
491
[50]492This group describes general \c EPS drawing methods and special
[209]493graph exporting tools.
[40]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.
[209]505
[40]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>
[50]520  that makes it possible to check whether a certain implementation of a
[40]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
[50]533This group describes the skeletons and concept checking classes of LEMON's
[40]534graph structures and helper classes used to implement these.
535*/
536
537/* --- Unused group
538@defgroup experimental Experimental Structures and Algorithms
[50]539This group describes some Experimental structures and algorithms.
[40]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
[41]551It order to compile them, use <tt>--enable-demo</tt> configure option when
552build the library.
[40]553*/
554
555/**
556@defgroup tools Standalone utility applications
557
[209]558Some utility applications are listed here.
[40]559
560The standard compilation procedure (<tt>./configure;make</tt>) will compile
[209]561them, as well.
[40]562*/
563
Note: See TracBrowser for help on using the repository browser.