doc/groups.dox
 author Peter Kovacs Sat, 05 Jul 2008 00:14:27 +0200 changeset 192 7bf5f97d574f parent 156 e561aa7675de child 209 765619b7cbb2 permissions -rw-r--r--
Doc improvements in LGF related files
     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

    21 This 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

    29 The implementation of combinatorial algorithms heavily relies on

    30 efficient graph implementations. LEMON offers data structures which are

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

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

    33

    34 The most efficient implementation of diverse applications require the

    35 usage of different physical graph implementations. These differences

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

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

    38 accessed.  LEMON provides several physical graph structures to meet

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

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

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

    42

    43 Alteration of standard containers need a very limited number of

    44 operations, these together satisfy the everyday requirements.

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

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

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

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

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

    50 is to be shrunk for another algorithm.

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

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

    53 in conjunction with other graph representations.

    54

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

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

    57 with any graph structures.

    58 */

    59

    60 /**

    61 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs

    62 @ingroup graphs

    63 \brief Graph types between real graphs and graph adaptors.

    64

    65 This group describes some graph types between real graphs and graph adaptors.

    66 These classes wrap graphs to give new functionality as the adaptors do it.

    67 On the other hand they are not light-weight structures as the adaptors.

    68 */

    69

    70 /**

    71 @defgroup maps Maps

    72 @ingroup datas

    73 \brief Map structures implemented in LEMON.

    74

    75 This group describes the map structures implemented in LEMON.

    76

    77 LEMON provides several special purpose maps that e.g. combine

    78 new maps from existing ones.

    79 */

    80

    81 /**

    82 @defgroup graph_maps Graph Maps

    83 @ingroup maps

    84 \brief Special graph-related maps.

    85

    86 This group describes maps that are specifically designed to assign

    87 values to the nodes and arcs of graphs.

    88 */

    89

    90

    91 /**

    92 \defgroup map_adaptors Map Adaptors

    93 \ingroup maps

    94 \brief Tools to create new maps from existing ones

    95

    96 This group describes map adaptors that are used to create "implicit"

    97 maps from other maps.

    98

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

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

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

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

   103

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

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

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

   107 usage of map adaptors with the \c digraphToEps() function.

   108 \code

   109   Color nodeColor(int deg) {

   110     if (deg >= 2) {

   111       return Color(0.5, 0.0, 0.5);

   112     } else if (deg == 1) {

   113       return Color(1.0, 0.5, 1.0);

   114     } else {

   115       return Color(0.0, 0.0, 0.0);

   116     }

   117   }

   118

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

   120

   121   digraphToEps(graph, "graph.eps")

   122     .coords(coords).scaleToA4().undirected()

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

   124     .run();

   125 \endcode

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

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

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

   129 get the color of each node.

   130

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

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

   133 function map adaptors give back temporary objects.

   134 \code

   135   Digraph graph;

   136

   137   typedef Digraph::ArcMap<double> DoubleArcMap;

   138   DoubleArcMap length(graph);

   139   DoubleArcMap speed(graph);

   140

   141   typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;

   142   TimeMap time(length, speed);

   143

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

   145   dijkstra.run(source, target);

   146 \endcode

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

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

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

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

   151 \c Dijkstra algorithm.

   152 */

   153

   154 /**

   155 @defgroup matrices Matrices

   156 @ingroup datas

   157 \brief Two dimensional data storages implemented in LEMON.

   158

   159 This group describes two dimensional data storages implemented in LEMON.

   160 */

   161

   162 /**

   163 @defgroup paths Path Structures

   164 @ingroup datas

   165 \brief Path structures implemented in LEMON.

   166

   167 This group describes the path structures implemented in LEMON.

   168

   169 LEMON provides flexible data structures to work with paths.

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

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

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

   173 any kind of path structure.

   174

   175 \sa lemon::concepts::Path

   176

   177 */

   178

   179 /**

   180 @defgroup auxdat Auxiliary Data Structures

   181 @ingroup datas

   182 \brief Auxiliary data structures implemented in LEMON.

   183

   184 This group describes some data structures implemented in LEMON in

   185 order to make it easier to implement combinatorial algorithms.

   186 */

   187

   188

   189 /**

   190 @defgroup algs Algorithms

   191 \brief This group describes the several algorithms

   192 implemented in LEMON.

   193

   194 This group describes the several algorithms

   195 implemented in LEMON.

   196 */

   197

   198 /**

   199 @defgroup search Graph Search

   200 @ingroup algs

   201 \brief Common graph search algorithms.

   202

   203 This group describes the common graph search algorithms like

   204 Breadth-first search (Bfs) and Depth-first search (Dfs).

   205 */

   206

   207 /**

   208 @defgroup shortest_path Shortest Path algorithms

   209 @ingroup algs

   210 \brief Algorithms for finding shortest paths.

   211

   212 This group describes the algorithms for finding shortest paths in graphs.

   213 */

   214

   215 /**

   216 @defgroup max_flow Maximum Flow algorithms

   217 @ingroup algs

   218 \brief Algorithms for finding maximum flows.

   219

   220 This group describes the algorithms for finding maximum flows and

   221 feasible circulations.

   222

   223 The maximum flow problem is to find a flow between a single source and

   224 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$

   225 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity

   226 function and given \f$s, t \in V\f$ source and target node. The

   227 maximum flow is the \f$f_a\f$ solution of the next optimization problem:

   228

   229 \f[ 0 \le f_a \le c_a \f]

   230 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv} \qquad \forall u \in V \setminus \{s,t\}\f]

   231 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]

   232

   233 LEMON contains several algorithms for solving maximum flow problems:

   234 - \ref lemon::EdmondsKarp "Edmonds-Karp"

   235 - \ref lemon::Preflow "Goldberg's Preflow algorithm"

   236 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"

   237 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"

   238

   239 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the

   240 fastest method to compute the maximum flow. All impelementations

   241 provides functions to query the minimum cut, which is the dual linear

   242 programming problem of the maximum flow.

   243

   244 */

   245

   246 /**

   247 @defgroup min_cost_flow Minimum Cost Flow algorithms

   248 @ingroup algs

   249

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

   251

   252 This group describes the algorithms for finding minimum cost flows and

   253 circulations.

   254 */

   255

   256 /**

   257 @defgroup min_cut Minimum Cut algorithms

   258 @ingroup algs

   259

   260 \brief Algorithms for finding minimum cut in graphs.

   261

   262 This group describes the algorithms for finding minimum cut in graphs.

   263

   264 The minimum cut problem is to find a non-empty and non-complete

   265 \f$X\f$ subset of the vertices with minimum overall capacity on

   266 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an

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

   268 cut is the \f$X\f$ solution of the next optimization problem:

   269

   270 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}\sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]

   271

   272 LEMON contains several algorithms related to minimum cut problems:

   273

   274 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut

   275   in directed graphs

   276 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to

   277   calculate minimum cut in undirected graphs

   278 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all

   279   pairs minimum cut in undirected graphs

   280

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

   282 please see the \ref max_flow "Maximum Flow page".

   283

   284 */

   285

   286 /**

   287 @defgroup graph_prop Connectivity and other graph properties

   288 @ingroup algs

   289 \brief Algorithms for discovering the graph properties

   290

   291 This group describes the algorithms for discovering the graph properties

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

   293

   294 \image html edge_biconnected_components.png

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

   296 */

   297

   298 /**

   299 @defgroup planar Planarity embedding and drawing

   300 @ingroup algs

   301 \brief Algorithms for planarity checking, embedding and drawing

   302

   303 This group describes the algorithms for planarity checking, embedding and drawing.

   304

   305 \image html planar.png

   306 \image latex planar.eps "Plane graph" width=\textwidth

   307 */

   308

   309 /**

   310 @defgroup matching Matching algorithms

   311 @ingroup algs

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

   313

   314 This group contains algorithm objects and functions to calculate

   315 matchings in graphs and bipartite graphs. The general matching problem is

   316 finding a subset of the arcs which does not shares common endpoints.

   317

   318 There are several different algorithms for calculate matchings in

   319 graphs.  The matching problems in bipartite graphs are generally

   320 easier than in general graphs. The goal of the matching optimization

   321 can be the finding maximum cardinality, maximum weight or minimum cost

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

   323 maximum cardinality matching.

   324

   325 Lemon contains the next algorithms:

   326 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp

   327   augmenting path algorithm for calculate maximum cardinality matching in

   328   bipartite graphs

   329 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel

   330   algorithm for calculate maximum cardinality matching in bipartite graphs

   331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"

   332   Successive shortest path algorithm for calculate maximum weighted matching

   333   and maximum weighted bipartite matching in bipartite graph

   334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"

   335   Successive shortest path algorithm for calculate minimum cost maximum

   336   matching in bipartite graph

   337 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm

   338   for calculate maximum cardinality matching in general graph

   339 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom

   340   shrinking algorithm for calculate maximum weighted matching in general

   341   graph

   342 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"

   343   Edmond's blossom shrinking algorithm for calculate maximum weighted

   344   perfect matching in general graph

   345

   346 \image html bipartite_matching.png

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

   348

   349 */

   350

   351 /**

   352 @defgroup spantree Minimum Spanning Tree algorithms

   353 @ingroup algs

   354 \brief Algorithms for finding a minimum cost spanning tree in a graph.

   355

   356 This group describes the algorithms for finding a minimum cost spanning

   357 tree in a graph

   358 */

   359

   360

   361 /**

   362 @defgroup auxalg Auxiliary algorithms

   363 @ingroup algs

   364 \brief Auxiliary algorithms implemented in LEMON.

   365

   366 This group describes some algorithms implemented in LEMON

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

   368 */

   369

   370 /**

   371 @defgroup approx Approximation algorithms

   372 \brief Approximation algorithms.

   373

   374 This group describes the approximation and heuristic algorithms

   375 implemented in LEMON.

   376 */

   377

   378 /**

   379 @defgroup gen_opt_group General Optimization Tools

   380 \brief This group describes some general optimization frameworks

   381 implemented in LEMON.

   382

   383 This group describes some general optimization frameworks

   384 implemented in LEMON.

   385

   386 */

   387

   388 /**

   389 @defgroup lp_group Lp and Mip solvers

   390 @ingroup gen_opt_group

   391 \brief Lp and Mip solver interfaces for LEMON.

   392

   393 This group describes Lp and Mip solver interfaces for LEMON. The

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

   395 interface.

   396

   397 */

   398

   399 /**

   400 @defgroup lp_utils Tools for Lp and Mip solvers

   401 @ingroup lp_group

   402 \brief Helper tools to the Lp and Mip solvers.

   403

   404 This group adds some helper tools to general optimization framework

   405 implemented in LEMON.

   406 */

   407

   408 /**

   409 @defgroup metah Metaheuristics

   410 @ingroup gen_opt_group

   411 \brief Metaheuristics for LEMON library.

   412

   413 This group describes some metaheuristic optimization tools.

   414 */

   415

   416 /**

   417 @defgroup utils Tools and Utilities

   418 \brief Tools and utilities for programming in LEMON

   419

   420 Tools and utilities for programming in LEMON.

   421 */

   422

   423 /**

   424 @defgroup gutils Basic Graph Utilities

   425 @ingroup utils

   426 \brief Simple basic graph utilities.

   427

   428 This group describes some simple basic graph utilities.

   429 */

   430

   431 /**

   432 @defgroup misc Miscellaneous Tools

   433 @ingroup utils

   434 \brief Tools for development, debugging and testing.

   435

   436 This group describes several useful tools for development,

   437 debugging and testing.

   438 */

   439

   440 /**

   441 @defgroup timecount Time measuring and Counting

   442 @ingroup misc

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

   444

   445 This group describes simple tools for measuring the performance

   446 of algorithms.

   447 */

   448

   449 /**

   450 @defgroup graphbits Tools for Graph Implementation

   451 @ingroup utils

   452 \brief Tools to make it easier to create graphs.

   453

   454 This group describes the tools that makes it easier to create graphs and

   455 the maps that dynamically update with the graph changes.

   456 */

   457

   458 /**

   459 @defgroup exceptions Exceptions

   460 @ingroup utils

   461 \brief Exceptions defined in LEMON.

   462

   463 This group describes the exceptions defined in LEMON.

   464 */

   465

   466 /**

   467 @defgroup io_group Input-Output

   468 \brief Graph Input-Output methods

   469

   470 This group describes the tools for importing and exporting graphs

   471 and graph related data. Now it supports the LEMON format, the

   472 \c DIMACS format and the encapsulated postscript (EPS) format.

   473 */

   474

   475 /**

   476 @defgroup lemon_io Lemon Input-Output

   477 @ingroup io_group

   478 \brief Reading and writing \ref lgf-format "Lemon Graph Format".

   479

   480 This group describes methods for reading and writing \ref lgf-format "Lemon Graph Format".

   481 */

   482

   483 /**

   484 @defgroup eps_io Postscript exporting

   485 @ingroup io_group

   486 \brief General \c EPS drawer and graph exporter

   487

   488 This group describes general \c EPS drawing methods and special

   489 graph exporting tools.

   490 */

   491

   492

   493 /**

   494 @defgroup concept Concepts

   495 \brief Skeleton classes and concept checking classes

   496

   497 This group describes the data/algorithm skeletons and concept checking

   498 classes implemented in LEMON.

   499

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

   501

   502 - These classes contain the documentations of the concepts. In order

   503   to avoid document multiplications, an implementation of a concept

   504   simply refers to the corresponding concept class.

   505

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

   507   implementation of the concepts should provide, however completely

   508   without implementations and real data structures behind the

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

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

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

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

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

   514

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

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

   517   concept indeed provides all the required features.

   518

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

   520

   521 */

   522

   523

   524 /**

   525 @defgroup graph_concepts Graph Structure Concepts

   526 @ingroup concept

   527 \brief Skeleton and concept checking classes for graph structures

   528

   529 This group describes the skeletons and concept checking classes of LEMON's

   530 graph structures and helper classes used to implement these.

   531 */

   532

   533 /* --- Unused group

   534 @defgroup experimental Experimental Structures and Algorithms

   535 This group describes some Experimental structures and algorithms.

   536 The stuff here is subject to change.

   537 */

   538

   539 /**

   540 \anchor demoprograms

   541

   542 @defgroup demos Demo programs

   543

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

   545 the \c demo subdirectory of the source tree.

   546

   547 It order to compile them, use <tt>--enable-demo</tt> configure option when

   548 build the library.

   549 */

   550

   551 /**

   552 @defgroup tools Standalone utility applications

   553

   554 Some utility applications are listed here.

   555

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

   557 them, as well.

   558 */

   559