COIN-OR::LEMON - Graph Library

Changeset 844:c01a98ce01fd in lemon


Ignore:
Timestamp:
05/12/09 13:09:55 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
1.1
Parents:
843:189760a7cdd0 (diff), 712:e652b6f9a29f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge

Files:
1 deleted
2 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r710 r844  
    227227
    228228/**
    229 @defgroup matrices Matrices
    230 @ingroup datas
    231 \brief Two dimensional data storages implemented in LEMON.
    232 
    233 This group contains two dimensional data storages implemented in LEMON.
    234 */
    235 
    236 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    284276This group contains the algorithms for finding shortest paths in digraphs.
    285277
    286  - \ref Dijkstra algorithm for finding shortest paths from a source node
    287    when all arc lengths are non-negative.
    288  - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
    289    from a source node when arc lenghts can be either positive or negative,
    290    but the digraph should not contain directed cycles with negative total
    291    length.
    292  - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
    293    for solving the \e all-pairs \e shortest \e paths \e problem when arc
    294    lenghts can be either positive or negative, but the digraph should
    295    not contain directed cycles with negative total length.
     278 - \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a
     279   source node when all arc lengths are non-negative.
    296280 - \ref Suurballe A successive shortest path algorithm for finding
    297281   arc-disjoint paths between two nodes having minimum total length.
     
    318302\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f]
    319303
    320 LEMON contains several algorithms for solving maximum flow problems:
    321 - \ref EdmondsKarp Edmonds-Karp algorithm.
    322 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    323 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    324 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    325 
    326 In most cases the \ref Preflow "Preflow" algorithm provides the
    327 fastest method for computing a maximum flow. All implementations
    328 also provide functions to query the minimum cut, which is the dual
    329 problem of maximum flow.
     304\ref Preflow implements the preflow push-relabel algorithm of Goldberg and
     305Tarjan for solving this problem. It also provides functions to query the
     306minimum cut, which is the dual problem of maximum flow.
     307
    330308
    331309\ref Circulation is a preflow push-relabel algorithm implemented directly
     
    345323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    346324
    347 LEMON contains several algorithms for this problem.
    348  - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
    350  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
    352  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    353    capacity scaling.
    354  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    355  - \ref CycleCanceling Cycle-Canceling algorithms.
    356 
    357 In general NetworkSimplex is the most efficient implementation,
    358 but in special cases other algorithms could be faster.
    359 For example, if the total supply and/or capacities are rather small,
    360 CapacityScaling is usually the fastest algorithm (without effective scaling).
     325\ref NetworkSimplex is an efficient implementation of the primal Network
     326Simplex algorithm for finding minimum cost flows. It also provides dual
     327solution (node potentials), if an optimal flow is found.
    361328*/
    362329
     
    382349- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
    383350  in directed graphs.
    384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
    385   calculating minimum cut in undirected graphs.
    386351- \ref GomoryHu "Gomory-Hu tree computation" for calculating
    387352  all-pairs minimum cut in undirected graphs.
     
    404369
    405370/**
    406 @defgroup planar Planarity Embedding and Drawing
    407 @ingroup algs
    408 \brief Algorithms for planarity checking, embedding and drawing
    409 
    410 This group contains the algorithms for planarity checking,
    411 embedding and drawing.
    412 
    413 \image html planar.png
    414 \image latex planar.eps "Plane graph" width=\textwidth
    415 */
    416 
    417 /**
    418371@defgroup matching Matching Algorithms
    419372@ingroup algs
    420373\brief Algorithms for finding matchings in graphs and bipartite graphs.
    421374
    422 This group contains the algorithms for calculating
    423 matchings in graphs and bipartite graphs. The general matching problem is
    424 finding a subset of the edges for which each node has at most one incident
    425 edge.
     375This group contains the algorithms for calculating matchings in graphs.
     376The general matching problem is finding a subset of the edges for which
     377each node has at most one incident edge.
    426378
    427379There are several different algorithms for calculate matchings in
    428 graphs.  The matching problems in bipartite graphs are generally
    429 easier than in general graphs. The goal of the matching optimization
     380graphs. The goal of the matching optimization
    430381can be finding maximum cardinality, maximum weight or minimum cost
    431382matching. The search can be constrained to find perfect or
     
    433384
    434385The matching algorithms implemented in LEMON:
    435 - \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
    436   for calculating maximum cardinality matching in bipartite graphs.
    437 - \ref PrBipartiteMatching Push-relabel algorithm
    438   for calculating maximum cardinality matching in bipartite graphs.
    439 - \ref MaxWeightedBipartiteMatching
    440   Successive shortest path algorithm for calculating maximum weighted
    441   matching and maximum weighted bipartite matching in bipartite graphs.
    442 - \ref MinCostMaxBipartiteMatching
    443   Successive shortest path algorithm for calculating minimum cost maximum
    444   matching in bipartite graphs.
    445386- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
    446387  maximum cardinality matching in general graphs.
     
    474415
    475416/**
    476 @defgroup approx Approximation Algorithms
    477 @ingroup algs
    478 \brief Approximation algorithms.
    479 
    480 This group contains the approximation and heuristic algorithms
    481 implemented in LEMON.
    482 */
    483 
    484 /**
    485417@defgroup gen_opt_group General Optimization Tools
    486418\brief This group contains some general optimization frameworks
     
    499431various LP solvers could be used in the same manner with this
    500432interface.
    501 */
    502 
    503 /**
    504 @defgroup lp_utils Tools for Lp and Mip Solvers
    505 @ingroup lp_group
    506 \brief Helper tools to the Lp and Mip solvers.
    507 
    508 This group adds some helper tools to general optimization framework
    509 implemented in LEMON.
    510 */
    511 
    512 /**
    513 @defgroup metah Metaheuristics
    514 @ingroup gen_opt_group
    515 \brief Metaheuristics for LEMON library.
    516 
    517 This group contains some metaheuristic optimization tools.
    518433*/
    519434
  • doc/groups.dox

    r843 r844  
    139139
    140140/**
    141 @defgroup semi_adaptors Semi-Adaptor Classes for Graphs
    142 @ingroup graphs
    143 \brief Graph types between real graphs and graph adaptors.
    144 
    145 This group contains some graph types between real graphs and graph adaptors.
    146 These classes wrap graphs to give new functionality as the adaptors do it.
    147 On the other hand they are not light-weight structures as the adaptors.
    148 */
    149 
    150 /**
    151141@defgroup maps Maps
    152142@ingroup datas
     
    316306minimum cut, which is the dual problem of maximum flow.
    317307
     308
    318309\ref Circulation is a preflow push-relabel algorithm implemented directly
    319310for finding feasible circulations, which is a somewhat different problem,
     
    323314
    324315/**
    325 @defgroup min_cost_flow Minimum Cost Flow Algorithms
     316@defgroup min_cost_flow_algs Minimum Cost Flow Algorithms
    326317@ingroup algs
    327318
     
    329320
    330321This group contains the algorithms for finding minimum cost flows and
    331 circulations.
    332 
    333 The \e minimum \e cost \e flow \e problem is to find a feasible flow of
    334 minimum total cost from a set of supply nodes to a set of demand nodes
    335 in a network with capacity constraints (lower and upper bounds)
    336 and arc costs.
    337 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
    338 \f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
    339 upper bounds for the flow values on the arcs, for which
    340 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
    341 \f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
    342 on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
    343 signed supply values of the nodes.
    344 If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    345 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    346 \f$-sup(u)\f$ demand.
    347 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
    348 of the following optimization problem.
    349 
    350 \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
    351 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq
    352     sup(u) \quad \forall u\in V \f]
    353 \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]
    354 
    355 The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be
    356 zero or negative in order to have a feasible solution (since the sum
    357 of the expressions on the left-hand side of the inequalities is zero).
    358 It means that the total demand must be greater or equal to the total
    359 supply and all the supplies have to be carried out from the supply nodes,
    360 but there could be demands that are not satisfied.
    361 If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand
    362 constraints have to be satisfied with equality, i.e. all demands
    363 have to be satisfied and all supplies have to be used.
    364 
    365 If you need the opposite inequalities in the supply/demand constraints
    366 (i.e. the total demand is less than the total supply and all the demands
    367 have to be satisfied while there could be supplies that are not used),
    368 then you could easily transform the problem to the above form by reversing
    369 the direction of the arcs and taking the negative of the supply values
    370 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    371 However \ref NetworkSimplex algorithm also supports this form directly
    372 for the sake of convenience.
    373 
    374 A feasible solution for this problem can be found using \ref Circulation.
    375 
    376 Note that the above formulation is actually more general than the usual
    377 definition of the minimum cost flow problem, in which strict equalities
    378 are required in the supply/demand contraints, i.e.
    379 
    380 \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) =
    381     sup(u) \quad \forall u\in V. \f]
    382 
    383 However if the sum of the supply values is zero, then these two problems
    384 are equivalent. So if you need the equality form, you have to ensure this
    385 additional contraint for the algorithms.
    386 
    387 The dual solution of the minimum cost flow problem is represented by node
    388 potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
    389 An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
    390 is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
    391 node potentials the following \e complementary \e slackness optimality
    392 conditions hold.
    393 
    394  - For all \f$uv\in A\f$ arcs:
    395    - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$;
    396    - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    397    - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    398  - For all \f$u\in V\f$ nodes:
    399    - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    400      then \f$\pi(u)=0\f$.
    401  
    402 Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    403 \f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
    404 \f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
     322circulations. For more information about this problem and its dual
     323solution see \ref min_cost_flow "Minimum Cost Flow Problem".
    405324
    406325\ref NetworkSimplex is an efficient implementation of the primal Network
     
    480399@defgroup spantree Minimum Spanning Tree Algorithms
    481400@ingroup algs
    482 \brief Algorithms for finding a minimum cost spanning tree in a graph.
    483 
    484 This group contains the algorithms for finding a minimum cost spanning
    485 tree in a graph.
     401\brief Algorithms for finding minimum cost spanning trees and arborescences.
     402
     403This group contains the algorithms for finding minimum cost spanning
     404trees and arborescences.
    486405*/
    487406
Note: See TracChangeset for help on using the changeset viewer.