Changes in / [757:9fbbd802020f:753:48fe2a46bf91] in lemon-1.2
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/Doxyfile.in
r756 r744 1 # Doxyfile 1.5. 91 # Doxyfile 1.5.7.1 2 2 3 3 #--------------------------------------------------------------------------- … … 22 22 QT_AUTOBRIEF = NO 23 23 MULTILINE_CPP_IS_BRIEF = NO 24 DETAILS_AT_TOP = YES 24 25 INHERIT_DOCS = NO 25 26 SEPARATE_MEMBER_PAGES = NO … … 224 225 SKIP_FUNCTION_MACROS = YES 225 226 #--------------------------------------------------------------------------- 226 # Options related to the search engine227 # Configuration::additions related to external references 227 228 #--------------------------------------------------------------------------- 228 229 TAGFILES = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/ " -
doc/groups.dox
r755 r742 317 317 318 318 This group contains the common graph search algorithms, namely 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) 320 \ref clrs01algorithms. 319 \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). 321 320 */ 322 321 … … 326 325 \brief Algorithms for finding shortest paths. 327 326 328 This group contains the algorithms for finding shortest paths in digraphs 329 \ref clrs01algorithms. 327 This group contains the algorithms for finding shortest paths in digraphs. 330 328 331 329 - \ref Dijkstra algorithm for finding shortest paths from a source node … … 349 347 350 348 This group contains the algorithms for finding minimum cost spanning 351 trees and arborescences \ref clrs01algorithms.349 trees and arborescences. 352 350 */ 353 351 … … 358 356 359 357 This group contains the algorithms for finding maximum flows and 360 feasible circulations \ref clrs01algorithms, \ref amo93networkflows.358 feasible circulations. 361 359 362 360 The \e maximum \e flow \e problem is to find a flow of maximum value between … … 373 371 374 372 LEMON contains several algorithms for solving maximum flow problems: 375 - \ref EdmondsKarp Edmonds-Karp algorithm 376 \ref edmondskarp72theoretical. 377 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm 378 \ref goldberg88newapproach. 379 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees 380 \ref dinic70algorithm, \ref sleator83dynamic. 381 - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees 382 \ref goldberg88newapproach, \ref sleator83dynamic. 383 384 In most cases the \ref Preflow algorithm provides the 373 - \ref EdmondsKarp Edmonds-Karp algorithm. 374 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. 375 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. 376 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. 377 378 In most cases the \ref Preflow "Preflow" algorithm provides the 385 379 fastest method for computing a maximum flow. All implementations 386 380 also provide functions to query the minimum cut, which is the dual … … 400 394 401 395 This group contains the algorithms for finding minimum cost flows and 402 circulations \ref amo93networkflows. For more information about this 403 problem and its dual solution, see \ref min_cost_flow 404 "Minimum Cost Flow Problem". 396 circulations. For more information about this problem and its dual 397 solution see \ref min_cost_flow "Minimum Cost Flow Problem". 405 398 406 399 LEMON contains several algorithms for this problem. 407 400 - \ref NetworkSimplex Primal Network Simplex algorithm with various 408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.401 pivot strategies. 409 402 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on 410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, 411 \ref bunnagel98efficient. 403 cost scaling. 412 404 - \ref CapacityScaling Successive Shortest %Path algorithm with optional 413 capacity scaling \ref edmondskarp72theoretical. 414 - \ref CancelAndTighten The Cancel and Tighten algorithm 415 \ref goldberg89cyclecanceling. 416 - \ref CycleCanceling Cycle-Canceling algorithms 417 \ref klein67primal, \ref goldberg89cyclecanceling. 405 capacity scaling. 406 - \ref CancelAndTighten The Cancel and Tighten algorithm. 407 - \ref CycleCanceling Cycle-Canceling algorithms. 418 408 419 409 In general NetworkSimplex is the most efficient implementation, … … 545 535 546 536 /** 547 @defgroup lp_group L P and MIPSolvers537 @defgroup lp_group Lp and Mip Solvers 548 538 @ingroup gen_opt_group 549 \brief LP and MIP solver interfaces for LEMON. 550 551 This group contains LP and MIP solver interfaces for LEMON. 552 Various LP solvers could be used in the same manner with this 553 high-level interface. 554 555 The currently supported solvers are \ref glpk, \ref clp, \ref cbc, 556 \ref cplex, \ref soplex. 539 \brief Lp and Mip solver interfaces for LEMON. 540 541 This group contains Lp and Mip solver interfaces for LEMON. The 542 various LP solvers could be used in the same manner with this 543 interface. 557 544 */ 558 545 -
doc/mainpage.dox
r755 r658 22 22 \section intro Introduction 23 23 24 <b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 25 and <b>O</b>ptimization in <b>N</b>etworks</i>. 26 It is a C++ template library providing efficient implementation of common 27 data structures and algorithms with focus on combinatorial optimization 28 problems in graphs and networks. 24 \subsection whatis What is LEMON 25 26 LEMON stands for <b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling 27 and <b>O</b>ptimization in <b>N</b>etworks. 28 It is a C++ template 29 library aimed at combinatorial optimization tasks which 30 often involve in working 31 with graphs. 29 32 30 33 <b> … … 36 39 </b> 37 40 38 The project is maintained by the 39 <a href="http://www.cs.elte.hu/egres/">Egerváry Research Group on 40 Combinatorial Optimization</a> \ref egres 41 at the Operations Research Department of the 42 <a href="http://www.elte.hu/">Eötvös Loránd University, 43 Budapest</a>, Hungary. 44 LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a> 45 initiative \ref coinor. 46 47 \section howtoread How to Read the Documentation 41 \subsection howtoread How to read the documentation 48 42 49 43 If you would like to get to know the library, see -
doc/min_cost_flow.dox
r755 r663 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 \ref amo93networkflows.29 and arc costs. 30 30 31 31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, -
doc/references.bib
r755 r743 13 13 title = {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on 14 14 {C}ombinatorial {O}ptimization}, 15 url = {http://www.cs.elte.hu/egres/} 15 howpublished = {\url{http://www.cs.elte.hu/egres/}}, 16 year = 2009 16 17 } 17 18 … … 20 21 title = {{COIN-OR} -- {C}omputational {I}nfrastructure for 21 22 {O}perations {R}esearch}, 22 url = {http://www.coin-or.org/} 23 howpublished = {\url{http://www.coin-or.org/}}, 24 year = 2009 23 25 } 24 26 … … 29 31 key = {Boost}, 30 32 title = {{B}oost {C++} {L}ibraries}, 31 url = {http://www.boost.org/} 33 howpublished = {\url{http://www.boost.org/}}, 34 year = 2009 32 35 } 33 36 … … 45 48 title = {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and 46 49 {A}lgorithms}, 47 url = {http://www.algorithmic-solutions.com/} 50 howpublished = {\url{http://www.algorithmic-solutions.com/}}, 51 year = 2009 48 52 } 49 53 … … 64 68 key = {CMake}, 65 69 title = {{CMake} -- {C}ross {P}latform {M}ake}, 66 url = {http://www.cmake.org/} 70 howpublished = {\url{http://www.cmake.org/}}, 71 year = 2009 67 72 } 68 73 … … 71 76 title = {{Doxygen} -- {S}ource code documentation generator 72 77 tool}, 73 url = {http://www.doxygen.org/} 78 howpublished = {\url{http://www.doxygen.org/}}, 79 year = 2009 74 80 } 75 81 … … 80 86 key = {GLPK}, 81 87 title = {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it}, 82 url = {http://www.gnu.org/software/glpk/} 88 howpublished = {\url{http://www.gnu.org/software/glpk/}}, 89 year = 2009 83 90 } 84 91 … … 86 93 key = {Clp}, 87 94 title = {{Clp} -- {Coin-Or} {L}inear {P}rogramming}, 88 url = {http://projects.coin-or.org/Clp/} 95 howpublished = {\url{http://projects.coin-or.org/Clp/}}, 96 year = 2009 89 97 } 90 98 … … 92 100 key = {Cbc}, 93 101 title = {{Cbc} -- {Coin-Or} {B}ranch and {C}ut}, 94 url = {http://projects.coin-or.org/Cbc/} 102 howpublished = {\url{http://projects.coin-or.org/Cbc/}}, 103 year = 2009 95 104 } 96 105 … … 98 107 key = {CPLEX}, 99 108 title = {{ILOG} {CPLEX}}, 100 url = {http://www.ilog.com/} 109 howpublished = {\url{http://www.ilog.com/}}, 110 year = 2009 101 111 } 102 112 … … 105 115 title = {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented 106 116 {S}implex}, 107 url = {http://soplex.zib.de/} 117 howpublished = {\url{http://soplex.zib.de/}}, 118 year = 2009 108 119 } 109 120 … … 151 162 %%%%% Maximum flow algorithms %%%%% 152 163 153 @article{edmondskarp72theoretical, 154 author = {Jack Edmonds and Richard M. Karp}, 155 title = {Theoretical improvements in algorithmic efficiency 156 for network flow problems}, 157 journal = {Journal of the ACM}, 158 year = 1972, 159 volume = 19, 160 number = 2, 161 pages = {248-264} 162 } 163 164 @article{goldberg88newapproach, 164 @inproceedings{goldberg86newapproach, 165 165 author = {Andrew V. Goldberg and Robert E. Tarjan}, 166 166 title = {A new approach to the maximum flow problem}, 167 journal = {Journal of the ACM}, 168 year = 1988, 169 volume = 35, 170 number = 4, 171 pages = {921-940} 167 booktitle = {STOC '86: Proceedings of the Eighteenth Annual ACM 168 Symposium on Theory of Computing}, 169 year = 1986, 170 publisher = {ACM Press}, 171 address = {New York, NY}, 172 pages = {136-146} 172 173 } 173 174 … … 240 241 } 241 242 242 @ article{goldberg89cyclecanceling,243 @inproceedings{goldberg88cyclecanceling, 243 244 author = {Andrew V. Goldberg and Robert E. Tarjan}, 244 245 title = {Finding minimum-cost circulations by canceling 245 246 negative cycles}, 247 booktitle = {STOC '88: Proceedings of the Twentieth Annual ACM 248 Symposium on Theory of Computing}, 249 year = 1988, 250 publisher = {ACM Press}, 251 address = {New York, NY}, 252 pages = {388-397} 253 } 254 255 @article{edmondskarp72theoretical, 256 author = {Jack Edmonds and Richard M. Karp}, 257 title = {Theoretical improvements in algorithmic efficiency 258 for network flow problems}, 246 259 journal = {Journal of the ACM}, 247 year = 1989, 248 volume = 36, 249 number = 4, 250 pages = {873-886} 251 } 252 253 @article{goldberg90approximation, 260 year = 1972, 261 volume = 19, 262 number = 2, 263 pages = {248-264} 264 } 265 266 @inproceedings{goldberg87approximation, 267 author = {Andrew V. Goldberg and Robert E. Tarjan}, 268 title = {Solving minimum-cost flow problems by successive 269 approximation}, 270 booktitle = {STOC '87: Proceedings of the Nineteenth Annual ACM 271 Symposium on Theory of Computing}, 272 year = 1987, 273 publisher = {ACM Press}, 274 address = {New York, NY}, 275 pages = {7-18} 276 } 277 278 @article{goldberg90finding, 254 279 author = {Andrew V. Goldberg and Robert E. Tarjan}, 255 280 title = {Finding Minimum-Cost Circulations by Successive … … 284 309 } 285 310 286 @book{dantzig63linearprog,287 author = {George B. Dantzig},288 title = {Linear Programming and Extensions},289 publisher = {Princeton University Press},290 year = 1963291 }292 293 311 @mastersthesis{kellyoneill91netsimplex, 294 312 author = {Damian J. Kelly and Garrett M. O'Neill}, … … 300 318 month = sep, 301 319 } 320 321 @techreport{lobel96networksimplex, 322 author = {Andreas L{\"o}bel}, 323 title = {Solving large-scale real-world minimum-cost flow 324 problems by a network simplex method}, 325 institution = {Konrad-Zuse-Zentrum fur Informationstechnik Berlin 326 ({ZIB})}, 327 address = {Berlin, Germany}, 328 year = 1996, 329 number = {SC 96-7} 330 } 331 332 @article{frangioni06computational, 333 author = {Antonio Frangioni and Antonio Manca}, 334 title = {A Computational Study of Cost Reoptimization for 335 Min-Cost Flow Problems}, 336 journal = {INFORMS Journal On Computing}, 337 year = 2006, 338 volume = 18, 339 number = 1, 340 pages = {61-70} 341 } -
lemon/network_simplex.h
r755 r730 41 41 /// 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 /// \ref kellyoneill91netsimplex. 43 /// for finding a \ref min_cost_flow "minimum cost flow". 46 44 /// This algorithm is a specialized version of the linear programming 47 45 /// simplex method directly for the minimum cost flow problem. -
lemon/preflow.h
r755 r715 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 \ref clrs01algorithms, 106 /// \ref amo93networkflows, \ref goldberg88newapproach. 105 /// "flow of maximum value" in a digraph. 107 106 /// The preflow algorithms are the fastest known maximum 108 107 /// flow algorithms. The current implementation uses a mixture of the -
scripts/bib2dox.py
r754 r745 71 71 author_rex = re.compile('\s+and\s+') 72 72 rembraces_rex = re.compile('[{}]') 73 capitalize_rex = re.compile('({ [^}]*})')73 capitalize_rex = re.compile('({\w*})') 74 74 75 75 # used by bibtexkeywords(data) … … 364 364 if entrycont.has_key('note') and (entrycont['note'] != ''): 365 365 entry.append(entrycont['note'] + '.') 366 if entrycont.has_key('url') and (entrycont['url'] != ''):367 entry.append(entrycont['url'] + '.')368 366 369 367 # generate keys for sorting and for the output … … 413 411 field = string.lower(field) 414 412 data = data_rex.sub('\g<2>', line) 415 416 if field == 'url':417 data = '\\url{' + data.strip() + '}'418 413 419 414 if field in ('author', 'editor'):
Note: See TracChangeset
for help on using the changeset viewer.