*

  *

  */

  */

 /**

 /**

 @defgroup datas Data Structures

 @defgroup datas Data Structures

 */

 */

 /**

 /**

 @defgroup graphs Graph Structures

 @defgroup graphs Graph Structures

 @ingroup datas

 @ingroup datas

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

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

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

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

 is to be shrunk for another algorithm. 

 is to be shrunk for another algorithm. 

 LEMON also provides a variety of graphs for these requirements called 

 LEMON also provides a variety of graphs for these requirements called 

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

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

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

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

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

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

 with any graph structures. 

 with any graph structures. 

 */

 */

 /**

 /**

 @ingroup graphs

 @ingroup graphs

 \brief Graph types between real graphs and graph adaptors.

 \brief Graph types between real graphs and graph adaptors.

 */

 */

 /**

 /**

 @defgroup maps Maps 

 @defgroup maps Maps 

 @ingroup datas

 @ingroup datas

 new maps from existing ones.

 new maps from existing ones.

 */

 */

 /**

 /**

 @defgroup graph_maps Graph Maps 

 @defgroup graph_maps Graph Maps 

 @ingroup maps

 @ingroup maps

 \brief Special Graph-Related Maps.

 \brief Special Graph-Related Maps.

 */

 */

 /**

 /**

 \defgroup map_adaptors Map Adaptors

 \defgroup map_adaptors Map Adaptors

 \ingroup maps

 \ingroup maps

 \brief Tools to create new maps from existing ones

 \brief Tools to create new maps from existing ones

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

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

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

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

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

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

 of different Value type.

 of different Value type.

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

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

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

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

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

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

 \code

 \code

   Color nodeColor(int deg) {

   Color nodeColor(int deg) {

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

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

 get color of each node.

 get color of each node.

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

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

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

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

 \code

 \code

   Graph graph;

   Graph graph;

   typedef Graph::EdgeMap<double> DoubleEdgeMap;

   typedef Graph::EdgeMap<double> DoubleEdgeMap;

   DoubleEdgeMap length(graph);

   DoubleEdgeMap length(graph);

 */

 */

 /**

 /**

 @defgroup matrices Matrices 

 @defgroup matrices Matrices 

 @ingroup datas

 @ingroup datas

 */

 */

 /**

 /**

 @defgroup paths Path Structures

 @defgroup paths Path Structures

 @ingroup datas

 @ingroup datas

 \brief Path structures implemented in LEMON.

 \brief Path structures implemented in LEMON.

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

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

 any kind of path structure.

 any kind of path structure.

 \sa lemon::concepts::Path

 \sa lemon::concepts::Path

 */

 */

 /**

 /**

 @defgroup auxdat Auxiliary Data Structures

 @defgroup auxdat Auxiliary Data Structures

 @ingroup datas

 @ingroup datas

 order to make it easier to implement combinatorial algorithms.

 order to make it easier to implement combinatorial algorithms.

 */

 */

 /**

 /**

 */

 */

 /**

 /**

 @defgroup search Graph Search

 @defgroup search Graph Search

 @ingroup algs

 @ingroup algs

 */

 */

 /**

 /**

 @defgroup shortest_path Shortest Path algorithms

 @defgroup shortest_path Shortest Path algorithms

 @ingroup algs

 @ingroup algs

 */

 */

 /** 

 /** 

 @defgroup max_flow Maximum Flow algorithms 

 @defgroup max_flow Maximum Flow algorithms 

 @ingroup algs 

 @ingroup algs 

 This group describes the algorithms for finding maximum flows and

 This group describes the algorithms for finding maximum flows and

 feasible circulations.

 feasible circulations.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 fastest method to compute the maximum flow. All impelementations

 fastest method to compute the maximum flow. All impelementations

 */

 */

 /**

 /**

 @defgroup min_cost_flow Minimum Cost Flow algorithms

 @defgroup min_cost_flow Minimum Cost Flow algorithms

 @ingroup algs

 @ingroup algs

 This group describes the algorithms for finding minimum cost flows and

 This group describes the algorithms for finding minimum cost flows and

 circulations.  

 circulations.  

 */

 */

 /**

 /**

 @defgroup min_cut Minimum Cut algorithms 

 @defgroup min_cut Minimum Cut algorithms 

 @ingroup algs 

 @ingroup algs 

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

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

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

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

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

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

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

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

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

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

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

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

   in directed graphs  

   in directed graphs  

   calculate minimum cut in undirected graphs

   calculate minimum cut in undirected graphs

   pairs minimum cut in undirected graphs

   pairs minimum cut in undirected graphs

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

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

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

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

 */

 */

 /**

 /**

 @defgroup graph_prop Connectivity and other graph properties

 @defgroup graph_prop Connectivity and other graph properties

 @ingroup algs

 @ingroup algs

 \image html edge_biconnected_components.png

 \image html edge_biconnected_components.png

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

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

 */

 */

 /**

 /**

 @defgroup planar Planarity embedding and drawing

 @defgroup planar Planarity embedding and drawing

 @ingroup algs

 @ingroup algs

 \image html planar.png

 \image html planar.png

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

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

 */

 */

 /**

 /**

 @defgroup matching Matching algorithms 

 @defgroup matching Matching algorithms 

 @ingroup algs

 @ingroup algs

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

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

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

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

 There are several different algorithms for calculate matchings in

 There are several different algorithms for calculate matchings in

 graphs.  The matching problems in bipartite graphs are generally

 graphs.  The matching problems in bipartite graphs are generally

 */

 */

 /**

 /**

 @defgroup spantree Minimum Spanning Tree algorithms

 @defgroup spantree Minimum Spanning Tree algorithms

 @ingroup algs

 @ingroup algs

 tree in a graph

 tree in a graph

 */

 */

 /**

 /**

 @defgroup auxalg Auxiliary algorithms

 @defgroup auxalg Auxiliary algorithms

 @ingroup algs

 @ingroup algs

 */

 */

 /**

 /**

 @defgroup approx Approximation algorithms

 @defgroup approx Approximation algorithms

 */

 */

 /**

 /**

 @defgroup gen_opt_group General Optimization Tools

 @defgroup gen_opt_group General Optimization Tools

 \brief This group describes some general optimization frameworks

 \brief This group describes some general optimization frameworks

 */

 */

 /** 

 /** 

 @defgroup lp_utils Tools for Lp and Mip solvers 

 @defgroup lp_utils Tools for Lp and Mip solvers 

 @ingroup lp_group

 @ingroup lp_group

 This group adds some helper tools to general optimization framework

 This group adds some helper tools to general optimization framework

 implemented in LEMON.

 implemented in LEMON.

 */

 */

 /**

 /**

 @defgroup metah Metaheuristics

 @defgroup metah Metaheuristics

 @ingroup gen_opt_group

 @ingroup gen_opt_group

 \brief Metaheuristics for LEMON library.

 \brief Metaheuristics for LEMON library.

 */

 */

 /**

 /**

 @defgroup utils Tools and Utilities 

 @defgroup utils Tools and Utilities 

 */

 */

 /**

 /**

 @defgroup gutils Basic Graph Utilities

 @defgroup gutils Basic Graph Utilities

 @ingroup utils

 @ingroup utils

 This group describes some simple basic graph utilities.

 This group describes some simple basic graph utilities.

 */

 */

 /**

 /**

 @defgroup misc Miscellaneous Tools

 @defgroup misc Miscellaneous Tools

 @ingroup utils

 @ingroup utils

 debugging and testing.

 debugging and testing.

 */

 */

 /**

 /**

 @defgroup timecount Time measuring and Counting

 @defgroup timecount Time measuring and Counting

 @ingroup misc

 @ingroup misc

 of algorithms.

 of algorithms.

 */

 */

 /**

 /**

 @defgroup graphbits Tools for Graph Implementation

 @defgroup graphbits Tools for Graph Implementation

 @ingroup utils

 @ingroup utils

 the maps that dynamically update with the graph changes.

 the maps that dynamically update with the graph changes.

 */

 */

 /**

 /**

 @defgroup exceptions Exceptions

 @defgroup exceptions Exceptions

 @ingroup utils

 @ingroup utils

 */

 */

 /**

 /**

 @defgroup io_group Input-Output

 @defgroup io_group Input-Output

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

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

 */

 */

 /**

 /**

 @defgroup lemon_io Lemon Input-Output

 @defgroup lemon_io Lemon Input-Output

 @ingroup io_group

 @ingroup io_group

 \brief Reading and writing LEMON format

 \brief Reading and writing LEMON format

 tutorial pages.

 tutorial pages.

 */

 */

 /**

 /**

 @defgroup section_io Section readers and writers

 @defgroup section_io Section readers and writers

 @ingroup lemon_io

 @ingroup lemon_io

 @ingroup lemon_io

 @ingroup lemon_io

 */

 */

 /**

 /**

 @defgroup eps_io Postscript exporting

 @defgroup eps_io Postscript exporting

 @ingroup io_group

 @ingroup io_group

 \brief General \c EPS drawer and graph exporter

 \brief General \c EPS drawer and graph exporter

 graph exporting tools. 

 graph exporting tools. 

 */

 */

 /**

 /**

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

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

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

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

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

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

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

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

   concept indeed provides all the required features.

   concept indeed provides all the required features.

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

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

 */

 */

 /**

 /**

 @defgroup graph_concepts Graph Structure Concepts

 @defgroup graph_concepts Graph Structure Concepts

 @ingroup concept

 @ingroup concept

 \brief Skeleton and concept checking classes for graph structures

 \brief Skeleton and concept checking classes for graph structures

 graph structures and helper classes used to implement these.

 graph structures and helper classes used to implement these.

 */

 */

 /* --- Unused group

 /* --- Unused group

 @defgroup experimental Experimental Structures and Algorithms

 @defgroup experimental Experimental Structures and Algorithms

 The stuff here is subject to change.

 The stuff here is subject to change.

 */

 */

 /**

 /**

 \anchor demoprograms

 \anchor demoprograms

 @defgroup demos Demo programs

 @defgroup demos Demo programs

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

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

 the \c demo subdirectory of the source tree.

 the \c demo subdirectory of the source tree.

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

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

 them, as well. 

 them, as well.