COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/groups.dox @ 2530:f86f7e4eb2ba

Last change on this file since 2530:f86f7e4eb2ba was 2530:f86f7e4eb2ba, checked in by Balazs Dezso, 12 years ago

Reimplementation of Hao-Orlin algorithm
Little modifictaion in NagamochiIbaraki?
More docs for minimum cut algorithms

File size: 16.1 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
264\brief This group describes the algorithms for finding minimum cut in
265graphs.
266
267This group describes the algorithms for finding minimum cut in graphs.
268
269The minimum cut problem is to find a non-empty and non-complete
270\f$X\f$ subset of the vertices with minimum overall capacity on
271outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
272\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
273cut is the solution of the next optimization problem:
274
275\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
276
277The lemon contains several algorithms related to minimum cut problems:
278
279- \ref lemon::HaoOrlin "Hao-Orlin algorithm" for calculate minimum cut
280  in directed graphs 
281- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
282  calculate minimum cut in undirected graphs
283- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" for calculate all
284  pairs minimum cut in undirected graphs
285
286If you want to find minimum cut just between two distinict nodes,
287please see the \ref max_flow "Maximum Flow page".
288
289*/
290
291/**
292@defgroup graph_prop Connectivity and other graph properties
293@ingroup algs
294\brief This group describes the algorithms
295for discover the graph properties
296
297This group describes the algorithms for discover the graph properties
298like connectivity, bipartiteness, euler property, simplicity, etc...
299
300\image html edge_biconnected_components.png
301\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
302*/
303
304/**
305@defgroup planar Planarity embedding and drawing
306@ingroup algs
307\brief This group contains algorithms for planarity embedding and drawing
308
309This group contains algorithms for planarity checking, embedding and drawing.
310
311\image html planar.png
312\image latex planar.eps "Plane graph" width=\textwidth
313*/
314
315/**
316@defgroup matching Matching algorithms
317@ingroup algs
318\brief This group describes the algorithms
319for find matchings in graphs and bipartite graphs.
320
321This group provides some algorithm objects and function
322to calculate matchings in graphs and bipartite graphs.
323
324\image html bipartite_matching.png
325\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
326
327*/
328
329/**
330@defgroup spantree Minimum Spanning Tree algorithms
331@ingroup algs
332\brief This group contains the algorithms for finding a minimum cost spanning
333tree in a graph
334
335This group contains the algorithms for finding a minimum cost spanning
336tree in a graph
337*/
338
339
340/**
341@defgroup auxalg Auxiliary algorithms
342@ingroup algs
343\brief Some algorithms implemented in LEMON.
344
345This group describes the algorithms in LEMON in order to make
346it easier to implement complex algorithms.
347*/
348
349/**
350@defgroup approx Approximation algorithms
351\brief Approximation algorithms
352
353Approximation and heuristic algorithms
354*/
355
356/**
357@defgroup gen_opt_group General Optimization Tools
358\brief This group describes some general optimization frameworks
359implemented in LEMON.
360
361This group describes some general optimization frameworks
362implemented in LEMON.
363
364*/
365
366/**
367@defgroup lp_group Lp and Mip solvers
368@ingroup gen_opt_group
369\brief Lp and Mip solver interfaces for LEMON.
370
371This group describes Lp and Mip solver interfaces for LEMON. The
372various LP solvers could be used in the same manner with this
373interface.
374
375*/
376
377/**
378@defgroup lp_utils Tools for Lp and Mip solvers
379@ingroup lp_group
380\brief This group adds some helper tools to the Lp and Mip solvers
381implemented in LEMON.
382
383This group adds some helper tools to general optimization framework
384implemented in LEMON.
385*/
386
387/**
388@defgroup metah Metaheuristics
389@ingroup gen_opt_group
390\brief Metaheuristics for LEMON library.
391
392This group contains some metaheuristic optimization tools.
393*/
394
395/**
396@defgroup utils Tools and Utilities
397\brief Tools and Utilities for Programming in LEMON
398
399Tools and Utilities for Programming in LEMON
400*/
401
402/**
403@defgroup gutils Basic Graph Utilities
404@ingroup utils
405\brief This group describes some simple basic graph utilities.
406
407This group describes some simple basic graph utilities.
408*/
409
410/**
411@defgroup misc Miscellaneous Tools
412@ingroup utils
413Here you can find several useful tools for development,
414debugging and testing.
415*/
416
417
418/**
419@defgroup timecount Time measuring and Counting
420@ingroup misc
421Here you can find simple tools for measuring the performance
422of algorithms.
423*/
424
425/**
426@defgroup graphbits Tools for Graph Implementation
427@ingroup utils
428\brief Tools to Make It Easier to Make Graphs.
429
430This group describes the tools that makes it easier to make graphs and
431the maps that dynamically update with the graph changes.
432*/
433
434/**
435@defgroup exceptions Exceptions
436@ingroup utils
437This group contains the exceptions thrown by LEMON library
438*/
439
440/**
441@defgroup io_group Input-Output
442\brief Several Graph Input-Output methods
443
444Here you can find tools for importing and exporting graphs
445and graph related data. Now it supports the LEMON format, the
446\c DIMACS format and the encapsulated postscript format.
447*/
448
449/**
450@defgroup lemon_io Lemon Input-Output
451@ingroup io_group
452\brief Reading and writing LEMON format
453
454Methods for reading and writing LEMON format. More about this
455format you can find on the \ref graph-io-page "Graph Input-Output"
456tutorial pages.
457*/
458
459/**
460@defgroup section_io Section readers and writers
461@ingroup lemon_io
462\brief Section readers and writers for lemon Input-Output.
463
464Here you can find which section readers and writers can attach to
465the LemonReader and LemonWriter.
466*/
467
468/**
469@defgroup item_io Item Readers and Writers
470@ingroup lemon_io
471\brief Item readers and writers for lemon Input-Output.
472
473The Input-Output classes can handle more data type by example
474as map or attribute value. Each of these should be written and
475read some way. The module make possible to do this. 
476*/
477
478/**
479@defgroup eps_io Postscript exporting
480@ingroup io_group
481\brief General \c EPS drawer and graph exporter
482
483This group contains general \c EPS drawing methods and special
484graph exporting tools.
485*/
486
487
488/**
489@defgroup concept Concepts
490\brief Skeleton classes and concept checking classes
491
492This group describes the data/algorithm skeletons and concept checking
493classes implemented in LEMON.
494
495The purpose of the classes in this group is fourfold.
496 
497- These classes contain the documentations of the concepts. In order
498  to avoid document multiplications, an implementation of a concept
499  simply refers to the corresponding concept class.
500
501- These classes declare every functions, <tt>typedef</tt>s etc. an
502  implementation of the concepts should provide, however completely
503  without implementations and real data structures behind the
504  interface. On the other hand they should provide nothing else. All
505  the algorithms working on a data structure meeting a certain concept
506  should compile with these classes. (Though it will not run properly,
507  of course.) In this way it is easily to check if an algorithm
508  doesn't use any extra feature of a certain implementation.
509
510- The concept descriptor classes also provide a <em>checker class</em>
511  that makes it possible check whether a certain implementation of a
512  concept indeed provides all the required features.
513
514- Finally, They can serve as a skeleton of a new implementation of a concept.
515
516*/
517
518
519/**
520@defgroup graph_concepts Graph Structure Concepts
521@ingroup concept
522\brief Skeleton and concept checking classes for graph structures
523
524This group contains the skeletons and concept checking classes of LEMON's
525graph structures and helper classes used to implement these.
526*/
527
528/* --- Unused group
529@defgroup experimental Experimental Structures and Algorithms
530This group contains some Experimental structures and algorithms.
531The stuff here is subject to change.
532*/
533
534/**
535\anchor demoprograms
536
537@defgroup demos Demo programs
538
539Some demo programs are listed here. Their full source codes can be found in
540the \c demo subdirectory of the source tree.
541
542The standard compilation procedure (<tt>./configure;make</tt>) will compile
543them, as well.
544
545*/
546
547/**
548@defgroup tools Standalone utility applications
549
550Some utility applications are listed here.
551
552The standard compilation procedure (<tt>./configure;make</tt>) will compile
553them, as well.
554
555*/
556
Note: See TracBrowser for help on using the repository browser.