COIN-OR::LEMON - Graph Library

source: lemon-main/doc/groups.dox @ 416:76287c8caa26

Last change on this file since 416:76287c8caa26 was 416:76287c8caa26, checked in by Balazs Dezso <deba@…>, 16 years ago

Reorganication of graph adaptors and doc improvements (#67)

  • Moving to one file, lemon/adaptors.h
  • Renamings
  • Doc cleanings
File size: 20.8 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
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 arc/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
47arcs 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 structure.
58
59<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
60*/
61
62/**
63@defgroup graph_adaptors Adaptor Classes for graphs
64@ingroup graphs
65\brief This group contains several adaptor classes for digraphs and graphs
66
67The main parts of LEMON are the different graph structures, generic
68graph algorithms, graph concepts which couple these, and graph
69adaptors. While the previous notions are more or less clear, the
70latter one needs further explanation. Graph adaptors are graph classes
71which serve for considering graph structures in different ways.
72
73A short example makes this much clearer.  Suppose that we have an
74instance \c g of a directed graph type say ListDigraph and an algorithm
75\code
76template <typename Digraph>
77int algorithm(const Digraph&);
78\endcode
79is needed to run on the reverse oriented graph.  It may be expensive
80(in time or in memory usage) to copy \c g with the reversed
81arcs.  In this case, an adaptor class is used, which (according
82to LEMON digraph concepts) works as a digraph.  The adaptor uses the
83original digraph structure and digraph operations when methods of the
84reversed oriented graph are called.  This means that the adaptor have
85minor memory usage, and do not perform sophisticated algorithmic
86actions.  The purpose of it is to give a tool for the cases when a
87graph have to be used in a specific alteration.  If this alteration is
88obtained by a usual construction like filtering the arc-set or
89considering a new orientation, then an adaptor is worthwhile to use.
90To come back to the reverse oriented graph, in this situation
91\code
92template<typename Digraph> class ReverseDigraph;
93\endcode
94template class can be used. The code looks as follows
95\code
96ListDigraph g;
97ReverseDigraph<ListGraph> rg(g);
98int result = algorithm(rg);
99\endcode
100After running the algorithm, the original graph \c g is untouched.
101This techniques gives rise to an elegant code, and based on stable
102graph adaptors, complex algorithms can be implemented easily.
103
104In flow, circulation and bipartite matching problems, the residual
105graph is of particular importance. Combining an adaptor implementing
106this, shortest path algorithms and minimum mean cycle algorithms,
107a range of weighted and cardinality optimization algorithms can be
108obtained. For other examples, the interested user is referred to the
109detailed documentation of particular adaptors.
110
111The behavior of graph adaptors can be very different. Some of them keep
112capabilities of the original graph while in other cases this would be
113meaningless. This means that the concepts that they are models of depend
114on the graph adaptor, and the wrapped graph(s).
115If an arc of \c rg is deleted, this is carried out by deleting the
116corresponding arc of \c g, thus the adaptor modifies the original graph.
117
118But for a residual graph, this operation has no sense.
119Let us stand one more example here to simplify your work.
120RevGraphAdaptor has constructor
121\code
122ReverseDigraph(Digraph& digraph);
123\endcode
124This means that in a situation, when a <tt>const ListDigraph&</tt>
125reference to a graph is given, then it have to be instantiated with
126<tt>Digraph=const ListDigraph</tt>.
127\code
128int algorithm1(const ListDigraph& g) {
129  RevGraphAdaptor<const ListDigraph> rg(g);
130  return algorithm2(rg);
131}
132\endcode
133*/
134
135/**
136@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
137@ingroup graphs
138\brief Graph types between real graphs and graph adaptors.
139
140This group describes some graph types between real graphs and graph adaptors.
141These classes wrap graphs to give new functionality as the adaptors do it.
142On the other hand they are not light-weight structures as the adaptors.
143*/
144
145/**
146@defgroup maps Maps
147@ingroup datas
148\brief Map structures implemented in LEMON.
149
150This group describes the map structures implemented in LEMON.
151
152LEMON provides several special purpose maps and map adaptors that e.g. combine
153new maps from existing ones.
154
155<b>See also:</b> \ref map_concepts "Map Concepts".
156*/
157
158/**
159@defgroup graph_maps Graph Maps
160@ingroup maps
161\brief Special graph-related maps.
162
163This group describes maps that are specifically designed to assign
164values to the nodes and arcs of graphs.
165*/
166
167/**
168\defgroup map_adaptors Map Adaptors
169\ingroup maps
170\brief Tools to create new maps from existing ones
171
172This group describes map adaptors that are used to create "implicit"
173maps from other maps.
174
175Most of them are \ref lemon::concepts::ReadMap "read-only maps".
176They can make arithmetic and logical operations between one or two maps
177(negation, shifting, addition, multiplication, logical 'and', 'or',
178'not' etc.) or e.g. convert a map to another one of different Value type.
179
180The typical usage of this classes is passing implicit maps to
181algorithms.  If a function type algorithm is called then the function
182type map adaptors can be used comfortable. For example let's see the
183usage of map adaptors with the \c graphToEps() function.
184\code
185  Color nodeColor(int deg) {
186    if (deg >= 2) {
187      return Color(0.5, 0.0, 0.5);
188    } else if (deg == 1) {
189      return Color(1.0, 0.5, 1.0);
190    } else {
191      return Color(0.0, 0.0, 0.0);
192    }
193  }
194
195  Digraph::NodeMap<int> degree_map(graph);
196
197  graphToEps(graph, "graph.eps")
198    .coords(coords).scaleToA4().undirected()
199    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
200    .run();
201\endcode
202The \c functorToMap() function makes an \c int to \c Color map from the
203\c nodeColor() function. The \c composeMap() compose the \c degree_map
204and the previously created map. The composed map is a proper function to
205get the color of each node.
206
207The usage with class type algorithms is little bit harder. In this
208case the function type map adaptors can not be used, because the
209function map adaptors give back temporary objects.
210\code
211  Digraph graph;
212
213  typedef Digraph::ArcMap<double> DoubleArcMap;
214  DoubleArcMap length(graph);
215  DoubleArcMap speed(graph);
216
217  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
218  TimeMap time(length, speed);
219
220  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
221  dijkstra.run(source, target);
222\endcode
223We have a length map and a maximum speed map on the arcs of a digraph.
224The minimum time to pass the arc can be calculated as the division of
225the two maps which can be done implicitly with the \c DivMap template
226class. We use the implicit minimum time map as the length map of the
227\c Dijkstra algorithm.
228*/
229
230/**
231@defgroup matrices Matrices
232@ingroup datas
233\brief Two dimensional data storages implemented in LEMON.
234
235This group describes two dimensional data storages implemented in LEMON.
236*/
237
238/**
239@defgroup paths Path Structures
240@ingroup datas
241\brief %Path structures implemented in LEMON.
242
243This group describes the path structures implemented in LEMON.
244
245LEMON provides flexible data structures to work with paths.
246All of them have similar interfaces and they can be copied easily with
247assignment operators and copy constructors. This makes it easy and
248efficient to have e.g. the Dijkstra algorithm to store its result in
249any kind of path structure.
250
251\sa lemon::concepts::Path
252*/
253
254/**
255@defgroup auxdat Auxiliary Data Structures
256@ingroup datas
257\brief Auxiliary data structures implemented in LEMON.
258
259This group describes some data structures implemented in LEMON in
260order to make it easier to implement combinatorial algorithms.
261*/
262
263/**
264@defgroup algs Algorithms
265\brief This group describes the several algorithms
266implemented in LEMON.
267
268This group describes the several algorithms
269implemented in LEMON.
270*/
271
272/**
273@defgroup search Graph Search
274@ingroup algs
275\brief Common graph search algorithms.
276
277This group describes the common graph search algorithms like
278Breadth-First Search (BFS) and Depth-First Search (DFS).
279*/
280
281/**
282@defgroup shortest_path Shortest Path Algorithms
283@ingroup algs
284\brief Algorithms for finding shortest paths.
285
286This group describes the algorithms for finding shortest paths in graphs.
287*/
288
289/**
290@defgroup max_flow Maximum Flow Algorithms
291@ingroup algs
292\brief Algorithms for finding maximum flows.
293
294This group describes the algorithms for finding maximum flows and
295feasible circulations.
296
297The maximum flow problem is to find a flow between a single source and
298a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
299directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
300function and given \f$s, t \in V\f$ source and target node. The
301maximum flow is the \f$f_a\f$ solution of the next optimization problem:
302
303\f[ 0 \le f_a \le c_a \f]
304\f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
305\qquad \forall u \in V \setminus \{s,t\}\f]
306\f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
307
308LEMON contains several algorithms for solving maximum flow problems:
309- \ref lemon::EdmondsKarp "Edmonds-Karp"
310- \ref lemon::Preflow "Goldberg's Preflow algorithm"
311- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
312- \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
313
314In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
315fastest method to compute the maximum flow. All impelementations
316provides functions to query the minimum cut, which is the dual linear
317programming problem of the maximum flow.
318*/
319
320/**
321@defgroup min_cost_flow Minimum Cost Flow Algorithms
322@ingroup algs
323
324\brief Algorithms for finding minimum cost flows and circulations.
325
326This group describes the algorithms for finding minimum cost flows and
327circulations.
328*/
329
330/**
331@defgroup min_cut Minimum Cut Algorithms
332@ingroup algs
333
334\brief Algorithms for finding minimum cut in graphs.
335
336This group describes the algorithms for finding minimum cut in graphs.
337
338The minimum cut problem is to find a non-empty and non-complete
339\f$X\f$ subset of the vertices with minimum overall capacity on
340outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
341\f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
342cut is the \f$X\f$ solution of the next optimization problem:
343
344\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
345\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
346
347LEMON contains several algorithms related to minimum cut problems:
348
349- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
350  in directed graphs
351- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
352  calculate minimum cut in undirected graphs
353- \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
354  pairs minimum cut in undirected graphs
355
356If you want to find minimum cut just between two distinict nodes,
357please see the \ref max_flow "Maximum Flow page".
358*/
359
360/**
361@defgroup graph_prop Connectivity and Other Graph Properties
362@ingroup algs
363\brief Algorithms for discovering the graph properties
364
365This group describes the algorithms for discovering the graph properties
366like connectivity, bipartiteness, euler property, simplicity etc.
367
368\image html edge_biconnected_components.png
369\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
370*/
371
372/**
373@defgroup planar Planarity Embedding and Drawing
374@ingroup algs
375\brief Algorithms for planarity checking, embedding and drawing
376
377This group describes the algorithms for planarity checking,
378embedding and drawing.
379
380\image html planar.png
381\image latex planar.eps "Plane graph" width=\textwidth
382*/
383
384/**
385@defgroup matching Matching Algorithms
386@ingroup algs
387\brief Algorithms for finding matchings in graphs and bipartite graphs.
388
389This group contains algorithm objects and functions to calculate
390matchings in graphs and bipartite graphs. The general matching problem is
391finding a subset of the arcs which does not shares common endpoints.
392
393There are several different algorithms for calculate matchings in
394graphs.  The matching problems in bipartite graphs are generally
395easier than in general graphs. The goal of the matching optimization
396can be the finding maximum cardinality, maximum weight or minimum cost
397matching. The search can be constrained to find perfect or
398maximum cardinality matching.
399
400LEMON contains the next algorithms:
401- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
402  augmenting path algorithm for calculate maximum cardinality matching in
403  bipartite graphs
404- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
405  algorithm for calculate maximum cardinality matching in bipartite graphs
406- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
407  Successive shortest path algorithm for calculate maximum weighted matching
408  and maximum weighted bipartite matching in bipartite graph
409- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
410  Successive shortest path algorithm for calculate minimum cost maximum
411  matching in bipartite graph
412- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
413  for calculate maximum cardinality matching in general graph
414- \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
415  shrinking algorithm for calculate maximum weighted matching in general
416  graph
417- \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
418  Edmond's blossom shrinking algorithm for calculate maximum weighted
419  perfect matching in general graph
420
421\image html bipartite_matching.png
422\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
423*/
424
425/**
426@defgroup spantree Minimum Spanning Tree Algorithms
427@ingroup algs
428\brief Algorithms for finding a minimum cost spanning tree in a graph.
429
430This group describes the algorithms for finding a minimum cost spanning
431tree in a graph
432*/
433
434/**
435@defgroup auxalg Auxiliary Algorithms
436@ingroup algs
437\brief Auxiliary algorithms implemented in LEMON.
438
439This group describes some algorithms implemented in LEMON
440in order to make it easier to implement complex algorithms.
441*/
442
443/**
444@defgroup approx Approximation Algorithms
445@ingroup algs
446\brief Approximation algorithms.
447
448This group describes the approximation and heuristic algorithms
449implemented in LEMON.
450*/
451
452/**
453@defgroup gen_opt_group General Optimization Tools
454\brief This group describes some general optimization frameworks
455implemented in LEMON.
456
457This group describes some general optimization frameworks
458implemented in LEMON.
459*/
460
461/**
462@defgroup lp_group Lp and Mip Solvers
463@ingroup gen_opt_group
464\brief Lp and Mip solver interfaces for LEMON.
465
466This group describes Lp and Mip solver interfaces for LEMON. The
467various LP solvers could be used in the same manner with this
468interface.
469*/
470
471/**
472@defgroup lp_utils Tools for Lp and Mip Solvers
473@ingroup lp_group
474\brief Helper tools to the Lp and Mip solvers.
475
476This group adds some helper tools to general optimization framework
477implemented in LEMON.
478*/
479
480/**
481@defgroup metah Metaheuristics
482@ingroup gen_opt_group
483\brief Metaheuristics for LEMON library.
484
485This group describes some metaheuristic optimization tools.
486*/
487
488/**
489@defgroup utils Tools and Utilities
490\brief Tools and utilities for programming in LEMON
491
492Tools and utilities for programming in LEMON.
493*/
494
495/**
496@defgroup gutils Basic Graph Utilities
497@ingroup utils
498\brief Simple basic graph utilities.
499
500This group describes some simple basic graph utilities.
501*/
502
503/**
504@defgroup misc Miscellaneous Tools
505@ingroup utils
506\brief Tools for development, debugging and testing.
507
508This group describes several useful tools for development,
509debugging and testing.
510*/
511
512/**
513@defgroup timecount Time Measuring and Counting
514@ingroup misc
515\brief Simple tools for measuring the performance of algorithms.
516
517This group describes simple tools for measuring the performance
518of algorithms.
519*/
520
521/**
522@defgroup exceptions Exceptions
523@ingroup utils
524\brief Exceptions defined in LEMON.
525
526This group describes the exceptions defined in LEMON.
527*/
528
529/**
530@defgroup io_group Input-Output
531\brief Graph Input-Output methods
532
533This group describes the tools for importing and exporting graphs
534and graph related data. Now it supports the \ref lgf-format
535"LEMON Graph Format", the \c DIMACS format and the encapsulated
536postscript (EPS) format.
537*/
538
539/**
540@defgroup lemon_io LEMON Graph Format
541@ingroup io_group
542\brief Reading and writing LEMON Graph Format.
543
544This group describes methods for reading and writing
545\ref lgf-format "LEMON Graph Format".
546*/
547
548/**
549@defgroup eps_io Postscript Exporting
550@ingroup io_group
551\brief General \c EPS drawer and graph exporter
552
553This group describes general \c EPS drawing methods and special
554graph exporting tools.
555*/
556
557/**
558@defgroup dimacs_group DIMACS format
559@ingroup io_group
560\brief Read and write files in DIMACS format
561
562Tools to read a digraph from or write it to a file in DIMACS format data.
563*/
564
565/**
566@defgroup nauty_group NAUTY Format
567@ingroup io_group
568\brief Read \e Nauty format
569
570Tool to read graphs from \e Nauty format data.
571*/
572
573/**
574@defgroup concept Concepts
575\brief Skeleton classes and concept checking classes
576
577This group describes the data/algorithm skeletons and concept checking
578classes implemented in LEMON.
579
580The purpose of the classes in this group is fourfold.
581
582- These classes contain the documentations of the %concepts. In order
583  to avoid document multiplications, an implementation of a concept
584  simply refers to the corresponding concept class.
585
586- These classes declare every functions, <tt>typedef</tt>s etc. an
587  implementation of the %concepts should provide, however completely
588  without implementations and real data structures behind the
589  interface. On the other hand they should provide nothing else. All
590  the algorithms working on a data structure meeting a certain concept
591  should compile with these classes. (Though it will not run properly,
592  of course.) In this way it is easily to check if an algorithm
593  doesn't use any extra feature of a certain implementation.
594
595- The concept descriptor classes also provide a <em>checker class</em>
596  that makes it possible to check whether a certain implementation of a
597  concept indeed provides all the required features.
598
599- Finally, They can serve as a skeleton of a new implementation of a concept.
600*/
601
602/**
603@defgroup graph_concepts Graph Structure Concepts
604@ingroup concept
605\brief Skeleton and concept checking classes for graph structures
606
607This group describes the skeletons and concept checking classes of LEMON's
608graph structures and helper classes used to implement these.
609*/
610
611/**
612@defgroup map_concepts Map Concepts
613@ingroup concept
614\brief Skeleton and concept checking classes for maps
615
616This group describes the skeletons and concept checking classes of maps.
617*/
618
619/**
620\anchor demoprograms
621
622@defgroup demos Demo programs
623
624Some demo programs are listed here. Their full source codes can be found in
625the \c demo subdirectory of the source tree.
626
627It order to compile them, use <tt>--enable-demo</tt> configure option when
628build the library.
629*/
630
631/**
632@defgroup tools Standalone utility applications
633
634Some utility applications are listed here.
635
636The standard compilation procedure (<tt>./configure;make</tt>) will compile
637them, as well.
638*/
639
Note: See TracBrowser for help on using the repository browser.