doc/groups.dox
changeset 407 e22fc10ab6f1
parent 388 0a3ec097a76c
child 418 ad483acf1654
equal deleted inserted replaced
13:1ae52ff370ac 14:63a6d05271ae
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
       
    19 namespace lemon {
       
    20 
    19 /**
    21 /**
    20 @defgroup datas Data Structures
    22 @defgroup datas Data Structures
    21 This group describes the several data structures implemented in LEMON.
    23 This group describes the several data structures implemented in LEMON.
    22 */
    24 */
    23 
    25 
    86 @defgroup graph_maps Graph Maps
    88 @defgroup graph_maps Graph Maps
    87 @ingroup maps
    89 @ingroup maps
    88 \brief Special graph-related maps.
    90 \brief Special graph-related maps.
    89 
    91 
    90 This group describes maps that are specifically designed to assign
    92 This group describes maps that are specifically designed to assign
    91 values to the nodes and arcs of graphs.
    93 values to the nodes and arcs/edges of graphs.
       
    94 
       
    95 If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
       
    96 \c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
    92 */
    97 */
    93 
    98 
    94 /**
    99 /**
    95 \defgroup map_adaptors Map Adaptors
   100 \defgroup map_adaptors Map Adaptors
    96 \ingroup maps
   101 \ingroup maps
    97 \brief Tools to create new maps from existing ones
   102 \brief Tools to create new maps from existing ones
    98 
   103 
    99 This group describes map adaptors that are used to create "implicit"
   104 This group describes map adaptors that are used to create "implicit"
   100 maps from other maps.
   105 maps from other maps.
   101 
   106 
   102 Most of them are \ref lemon::concepts::ReadMap "read-only maps".
   107 Most of them are \ref concepts::ReadMap "read-only maps".
   103 They can make arithmetic and logical operations between one or two maps
   108 They can make arithmetic and logical operations between one or two maps
   104 (negation, shifting, addition, multiplication, logical 'and', 'or',
   109 (negation, shifting, addition, multiplication, logical 'and', 'or',
   105 'not' etc.) or e.g. convert a map to another one of different Value type.
   110 'not' etc.) or e.g. convert a map to another one of different Value type.
   106 
   111 
   107 The typical usage of this classes is passing implicit maps to
   112 The typical usage of this classes is passing implicit maps to
   199 /**
   204 /**
   200 @defgroup search Graph Search
   205 @defgroup search Graph Search
   201 @ingroup algs
   206 @ingroup algs
   202 \brief Common graph search algorithms.
   207 \brief Common graph search algorithms.
   203 
   208 
   204 This group describes the common graph search algorithms like
   209 This group describes the common graph search algorithms, namely
   205 Breadth-First Search (BFS) and Depth-First Search (DFS).
   210 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
   206 */
   211 */
   207 
   212 
   208 /**
   213 /**
   209 @defgroup shortest_path Shortest Path Algorithms
   214 @defgroup shortest_path Shortest Path Algorithms
   210 @ingroup algs
   215 @ingroup algs
   211 \brief Algorithms for finding shortest paths.
   216 \brief Algorithms for finding shortest paths.
   212 
   217 
   213 This group describes the algorithms for finding shortest paths in graphs.
   218 This group describes the algorithms for finding shortest paths in digraphs.
       
   219 
       
   220  - \ref Dijkstra algorithm for finding shortest paths from a source node
       
   221    when all arc lengths are non-negative.
       
   222  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
       
   223    from a source node when arc lenghts can be either positive or negative,
       
   224    but the digraph should not contain directed cycles with negative total
       
   225    length.
       
   226  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
       
   227    for solving the \e all-pairs \e shortest \e paths \e problem when arc
       
   228    lenghts can be either positive or negative, but the digraph should
       
   229    not contain directed cycles with negative total length.
       
   230  - \ref Suurballe A successive shortest path algorithm for finding
       
   231    arc-disjoint paths between two nodes having minimum total length.
   214 */
   232 */
   215 
   233 
   216 /**
   234 /**
   217 @defgroup max_flow Maximum Flow Algorithms
   235 @defgroup max_flow Maximum Flow Algorithms
   218 @ingroup algs
   236 @ingroup algs
   219 \brief Algorithms for finding maximum flows.
   237 \brief Algorithms for finding maximum flows.
   220 
   238 
   221 This group describes the algorithms for finding maximum flows and
   239 This group describes the algorithms for finding maximum flows and
   222 feasible circulations.
   240 feasible circulations.
   223 
   241 
   224 The maximum flow problem is to find a flow between a single source and
   242 The \e maximum \e flow \e problem is to find a flow of maximum value between
   225 a single target that is maximum. Formally, there is a \f$G=(V,A)\f$
   243 a single source and a single target. Formally, there is a \f$G=(V,A)\f$
   226 directed graph, an \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity
   244 digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
   227 function and given \f$s, t \in V\f$ source and target node. The
   245 \f$s, t \in V\f$ source and target nodes.
   228 maximum flow is the \f$f_a\f$ solution of the next optimization problem:
   246 A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
   229 
   247 following optimization problem.
   230 \f[ 0 \le f_a \le c_a \f]
   248 
   231 \f[ \sum_{v\in\delta^{-}(u)}f_{vu}=\sum_{v\in\delta^{+}(u)}f_{uv}
   249 \f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
   232 \qquad \forall u \in V \setminus \{s,t\}\f]
   250 \f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
   233 \f[ \max \sum_{v\in\delta^{+}(s)}f_{uv} - \sum_{v\in\delta^{-}(s)}f_{vu}\f]
   251     \qquad \forall v\in V\setminus\{s,t\} \f]
       
   252 \f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
   234 
   253 
   235 LEMON contains several algorithms for solving maximum flow problems:
   254 LEMON contains several algorithms for solving maximum flow problems:
   236 - \ref lemon::EdmondsKarp "Edmonds-Karp"
   255 - \ref EdmondsKarp Edmonds-Karp algorithm.
   237 - \ref lemon::Preflow "Goldberg's Preflow algorithm"
   256 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
   238 - \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
   257 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
   239 - \ref lemon::GoldbergTarjan "Preflow algorithm with dynamic trees"
   258 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
   240 
   259 
   241 In most cases the \ref lemon::Preflow "Preflow" algorithm provides the
   260 In most cases the \ref Preflow "Preflow" algorithm provides the
   242 fastest method to compute the maximum flow. All impelementations
   261 fastest method for computing a maximum flow. All implementations
   243 provides functions to query the minimum cut, which is the dual linear
   262 provides functions to also query the minimum cut, which is the dual
   244 programming problem of the maximum flow.
   263 problem of the maximum flow.
   245 */
   264 */
   246 
   265 
   247 /**
   266 /**
   248 @defgroup min_cost_flow Minimum Cost Flow Algorithms
   267 @defgroup min_cost_flow Minimum Cost Flow Algorithms
   249 @ingroup algs
   268 @ingroup algs
   250 
   269 
   251 \brief Algorithms for finding minimum cost flows and circulations.
   270 \brief Algorithms for finding minimum cost flows and circulations.
   252 
   271 
   253 This group describes the algorithms for finding minimum cost flows and
   272 This group describes the algorithms for finding minimum cost flows and
   254 circulations.
   273 circulations.
       
   274 
       
   275 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
       
   276 minimum total cost from a set of supply nodes to a set of demand nodes
       
   277 in a network with capacity constraints and arc costs.
       
   278 Formally, let \f$G=(V,A)\f$ be a digraph,
       
   279 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
       
   280 upper bounds for the flow values on the arcs,
       
   281 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
       
   282 on the arcs, and
       
   283 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
       
   284 of the nodes.
       
   285 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
       
   286 the following optimization problem.
       
   287 
       
   288 \f[ \min\sum_{a\in A} f(a) cost(a) \f]
       
   289 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
       
   290     supply(v) \qquad \forall v\in V \f]
       
   291 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
       
   292 
       
   293 LEMON contains several algorithms for solving minimum cost flow problems:
       
   294  - \ref CycleCanceling Cycle-canceling algorithms.
       
   295  - \ref CapacityScaling Successive shortest path algorithm with optional
       
   296    capacity scaling.
       
   297  - \ref CostScaling Push-relabel and augment-relabel algorithms based on
       
   298    cost scaling.
       
   299  - \ref NetworkSimplex Primal network simplex algorithm with various
       
   300    pivot strategies.
   255 */
   301 */
   256 
   302 
   257 /**
   303 /**
   258 @defgroup min_cut Minimum Cut Algorithms
   304 @defgroup min_cut Minimum Cut Algorithms
   259 @ingroup algs
   305 @ingroup algs
   260 
   306 
   261 \brief Algorithms for finding minimum cut in graphs.
   307 \brief Algorithms for finding minimum cut in graphs.
   262 
   308 
   263 This group describes the algorithms for finding minimum cut in graphs.
   309 This group describes the algorithms for finding minimum cut in graphs.
   264 
   310 
   265 The minimum cut problem is to find a non-empty and non-complete
   311 The \e minimum \e cut \e problem is to find a non-empty and non-complete
   266 \f$X\f$ subset of the vertices with minimum overall capacity on
   312 \f$X\f$ subset of the nodes with minimum overall capacity on
   267 outgoing arcs. Formally, there is \f$G=(V,A)\f$ directed graph, an
   313 outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
   268 \f$c_a:A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   314 \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
   269 cut is the \f$X\f$ solution of the next optimization problem:
   315 cut is the \f$X\f$ solution of the next optimization problem:
   270 
   316 
   271 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
   317 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
   272 \sum_{uv\in A, u\in X, v\not\in X}c_{uv}\f]
   318     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
   273 
   319 
   274 LEMON contains several algorithms related to minimum cut problems:
   320 LEMON contains several algorithms related to minimum cut problems:
   275 
   321 
   276 - \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
   322 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
   277   in directed graphs
   323   in directed graphs.
   278 - \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
   324 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
   279   calculate minimum cut in undirected graphs
   325   calculating minimum cut in undirected graphs.
   280 - \ref lemon::GomoryHuTree "Gomory-Hu tree computation" to calculate all
   326 - \ref GomoryHuTree "Gomory-Hu tree computation" for calculating
   281   pairs minimum cut in undirected graphs
   327   all-pairs minimum cut in undirected graphs.
   282 
   328 
   283 If you want to find minimum cut just between two distinict nodes,
   329 If you want to find minimum cut just between two distinict nodes,
   284 please see the \ref max_flow "Maximum Flow page".
   330 see the \ref max_flow "maximum flow problem".
   285 */
   331 */
   286 
   332 
   287 /**
   333 /**
   288 @defgroup graph_prop Connectivity and Other Graph Properties
   334 @defgroup graph_prop Connectivity and Other Graph Properties
   289 @ingroup algs
   335 @ingroup algs
   318 finding a subset of the arcs which does not shares common endpoints.
   364 finding a subset of the arcs which does not shares common endpoints.
   319 
   365 
   320 There are several different algorithms for calculate matchings in
   366 There are several different algorithms for calculate matchings in
   321 graphs.  The matching problems in bipartite graphs are generally
   367 graphs.  The matching problems in bipartite graphs are generally
   322 easier than in general graphs. The goal of the matching optimization
   368 easier than in general graphs. The goal of the matching optimization
   323 can be the finding maximum cardinality, maximum weight or minimum cost
   369 can be finding maximum cardinality, maximum weight or minimum cost
   324 matching. The search can be constrained to find perfect or
   370 matching. The search can be constrained to find perfect or
   325 maximum cardinality matching.
   371 maximum cardinality matching.
   326 
   372 
   327 LEMON contains the next algorithms:
   373 The matching algorithms implemented in LEMON:
   328 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
   374 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
   329   augmenting path algorithm for calculate maximum cardinality matching in
   375   for calculating maximum cardinality matching in bipartite graphs.
   330   bipartite graphs
   376 - \ref PrBipartiteMatching Push-relabel algorithm
   331 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
   377   for calculating maximum cardinality matching in bipartite graphs.
   332   algorithm for calculate maximum cardinality matching in bipartite graphs
   378 - \ref MaxWeightedBipartiteMatching
   333 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
   379   Successive shortest path algorithm for calculating maximum weighted
   334   Successive shortest path algorithm for calculate maximum weighted matching
   380   matching and maximum weighted bipartite matching in bipartite graphs.
   335   and maximum weighted bipartite matching in bipartite graph
   381 - \ref MinCostMaxBipartiteMatching
   336 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
   382   Successive shortest path algorithm for calculating minimum cost maximum
   337   Successive shortest path algorithm for calculate minimum cost maximum
   383   matching in bipartite graphs.
   338   matching in bipartite graph
   384 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
   339 - \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
   385   maximum cardinality matching in general graphs.
   340   for calculate maximum cardinality matching in general graph
   386 - \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
   341 - \ref lemon::MaxWeightedMatching "MaxWeightedMatching" Edmond's blossom
   387   maximum weighted matching in general graphs.
   342   shrinking algorithm for calculate maximum weighted matching in general
   388 - \ref MaxWeightedPerfectMatching
   343   graph
   389   Edmond's blossom shrinking algorithm for calculating maximum weighted
   344 - \ref lemon::MaxWeightedPerfectMatching "MaxWeightedPerfectMatching"
   390   perfect matching in general graphs.
   345   Edmond's blossom shrinking algorithm for calculate maximum weighted
       
   346   perfect matching in general graph
       
   347 
   391 
   348 \image html bipartite_matching.png
   392 \image html bipartite_matching.png
   349 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   393 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
   350 */
   394 */
   351 
   395 
   353 @defgroup spantree Minimum Spanning Tree Algorithms
   397 @defgroup spantree Minimum Spanning Tree Algorithms
   354 @ingroup algs
   398 @ingroup algs
   355 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   399 \brief Algorithms for finding a minimum cost spanning tree in a graph.
   356 
   400 
   357 This group describes the algorithms for finding a minimum cost spanning
   401 This group describes the algorithms for finding a minimum cost spanning
   358 tree in a graph
   402 tree in a graph.
   359 */
   403 */
   360 
   404 
   361 /**
   405 /**
   362 @defgroup auxalg Auxiliary Algorithms
   406 @defgroup auxalg Auxiliary Algorithms
   363 @ingroup algs
   407 @ingroup algs
   544 */
   588 */
   545 
   589 
   546 /**
   590 /**
   547 \anchor demoprograms
   591 \anchor demoprograms
   548 
   592 
   549 @defgroup demos Demo programs
   593 @defgroup demos Demo Programs
   550 
   594 
   551 Some demo programs are listed here. Their full source codes can be found in
   595 Some demo programs are listed here. Their full source codes can be found in
   552 the \c demo subdirectory of the source tree.
   596 the \c demo subdirectory of the source tree.
   553 
   597 
   554 It order to compile them, use <tt>--enable-demo</tt> configure option when
   598 It order to compile them, use <tt>--enable-demo</tt> configure option when
   555 build the library.
   599 build the library.
   556 */
   600 */
   557 
   601 
   558 /**
   602 /**
   559 @defgroup tools Standalone utility applications
   603 @defgroup tools Standalone Utility Applications
   560 
   604 
   561 Some utility applications are listed here.
   605 Some utility applications are listed here.
   562 
   606 
   563 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   607 The standard compilation procedure (<tt>./configure;make</tt>) will compile
   564 them, as well.
   608 them, as well.
   565 */
   609 */
   566 
   610 
       
   611 }