doc/groups.dox
 author Alpar Juttner Mon, 07 Jan 2008 19:23:03 +0100 changeset 41 b11737922197 parent 40 8f4e8273a458 child 50 a34c58ff6e40 permissions -rw-r--r--
Minor updates in the doc
     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 graph 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 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 edges 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 representation.

    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-Adaptors Classes for Graphs

    62 @ingroup graphs

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

    64

    65 Graph types between real graphs and graph adaptors. These classes wrap

    66 graphs to give new functionality as the adaptors do it. On the other

    67 hand 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

    75 LEMON provides several special maps that e.g. combine

    76 new maps from existing ones.

    77 */

    78

    79 /**

    80 @defgroup graph_maps Graph Maps

    81 @ingroup maps

    82 \brief Special Graph-Related Maps.

    83

    84 These maps are specifically designed to assign values to the nodes and edges of

    85 graphs.

    86 */

    87

    88

    89 /**

    90 \defgroup map_adaptors Map Adaptors

    91 \ingroup maps

    92 \brief Tools to create new maps from existing ones

    93

    94 Map adaptors are used to create "implicit" maps from other maps.

    95

    96 Most of them are \ref lemon::concepts::ReadMap "ReadMap"s. They can

    97 make arithmetic operations between one or two maps (negation, scaling,

    98 addition, multiplication etc.) or e.g. convert a map to another one

    99 of different Value type.

   100

   101 The typical usage of this classes is the passing implicit maps to

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

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

   104 usage 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

   123 The \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

   125 and the previous created map. The composed map is proper function to

   126 get color of each node.

   127

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

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

   130 function 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

   146 We have a length map and a maximum speed map on a graph. The minimum

   147 time to pass the edge can be calculated as the division of the two

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

   149 class. 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

   158 Two dimensional data storages.

   159 */

   160

   161 /**

   162 @defgroup paths Path Structures

   163 @ingroup datas

   164 \brief Path structures implemented in LEMON.

   165

   166 LEMON provides flexible data structures

   167 to work with paths.

   168

   169 All of them have similar interfaces, and it can be copied easily with

   170 assignment operator and copy constructor. This make it easy and

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

   172 any 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

   183 This group describes the data structures implemented in LEMON in

   184 order to make it easier to implement combinatorial algorithms.

   185 */

   186

   187

   188 /**

   189 @defgroup algs Algorithms

   190 \brief This group describes the several algorithms

   191 implemented in LEMON.

   192

   193 This group describes the several algorithms

   194 implemented in LEMON.

   195 */

   196

   197 /**

   198 @defgroup search Graph Search

   199 @ingroup algs

   200 \brief This group contains the common graph

   201 search algorithms.

   202

   203 This group contains the common graph

   204 search 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

   211 for finding shortest paths.

   212

   213 This group describes the algorithms for finding shortest paths in

   214 graphs.

   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

   223 This group describes the algorithms for finding maximum flows and

   224 feasible circulations.

   225

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

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

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

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

   230 maximum 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

   236 The 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

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

   243 fastest method to compute the maximum flow. All impelementations

   244 provides functions for query the minimum cut, which is the dual linear

   245 programming 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

   254 for finding minimum cost flows and circulations.

   255

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

   257 circulations.

   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

   265 graphs.

   266

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

   268

   269 The 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

   271 outgoing 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

   273 cut 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

   277 The 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

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

   287 please 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

   295 for discover the graph properties

   296

   297 This group describes the algorithms for discover the graph properties

   298 like 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

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

   319 for find matchings in graphs and bipartite graphs.

   320

   321 This group provides some algorithm objects and function to calculate

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

   323 finding a subset of the edges which does not shares common endpoints.

   324

   325 There are several different algorithms for calculate matchings in

   326 graphs.  The matching problems in bipartite graphs are generally

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

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

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

   330 maximum cardinality matching.

   331

   332 Lemon 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

   362 tree in a graph

   363

   364 This group contains the algorithms for finding a minimum cost spanning

   365 tree in a graph

   366 */

   367

   368

   369 /**

   370 @defgroup auxalg Auxiliary algorithms

   371 @ingroup algs

   372 \brief Some algorithms implemented in LEMON.

   373

   374 This group describes the algorithms in LEMON in order to make

   375 it easier to implement complex algorithms.

   376 */

   377

   378 /**

   379 @defgroup approx Approximation algorithms

   380 \brief Approximation algorithms

   381

   382 Approximation and heuristic algorithms

   383 */

   384

   385 /**

   386 @defgroup gen_opt_group General Optimization Tools

   387 \brief This group describes some general optimization frameworks

   388 implemented in LEMON.

   389

   390 This group describes some general optimization frameworks

   391 implemented 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

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

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

   402 interface.

   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

   410 implemented in LEMON.

   411

   412 This group adds some helper tools to general optimization framework

   413 implemented in LEMON.

   414 */

   415

   416 /**

   417 @defgroup metah Metaheuristics

   418 @ingroup gen_opt_group

   419 \brief Metaheuristics for LEMON library.

   420

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

   428 Tools 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

   436 This group describes some simple basic graph utilities.

   437 */

   438

   439 /**

   440 @defgroup misc Miscellaneous Tools

   441 @ingroup utils

   442 Here you can find several useful tools for development,

   443 debugging and testing.

   444 */

   445

   446

   447 /**

   448 @defgroup timecount Time measuring and Counting

   449 @ingroup misc

   450 Here you can find simple tools for measuring the performance

   451 of 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

   459 This group describes the tools that makes it easier to make graphs and

   460 the maps that dynamically update with the graph changes.

   461 */

   462

   463 /**

   464 @defgroup exceptions Exceptions

   465 @ingroup utils

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

   473 Here you can find tools for importing and exporting graphs

   474 and 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

   483 Methods for reading and writing LEMON format. More about this

   484 format you can find on the \ref graph-io-page "Graph Input-Output"

   485 tutorial 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

   493 Here you can find which section readers and writers can attach to

   494 the 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

   502 The Input-Output classes can handle more data type by example

   503 as map or attribute value. Each of these should be written and

   504 read 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

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

   513 graph exporting tools.

   514 */

   515

   516

   517 /**

   518 @defgroup concept Concepts

   519 \brief Skeleton classes and concept checking classes

   520

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

   522 classes implemented in LEMON.

   523

   524 The 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

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

   554 graph structures and helper classes used to implement these.

   555 */

   556

   557 /* --- Unused group

   558 @defgroup experimental Experimental Structures and Algorithms

   559 This group contains some Experimental structures and algorithms.

   560 The stuff here is subject to change.

   561 */

   562

   563 /**

   564 \anchor demoprograms

   565

   566 @defgroup demos Demo programs

   567

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

   569 the \c demo subdirectory of the source tree.

   570

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

   572 build the library.

   573

   574 */

   575

   576 /**

   577 @defgroup tools Standalone utility applications

   578

   579 Some utility applications are listed here.

   580

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

   582 them, as well.

   583

   584 */

   585