COIN-OR::LEMON - Graph Library

source: lemon/doc/groups.dox @ 41:b11737922197

Last change on this file since 41:b11737922197 was 41:b11737922197, checked in by Alpar Juttner <alpar@…>, 11 years ago

Minor updates in the doc

File size: 17.7 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 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 to calculate
322matchings in graphs and bipartite graphs. The general matching problem is
323finding a subset of the edges which does not shares common endpoints.
324 
325There are several different algorithms for calculate matchings in
326graphs.  The matching problems in bipartite graphs are generally
327easier than in general graphs. The goal of the matching optimization
328can be the finding maximum cardinality, maximum weight or minimum cost
329matching. The search can be constrained to find perfect or
330maximum cardinality matching.
331
332Lemon contains the next algorithms:
333- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
334  augmenting path algorithm for calculate maximum cardinality matching in
335  bipartite graphs
336- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
337  algorithm for calculate maximum cardinality matching in bipartite graphs
338- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
339  Successive shortest path algorithm for calculate maximum weighted matching
340  and maximum weighted bipartite matching in bipartite graph
341- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
342  Successive shortest path algorithm for calculate minimum cost maximum
343  matching in bipartite graph
344- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
345  for calculate maximum cardinality matching in general graph
346- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
347  shrinking algorithm for calculate maximum weighted matching in general
348  graph
349- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
350  Edmond's blossom shrinking algorithm for calculate maximum weighted
351  perfect matching in general graph
352
353\image html bipartite_matching.png
354\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
355
356*/
357
358/**
359@defgroup spantree Minimum Spanning Tree algorithms
360@ingroup algs
361\brief This group contains the algorithms for finding a minimum cost spanning
362tree in a graph
363
364This group contains the algorithms for finding a minimum cost spanning
365tree in a graph
366*/
367
368
369/**
370@defgroup auxalg Auxiliary algorithms
371@ingroup algs
372\brief Some algorithms implemented in LEMON.
373
374This group describes the algorithms in LEMON in order to make
375it easier to implement complex algorithms.
376*/
377
378/**
379@defgroup approx Approximation algorithms
380\brief Approximation algorithms
381
382Approximation and heuristic algorithms
383*/
384
385/**
386@defgroup gen_opt_group General Optimization Tools
387\brief This group describes some general optimization frameworks
388implemented in LEMON.
389
390This group describes some general optimization frameworks
391implemented in LEMON.
392
393*/
394
395/**
396@defgroup lp_group Lp and Mip solvers
397@ingroup gen_opt_group
398\brief Lp and Mip solver interfaces for LEMON.
399
400This group describes Lp and Mip solver interfaces for LEMON. The
401various LP solvers could be used in the same manner with this
402interface.
403
404*/
405
406/**
407@defgroup lp_utils Tools for Lp and Mip solvers
408@ingroup lp_group
409\brief This group adds some helper tools to the Lp and Mip solvers
410implemented in LEMON.
411
412This group adds some helper tools to general optimization framework
413implemented in LEMON.
414*/
415
416/**
417@defgroup metah Metaheuristics
418@ingroup gen_opt_group
419\brief Metaheuristics for LEMON library.
420
421This group contains some metaheuristic optimization tools.
422*/
423
424/**
425@defgroup utils Tools and Utilities
426\brief Tools and Utilities for Programming in LEMON
427
428Tools and Utilities for Programming in LEMON
429*/
430
431/**
432@defgroup gutils Basic Graph Utilities
433@ingroup utils
434\brief This group describes some simple basic graph utilities.
435
436This group describes some simple basic graph utilities.
437*/
438
439/**
440@defgroup misc Miscellaneous Tools
441@ingroup utils
442Here you can find several useful tools for development,
443debugging and testing.
444*/
445
446
447/**
448@defgroup timecount Time measuring and Counting
449@ingroup misc
450Here you can find simple tools for measuring the performance
451of algorithms.
452*/
453
454/**
455@defgroup graphbits Tools for Graph Implementation
456@ingroup utils
457\brief Tools to Make It Easier to Make Graphs.
458
459This group describes the tools that makes it easier to make graphs and
460the maps that dynamically update with the graph changes.
461*/
462
463/**
464@defgroup exceptions Exceptions
465@ingroup utils
466This group contains the exceptions thrown by LEMON library
467*/
468
469/**
470@defgroup io_group Input-Output
471\brief Several Graph Input-Output methods
472
473Here you can find tools for importing and exporting graphs
474and graph related data. Now it supports the LEMON format, the
475\c DIMACS format and the encapsulated postscript format.
476*/
477
478/**
479@defgroup lemon_io Lemon Input-Output
480@ingroup io_group
481\brief Reading and writing LEMON format
482
483Methods for reading and writing LEMON format. More about this
484format you can find on the \ref graph-io-page "Graph Input-Output"
485tutorial pages.
486*/
487
488/**
489@defgroup section_io Section readers and writers
490@ingroup lemon_io
491\brief Section readers and writers for lemon Input-Output.
492
493Here you can find which section readers and writers can attach to
494the LemonReader and LemonWriter.
495*/
496
497/**
498@defgroup item_io Item Readers and Writers
499@ingroup lemon_io
500\brief Item readers and writers for lemon Input-Output.
501
502The Input-Output classes can handle more data type by example
503as map or attribute value. Each of these should be written and
504read some way. The module make possible to do this. 
505*/
506
507/**
508@defgroup eps_io Postscript exporting
509@ingroup io_group
510\brief General \c EPS drawer and graph exporter
511
512This group contains general \c EPS drawing methods and special
513graph exporting tools.
514*/
515
516
517/**
518@defgroup concept Concepts
519\brief Skeleton classes and concept checking classes
520
521This group describes the data/algorithm skeletons and concept checking
522classes implemented in LEMON.
523
524The purpose of the classes in this group is fourfold.
525 
526- These classes contain the documentations of the concepts. In order
527  to avoid document multiplications, an implementation of a concept
528  simply refers to the corresponding concept class.
529
530- These classes declare every functions, <tt>typedef</tt>s etc. an
531  implementation of the concepts should provide, however completely
532  without implementations and real data structures behind the
533  interface. On the other hand they should provide nothing else. All
534  the algorithms working on a data structure meeting a certain concept
535  should compile with these classes. (Though it will not run properly,
536  of course.) In this way it is easily to check if an algorithm
537  doesn't use any extra feature of a certain implementation.
538
539- The concept descriptor classes also provide a <em>checker class</em>
540  that makes it possible check whether a certain implementation of a
541  concept indeed provides all the required features.
542
543- Finally, They can serve as a skeleton of a new implementation of a concept.
544
545*/
546
547
548/**
549@defgroup graph_concepts Graph Structure Concepts
550@ingroup concept
551\brief Skeleton and concept checking classes for graph structures
552
553This group contains the skeletons and concept checking classes of LEMON's
554graph structures and helper classes used to implement these.
555*/
556
557/* --- Unused group
558@defgroup experimental Experimental Structures and Algorithms
559This group contains some Experimental structures and algorithms.
560The stuff here is subject to change.
561*/
562
563/**
564\anchor demoprograms
565
566@defgroup demos Demo programs
567
568Some demo programs are listed here. Their full source codes can be found in
569the \c demo subdirectory of the source tree.
570
571It order to compile them, use <tt>--enable-demo</tt> configure option when
572build the library.
573
574*/
575
576/**
577@defgroup tools Standalone utility applications
578
579Some utility applications are listed here.
580
581The standard compilation procedure (<tt>./configure;make</tt>) will compile
582them, as well.
583
584*/
585
Note: See TracBrowser for help on using the repository browser.