COIN-OR::LEMON - Graph Library

Changes in / [753:48fe2a46bf91:757:9fbbd802020f] in lemon-main


Ignore:
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • doc/Doxyfile.in

    r744 r756  
    1 # Doxyfile 1.5.7.1
     1# Doxyfile 1.5.9
    22
    33#---------------------------------------------------------------------------
     
    2222QT_AUTOBRIEF           = NO
    2323MULTILINE_CPP_IS_BRIEF = NO
    24 DETAILS_AT_TOP         = YES
    2524INHERIT_DOCS           = NO
    2625SEPARATE_MEMBER_PAGES  = NO
     
    225224SKIP_FUNCTION_MACROS   = YES
    226225#---------------------------------------------------------------------------
    227 # Configuration::additions related to external references   
     226# Options related to the search engine   
    228227#---------------------------------------------------------------------------
    229228TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
  • doc/groups.dox

    r742 r755  
    317317
    318318This group contains the common graph search algorithms, namely
    319 \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\ref clrs01algorithms.
    320321*/
    321322
     
    325326\brief Algorithms for finding shortest paths.
    326327
    327 This group contains the algorithms for finding shortest paths in digraphs.
     328This group contains the algorithms for finding shortest paths in digraphs
     329\ref clrs01algorithms.
    328330
    329331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    347349
    348350This group contains the algorithms for finding minimum cost spanning
    349 trees and arborescences.
     351trees and arborescences \ref clrs01algorithms.
    350352*/
    351353
     
    356358
    357359This group contains the algorithms for finding maximum flows and
    358 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    359361
    360362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    371373
    372374LEMON contains several algorithms for solving maximum flow problems:
    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
     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
     384In most cases the \ref Preflow algorithm provides the
    379385fastest method for computing a maximum flow. All implementations
    380386also provide functions to query the minimum cut, which is the dual
     
    394400
    395401This group contains the algorithms for finding minimum cost flows and
    396 circulations. For more information about this problem and its dual
    397 solution see \ref min_cost_flow "Minimum Cost Flow Problem".
     402circulations \ref amo93networkflows. For more information about this
     403problem and its dual solution, see \ref min_cost_flow
     404"Minimum Cost Flow Problem".
    398405
    399406LEMON contains several algorithms for this problem.
    400407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    401    pivot strategies.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    402409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    403    cost scaling.
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
    404412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    405    capacity scaling.
    406  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    407  - \ref CycleCanceling Cycle-Canceling algorithms.
     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.
    408418
    409419In general NetworkSimplex is the most efficient implementation,
     
    535545
    536546/**
    537 @defgroup lp_group Lp and Mip Solvers
     547@defgroup lp_group LP and MIP Solvers
    538548@ingroup gen_opt_group
    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.
     549\brief LP and MIP solver interfaces for LEMON.
     550
     551This group contains LP and MIP solver interfaces for LEMON.
     552Various LP solvers could be used in the same manner with this
     553high-level interface.
     554
     555The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     556\ref cplex, \ref soplex.
    544557*/
    545558
  • doc/mainpage.dox

    r658 r755  
    2222\section intro Introduction
    2323
    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.
     24<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling
     25and <b>O</b>ptimization in <b>N</b>etworks</i>.
     26It is a C++ template library providing efficient implementation of common
     27data structures and algorithms with focus on combinatorial optimization
     28problems in graphs and networks.
    3229
    3330<b>
     
    3936</b>
    4037
    41 \subsection howtoread How to read the documentation
     38The project is maintained by the
     39<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on
     40Combinatorial Optimization</a> \ref egres
     41at the Operations Research Department of the
     42<a href="http://www.elte.hu/">E&ouml;tv&ouml;s Lor&aacute;nd University,
     43Budapest</a>, Hungary.
     44LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>
     45initiative \ref coinor.
     46
     47\section howtoread How to Read the Documentation
    4248
    4349If you would like to get to know the library, see
  • doc/min_cost_flow.dox

    r663 r755  
    2727minimum total cost from a set of supply nodes to a set of demand nodes
    2828in a network with capacity constraints (lower and upper bounds)
    29 and arc costs.
     29and arc costs \ref amo93networkflows.
    3030
    3131Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$,
  • doc/references.bib

    r743 r755  
    1313  title =        {{EGRES} -- {E}gerv{\'a}ry {R}esearch {G}roup on
    1414                  {C}ombinatorial {O}ptimization},
    15   howpublished = {\url{http://www.cs.elte.hu/egres/}},
    16   year =         2009
     15  url =          {http://www.cs.elte.hu/egres/}
    1716}
    1817
     
    2120  title =        {{COIN-OR} -- {C}omputational {I}nfrastructure for
    2221                  {O}perations {R}esearch},
    23   howpublished = {\url{http://www.coin-or.org/}},
    24   year =         2009
     22  url =          {http://www.coin-or.org/}
    2523}
    2624
     
    3129  key =          {Boost},
    3230  title =        {{B}oost {C++} {L}ibraries},
    33   howpublished = {\url{http://www.boost.org/}},
    34   year =         2009
     31  url =          {http://www.boost.org/}
    3532}
    3633
     
    4845  title =        {{LEDA} -- {L}ibrary of {E}fficient {D}ata {T}ypes and
    4946                  {A}lgorithms},
    50   howpublished = {\url{http://www.algorithmic-solutions.com/}},
    51   year =         2009
     47  url =          {http://www.algorithmic-solutions.com/}
    5248}
    5349
     
    6864  key =          {CMake},
    6965  title =        {{CMake} -- {C}ross {P}latform {M}ake},
    70   howpublished = {\url{http://www.cmake.org/}},
    71   year =         2009
     66  url =          {http://www.cmake.org/}
    7267}
    7368
     
    7671  title =        {{Doxygen} -- {S}ource code documentation generator
    7772                  tool},
    78   howpublished = {\url{http://www.doxygen.org/}},
    79   year =         2009
     73  url =          {http://www.doxygen.org/}
    8074}
    8175
     
    8680  key =          {GLPK},
    8781  title =        {{GLPK} -- {GNU} {L}inear {P}rogramming {K}it},
    88   howpublished = {\url{http://www.gnu.org/software/glpk/}},
    89   year =         2009
     82  url =          {http://www.gnu.org/software/glpk/}
    9083}
    9184
     
    9386  key =          {Clp},
    9487  title =        {{Clp} -- {Coin-Or} {L}inear {P}rogramming},
    95   howpublished = {\url{http://projects.coin-or.org/Clp/}},
    96   year =         2009
     88  url =          {http://projects.coin-or.org/Clp/}
    9789}
    9890
     
    10092  key =          {Cbc},
    10193  title =        {{Cbc} -- {Coin-Or} {B}ranch and {C}ut},
    102   howpublished = {\url{http://projects.coin-or.org/Cbc/}},
    103   year =         2009
     94  url =          {http://projects.coin-or.org/Cbc/}
    10495}
    10596
     
    10798  key =          {CPLEX},
    10899  title =        {{ILOG} {CPLEX}},
    109   howpublished = {\url{http://www.ilog.com/}},
    110   year =         2009
     100  url =          {http://www.ilog.com/}
    111101}
    112102
     
    115105  title =        {{SoPlex} -- {T}he {S}equential {O}bject-{O}riented
    116106                  {S}implex},
    117   howpublished = {\url{http://soplex.zib.de/}},
    118   year =         2009
     107  url =          {http://soplex.zib.de/}
    119108}
    120109
     
    162151%%%%% Maximum flow algorithms %%%%%
    163152
    164 @inproceedings{goldberg86newapproach,
     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,
    165165  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    166166  title =        {A new approach to the maximum flow problem},
    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}
     167  journal =      {Journal of the ACM},
     168  year =         1988,
     169  volume =       35,
     170  number =       4,
     171  pages =        {921-940}
    173172}
    174173
     
    241240}
    242241
    243 @inproceedings{goldberg88cyclecanceling,
     242@article{goldberg89cyclecanceling,
    244243  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    245244  title =        {Finding minimum-cost circulations by canceling
    246245                  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},
    259246  journal =      {Journal of the ACM},
    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,
     247  year =         1989,
     248  volume =       36,
     249  number =       4,
     250  pages =        {873-886}
     251}
     252
     253@article{goldberg90approximation,
    279254  author =       {Andrew V. Goldberg and Robert E. Tarjan},
    280255  title =        {Finding Minimum-Cost Circulations by Successive
     
    309284}
    310285
     286@book{dantzig63linearprog,
     287  author =       {George B. Dantzig},
     288  title =        {Linear Programming and Extensions},
     289  publisher =    {Princeton University Press},
     290  year =         1963
     291}
     292
    311293@mastersthesis{kellyoneill91netsimplex,
    312294  author =       {Damian J. Kelly and Garrett M. O'Neill},
     
    318300  month =        sep,
    319301}
    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

    r730 r755  
    4141  ///
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    43   /// for finding a \ref min_cost_flow "minimum cost flow".
     43  /// for finding a \ref min_cost_flow "minimum cost flow"
     44  /// \ref amo93networkflows, \ref dantzig63linearprog,
     45  /// \ref kellyoneill91netsimplex.
    4446  /// This algorithm is a specialized version of the linear programming
    4547  /// simplex method directly for the minimum cost flow problem.
  • lemon/preflow.h

    r715 r755  
    103103  /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    104104  /// \e push-relabel algorithm producing a \ref max_flow
    105   /// "flow of maximum value" in a digraph.
     105  /// "flow of maximum value" in a digraph \ref clrs01algorithms,
     106  /// \ref amo93networkflows, \ref goldberg88newapproach.
    106107  /// The preflow algorithms are the fastest known maximum
    107108  /// flow algorithms. The current implementation uses a mixture of the
  • scripts/bib2dox.py

    r745 r754  
    7171author_rex = re.compile('\s+and\s+')
    7272rembraces_rex = re.compile('[{}]')
    73 capitalize_rex = re.compile('({\w*})')
     73capitalize_rex = re.compile('({[^}]*})')
    7474
    7575# used by bibtexkeywords(data)
     
    364364            if entrycont.has_key('note') and (entrycont['note'] != ''):
    365365                entry.append(entrycont['note'] + '.')
     366            if entrycont.has_key('url') and (entrycont['url'] != ''):
     367                entry.append(entrycont['url'] + '.')
    366368
    367369            # generate keys for sorting and for the output
     
    411413                field = string.lower(field)
    412414                data =  data_rex.sub('\g<2>', line)
     415
     416            if field == 'url':
     417                data = '\\url{' + data.strip() + '}'
    413418           
    414419            if field in ('author', 'editor'):
Note: See TracChangeset for help on using the changeset viewer.