doc/groups.dox
 author Alpar Juttner Tue, 12 May 2009 12:09:55 +0100 branch 1.1 changeset 844 c01a98ce01fd parent 843 189760a7cdd0 parent 710 8b0df68370a4 child 1081 f1398882a928 permissions -rw-r--r--
Merge
     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-2009

     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 namespace lemon {

    20

    21 /**

    22 @defgroup datas Data Structures

    23 This group contains the several data structures implemented in LEMON.

    24 */

    25

    26 /**

    27 @defgroup graphs Graph Structures

    28 @ingroup datas

    29 \brief Graph structures implemented in LEMON.

    30

    31 The implementation of combinatorial algorithms heavily relies on

    32 efficient graph implementations. LEMON offers data structures which are

    33 planned to be easily used in an experimental phase of implementation studies,

    34 and thereafter the program code can be made efficient by small modifications.

    35

    36 The most efficient implementation of diverse applications require the

    37 usage of different physical graph implementations. These differences

    38 appear in the size of graph we require to handle, memory or time usage

    39 limitations or in the set of operations through which the graph can be

    40 accessed.  LEMON provides several physical graph structures to meet

    41 the diverging requirements of the possible users.  In order to save on

    42 running time or on memory usage, some structures may fail to provide

    43 some graph features like arc/edge or node deletion.

    44

    45 Alteration of standard containers need a very limited number of

    46 operations, these together satisfy the everyday requirements.

    47 In the case of graph structures, different operations are needed which do

    48 not alter the physical graph, but gives another view. If some nodes or

    49 arcs have to be hidden or the reverse oriented graph have to be used, then

    50 this is the case. It also may happen that in a flow implementation

    51 the residual graph can be accessed by another algorithm, or a node-set

    52 is to be shrunk for another algorithm.

    53 LEMON also provides a variety of graphs for these requirements called

    54 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only

    55 in conjunction with other graph representations.

    56

    57 You are free to use the graph structure that fit your requirements

    58 the best, most graph algorithms and auxiliary data structures can be used

    59 with any graph structure.

    60

    61 <b>See also:</b> \ref graph_concepts "Graph Structure Concepts".

    62 */

    63

    64 /**

    65 @defgroup graph_adaptors Adaptor Classes for Graphs

    66 @ingroup graphs

    67 \brief Adaptor classes for digraphs and graphs

    68

    69 This group contains several useful adaptor classes for digraphs and graphs.

    70

    71 The main parts of LEMON are the different graph structures, generic

    72 graph algorithms, graph concepts, which couple them, and graph

    73 adaptors. While the previous notions are more or less clear, the

    74 latter one needs further explanation. Graph adaptors are graph classes

    75 which serve for considering graph structures in different ways.

    76

    77 A short example makes this much clearer.  Suppose that we have an

    78 instance \c g of a directed graph type, say ListDigraph and an algorithm

    79 \code

    80 template <typename Digraph>

    81 int algorithm(const Digraph&);

    82 \endcode

    83 is needed to run on the reverse oriented graph.  It may be expensive

    84 (in time or in memory usage) to copy \c g with the reversed

    85 arcs.  In this case, an adaptor class is used, which (according

    86 to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.

    87 The adaptor uses the original digraph structure and digraph operations when

    88 methods of the reversed oriented graph are called.  This means that the adaptor

    89 have minor memory usage, and do not perform sophisticated algorithmic

    90 actions.  The purpose of it is to give a tool for the cases when a

    91 graph have to be used in a specific alteration.  If this alteration is

    92 obtained by a usual construction like filtering the node or the arc set or

    93 considering a new orientation, then an adaptor is worthwhile to use.

    94 To come back to the reverse oriented graph, in this situation

    95 \code

    96 template<typename Digraph> class ReverseDigraph;

    97 \endcode

    98 template class can be used. The code looks as follows

    99 \code

   100 ListDigraph g;

   101 ReverseDigraph<ListDigraph> rg(g);

   102 int result = algorithm(rg);

   103 \endcode

   104 During running the algorithm, the original digraph \c g is untouched.

   105 This techniques give rise to an elegant code, and based on stable

   106 graph adaptors, complex algorithms can be implemented easily.

   107

   108 In flow, circulation and matching problems, the residual

   109 graph is of particular importance. Combining an adaptor implementing

   110 this with shortest path algorithms or minimum mean cycle algorithms,

   111 a range of weighted and cardinality optimization algorithms can be

   112 obtained. For other examples, the interested user is referred to the

   113 detailed documentation of particular adaptors.

   114

   115 The behavior of graph adaptors can be very different. Some of them keep

   116 capabilities of the original graph while in other cases this would be

   117 meaningless. This means that the concepts that they meet depend

   118 on the graph adaptor, and the wrapped graph.

   119 For example, if an arc of a reversed digraph is deleted, this is carried

   120 out by deleting the corresponding arc of the original digraph, thus the

   121 adaptor modifies the original digraph.

   122 However in case of a residual digraph, this operation has no sense.

   123

   124 Let us stand one more example here to simplify your work.

   125 ReverseDigraph has constructor

   126 \code

   127 ReverseDigraph(Digraph& digraph);

   128 \endcode

   129 This means that in a situation, when a <tt>const %ListDigraph&</tt>

   130 reference to a graph is given, then it have to be instantiated with

   131 <tt>Digraph=const %ListDigraph</tt>.

   132 \code

   133 int algorithm1(const ListDigraph& g) {

   134   ReverseDigraph<const ListDigraph> rg(g);

   135   return algorithm2(rg);

   136 }

   137 \endcode

   138 */

   139

   140 /**

   141 @defgroup maps Maps

   142 @ingroup datas

   143 \brief Map structures implemented in LEMON.

   144

   145 This group contains the map structures implemented in LEMON.

   146

   147 LEMON provides several special purpose maps and map adaptors that e.g. combine

   148 new maps from existing ones.

   149

   150 <b>See also:</b> \ref map_concepts "Map Concepts".

   151 */

   152

   153 /**

   154 @defgroup graph_maps Graph Maps

   155 @ingroup maps

   156 \brief Special graph-related maps.

   157

   158 This group contains maps that are specifically designed to assign

   159 values to the nodes and arcs/edges of graphs.

   160

   161 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,

   162 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".

   163 */

   164

   165 /**

   166 \defgroup map_adaptors Map Adaptors

   167 \ingroup maps

   168 \brief Tools to create new maps from existing ones

   169

   170 This group contains map adaptors that are used to create "implicit"

   171 maps from other maps.

   172

   173 Most of them are \ref concepts::ReadMap "read-only maps".

   174 They can make arithmetic and logical operations between one or two maps

   175 (negation, shifting, addition, multiplication, logical 'and', 'or',

   176 'not' etc.) or e.g. convert a map to another one of different Value type.

   177

   178 The typical usage of this classes is passing implicit maps to

   179 algorithms.  If a function type algorithm is called then the function

   180 type map adaptors can be used comfortable. For example let's see the

   181 usage of map adaptors with the \c graphToEps() function.

   182 \code

   183   Color nodeColor(int deg) {

   184     if (deg >= 2) {

   185       return Color(0.5, 0.0, 0.5);

   186     } else if (deg == 1) {

   187       return Color(1.0, 0.5, 1.0);

   188     } else {

   189       return Color(0.0, 0.0, 0.0);

   190     }

   191   }

   192

   193   Digraph::NodeMap<int> degree_map(graph);

   194

   195   graphToEps(graph, "graph.eps")

   196     .coords(coords).scaleToA4().undirected()

   197     .nodeColors(composeMap(functorToMap(nodeColor), degree_map))

   198     .run();

   199 \endcode

   200 The \c functorToMap() function makes an \c int to \c Color map from the

   201 \c nodeColor() function. The \c composeMap() compose the \c degree_map

   202 and the previously created map. The composed map is a proper function to

   203 get the color of each node.

   204

   205 The usage with class type algorithms is little bit harder. In this

   206 case the function type map adaptors can not be used, because the

   207 function map adaptors give back temporary objects.

   208 \code

   209   Digraph graph;

   210

   211   typedef Digraph::ArcMap<double> DoubleArcMap;

   212   DoubleArcMap length(graph);

   213   DoubleArcMap speed(graph);

   214

   215   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

   216   TimeMap time(length, speed);

   217

   218   Dijkstra<Digraph, TimeMap> dijkstra(graph, time);

   219   dijkstra.run(source, target);

   220 \endcode

   221 We have a length map and a maximum speed map on the arcs of a digraph.

   222 The minimum time to pass the arc can be calculated as the division of

   223 the two maps which can be done implicitly with the \c DivMap template

   224 class. We use the implicit minimum time map as the length map of the

   225 \c Dijkstra algorithm.

   226 */

   227

   228 /**

   229 @defgroup paths Path Structures

   230 @ingroup datas

   231 \brief %Path structures implemented in LEMON.

   232

   233 This group contains the path structures implemented in LEMON.

   234

   235 LEMON provides flexible data structures to work with paths.

   236 All of them have similar interfaces and they can be copied easily with

   237 assignment operators and copy constructors. This makes it easy and

   238 efficient to have e.g. the Dijkstra algorithm to store its result in

   239 any kind of path structure.

   240

   241 \sa lemon::concepts::Path

   242 */

   243

   244 /**

   245 @defgroup auxdat Auxiliary Data Structures

   246 @ingroup datas

   247 \brief Auxiliary data structures implemented in LEMON.

   248

   249 This group contains some data structures implemented in LEMON in

   250 order to make it easier to implement combinatorial algorithms.

   251 */

   252

   253 /**

   254 @defgroup algs Algorithms

   255 \brief This group contains the several algorithms

   256 implemented in LEMON.

   257

   258 This group contains the several algorithms

   259 implemented in LEMON.

   260 */

   261

   262 /**

   263 @defgroup search Graph Search

   264 @ingroup algs

   265 \brief Common graph search algorithms.

   266

   267 This group contains the common graph search algorithms, namely

   268 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).

   269 */

   270

   271 /**

   272 @defgroup shortest_path Shortest Path Algorithms

   273 @ingroup algs

   274 \brief Algorithms for finding shortest paths.

   275

   276 This group contains the algorithms for finding shortest paths in digraphs.

   277

   278  - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a

   279    source node when all arc lengths are non-negative.

   280  - \ref Suurballe A successive shortest path algorithm for finding

   281    arc-disjoint paths between two nodes having minimum total length.

   282 */

   283

   284 /**

   285 @defgroup max_flow Maximum Flow Algorithms

   286 @ingroup algs

   287 \brief Algorithms for finding maximum flows.

   288

   289 This group contains the algorithms for finding maximum flows and

   290 feasible circulations.

   291

   292 The \e maximum \e flow \e problem is to find a flow of maximum value between

   293 a single source and a single target. Formally, there is a \f$G=(V,A)\f$

   294 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and

   295 \f$s, t \in V\f$ source and target nodes.

   296 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the

   297 following optimization problem.

   298

   299 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f]

   300 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu)

   301     \quad \forall u\in V\setminus\{s,t\} \f]

   302 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]

   303

   304 \ref Preflow implements the preflow push-relabel algorithm of Goldberg and

   305 Tarjan for solving this problem. It also provides functions to query the

   306 minimum cut, which is the dual problem of maximum flow.

   307

   308

   309 \ref Circulation is a preflow push-relabel algorithm implemented directly

   310 for finding feasible circulations, which is a somewhat different problem,

   311 but it is strongly related to maximum flow.

   312 For more information, see \ref Circulation.

   313 */

   314

   315 /**

   316 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms

   317 @ingroup algs

   318

   319 \brief Algorithms for finding minimum cost flows and circulations.

   320

   321 This group contains the algorithms for finding minimum cost flows and

   322 circulations. For more information about this problem and its dual

   323 solution see \ref min_cost_flow "Minimum Cost Flow Problem".

   324

   325 \ref NetworkSimplex is an efficient implementation of the primal Network

   326 Simplex algorithm for finding minimum cost flows. It also provides dual

   327 solution (node potentials), if an optimal flow is found.

   328 */

   329

   330 /**

   331 @defgroup min_cut Minimum Cut Algorithms

   332 @ingroup algs

   333

   334 \brief Algorithms for finding minimum cut in graphs.

   335

   336 This group contains the algorithms for finding minimum cut in graphs.

   337

   338 The \e minimum \e cut \e problem is to find a non-empty and non-complete

   339 \f$X\f$ subset of the nodes with minimum overall capacity on

   340 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a

   341 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum

   342 cut 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}cap(uv) \f]

   346

   347 LEMON contains several algorithms related to minimum cut problems:

   348

   349 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut

   350   in directed graphs.

   351 - \ref GomoryHu "Gomory-Hu tree computation" for calculating

   352   all-pairs minimum cut in undirected graphs.

   353

   354 If you want to find minimum cut just between two distinict nodes,

   355 see the \ref max_flow "maximum flow problem".

   356 */

   357

   358 /**

   359 @defgroup graph_properties Connectivity and Other Graph Properties

   360 @ingroup algs

   361 \brief Algorithms for discovering the graph properties

   362

   363 This group contains the algorithms for discovering the graph properties

   364 like connectivity, bipartiteness, euler property, simplicity etc.

   365

   366 \image html edge_biconnected_components.png

   367 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth

   368 */

   369

   370 /**

   371 @defgroup matching Matching Algorithms

   372 @ingroup algs

   373 \brief Algorithms for finding matchings in graphs and bipartite graphs.

   374

   375 This group contains the algorithms for calculating matchings in graphs.

   376 The general matching problem is finding a subset of the edges for which

   377 each node has at most one incident edge.

   378

   379 There are several different algorithms for calculate matchings in

   380 graphs. The goal of the matching optimization

   381 can be finding maximum cardinality, maximum weight or minimum cost

   382 matching. The search can be constrained to find perfect or

   383 maximum cardinality matching.

   384

   385 The matching algorithms implemented in LEMON:

   386 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating

   387   maximum cardinality matching in general graphs.

   388 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating

   389   maximum weighted matching in general graphs.

   390 - \ref MaxWeightedPerfectMatching

   391   Edmond's blossom shrinking algorithm for calculating maximum weighted

   392   perfect matching in general graphs.

   393

   394 \image html bipartite_matching.png

   395 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth

   396 */

   397

   398 /**

   399 @defgroup spantree Minimum Spanning Tree Algorithms

   400 @ingroup algs

   401 \brief Algorithms for finding minimum cost spanning trees and arborescences.

   402

   403 This group contains the algorithms for finding minimum cost spanning

   404 trees and arborescences.

   405 */

   406

   407 /**

   408 @defgroup auxalg Auxiliary Algorithms

   409 @ingroup algs

   410 \brief Auxiliary algorithms implemented in LEMON.

   411

   412 This group contains some algorithms implemented in LEMON

   413 in order to make it easier to implement complex algorithms.

   414 */

   415

   416 /**

   417 @defgroup gen_opt_group General Optimization Tools

   418 \brief This group contains some general optimization frameworks

   419 implemented in LEMON.

   420

   421 This group contains some general optimization frameworks

   422 implemented in LEMON.

   423 */

   424

   425 /**

   426 @defgroup lp_group Lp and Mip Solvers

   427 @ingroup gen_opt_group

   428 \brief Lp and Mip solver interfaces for LEMON.

   429

   430 This group contains Lp and Mip solver interfaces for LEMON. The

   431 various LP solvers could be used in the same manner with this

   432 interface.

   433 */

   434

   435 /**

   436 @defgroup utils Tools and Utilities

   437 \brief Tools and utilities for programming in LEMON

   438

   439 Tools and utilities for programming in LEMON.

   440 */

   441

   442 /**

   443 @defgroup gutils Basic Graph Utilities

   444 @ingroup utils

   445 \brief Simple basic graph utilities.

   446

   447 This group contains some simple basic graph utilities.

   448 */

   449

   450 /**

   451 @defgroup misc Miscellaneous Tools

   452 @ingroup utils

   453 \brief Tools for development, debugging and testing.

   454

   455 This group contains several useful tools for development,

   456 debugging and testing.

   457 */

   458

   459 /**

   460 @defgroup timecount Time Measuring and Counting

   461 @ingroup misc

   462 \brief Simple tools for measuring the performance of algorithms.

   463

   464 This group contains simple tools for measuring the performance

   465 of algorithms.

   466 */

   467

   468 /**

   469 @defgroup exceptions Exceptions

   470 @ingroup utils

   471 \brief Exceptions defined in LEMON.

   472

   473 This group contains the exceptions defined in LEMON.

   474 */

   475

   476 /**

   477 @defgroup io_group Input-Output

   478 \brief Graph Input-Output methods

   479

   480 This group contains the tools for importing and exporting graphs

   481 and graph related data. Now it supports the \ref lgf-format

   482 "LEMON Graph Format", the \c DIMACS format and the encapsulated

   483 postscript (EPS) format.

   484 */

   485

   486 /**

   487 @defgroup lemon_io LEMON Graph Format

   488 @ingroup io_group

   489 \brief Reading and writing LEMON Graph Format.

   490

   491 This group contains methods for reading and writing

   492 \ref lgf-format "LEMON Graph Format".

   493 */

   494

   495 /**

   496 @defgroup eps_io Postscript Exporting

   497 @ingroup io_group

   498 \brief General \c EPS drawer and graph exporter

   499

   500 This group contains general \c EPS drawing methods and special

   501 graph exporting tools.

   502 */

   503

   504 /**

   505 @defgroup dimacs_group DIMACS format

   506 @ingroup io_group

   507 \brief Read and write files in DIMACS format

   508

   509 Tools to read a digraph from or write it to a file in DIMACS format data.

   510 */

   511

   512 /**

   513 @defgroup nauty_group NAUTY Format

   514 @ingroup io_group

   515 \brief Read \e Nauty format

   516

   517 Tool to read graphs from \e Nauty format data.

   518 */

   519

   520 /**

   521 @defgroup concept Concepts

   522 \brief Skeleton classes and concept checking classes

   523

   524 This group contains the data/algorithm skeletons and concept checking

   525 classes implemented in LEMON.

   526

   527 The purpose of the classes in this group is fourfold.

   528

   529 - These classes contain the documentations of the %concepts. In order

   530   to avoid document multiplications, an implementation of a concept

   531   simply refers to the corresponding concept class.

   532

   533 - These classes declare every functions, <tt>typedef</tt>s etc. an

   534   implementation of the %concepts should provide, however completely

   535   without implementations and real data structures behind the

   536   interface. On the other hand they should provide nothing else. All

   537   the algorithms working on a data structure meeting a certain concept

   538   should compile with these classes. (Though it will not run properly,

   539   of course.) In this way it is easily to check if an algorithm

   540   doesn't use any extra feature of a certain implementation.

   541

   542 - The concept descriptor classes also provide a <em>checker class</em>

   543   that makes it possible to check whether a certain implementation of a

   544   concept indeed provides all the required features.

   545

   546 - Finally, They can serve as a skeleton of a new implementation of a concept.

   547 */

   548

   549 /**

   550 @defgroup graph_concepts Graph Structure Concepts

   551 @ingroup concept

   552 \brief Skeleton and concept checking classes for graph structures

   553

   554 This group contains the skeletons and concept checking classes of LEMON's

   555 graph structures and helper classes used to implement these.

   556 */

   557

   558 /**

   559 @defgroup map_concepts Map Concepts

   560 @ingroup concept

   561 \brief Skeleton and concept checking classes for maps

   562

   563 This group contains the skeletons and concept checking classes of maps.

   564 */

   565

   566 /**

   567 \anchor demoprograms

   568

   569 @defgroup demos Demo Programs

   570

   571 Some demo programs are listed here. Their full source codes can be found in

   572 the \c demo subdirectory of the source tree.

   573

   574 In order to compile them, use the <tt>make demo</tt> or the

   575 <tt>make check</tt> commands.

   576 */

   577

   578 /**

   579 @defgroup tools Standalone Utility Applications

   580

   581 Some utility applications are listed here.

   582

   583 The standard compilation procedure (<tt>./configure;make</tt>) will compile

   584 them, as well.

   585 */

   586

   587 }