Changeset 1053:1c978b5bcc65 in lemon-main
- Timestamp:
- 03/18/13 17:41:19 (12 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 1 deleted
- 14 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/CMakeLists.txt
r1050 r1053 52 52 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r8 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 53 53 COMMAND ${CMAKE_COMMAND} -E remove_directory html 54 COMMAND ${PYTHON_EXECUTABLE} ${PROJECT_SOURCE_DIR}/scripts/bib2dox.py ${CMAKE_CURRENT_SOURCE_DIR}/references.bib >references.dox55 54 COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile 56 55 WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR} -
doc/Doxyfile.in
r1040 r1053 78 78 FILE_VERSION_FILTER = 79 79 LAYOUT_FILE = "@abs_top_srcdir@/doc/DoxygenLayout.xml" 80 CITE_BIB_FILES = "@abs_top_srcdir@/doc/references.bib" 80 81 #--------------------------------------------------------------------------- 81 82 # configuration options related to warning and progress messages -
doc/groups.dox
r1051 r1053 318 318 This group contains the common graph search algorithms, namely 319 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ refclrs01algorithms.320 \cite clrs01algorithms. 321 321 */ 322 322 … … 327 327 328 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ refclrs01algorithms.329 \cite clrs01algorithms. 330 330 331 331 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 349 349 350 350 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \ refclrs01algorithms.351 trees and arborescences \cite clrs01algorithms. 352 352 */ 353 353 … … 358 358 359 359 This group contains the algorithms for finding maximum flows and 360 feasible circulations \ ref clrs01algorithms, \refamo93networkflows.360 feasible circulations \cite clrs01algorithms, \cite amo93networkflows. 361 361 362 362 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 374 374 LEMON contains several algorithms for solving maximum flow problems: 375 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ refedmondskarp72theoretical.376 \cite edmondskarp72theoretical. 377 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ refgoldberg88newapproach.378 \cite goldberg88newapproach. 379 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ ref dinic70algorithm, \refsleator83dynamic.380 \cite dinic70algorithm, \cite sleator83dynamic. 381 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ ref goldberg88newapproach, \refsleator83dynamic.382 \cite goldberg88newapproach, \cite sleator83dynamic. 383 383 384 384 In most cases the \ref Preflow algorithm provides the … … 400 400 401 401 This group contains the algorithms for finding minimum cost flows and 402 circulations \ refamo93networkflows. For more information about this402 circulations \cite amo93networkflows. For more information about this 403 403 problem and its dual solution, see: \ref min_cost_flow 404 404 "Minimum Cost Flow Problem". … … 406 406 LEMON contains several algorithms for this problem. 407 407 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 pivot strategies \ ref dantzig63linearprog, \refkellyoneill91netsimplex.408 pivot strategies \cite dantzig63linearprog, \cite kellyoneill91netsimplex. 409 409 - \ref CostScaling Cost Scaling algorithm based on push/augment and 410 relabel operations \ ref goldberg90approximation, \refgoldberg97efficient,411 \ refbunnagel98efficient.410 relabel operations \cite goldberg90approximation, \cite goldberg97efficient, 411 \cite bunnagel98efficient. 412 412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive 413 shortest path method \ refedmondskarp72theoretical.413 shortest path method \cite edmondskarp72theoretical. 414 414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are 415 strongly polynomial \ ref klein67primal, \refgoldberg89cyclecanceling.415 strongly polynomial \cite klein67primal, \cite goldberg89cyclecanceling. 416 416 417 417 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient … … 431 431 432 432 For more details about these implementations and for a comprehensive 433 experimental study, see the paper \ refKiralyKovacs12MCF.433 experimental study, see the paper \cite KiralyKovacs12MCF. 434 434 It also compares these codes to other publicly available 435 435 minimum cost flow solvers. … … 472 472 473 473 This group contains the algorithms for finding minimum mean cycles 474 \ ref amo93networkflows, \refkarp78characterization.474 \cite amo93networkflows, \cite karp78characterization. 475 475 476 476 The \e minimum \e mean \e cycle \e problem is to find a directed cycle … … 488 488 489 489 LEMON contains three algorithms for solving the minimum mean cycle problem: 490 - \ref KarpMmc Karp's original algorithm \ refkarp78characterization.490 - \ref KarpMmc Karp's original algorithm \cite karp78characterization. 491 491 - \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved 492 version of Karp's algorithm \ refhartmann93finding.492 version of Karp's algorithm \cite hartmann93finding. 493 493 - \ref HowardMmc Howard's policy iteration algorithm 494 \ ref dasdan98minmeancycle, \refdasdan04experimental.494 \cite dasdan98minmeancycle, \cite dasdan04experimental. 495 495 496 496 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the … … 648 648 high-level interface. 649 649 650 The currently supported solvers are \ ref glpk, \ref clp, \refcbc,651 \ ref cplex, \refsoplex.650 The currently supported solvers are \cite glpk, \cite clp, \cite cbc, 651 \cite cplex, \cite soplex. 652 652 */ 653 653 -
doc/mainpage.dox.in
r1051 r1053 26 26 It is a C++ template library providing efficient implementations of common 27 27 data structures and algorithms with focus on combinatorial optimization 28 tasks connected mainly with graphs and networks \ refDezsoJuttnerKovacs11Lemon.28 tasks connected mainly with graphs and networks \cite DezsoJuttnerKovacs11Lemon. 29 29 30 30 <b> … … 38 38 The project is maintained by the 39 39 <a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on 40 Combinatorial Optimization</a> \ refegres40 Combinatorial Optimization</a> \cite egres 41 41 at the Operations Research Department of the 42 42 <a href="http://www.elte.hu/en/">Eötvös Loránd University</a>, 43 43 Budapest, Hungary. 44 44 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> 45 initiative \ refcoinor.45 initiative \cite coinor. 46 46 47 47 \section howtoread How to Read the Documentation -
doc/min_cost_flow.dox
r1002 r1053 27 27 minimum total cost from a set of supply nodes to a set of demand nodes 28 28 in a network with capacity constraints (lower and upper bounds) 29 and arc costs \ refamo93networkflows.29 and arc costs \cite amo93networkflows. 30 30 31 31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, -
lemon/capacity_scaling.h
r1049 r1053 67 67 /// \ref CapacityScaling implements the capacity scaling version 68 68 /// of the successive shortest path algorithm for finding a 69 /// \ref min_cost_flow "minimum cost flow" \ refamo93networkflows,70 /// \ refedmondskarp72theoretical. It is an efficient dual69 /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, 70 /// \cite edmondskarp72theoretical. It is an efficient dual 71 71 /// solution method, which runs in polynomial time 72 72 /// \f$O(e\log U (n+e)\log n)\f$, where <i>U</i> denotes the maximum -
lemon/cost_scaling.h
r1049 r1053 92 92 /// \ref CostScaling implements a cost scaling algorithm that performs 93 93 /// push/augment and relabel operations for finding a \ref min_cost_flow 94 /// "minimum cost flow" \ ref amo93networkflows, \refgoldberg90approximation,95 /// \ ref goldberg97efficient, \refbunnagel98efficient.94 /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation, 95 /// \cite goldberg97efficient, \cite bunnagel98efficient. 96 96 /// It is a highly efficient primal-dual solution method, which 97 97 /// can be viewed as the generalization of the \ref Preflow -
lemon/cycle_canceling.h
r1049 r1053 48 48 /// \ref CycleCanceling implements three different cycle-canceling 49 49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" 50 /// \ ref amo93networkflows, \refklein67primal,51 /// \ refgoldberg89cyclecanceling.50 /// \cite amo93networkflows, \cite klein67primal, 51 /// \cite goldberg89cyclecanceling. 52 52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 53 53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. … … 132 132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a 133 133 /// well-known strongly polynomial method 134 /// \ refgoldberg89cyclecanceling. It improves along a134 /// \cite goldberg89cyclecanceling. It improves along a 135 135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 136 136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). … … 138 138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an 139 139 /// improved version of the previous method 140 /// \ refgoldberg89cyclecanceling.140 /// \cite goldberg89cyclecanceling. 141 141 /// It is faster both in theory and in practice, its running time 142 142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). -
lemon/grosso_locatelli_pullan_mc.h
r918 r1053 41 41 /// \ref GrossoLocatelliPullanMc implements the iterated local search 42 42 /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum 43 /// \e clique \e problem \ refgrosso08maxclique.43 /// \e clique \e problem \cite grosso08maxclique. 44 44 /// It is to find the largest complete subgraph (\e clique) in an 45 45 /// undirected graph, i.e., the largest set of nodes where each -
lemon/hartmann_orlin_mmc.h
r1049 r1053 99 99 /// This class implements the Hartmann-Orlin algorithm for finding 100 100 /// a directed cycle of minimum mean cost in a digraph 101 /// \ ref hartmann93finding, \refdasdan98minmeancycle.101 /// \cite hartmann93finding, \cite dasdan98minmeancycle. 102 102 /// This method is based on \ref KarpMmc "Karp"'s original algorithm, but 103 103 /// applies an early termination scheme. It makes the algorithm -
lemon/howard_mmc.h
r1049 r1053 99 99 /// This class implements Howard's policy iteration algorithm for finding 100 100 /// a directed cycle of minimum mean cost in a digraph 101 /// \ ref dasdan98minmeancycle, \refdasdan04experimental.101 /// \cite dasdan98minmeancycle, \cite dasdan04experimental. 102 102 /// This class provides the most efficient algorithm for the 103 103 /// minimum mean cycle problem, though the best known theoretical -
lemon/karp_mmc.h
r1049 r1053 99 99 /// This class implements Karp's algorithm for finding a directed 100 100 /// cycle of minimum mean cost in a digraph 101 /// \ ref karp78characterization, \refdasdan98minmeancycle.101 /// \cite karp78characterization, \cite dasdan98minmeancycle. 102 102 /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e). 103 103 /// -
lemon/network_simplex.h
r1049 r1053 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ ref amo93networkflows, \refdantzig63linearprog,45 /// \ refkellyoneill91netsimplex.44 /// \cite amo93networkflows, \cite dantzig63linearprog, 45 /// \cite kellyoneill91netsimplex. 46 46 /// This algorithm is a highly efficient specialized version of the 47 47 /// linear programming simplex method directly for the minimum cost -
lemon/preflow.h
r966 r1053 103 103 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 104 104 /// \e push-relabel algorithm producing a \ref max_flow 105 /// "flow of maximum value" in a digraph \ refclrs01algorithms,106 /// \ ref amo93networkflows, \refgoldberg88newapproach.105 /// "flow of maximum value" in a digraph \cite clrs01algorithms, 106 /// \cite amo93networkflows, \cite goldberg88newapproach. 107 107 /// The preflow algorithms are the fastest known maximum 108 108 /// flow algorithms. The current implementation uses a mixture of the
Note: See TracChangeset
for help on using the changeset viewer.