Changes in doc/groups.dox [606:c5fd2d996909:1271:fb1c7da561ce] in lemon
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r606 r1271 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 113 113 detailed documentation of particular adaptors. 114 114 115 Since the adaptor classes conform to the \ref graph_concepts "graph concepts", 116 an adaptor can even be applied to another one. 117 The following image illustrates a situation when a \ref SubDigraph adaptor 118 is applied on a digraph and \ref Undirector is applied on the subgraph. 119 120 \image html adaptors2.png 121 \image latex adaptors2.eps "Using graph adaptors" width=\textwidth 122 115 123 The behavior of graph adaptors can be very different. Some of them keep 116 124 capabilities of the original graph while in other cases this would be … … 139 147 140 148 /** 141 @defgroup semi_adaptors Semi-Adaptor 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 light-weight structures as the adaptors.148 */149 150 /**151 149 @defgroup maps Maps 152 150 @ingroup datas … … 237 235 238 236 /** 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 237 @defgroup paths Path Structures 248 238 @ingroup datas … … 257 247 any kind of path structure. 258 248 259 \sa lemon::concepts::Path 249 \sa \ref concepts::Path "Path concept" 250 */ 251 252 /** 253 @defgroup heaps Heap Structures 254 @ingroup datas 255 \brief %Heap structures implemented in LEMON. 256 257 This group contains the heap structures implemented in LEMON. 258 259 LEMON provides several heap classes. They are efficient implementations 260 of the abstract data type \e priority \e queue. They store items with 261 specified values called \e priorities in such a way that finding and 262 removing the item with minimum priority are efficient. 263 The basic operations are adding and erasing items, changing the priority 264 of an item, etc. 265 266 Heaps are crucial in several algorithms, such as Dijkstra and Prim. 267 The heap implementations have the same interface, thus any of them can be 268 used easily in such algorithms. 269 270 \sa \ref concepts::Heap "Heap concept" 260 271 */ 261 272 … … 270 281 271 282 /** 283 @defgroup geomdat Geometric Data Structures 284 @ingroup auxdat 285 \brief Geometric data structures implemented in LEMON. 286 287 This group contains geometric data structures implemented in LEMON. 288 289 - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional 290 vector with the usual operations. 291 - \ref lemon::dim2::Box "dim2::Box" can be used to determine the 292 rectangular bounding box of a set of \ref lemon::dim2::Point 293 "dim2::Point"'s. 294 */ 295 296 /** 297 @defgroup matrices Matrices 298 @ingroup auxdat 299 \brief Two dimensional data storages implemented in LEMON. 300 301 This group contains two dimensional data storages implemented in LEMON. 302 */ 303 304 /** 272 305 @defgroup algs Algorithms 273 306 \brief This group contains the several algorithms … … 284 317 285 318 This group contains the common graph search algorithms, namely 286 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \cite clrs01algorithms. 287 321 */ 288 322 … … 292 326 \brief Algorithms for finding shortest paths. 293 327 294 This group contains the algorithms for finding shortest paths in digraphs. 328 This group contains the algorithms for finding shortest paths in digraphs 329 \cite clrs01algorithms. 295 330 296 331 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 309 344 310 345 /** 346 @defgroup spantree Minimum Spanning Tree Algorithms 347 @ingroup algs 348 \brief Algorithms for finding minimum cost spanning trees and arborescences. 349 350 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \cite clrs01algorithms. 352 */ 353 354 /** 311 355 @defgroup max_flow Maximum Flow Algorithms 312 356 @ingroup algs … … 314 358 315 359 This group contains the algorithms for finding maximum flows and 316 feasible circulations .360 feasible circulations \cite clrs01algorithms, \cite amo93networkflows. 317 361 318 362 The \e maximum \e flow \e problem is to find a flow of maximum value between 319 363 a single source and a single target. Formally, there is a \f$G=(V,A)\f$ 320 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and364 digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and 321 365 \f$s, t \in V\f$ source and target nodes. 322 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the366 A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the 323 367 following optimization problem. 324 368 325 \f[ \max\sum_{ a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]326 \f[ \sum_{ a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)327 \q quad \forall v\in V\setminus\{s,t\} \f]328 \f[ 0 \leq f( a) \leq cap(a) \qquad \forall a\in A \f]369 \f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] 370 \f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) 371 \quad \forall u\in V\setminus\{s,t\} \f] 372 \f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] 329 373 330 374 LEMON contains several algorithms for solving maximum flow problems: 331 - \ref EdmondsKarp Edmonds-Karp algorithm. 332 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 333 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 334 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 335 336 In most cases the \ref Preflow "Preflow" algorithm provides the 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \cite edmondskarp72theoretical. 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \cite goldberg88newapproach. 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \cite dinic70algorithm, \cite sleator83dynamic. 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \cite goldberg88newapproach, \cite sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 337 385 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. 340 */ 341 342 /** 343 @defgroup min_cost_flow Minimum Cost Flow Algorithms 386 also provide functions to query the minimum cut, which is the dual 387 problem of maximum flow. 388 389 \ref Circulation is a preflow push-relabel algorithm implemented directly 390 for finding feasible circulations, which is a somewhat different problem, 391 but it is strongly related to maximum flow. 392 For more information, see \ref Circulation. 393 */ 394 395 /** 396 @defgroup min_cost_flow_algs Minimum Cost Flow Algorithms 344 397 @ingroup algs 345 398 … … 347 400 348 401 This group contains the algorithms for finding minimum cost flows and 349 circulations. 350 351 The \e minimum \e cost \e flow \e problem is to find a feasible flow of 352 minimum total cost from a set of supply nodes to a set of demand nodes 353 in a network with capacity constraints and arc costs. 354 Formally, let \f$G=(V,A)\f$ be a digraph, 355 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and 356 upper bounds for the flow values on the arcs, 357 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow 358 on the arcs, and 359 \f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values 360 of the nodes. 361 A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of 362 the following optimization problem. 363 364 \f[ \min\sum_{a\in A} f(a) cost(a) \f] 365 \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = 366 supply(v) \qquad \forall v\in V \f] 367 \f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] 368 369 LEMON contains several algorithms for solving minimum cost flow problems: 370 - \ref CycleCanceling Cycle-canceling algorithms. 371 - \ref CapacityScaling Successive shortest path algorithm with optional 372 capacity scaling. 373 - \ref CostScaling Push-relabel and augment-relabel algorithms based on 374 cost scaling. 375 - \ref NetworkSimplex Primal network simplex algorithm with various 376 pivot strategies. 402 circulations \cite amo93networkflows. For more information about this 403 problem and its dual solution, see: \ref min_cost_flow 404 "Minimum Cost Flow Problem". 405 406 LEMON contains several algorithms for this problem. 407 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex. 409 - \ref CostScaling Cost Scaling algorithm based on push/augment and 410 relabel operations \cite goldberg90approximation, \cite goldberg97efficient, 411 \cite bunnagel98efficient. 412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 413 shortest path method \cite edmondskarp72theoretical. 414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 415 strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling. 416 417 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient 418 implementations. 419 \ref NetworkSimplex is usually the fastest on relatively small graphs (up to 420 several thousands of nodes) and on dense graphs, while \ref CostScaling is 421 typically more efficient on large graphs (e.g. hundreds of thousands of 422 nodes or above), especially if they are sparse. 423 However, other algorithms could be faster in special cases. 424 For example, if the total supply and/or capacities are rather small, 425 \ref CapacityScaling is usually the fastest algorithm 426 (without effective scaling). 427 428 These classes are intended to be used with integer-valued input data 429 (capacities, supply values, and costs), except for \ref CapacityScaling, 430 which is capable of handling real-valued arc costs (other numerical 431 data are required to be integer). 432 433 For more details about these implementations and for a comprehensive 434 experimental study, see the paper \cite KiralyKovacs12MCF. 435 It also compares these codes to other publicly available 436 minimum cost flow solvers. 377 437 */ 378 438 … … 392 452 393 453 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}} 394 \sum_{uv\in A ,u\in X, v\not\in X}cap(uv) \f]454 \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f] 395 455 396 456 LEMON contains several algorithms related to minimum cut problems: … … 408 468 409 469 /** 410 @defgroup graph_prop Connectivity and Other Graph Properties 411 @ingroup algs 412 \brief Algorithms for discovering the graph properties 413 414 This group contains the algorithms for discovering the graph properties 415 like connectivity, bipartiteness, euler property, simplicity etc. 416 417 \image html edge_biconnected_components.png 418 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth 419 */ 420 421 /** 422 @defgroup planar Planarity Embedding and Drawing 423 @ingroup algs 424 \brief Algorithms for planarity checking, embedding and drawing 425 426 This group contains the algorithms for planarity checking, 427 embedding and drawing. 428 429 \image html planar.png 430 \image latex planar.eps "Plane graph" width=\textwidth 470 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms 471 @ingroup algs 472 \brief Algorithms for finding minimum mean cycles. 473 474 This group contains the algorithms for finding minimum mean cycles 475 \cite amo93networkflows, \cite karp78characterization. 476 477 The \e minimum \e mean \e cycle \e problem is to find a directed cycle 478 of minimum mean length (cost) in a digraph. 479 The mean length of a cycle is the average length of its arcs, i.e. the 480 ratio between the total length of the cycle and the number of arcs on it. 481 482 This problem has an important connection to \e conservative \e length 483 \e functions, too. A length function on the arcs of a digraph is called 484 conservative if and only if there is no directed cycle of negative total 485 length. For an arbitrary length function, the negative of the minimum 486 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the 487 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length 488 function. 489 490 LEMON contains three algorithms for solving the minimum mean cycle problem: 491 - \ref KarpMmc Karp's original algorithm \cite karp78characterization. 492 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 493 version of Karp's algorithm \cite hartmann93finding. 494 - \ref HowardMmc Howard's policy iteration algorithm 495 \cite dasdan98minmeancycle, \cite dasdan04experimental. 496 497 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the 498 most efficient one, though the best known theoretical bound on its running 499 time is exponential. 500 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms 501 run in time O(nm) and use space O(n<sup>2</sup>+m). 431 502 */ 432 503 … … 436 507 \brief Algorithms for finding matchings in graphs and bipartite graphs. 437 508 438 This group contains algorithm objects and functions to calculate509 This group contains the algorithms for calculating 439 510 matchings in graphs and bipartite graphs. The general matching problem is 440 finding a subset of the arcs which does not shares common endpoints. 511 finding a subset of the edges for which each node has at most one incident 512 edge. 441 513 442 514 There are several different algorithms for calculate matchings in … … 465 537 Edmond's blossom shrinking algorithm for calculating maximum weighted 466 538 perfect matching in general graphs. 467 468 \image html bipartite_matching.png 469 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth 470 */ 471 472 /** 473 @defgroup spantree Minimum Spanning Tree Algorithms 474 @ingroup algs 475 \brief Algorithms for finding a minimum cost spanning tree in a graph. 476 477 This group contains the algorithms for finding a minimum cost spanning 478 tree in a graph. 539 - \ref MaxFractionalMatching Push-relabel algorithm for calculating 540 maximum cardinality fractional matching in general graphs. 541 - \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating 542 maximum weighted fractional matching in general graphs. 543 - \ref MaxWeightedPerfectFractionalMatching 544 Augmenting path algorithm for calculating maximum weighted 545 perfect fractional matching in general graphs. 546 547 \image html matching.png 548 \image latex matching.eps "Min Cost Perfect Matching" width=\textwidth 549 */ 550 551 /** 552 @defgroup graph_properties Connectivity and Other Graph Properties 553 @ingroup algs 554 \brief Algorithms for discovering the graph properties 555 556 This group contains the algorithms for discovering the graph properties 557 like connectivity, bipartiteness, euler property, simplicity etc. 558 559 \image html connected_components.png 560 \image latex connected_components.eps "Connected components" width=\textwidth 561 */ 562 563 /** 564 @defgroup planar Planar Embedding and Drawing 565 @ingroup algs 566 \brief Algorithms for planarity checking, embedding and drawing 567 568 This group contains the algorithms for planarity checking, 569 embedding and drawing. 570 571 \image html planar.png 572 \image latex planar.eps "Plane graph" width=\textwidth 573 */ 574 575 /** 576 @defgroup tsp Traveling Salesman Problem 577 @ingroup algs 578 \brief Algorithms for the symmetric traveling salesman problem 579 580 This group contains basic heuristic algorithms for the the symmetric 581 \e traveling \e salesman \e problem (TSP). 582 Given an \ref FullGraph "undirected full graph" with a cost map on its edges, 583 the problem is to find a shortest possible tour that visits each node exactly 584 once (i.e. the minimum cost Hamiltonian cycle). 585 586 These TSP algorithms are intended to be used with a \e metric \e cost 587 \e function, i.e. the edge costs should satisfy the triangle inequality. 588 Otherwise the algorithms could yield worse results. 589 590 LEMON provides five well-known heuristics for solving symmetric TSP: 591 - \ref NearestNeighborTsp Neareast neighbor algorithm 592 - \ref GreedyTsp Greedy algorithm 593 - \ref InsertionTsp Insertion heuristic (with four selection methods) 594 - \ref ChristofidesTsp Christofides algorithm 595 - \ref Opt2Tsp 2-opt algorithm 596 597 \ref NearestNeighborTsp, \ref GreedyTsp, and \ref InsertionTsp are the fastest 598 solution methods. Furthermore, \ref InsertionTsp is usually quite effective. 599 600 \ref ChristofidesTsp is somewhat slower, but it has the best guaranteed 601 approximation factor: 3/2. 602 603 \ref Opt2Tsp usually provides the best results in practice, but 604 it is the slowest method. It can also be used to improve given tours, 605 for example, the results of other algorithms. 606 607 \image html tsp.png 608 \image latex tsp.eps "Traveling salesman problem" width=\textwidth 609 */ 610 611 /** 612 @defgroup approx_algs Approximation Algorithms 613 @ingroup algs 614 \brief Approximation algorithms. 615 616 This group contains the approximation and heuristic algorithms 617 implemented in LEMON. 618 619 <b>Maximum Clique Problem</b> 620 - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of 621 Grosso, Locatelli, and Pullan. 479 622 */ 480 623 … … 486 629 This group contains some algorithms implemented in LEMON 487 630 in order to make it easier to implement complex algorithms. 488 */489 490 /**491 @defgroup approx Approximation Algorithms492 @ingroup algs493 \brief Approximation algorithms.494 495 This group contains the approximation and heuristic algorithms496 implemented in LEMON.497 631 */ 498 632 … … 507 641 508 642 /** 509 @defgroup lp_group L p and MipSolvers643 @defgroup lp_group LP and MIP Solvers 510 644 @ingroup gen_opt_group 511 \brief Lp and Mip solver interfaces for LEMON. 512 513 This group contains Lp and Mip solver interfaces for LEMON. The 514 various LP solvers could be used in the same manner with this 515 interface. 645 \brief LP and MIP solver interfaces for LEMON. 646 647 This group contains LP and MIP solver interfaces for LEMON. 648 Various LP solvers could be used in the same manner with this 649 high-level interface. 650 651 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, 652 \cite cplex, \cite soplex. 516 653 */ 517 654 … … 600 737 This group contains general \c EPS drawing methods and special 601 738 graph exporting tools. 602 */ 603 604 /** 605 @defgroup dimacs_group DIMACS format 739 740 \image html graph_to_eps.png 741 */ 742 743 /** 744 @defgroup dimacs_group DIMACS Format 606 745 @ingroup io_group 607 746 \brief Read and write files in DIMACS format … … 652 791 \brief Skeleton and concept checking classes for graph structures 653 792 654 This group contains the skeletons and concept checking classes of LEMON's655 graph structures and helper classes used to implement these.793 This group contains the skeletons and concept checking classes of 794 graph structures. 656 795 */ 657 796 … … 665 804 666 805 /** 806 @defgroup tools Standalone Utility Applications 807 808 Some utility applications are listed here. 809 810 The standard compilation procedure (<tt>./configure;make</tt>) will compile 811 them, as well. 812 */ 813 814 /** 667 815 \anchor demoprograms 668 816 … … 672 820 the \c demo subdirectory of the source tree. 673 821 674 It order to compile them, use <tt>--enable-demo</tt> configure option when 675 build the library. 676 */ 677 678 /** 679 @defgroup tools Standalone Utility Applications 680 681 Some utility applications are listed here. 682 683 The standard compilation procedure (<tt>./configure;make</tt>) will compile 684 them, as well. 822 In order to compile them, use the <tt>make demo</tt> or the 823 <tt>make check</tt> commands. 685 824 */ 686 825
Note: See TracChangeset
for help on using the changeset viewer.