COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/groups.dox @ 2514:57143c09dc20

Last change on this file since 2514:57143c09dc20 was 2514:57143c09dc20, checked in by Balazs Dezso, 12 years ago

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

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