Changes in doc/groups.dox [884:3ed8f7c8bed8:663:8b0df68370a4] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r884 r663 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 105 * Copyright (C) 2003-2009 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 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 … … 239 247 any kind of path structure. 240 248 241 \sa \ref concepts::Path "Path concept" 242 */ 243 244 /** 245 @defgroup heaps Heap Structures 246 @ingroup datas 247 \brief %Heap structures implemented in LEMON. 248 249 This group contains the heap structures implemented in LEMON. 250 251 LEMON provides several heap classes. They are efficient implementations 252 of the abstract data type \e priority \e queue. They store items with 253 specified values called \e priorities in such a way that finding and 254 removing the item with minimum priority are efficient. 255 The basic operations are adding and erasing items, changing the priority 256 of an item, etc. 257 258 Heaps are crucial in several algorithms, such as Dijkstra and Prim. 259 The heap implementations have the same interface, thus any of them can be 260 used easily in such algorithms. 261 262 \sa \ref concepts::Heap "Heap concept" 249 \sa lemon::concepts::Path 263 250 */ 264 251 … … 273 260 274 261 /** 275 @defgroup geomdat Geometric Data Structures276 @ingroup auxdat277 \brief Geometric data structures implemented in LEMON.278 279 This group contains geometric data structures implemented in LEMON.280 281 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional282 vector with the usual operations.283 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the284 rectangular bounding box of a set of \ref lemon::dim2::Point285 "dim2::Point"'s.286 */287 288 /**289 262 @defgroup algs Algorithms 290 263 \brief This group contains the several algorithms … … 301 274 302 275 This group contains the common graph search algorithms, namely 303 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 304 \ref clrs01algorithms. 276 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 305 277 */ 306 278 … … 310 282 \brief Algorithms for finding shortest paths. 311 283 312 This group contains the algorithms for finding shortest paths in digraphs 313 \ref clrs01algorithms. 284 This group contains the algorithms for finding shortest paths in digraphs. 314 285 315 286 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 319 290 but the digraph should not contain directed cycles with negative total 320 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. 321 296 - \ref Suurballe A successive shortest path algorithm for finding 322 297 arc-disjoint paths between two nodes having minimum total length. … … 324 299 325 300 /** 326 @defgroup spantree Minimum Spanning Tree Algorithms327 @ingroup algs328 \brief Algorithms for finding minimum cost spanning trees and arborescences.329 330 This group contains the algorithms for finding minimum cost spanning331 trees and arborescences \ref clrs01algorithms.332 */333 334 /**335 301 @defgroup max_flow Maximum Flow Algorithms 336 302 @ingroup algs … … 338 304 339 305 This group contains the algorithms for finding maximum flows and 340 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.306 feasible circulations. 341 307 342 308 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 352 318 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 353 319 354 \ref Preflow is an efficient implementation of Goldberg-Tarjan's 355 preflow push-relabel algorithm \ref goldberg88newapproach for finding 356 maximum flows. It also provides functions to query the minimum cut, 357 which is the dual problem of maximum flow. 358 359 \ref Circulation is a preflow push-relabel algorithm implemented directly 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. 330 331 \ref Circulation is a preflow push-relabel algorithm implemented directly 360 332 for finding feasible circulations, which is a somewhat different problem, 361 333 but it is strongly related to maximum flow. … … 370 342 371 343 This group contains the algorithms for finding minimum cost flows and 372 circulations \ref amo93networkflows. For more information about this 373 problem and its dual solution, see \ref min_cost_flow 374 "Minimum Cost Flow Problem". 344 circulations. For more information about this problem and its dual 345 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 375 346 376 347 LEMON contains several algorithms for this problem. 377 348 - \ref NetworkSimplex Primal Network Simplex algorithm with various 378 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. 379 - \ref CostScaling Cost Scaling algorithm based on push/augment and 380 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, 381 \ref bunnagel98efficient. 382 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 383 shortest path method \ref edmondskarp72theoretical. 384 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 385 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. 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. 386 356 387 357 In general NetworkSimplex is the most efficient implementation, … … 406 376 407 377 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 408 \sum_{uv\in A :u\in X, v\not\in X}cap(uv) \f]378 \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f] 409 379 410 380 LEMON contains several algorithms related to minimum cut problems: … … 412 382 - \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut 413 383 in directed graphs. 384 - \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for 385 calculating minimum cut in undirected graphs. 414 386 - \ref GomoryHu "Gomory-Hu tree computation" for calculating 415 387 all-pairs minimum cut in undirected graphs. … … 420 392 421 393 /** 422 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 423 @ingroup algs 424 \brief Algorithms for finding minimum mean cycles. 425 426 This group contains the algorithms for finding minimum mean cycles 427 \ref clrs01algorithms, \ref amo93networkflows. 428 429 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 430 of minimum mean length (cost) in a digraph. 431 The mean length of a cycle is the average length of its arcs, i.e. the 432 ratio between the total length of the cycle and the number of arcs on it. 433 434 This problem has an important connection to \e conservative \e length 435 \e functions, too. A length function on the arcs of a digraph is called 436 conservative if and only if there is no directed cycle of negative total 437 length. For an arbitrary length function, the negative of the minimum 438 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 439 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 440 function. 441 442 LEMON contains three algorithms for solving the minimum mean cycle problem: 443 - \ref KarpMmc Karp's original algorithm \ref amo93networkflows, 444 \ref dasdan98minmeancycle. 445 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 446 version of Karp's algorithm \ref dasdan98minmeancycle. 447 - \ref HowardMmc Howard's policy iteration algorithm 448 \ref dasdan98minmeancycle. 449 450 In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the 451 most efficient one, though the best known theoretical bound on its running 452 time is exponential. 453 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms 454 run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is 455 typically faster due to the applied early termination scheme. 394 @defgroup graph_properties Connectivity and Other Graph Properties 395 @ingroup algs 396 \brief Algorithms for discovering the graph properties 397 398 This group contains the algorithms for discovering the graph properties 399 like connectivity, bipartiteness, euler property, simplicity etc. 400 401 \image html edge_biconnected_components.png 402 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 403 */ 404 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 456 415 */ 457 416 … … 474 433 475 434 The 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. 476 445 - \ref MaxMatching Edmond's blossom shrinking algorithm for calculating 477 446 maximum cardinality matching in general graphs. … … 481 450 Edmond's blossom shrinking algorithm for calculating maximum weighted 482 451 perfect matching in general graphs. 483 - \ref MaxFractionalMatching Push-relabel algorithm for calculating 484 maximum cardinality fractional matching in general graphs. 485 - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating 486 maximum weighted fractional matching in general graphs. 487 - \ref MaxWeightedPerfectFractionalMatching 488 Augmenting path algorithm for calculating maximum weighted 489 perfect fractional matching in general graphs. 490 491 \image html matching.png 492 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth 493 */ 494 495 /** 496 @defgroup graph_properties Connectivity and Other Graph Properties 497 @ingroup algs 498 \brief Algorithms for discovering the graph properties 499 500 This group contains the algorithms for discovering the graph properties 501 like connectivity, bipartiteness, euler property, simplicity etc. 502 503 \image html connected_components.png 504 \image latex connected_components.eps "Connected components" width=\textwidth 505 */ 506 507 /** 508 @defgroup planar Planarity Embedding and Drawing 509 @ingroup algs 510 \brief Algorithms for planarity checking, embedding and drawing 511 512 This group contains the algorithms for planarity checking, 513 embedding and drawing. 514 515 \image html planar.png 516 \image latex planar.eps "Plane graph" width=\textwidth 452 453 \image html bipartite_matching.png 454 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 455 */ 456 457 /** 458 @defgroup spantree Minimum Spanning Tree Algorithms 459 @ingroup algs 460 \brief Algorithms for finding minimum cost spanning trees and arborescences. 461 462 This group contains the algorithms for finding minimum cost spanning 463 trees and arborescences. 517 464 */ 518 465 … … 524 471 This group contains some algorithms implemented in LEMON 525 472 in order to make it easier to implement complex algorithms. 473 */ 474 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. 526 482 */ 527 483 … … 536 492 537 493 /** 538 @defgroup lp_group L P and MIPSolvers494 @defgroup lp_group Lp and Mip Solvers 539 495 @ingroup gen_opt_group 540 \brief LP and MIP solver interfaces for LEMON. 541 542 This group contains LP and MIP solver interfaces for LEMON. 543 Various LP solvers could be used in the same manner with this 544 high-level interface. 545 546 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 547 \ref cplex, \ref soplex. 496 \brief Lp and Mip solver interfaces for LEMON. 497 498 This group contains Lp and Mip solver interfaces for LEMON. The 499 various LP solvers could be used in the same manner with this 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. 548 518 */ 549 519 … … 618 588 619 589 /** 620 @defgroup dimacs_group DIMACS Format590 @defgroup dimacs_group DIMACS format 621 591 @ingroup io_group 622 592 \brief Read and write files in DIMACS format … … 667 637 \brief Skeleton and concept checking classes for graph structures 668 638 669 This group contains the skeletons and concept checking classes of 670 graph structures .639 This group contains the skeletons and concept checking classes of LEMON's 640 graph structures and helper classes used to implement these. 671 641 */ 672 642 … … 680 650 681 651 /** 652 \anchor demoprograms 653 654 @defgroup demos Demo Programs 655 656 Some demo programs are listed here. Their full source codes can be found in 657 the \c demo subdirectory of the source tree. 658 659 In order to compile them, use the <tt>make demo</tt> or the 660 <tt>make check</tt> commands. 661 */ 662 663 /** 682 664 @defgroup tools Standalone Utility Applications 683 665 … … 688 670 */ 689 671 690 /**691 \anchor demoprograms692 693 @defgroup demos Demo Programs694 695 Some demo programs are listed here. Their full source codes can be found in696 the \c demo subdirectory of the source tree.697 698 In order to compile them, use the <tt>make demo</tt> or the699 <tt>make check</tt> commands.700 */701 702 672 }
Note: See TracChangeset
for help on using the changeset viewer.