COIN-OR::LEMON - Graph Library

source: lemon/doc/groups.dox @ 88:18444049848b

Last change on this file since 88:18444049848b was 50:a34c58ff6e40, checked in by Peter Kovacs <kpeter@…>, 17 years ago

Improved groups.dox.
Added missing brief descriptions.
Changed descriptions to be unifom.
Some minor fixes.

File size: 18.1 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 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
47edges 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 edges 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 "ReadMap"s. They can
100make arithmetic operations between one or two maps (negation, scaling,
101addition, multiplication etc.) or e.g. convert a map to another one
102of 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 graphToEps() 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  Graph::NodeMap<int> degree_map(graph);
120 
121  graphToEps(graph, "graph.eps")
122    .coords(coords).scaleToA4().undirected()
123    .nodeColors(composeMap(functorMap(nodeColor), degree_map))
124    .run();
125\endcode
126The \c functorMap() 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 previous created map. The composed map is proper function to
129get 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  Graph graph;
136 
137  typedef Graph::EdgeMap<double> DoubleEdgeMap;
138  DoubleEdgeMap length(graph);
139  DoubleEdgeMap speed(graph);
140 
141  typedef DivMap<DoubleEdgeMap, DoubleEdgeMap> TimeMap;
142 
143  TimeMap time(length, speed);
144 
145  Dijkstra<Graph, TimeMap> dijkstra(graph, time);
146  dijkstra.run(source, target);
147\endcode
148
149We have a length map and a maximum speed map on a graph. The minimum
150time to pass the edge can be calculated as the division of the two
151maps which can be done implicitly with the \c DivMap template
152class. We use the implicit minimum time map as the length map of the
153\c Dijkstra algorithm.
154*/
155
156/**
157@defgroup matrices Matrices
158@ingroup datas
159\brief Two dimensional data storages implemented in LEMON.
160
161This group describes two dimensional data storages implemented in LEMON.
162*/
163
164/**
165@defgroup paths Path Structures
166@ingroup datas
167\brief Path structures implemented in LEMON.
168
169This group describes the path structures implemented in LEMON.
170
171LEMON provides flexible data structures to work with paths.
172All of them have similar interfaces and they can be copied easily with
173assignment operators and copy constructors. This makes it easy and
174efficient to have e.g. the Dijkstra algorithm to store its result in
175any kind of path structure.
176
177\sa lemon::concepts::Path
178
179*/
180
181/**
182@defgroup auxdat Auxiliary Data Structures
183@ingroup datas
184\brief Auxiliary data structures implemented in LEMON.
185
186This group describes some data structures implemented in LEMON in
187order to make it easier to implement combinatorial algorithms.
188*/
189
190
191/**
192@defgroup algs Algorithms
193\brief This group describes the several algorithms
194implemented in LEMON.
195
196This group describes the several algorithms
197implemented in LEMON.
198*/
199
200/**
201@defgroup search Graph Search
202@ingroup algs
203\brief Common graph search algorithms.
204
205This group describes the common graph search algorithms like
206Breadth-first search (Bfs) and Depth-first search (Dfs).
207*/
208
209/**
210@defgroup shortest_path Shortest Path algorithms
211@ingroup algs
212\brief Algorithms for finding shortest paths.
213
214This group describes the algorithms for finding shortest paths in graphs.
215*/
216
217/**
218@defgroup max_flow Maximum Flow algorithms
219@ingroup algs
220\brief Algorithms for finding maximum flows.
221
222This group describes the algorithms for finding maximum flows and
223feasible circulations.
224
225The maximum flow problem is to find a flow between a single source and
226a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
227directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
228function and given \f$s, t \in V\f$ source and target node. The
229maximum flow is the \f$f_a\f$ solution of the next optimization problem:
230
231\f[ 0 \le f_a \le c_a \f]
232\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]
233\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
234
235LEMON contains several algorithms for solving maximum flow problems:
236- \ref lemon::EdmondsKarp "Edmonds-Karp"
237- \ref lemon::Preflow "Goldberg's Preflow algorithm"
238- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
239- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
240
241In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
242fastest method to compute the maximum flow. All impelementations
243provides functions to query the minimum cut, which is the dual linear
244programming problem of the maximum flow.
245
246*/
247
248/**
249@defgroup min_cost_flow Minimum Cost Flow algorithms
250@ingroup algs
251
252\brief Algorithms for finding minimum cost flows and circulations.
253
254This group describes the algorithms for finding minimum cost flows and
255circulations. 
256*/
257
258/**
259@defgroup min_cut Minimum Cut algorithms
260@ingroup algs
261
262\brief Algorithms for finding minimum cut in graphs.
263
264This group describes the algorithms for finding minimum cut in graphs.
265
266The minimum cut problem is to find a non-empty and non-complete
267\f$X\f$ subset of the vertices with minimum overall capacity on
268outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
269\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
270cut is the \f$X\f$ solution of the next optimization problem:
271
272\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\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, embedding and drawing.
306
307\image html planar.png
308\image latex planar.eps "Plane graph" width=\textwidth
309*/
310
311/**
312@defgroup matching Matching algorithms
313@ingroup algs
314\brief Algorithms for finding matchings in graphs and bipartite graphs.
315
316This group contains algorithm objects and functions to calculate
317matchings in graphs and bipartite graphs. The general matching problem is
318finding a subset of the edges which does not shares common endpoints.
319 
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
327Lemon contains the next algorithms:
328- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
329  augmenting path algorithm for calculate maximum cardinality matching in
330  bipartite graphs
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
335  and maximum weighted bipartite matching in bipartite graph
336- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
337  Successive shortest path algorithm for calculate minimum cost maximum
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
353/**
354@defgroup spantree Minimum Spanning Tree algorithms
355@ingroup algs
356\brief Algorithms for finding a minimum cost spanning tree in a graph.
357
358This group describes the algorithms for finding a minimum cost spanning
359tree in a graph
360*/
361
362
363/**
364@defgroup auxalg Auxiliary algorithms
365@ingroup algs
366\brief Auxiliary algorithms implemented in LEMON.
367
368This group describes some algorithms implemented in LEMON
369in order to make it easier to implement complex algorithms.
370*/
371
372/**
373@defgroup approx Approximation algorithms
374\brief Approximation algorithms.
375
376This group describes the approximation and heuristic algorithms
377implemented in LEMON.
378*/
379
380/**
381@defgroup gen_opt_group General Optimization Tools
382\brief This group describes some general optimization frameworks
383implemented in LEMON.
384
385This group describes some general optimization frameworks
386implemented in LEMON.
387
388*/
389
390/**
391@defgroup lp_group Lp and Mip solvers
392@ingroup gen_opt_group
393\brief Lp and Mip solver interfaces for LEMON.
394
395This group describes Lp and Mip solver interfaces for LEMON. The
396various LP solvers could be used in the same manner with this
397interface.
398
399*/
400
401/**
402@defgroup lp_utils Tools for Lp and Mip solvers
403@ingroup lp_group
404\brief Helper tools to the Lp and Mip solvers.
405
406This group adds some helper tools to general optimization framework
407implemented in LEMON.
408*/
409
410/**
411@defgroup metah Metaheuristics
412@ingroup gen_opt_group
413\brief Metaheuristics for LEMON library.
414
415This group describes some metaheuristic optimization tools.
416*/
417
418/**
419@defgroup utils Tools and Utilities
420\brief Tools and utilities for programming in LEMON
421
422Tools and utilities for programming in LEMON.
423*/
424
425/**
426@defgroup gutils Basic Graph Utilities
427@ingroup utils
428\brief Simple basic graph utilities.
429
430This group describes some simple basic graph utilities.
431*/
432
433/**
434@defgroup misc Miscellaneous Tools
435@ingroup utils
436\brief Tools for development, debugging and testing.
437
438This group describes several useful tools for development,
439debugging and testing.
440*/
441
442/**
443@defgroup timecount Time measuring and Counting
444@ingroup misc
445\brief Simple tools for measuring the performance of algorithms.
446
447This group describes simple tools for measuring the performance
448of algorithms.
449*/
450
451/**
452@defgroup graphbits Tools for Graph Implementation
453@ingroup utils
454\brief Tools to make it easier to create graphs.
455
456This group describes the tools that makes it easier to create graphs and
457the maps that dynamically update with the graph changes.
458*/
459
460/**
461@defgroup exceptions Exceptions
462@ingroup utils
463\brief Exceptions defined in LEMON.
464
465This group describes the exceptions defined in LEMON.
466*/
467
468/**
469@defgroup io_group Input-Output
470\brief Graph Input-Output methods
471
472This group describes the tools for importing and exporting graphs
473and graph related data. Now it supports the LEMON format, the
474\c DIMACS format and the encapsulated postscript (EPS) format.
475*/
476
477/**
478@defgroup lemon_io Lemon Input-Output
479@ingroup io_group
480\brief Reading and writing LEMON format
481
482This group describes methods for reading and writing LEMON format.
483You can find more about this format on the \ref graph-io-page "Graph Input-Output"
484tutorial pages.
485*/
486
487/**
488@defgroup section_io Section readers and writers
489@ingroup lemon_io
490\brief Section readers and writers for lemon Input-Output.
491
492This group describes section readers and writers that can be attached to
493\ref LemonReader and \ref LemonWriter.
494*/
495
496/**
497@defgroup item_io Item Readers and Writers
498@ingroup lemon_io
499\brief Item readers and writers for lemon Input-Output.
500
501The Input-Output classes can handle more data type by example
502as map or attribute value. Each of these should be written and
503read some way. The module make possible to do this. 
504*/
505
506/**
507@defgroup eps_io Postscript exporting
508@ingroup io_group
509\brief General \c EPS drawer and graph exporter
510
511This group describes general \c EPS drawing methods and special
512graph exporting tools.
513*/
514
515
516/**
517@defgroup concept Concepts
518\brief Skeleton classes and concept checking classes
519
520This group describes the data/algorithm skeletons and concept checking
521classes implemented in LEMON.
522
523The purpose of the classes in this group is fourfold.
524 
525- These classes contain the documentations of the concepts. In order
526  to avoid document multiplications, an implementation of a concept
527  simply refers to the corresponding concept class.
528
529- These classes declare every functions, <tt>typedef</tt>s etc. an
530  implementation of the concepts should provide, however completely
531  without implementations and real data structures behind the
532  interface. On the other hand they should provide nothing else. All
533  the algorithms working on a data structure meeting a certain concept
534  should compile with these classes. (Though it will not run properly,
535  of course.) In this way it is easily to check if an algorithm
536  doesn't use any extra feature of a certain implementation.
537
538- The concept descriptor classes also provide a <em>checker class</em>
539  that makes it possible to check whether a certain implementation of a
540  concept indeed provides all the required features.
541
542- Finally, They can serve as a skeleton of a new implementation of a concept.
543
544*/
545
546
547/**
548@defgroup graph_concepts Graph Structure Concepts
549@ingroup concept
550\brief Skeleton and concept checking classes for graph structures
551
552This group describes the skeletons and concept checking classes of LEMON's
553graph structures and helper classes used to implement these.
554*/
555
556/* --- Unused group
557@defgroup experimental Experimental Structures and Algorithms
558This group describes some Experimental structures and algorithms.
559The stuff here is subject to change.
560*/
561
562/**
563\anchor demoprograms
564
565@defgroup demos Demo programs
566
567Some demo programs are listed here. Their full source codes can be found in
568the \c demo subdirectory of the source tree.
569
570It order to compile them, use <tt>--enable-demo</tt> configure option when
571build the library.
572*/
573
574/**
575@defgroup tools Standalone utility applications
576
577Some utility applications are listed here.
578
579The standard compilation procedure (<tt>./configure;make</tt>) will compile
580them, as well.
581*/
582
Note: See TracBrowser for help on using the repository browser.