Changeset 843:189760a7cdd0 in lemon
 Timestamp:
 05/07/09 02:05:12 (13 years ago)
 Branch:
 1.1
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

doc/groups.dox
r687 r843 237 237 238 238 /** 239 @defgroup matrices Matrices240 @ingroup datas241 \brief Two dimensional data storages implemented in LEMON.242 243 This group contains two dimensional data storages implemented in LEMON.244 */245 246 /**247 239 @defgroup paths Path Structures 248 240 @ingroup datas … … 294 286 This group contains the algorithms for finding shortest paths in digraphs. 295 287 296  \ref Dijkstra algorithm for finding shortest paths from a source node 297 when all arc lengths are nonnegative. 298  \ref BellmanFord "BellmanFord" algorithm for finding shortest paths 299 from a source node when arc lenghts can be either positive or negative, 300 but the digraph should not contain directed cycles with negative total 301 length. 302  \ref FloydWarshall "FloydWarshall" and \ref Johnson "Johnson" algorithms 303 for solving the \e allpairs \e shortest \e paths \e problem when arc 304 lenghts can be either positive or negative, but the digraph should 305 not contain directed cycles with negative total length. 288  \ref Dijkstra Dijkstra's algorithm for finding shortest paths from a 289 source node when all arc lengths are nonnegative. 306 290  \ref Suurballe A successive shortest path algorithm for finding 307 291 arcdisjoint paths between two nodes having minimum total length. … … 328 312 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 329 313 330 LEMON contains several algorithms for solving maximum flow problems: 331  \ref EdmondsKarp EdmondsKarp algorithm. 332  \ref Preflow GoldbergTarjan's preflow pushrelabel algorithm. 333  \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 334  \ref GoldbergTarjan Preflow pushrelabel algorithm with dynamic trees. 335 336 In most cases the \ref Preflow "Preflow" algorithm provides the 337 fastest method for computing a maximum flow. All implementations 338 provides functions to also query the minimum cut, which is the dual 339 problem of the maximum flow. 314 \ref Preflow implements the preflow pushrelabel algorithm of Goldberg and 315 Tarjan for solving this problem. It also provides functions to query the 316 minimum cut, which is the dual problem of maximum flow. 317 318 \ref Circulation is a preflow pushrelabel algorithm implemented directly 319 for finding feasible circulations, which is a somewhat different problem, 320 but it is strongly related to maximum flow. 321 For more information, see \ref Circulation. 340 322 */ 341 323 … … 422 404 \f[ cost^\pi(uv) = cost(uv) + \pi(u)  \pi(v).\f] 423 405 424 All algorithms provide dual solution (node potentials) as well, 425 if an optimal flow is found. 426 427 LEMON contains several algorithms for solving minimum cost flow problems. 428  \ref NetworkSimplex Primal Network Simplex algorithm with various 429 pivot strategies. 430  \ref CostScaling PushRelabel and AugmentRelabel algorithms based on 431 cost scaling. 432  \ref CapacityScaling Successive Shortest %Path algorithm with optional 433 capacity scaling. 434  \ref CancelAndTighten The Cancel and Tighten algorithm. 435  \ref CycleCanceling CycleCanceling algorithms. 436 437 Most of these implementations support the general inequality form of the 438 minimum cost flow problem, but CancelAndTighten and CycleCanceling 439 only support the equality form due to the primal method they use. 440 441 In general NetworkSimplex is the most efficient implementation, 442 but in special cases other algorithms could be faster. 443 For example, if the total supply and/or capacities are rather small, 444 CapacityScaling is usually the fastest algorithm (without effective scaling). 406 \ref NetworkSimplex is an efficient implementation of the primal Network 407 Simplex algorithm for finding minimum cost flows. It also provides dual 408 solution (node potentials), if an optimal flow is found. 445 409 */ 446 410 … … 466 430  \ref HaoOrlin "HaoOrlin algorithm" for calculating minimum cut 467 431 in directed graphs. 468  \ref NagamochiIbaraki "NagamochiIbaraki algorithm" for469 calculating minimum cut in undirected graphs.470 432  \ref GomoryHu "GomoryHu tree computation" for calculating 471 433 allpairs minimum cut in undirected graphs. … … 488 450 489 451 /** 490 @defgroup planar Planarity Embedding and Drawing491 @ingroup algs492 \brief Algorithms for planarity checking, embedding and drawing493 494 This group contains the algorithms for planarity checking,495 embedding and drawing.496 497 \image html planar.png498 \image latex planar.eps "Plane graph" width=\textwidth499 */500 501 /**502 452 @defgroup matching Matching Algorithms 503 453 @ingroup algs 504 454 \brief Algorithms for finding matchings in graphs and bipartite graphs. 505 455 506 This group contains the algorithms for calculating 507 matchings in graphs and bipartite graphs. The general matching problem is 508 finding a subset of the edges for which each node has at most one incident 509 edge. 456 This group contains the algorithms for calculating matchings in graphs. 457 The general matching problem is finding a subset of the edges for which 458 each node has at most one incident edge. 510 459 511 460 There are several different algorithms for calculate matchings in 512 graphs. The matching problems in bipartite graphs are generally 513 easier than in general graphs. The goal of the matching optimization 461 graphs. The goal of the matching optimization 514 462 can be finding maximum cardinality, maximum weight or minimum cost 515 463 matching. The search can be constrained to find perfect or … … 517 465 518 466 The matching algorithms implemented in LEMON: 519  \ref MaxBipartiteMatching HopcroftKarp augmenting path algorithm520 for calculating maximum cardinality matching in bipartite graphs.521  \ref PrBipartiteMatching Pushrelabel algorithm522 for calculating maximum cardinality matching in bipartite graphs.523  \ref MaxWeightedBipartiteMatching524 Successive shortest path algorithm for calculating maximum weighted525 matching and maximum weighted bipartite matching in bipartite graphs.526  \ref MinCostMaxBipartiteMatching527 Successive shortest path algorithm for calculating minimum cost maximum528 matching in bipartite graphs.529 467  \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 530 468 maximum cardinality matching in general graphs. … … 558 496 559 497 /** 560 @defgroup approx Approximation Algorithms561 @ingroup algs562 \brief Approximation algorithms.563 564 This group contains the approximation and heuristic algorithms565 implemented in LEMON.566 */567 568 /**569 498 @defgroup gen_opt_group General Optimization Tools 570 499 \brief This group contains some general optimization frameworks … … 583 512 various LP solvers could be used in the same manner with this 584 513 interface. 585 */586 587 /**588 @defgroup lp_utils Tools for Lp and Mip Solvers589 @ingroup lp_group590 \brief Helper tools to the Lp and Mip solvers.591 592 This group adds some helper tools to general optimization framework593 implemented in LEMON.594 */595 596 /**597 @defgroup metah Metaheuristics598 @ingroup gen_opt_group599 \brief Metaheuristics for LEMON library.600 601 This group contains some metaheuristic optimization tools.602 514 */ 603 515 
lemon/suurballe.h
r670 r843 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 \ref CapacityScaling49 /// "Successive Shortest Path"algorithm directly for this problem.48 /// efficient specialized version of the Successive Shortest Path 49 /// 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.