Changeset 844:c01a98ce01fd in lemon
 Timestamp:
 05/12/09 13:09:55 (10 years ago)
 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
 Files:

 1 deleted
 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r710 r844 227 227 228 228 /** 229 @defgroup matrices Matrices230 @ingroup datas231 \brief Two dimensional data storages implemented in LEMON.232 233 This group contains two dimensional data storages implemented in LEMON.234 */235 236 /**237 229 @defgroup paths Path Structures 238 230 @ingroup datas … … 284 276 This group contains the algorithms for finding shortest paths in digraphs. 285 277 286  \ref Dijkstra algorithm for finding shortest paths from a source node 287 when all arc lengths are nonnegative. 288  \ref BellmanFord "BellmanFord" 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 "FloydWarshall" and \ref Johnson "Johnson" algorithms 293 for solving the \e allpairs \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 nonnegative. 296 280  \ref Suurballe A successive shortest path algorithm for finding 297 281 arcdisjoint paths between two nodes having minimum total length. … … 318 302 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 319 303 320 LEMON contains several algorithms for solving maximum flow problems: 321  \ref EdmondsKarp EdmondsKarp algorithm. 322  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm. 323  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 324  \ref GoldbergTarjan Preflow pushrelabel 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 pushrelabel algorithm of Goldberg and 305 Tarjan for solving this problem. It also provides functions to query the 306 minimum cut, which is the dual problem of maximum flow. 307 330 308 331 309 \ref Circulation is a preflow pushrelabel algorithm implemented directly … … 345 323 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 346 324 347 LEMON contains several algorithms for this problem. 348  \ref NetworkSimplex Primal Network Simplex algorithm with various 349 pivot strategies. 350  \ref CostScaling PushRelabel and AugmentRelabel 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 CycleCanceling 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 326 Simplex algorithm for finding minimum cost flows. It also provides dual 327 solution (node potentials), if an optimal flow is found. 361 328 */ 362 329 … … 382 349  \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut 383 350 in directed graphs. 384  \ref NagamochiIbaraki "NagamochiIbaraki algorithm" for385 calculating minimum cut in undirected graphs.386 351  \ref GomoryHu "GomoryHu tree computation" for calculating 387 352 allpairs minimum cut in undirected graphs. … … 404 369 405 370 /** 406 @defgroup planar Planarity Embedding and Drawing407 @ingroup algs408 \brief Algorithms for planarity checking, embedding and drawing409 410 This group contains the algorithms for planarity checking,411 embedding and drawing.412 413 \image html planar.png414 \image latex planar.eps "Plane graph" width=\textwidth415 */416 417 /**418 371 @defgroup matching Matching Algorithms 419 372 @ingroup algs 420 373 \brief Algorithms for finding matchings in graphs and bipartite graphs. 421 374 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. 375 This group contains the algorithms for calculating matchings in graphs. 376 The general matching problem is finding a subset of the edges for which 377 each node has at most one incident edge. 426 378 427 379 There 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 380 graphs. The goal of the matching optimization 430 381 can be finding maximum cardinality, maximum weight or minimum cost 431 382 matching. The search can be constrained to find perfect or … … 433 384 434 385 The matching algorithms implemented in LEMON: 435  \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm436 for calculating maximum cardinality matching in bipartite graphs.437  \ref PrBipartiteMatching Pushrelabel algorithm438 for calculating maximum cardinality matching in bipartite graphs.439  \ref MaxWeightedBipartiteMatching440 Successive shortest path algorithm for calculating maximum weighted441 matching and maximum weighted bipartite matching in bipartite graphs.442  \ref MinCostMaxBipartiteMatching443 Successive shortest path algorithm for calculating minimum cost maximum444 matching in bipartite graphs.445 386  \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 446 387 maximum cardinality matching in general graphs. … … 474 415 475 416 /** 476 @defgroup approx Approximation Algorithms477 @ingroup algs478 \brief Approximation algorithms.479 480 This group contains the approximation and heuristic algorithms481 implemented in LEMON.482 */483 484 /**485 417 @defgroup gen_opt_group General Optimization Tools 486 418 \brief This group contains some general optimization frameworks … … 499 431 various LP solvers could be used in the same manner with this 500 432 interface. 501 */502 503 /**504 @defgroup lp_utils Tools for Lp and Mip Solvers505 @ingroup lp_group506 \brief Helper tools to the Lp and Mip solvers.507 508 This group adds some helper tools to general optimization framework509 implemented in LEMON.510 */511 512 /**513 @defgroup metah Metaheuristics514 @ingroup gen_opt_group515 \brief Metaheuristics for LEMON library.516 517 This group contains some metaheuristic optimization tools.518 433 */ 519 434 
doc/groups.dox
r843 r844 139 139 140 140 /** 141 @defgroup semi_adaptors SemiAdaptor Classes for Graphs142 @ingroup graphs143 \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 lightweight structures as the adaptors.148 */149 150 /**151 141 @defgroup maps Maps 152 142 @ingroup datas … … 316 306 minimum cut, which is the dual problem of maximum flow. 317 307 308 318 309 \ref Circulation is a preflow pushrelabel algorithm implemented directly 319 310 for finding feasible circulations, which is a somewhat different problem, … … 323 314 324 315 /** 325 @defgroup min_cost_flow Minimum Cost Flow Algorithms316 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms 326 317 @ingroup algs 327 318 … … 329 320 330 321 This 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 lefthand 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] 322 circulations. For more information about this problem and its dual 323 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 405 324 406 325 \ref NetworkSimplex is an efficient implementation of the primal Network … … 480 399 @defgroup spantree Minimum Spanning Tree Algorithms 481 400 @ingroup algs 482 \brief Algorithms for finding a minimum cost spanning tree in a graph.483 484 This group contains the algorithms for finding aminimum cost spanning485 tree in a graph.401 \brief Algorithms for finding minimum cost spanning trees and arborescences. 402 403 This group contains the algorithms for finding minimum cost spanning 404 trees and arborescences. 486 405 */ 487 406
Note: See TracChangeset
for help on using the changeset viewer.