COIN-OR::LEMON - Graph Library

Changeset 770:432c54cec63c in lemon-main


Ignore:
Timestamp:
11/05/09 08:39:49 (15 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
769:e746fb14e680 (diff), 757:9fbbd802020f (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge #179 (Port the min mean cycle algorithms)

Files:
8 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r755 r770  
    454454
    455455/**
     456@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     457@ingroup algs
     458\brief Algorithms for finding minimum mean cycles.
     459
     460This group contains the algorithms for finding minimum mean cycles.
     461
     462The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     463of minimum mean length (cost) in a digraph.
     464The mean length of a cycle is the average length of its arcs, i.e. the
     465ratio between the total length of the cycle and the number of arcs on it.
     466
     467This problem has an important connection to \e conservative \e length
     468\e functions, too. A length function on the arcs of a digraph is called
     469conservative if and only if there is no directed cycle of negative total
     470length. For an arbitrary length function, the negative of the minimum
     471cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     472arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     473function.
     474
     475LEMON contains three algorithms for solving the minimum mean cycle problem:
     476- \ref Karp "Karp"'s original algorithm.
     477- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     478  version of Karp's algorithm.
     479- \ref Howard "Howard"'s policy iteration algorithm.
     480
     481In practice, the Howard algorithm proved to be by far the most efficient
     482one, though the best known theoretical bound on its running time is
     483exponential.
     484Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     485O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     486applied early termination scheme.
     487*/
     488
     489/**
    456490@defgroup matching Matching Algorithms
    457491@ingroup algs
  • doc/groups.dox

    r768 r770  
    227227
    228228/**
    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 /**
    237229@defgroup paths Path Structures
    238230@ingroup datas
     
    247239any kind of path structure.
    248240
    249 \sa lemon::concepts::Path
     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
     249This group contains the heap structures implemented in LEMON.
     250
     251LEMON provides several heap classes. They are efficient implementations
     252of the abstract data type \e priority \e queue. They store items with
     253specified values called \e priorities in such a way that finding and
     254removing the item with minimum priority are efficient.
     255The basic operations are adding and erasing items, changing the priority
     256of an item, etc.
     257
     258Heaps are crucial in several algorithms, such as Dijkstra and Prim.
     259The heap implementations have the same interface, thus any of them can be
     260used easily in such algorithms.
     261
     262\sa \ref concepts::Heap "Heap concept"
     263*/
     264
     265/**
     266@defgroup matrices Matrices
     267@ingroup datas
     268\brief Two dimensional data storages implemented in LEMON.
     269
     270This group contains two dimensional data storages implemented in LEMON.
    250271*/
    251272
     
    260281
    261282/**
     283@defgroup geomdat Geometric Data Structures
     284@ingroup auxdat
     285\brief Geometric data structures implemented in LEMON.
     286
     287This 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
     301This group contains two dimensional data storages implemented in LEMON.
     302*/
     303
     304/**
    262305@defgroup algs Algorithms
    263306\brief This group contains the several algorithms
     
    274317
    275318This group contains the common graph search algorithms, namely
    276 \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.
    277321*/
    278322
     
    282326\brief Algorithms for finding shortest paths.
    283327
    284 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.
    285330
    286331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    299344
    300345/**
     346@defgroup spantree Minimum Spanning Tree Algorithms
     347@ingroup algs
     348\brief Algorithms for finding minimum cost spanning trees and arborescences.
     349
     350This group contains the algorithms for finding minimum cost spanning
     351trees and arborescences \ref clrs01algorithms.
     352*/
     353
     354/**
    301355@defgroup max_flow Maximum Flow Algorithms
    302356@ingroup algs
     
    304358
    305359This group contains the algorithms for finding maximum flows and
    306 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    307361
    308362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    319373
    320374LEMON 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
     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
    327385fastest method for computing a maximum flow. All implementations
    328386also provide functions to query the minimum cut, which is the dual
     
    342400
    343401This group contains the algorithms for finding minimum cost flows and
    344 circulations. For more information about this problem and its dual
    345 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".
    346405
    347406LEMON contains several algorithms for this problem.
    348407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    349    pivot strategies.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
    350409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    351    cost scaling.
     410   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
    352412 - \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.
     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.
    356418
    357419In general NetworkSimplex is the most efficient implementation,
     
    376438
    377439\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    378     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     440    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    379441
    380442LEMON contains several algorithms related to minimum cut problems:
     
    423485O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    424486applied early termination scheme.
    425 */
    426 
    427 /**
    428 @defgroup graph_properties Connectivity and Other Graph Properties
    429 @ingroup algs
    430 \brief Algorithms for discovering the graph properties
    431 
    432 This group contains the algorithms for discovering the graph properties
    433 like connectivity, bipartiteness, euler property, simplicity etc.
    434 
    435 \image html edge_biconnected_components.png
    436 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    437 */
    438 
    439 /**
    440 @defgroup planar Planarity Embedding and Drawing
    441 @ingroup algs
    442 \brief Algorithms for planarity checking, embedding and drawing
    443 
    444 This group contains the algorithms for planarity checking,
    445 embedding and drawing.
    446 
    447 \image html planar.png
    448 \image latex planar.eps "Plane graph" width=\textwidth
    449487*/
    450488
     
    490528
    491529/**
    492 @defgroup spantree Minimum Spanning Tree Algorithms
    493 @ingroup algs
    494 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    495 
    496 This group contains the algorithms for finding minimum cost spanning
    497 trees and arborescences.
     530@defgroup graph_properties Connectivity and Other Graph Properties
     531@ingroup algs
     532\brief Algorithms for discovering the graph properties
     533
     534This group contains the algorithms for discovering the graph properties
     535like connectivity, bipartiteness, euler property, simplicity etc.
     536
     537\image html connected_components.png
     538\image latex connected_components.eps "Connected components" width=\textwidth
     539*/
     540
     541/**
     542@defgroup planar Planarity Embedding and Drawing
     543@ingroup algs
     544\brief Algorithms for planarity checking, embedding and drawing
     545
     546This group contains the algorithms for planarity checking,
     547embedding and drawing.
     548
     549\image html planar.png
     550\image latex planar.eps "Plane graph" width=\textwidth
     551*/
     552
     553/**
     554@defgroup approx Approximation Algorithms
     555@ingroup algs
     556\brief Approximation algorithms.
     557
     558This group contains the approximation and heuristic algorithms
     559implemented in LEMON.
    498560*/
    499561
     
    505567This group contains some algorithms implemented in LEMON
    506568in order to make it easier to implement complex algorithms.
    507 */
    508 
    509 /**
    510 @defgroup approx Approximation Algorithms
    511 @ingroup algs
    512 \brief Approximation algorithms.
    513 
    514 This group contains the approximation and heuristic algorithms
    515 implemented in LEMON.
    516569*/
    517570
     
    526579
    527580/**
    528 @defgroup lp_group Lp and Mip Solvers
     581@defgroup lp_group LP and MIP Solvers
    529582@ingroup gen_opt_group
    530 \brief Lp and Mip solver interfaces for LEMON.
    531 
    532 This group contains Lp and Mip solver interfaces for LEMON. The
    533 various LP solvers could be used in the same manner with this
    534 interface.
     583\brief LP and MIP solver interfaces for LEMON.
     584
     585This group contains LP and MIP solver interfaces for LEMON.
     586Various LP solvers could be used in the same manner with this
     587high-level interface.
     588
     589The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     590\ref cplex, \ref soplex.
    535591*/
    536592
     
    622678
    623679/**
    624 @defgroup dimacs_group DIMACS format
     680@defgroup dimacs_group DIMACS Format
    625681@ingroup io_group
    626682\brief Read and write files in DIMACS format
     
    671727\brief Skeleton and concept checking classes for graph structures
    672728
    673 This group contains the skeletons and concept checking classes of LEMON's
    674 graph structures and helper classes used to implement these.
     729This group contains the skeletons and concept checking classes of
     730graph structures.
    675731*/
    676732
     
    684740
    685741/**
     742@defgroup tools Standalone Utility Applications
     743
     744Some utility applications are listed here.
     745
     746The standard compilation procedure (<tt>./configure;make</tt>) will compile
     747them, as well.
     748*/
     749
     750/**
    686751\anchor demoprograms
    687752
     
    695760*/
    696761
    697 /**
    698 @defgroup tools Standalone Utility Applications
    699 
    700 Some utility applications are listed here.
    701 
    702 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    703 them, as well.
    704 */
    705 
    706762}
  • lemon/Makefile.am

    r708 r770  
    8787        lemon/graph_to_eps.h \
    8888        lemon/grid_graph.h \
     89        lemon/hartmann_orlin.h \
     90        lemon/howard.h \
    8991        lemon/hypercube_graph.h \
     92        lemon/karp.h \
    9093        lemon/kary_heap.h \
    9194        lemon/kruskal.h \
  • lemon/Makefile.am

    r766 r770  
    5858        lemon/arg_parser.h \
    5959        lemon/assert.h \
     60        lemon/bellman_ford.h \
    6061        lemon/bfs.h \
    6162        lemon/bin_heap.h \
     63        lemon/binom_heap.h \
    6264        lemon/bucket_heap.h \
    6365        lemon/cbc.h \
     
    7981        lemon/euler.h \
    8082        lemon/fib_heap.h \
     83        lemon/fourary_heap.h \
    8184        lemon/full_graph.h \
    8285        lemon/glpk.h \
     
    8891        lemon/hypercube_graph.h \
    8992        lemon/karp.h \
     93        lemon/kary_heap.h \
    9094        lemon/kruskal.h \
    9195        lemon/hao_orlin.h \
     
    96100        lemon/lp_base.h \
    97101        lemon/lp_skeleton.h \
    98         lemon/list_graph.h \
    99102        lemon/maps.h \
    100103        lemon/matching.h \
     
    103106        lemon/nauty_reader.h \
    104107        lemon/network_simplex.h \
     108        lemon/pairing_heap.h \
    105109        lemon/path.h \
    106110        lemon/preflow.h \
  • test/CMakeLists.txt

    r698 r770  
    3333  min_cost_arborescence_test
    3434  min_cost_flow_test
     35  min_mean_cycle_test
    3536  path_test
    3637  preflow_test
  • test/CMakeLists.txt

    r763 r770  
    1010SET(TESTS
    1111  adaptors_test
     12  bellman_ford_test
    1213  bfs_test
    1314  circulation_test
  • test/Makefile.am

    r698 r770  
    3131        test/min_cost_arborescence_test \
    3232        test/min_cost_flow_test \
     33        test/min_mean_cycle_test \
    3334        test/path_test \
    3435        test/preflow_test \
     
    7980test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8081test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
     82test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
    8183test_path_test_SOURCES = test/path_test.cc
    8284test_preflow_test_SOURCES = test/preflow_test.cc
  • test/Makefile.am

    r763 r770  
    88check_PROGRAMS += \
    99        test/adaptors_test \
     10        test/bellman_ford_test \
    1011        test/bfs_test \
    1112        test/circulation_test \
     
    5455
    5556test_adaptors_test_SOURCES = test/adaptors_test.cc
     57test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
    5658test_bfs_test_SOURCES = test/bfs_test.cc
    5759test_circulation_test_SOURCES = test/circulation_test.cc
Note: See TracChangeset for help on using the changeset viewer.