Changes in / [849:017b06600347:731:7b1a6e963018] in lemon
 Files:

 1 deleted
 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r844 r710 227 227 228 228 /** 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 /** 229 237 @defgroup paths Path Structures 230 238 @ingroup datas … … 276 284 This group contains the algorithms for finding shortest paths in digraphs. 277 285 278  \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 279 source node when all arc lengths are nonnegative. 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. 280 296  \ref Suurballe A successive shortest path algorithm for finding 281 297 arcdisjoint paths between two nodes having minimum total length. … … 302 318 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 303 319 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 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. 308 330 309 331 \ref Circulation is a preflow pushrelabel algorithm implemented directly … … 323 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 324 346 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. 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). 328 361 */ 329 362 … … 349 382  \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut 350 383 in directed graphs. 384  \ref NagamochiIbaraki "NagamochiIbaraki algorithm" for 385 calculating minimum cut in undirected graphs. 351 386  \ref GomoryHu "GomoryHu tree computation" for calculating 352 387 allpairs minimum cut in undirected graphs. … … 369 404 370 405 /** 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 /** 371 418 @defgroup matching Matching Algorithms 372 419 @ingroup algs 373 420 \brief Algorithms for finding matchings in graphs and bipartite graphs. 374 421 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. 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. 378 426 379 427 There are several different algorithms for calculate matchings in 380 graphs. The goal of the matching optimization 428 graphs. The matching problems in bipartite graphs are generally 429 easier than in general graphs. The goal of the matching optimization 381 430 can be finding maximum cardinality, maximum weight or minimum cost 382 431 matching. The search can be constrained to find perfect or … … 384 433 385 434 The matching algorithms implemented in LEMON: 435  \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm 436 for calculating maximum cardinality matching in bipartite graphs. 437  \ref PrBipartiteMatching Pushrelabel 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. 386 445  \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 387 446 maximum cardinality matching in general graphs. … … 415 474 416 475 /** 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 /** 417 485 @defgroup gen_opt_group General Optimization Tools 418 486 \brief This group contains some general optimization frameworks … … 431 499 various LP solvers could be used in the same manner with this 432 500 interface. 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. 433 518 */ 434 519 
lemon/suurballe.h
r843 r670 46 46 /// Note that this problem is a special case of the \ref min_cost_flow 47 47 /// "minimum cost flow problem". This implementation is actually an 48 /// efficient specialized version of the Successive Shortest Path49 /// algorithm directly for this problem.48 /// efficient specialized version of the \ref CapacityScaling 49 /// "Successive Shortest Path" algorithm directly for this problem. 50 50 /// Therefore this class provides query functions for flow values and 51 51 /// node potentials (the dual solution) just like the minimum cost flow
Note: See TracChangeset
for help on using the changeset viewer.