COIN-OR::LEMON - Graph Library

Changeset 874:d8ea85825e02 in lemon-1.2


Ignore:
Timestamp:
03/16/10 21:27:35 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
873:23da1b807280 (diff), 872:41d7ac528c3a (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 #314

Files:
8 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r869 r874  
    281281
    282282/**
     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/**
    283305@defgroup algs Algorithms
    284306\brief This group contains the several algorithms
     
    295317
    296318This group contains the common graph search algorithms, namely
    297 \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.
    298321*/
    299322
     
    303326\brief Algorithms for finding shortest paths.
    304327
    305 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.
    306330
    307331 - \ref Dijkstra algorithm for finding shortest paths from a source node
     
    320344
    321345/**
     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/**
    322355@defgroup max_flow Maximum Flow Algorithms
    323356@ingroup algs
     
    325358
    326359This group contains the algorithms for finding maximum flows and
    327 feasible circulations.
     360feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
    328361
    329362The \e maximum \e flow \e problem is to find a flow of maximum value between
     
    340373
    341374LEMON contains several algorithms for solving maximum flow problems:
    342 - \ref EdmondsKarp Edmonds-Karp algorithm.
    343 - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
    344 - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
    345 - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
    346 
    347 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
    348385fastest method for computing a maximum flow. All implementations
    349386also provide functions to query the minimum cut, which is the dual
     
    363400
    364401This group contains the algorithms for finding minimum cost flows and
    365 circulations. For more information about this problem and its dual
    366 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".
    367405
    368406LEMON contains several algorithms for this problem.
    369407 - \ref NetworkSimplex Primal Network Simplex algorithm with various
    370    pivot strategies.
    371  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
    372    cost scaling.
    373  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
    374    capacity scaling.
    375  - \ref CancelAndTighten The Cancel and Tighten algorithm.
    376  - \ref CycleCanceling Cycle-Canceling algorithms.
     408   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
     409 - \ref CostScaling Cost Scaling algorithm based on push/augment and
     410   relabel operations \ref goldberg90approximation, \ref goldberg97efficient,
     411   \ref bunnagel98efficient.
     412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive
     413   shortest path method \ref edmondskarp72theoretical.
     414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
     415   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    377416
    378417In general NetworkSimplex is the most efficient implementation,
     
    397436
    398437\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
    399     \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
     438    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
    400439
    401440LEMON contains several algorithms related to minimum cut problems:
     
    413452
    414453/**
    415 @defgroup graph_properties Connectivity and Other Graph Properties
    416 @ingroup algs
    417 \brief Algorithms for discovering the graph properties
    418 
    419 This group contains the algorithms for discovering the graph properties
    420 like connectivity, bipartiteness, euler property, simplicity etc.
    421 
    422 \image html edge_biconnected_components.png
    423 \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
    424 */
    425 
    426 /**
    427 @defgroup planar Planarity Embedding and Drawing
    428 @ingroup algs
    429 \brief Algorithms for planarity checking, embedding and drawing
    430 
    431 This group contains the algorithms for planarity checking,
    432 embedding and drawing.
    433 
    434 \image html planar.png
    435 \image latex planar.eps "Plane graph" width=\textwidth
     454@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     455@ingroup algs
     456\brief Algorithms for finding minimum mean cycles.
     457
     458This group contains the algorithms for finding minimum mean cycles
     459\ref clrs01algorithms, \ref amo93networkflows.
     460
     461The \e minimum \e mean \e cycle \e problem is to find a directed cycle
     462of minimum mean length (cost) in a digraph.
     463The mean length of a cycle is the average length of its arcs, i.e. the
     464ratio between the total length of the cycle and the number of arcs on it.
     465
     466This problem has an important connection to \e conservative \e length
     467\e functions, too. A length function on the arcs of a digraph is called
     468conservative if and only if there is no directed cycle of negative total
     469length. For an arbitrary length function, the negative of the minimum
     470cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
     471arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
     472function.
     473
     474LEMON contains three algorithms for solving the minimum mean cycle problem:
     475- \ref Karp "Karp"'s original algorithm \ref amo93networkflows,
     476  \ref dasdan98minmeancycle.
     477- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
     478  version of Karp's algorithm \ref dasdan98minmeancycle.
     479- \ref Howard "Howard"'s policy iteration algorithm
     480  \ref dasdan98minmeancycle.
     481
     482In practice, the Howard algorithm proved to be by far the most efficient
     483one, though the best known theoretical bound on its running time is
     484exponential.
     485Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
     486O(n<sup>2</sup>+e), but the latter one is typically faster due to the
     487applied early termination scheme.
    436488*/
    437489
     
    479531  perfect fractional matching in general graphs.
    480532
    481 \image html bipartite_matching.png
    482 \image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
    483 */
    484 
    485 /**
    486 @defgroup spantree Minimum Spanning Tree Algorithms
    487 @ingroup algs
    488 \brief Algorithms for finding minimum cost spanning trees and arborescences.
    489 
    490 This group contains the algorithms for finding minimum cost spanning
    491 trees and arborescences.
     533\image html matching.png
     534\image latex matching.eps "Min Cost Perfect Matching" width=\textwidth
     535*/
     536
     537/**
     538@defgroup graph_properties Connectivity and Other Graph Properties
     539@ingroup algs
     540\brief Algorithms for discovering the graph properties
     541
     542This group contains the algorithms for discovering the graph properties
     543like connectivity, bipartiteness, euler property, simplicity etc.
     544
     545\image html connected_components.png
     546\image latex connected_components.eps "Connected components" width=\textwidth
     547*/
     548
     549/**
     550@defgroup planar Planarity Embedding and Drawing
     551@ingroup algs
     552\brief Algorithms for planarity checking, embedding and drawing
     553
     554This group contains the algorithms for planarity checking,
     555embedding and drawing.
     556
     557\image html planar.png
     558\image latex planar.eps "Plane graph" width=\textwidth
     559*/
     560
     561/**
     562@defgroup approx Approximation Algorithms
     563@ingroup algs
     564\brief Approximation algorithms.
     565
     566This group contains the approximation and heuristic algorithms
     567implemented in LEMON.
    492568*/
    493569
     
    499575This group contains some algorithms implemented in LEMON
    500576in order to make it easier to implement complex algorithms.
    501 */
    502 
    503 /**
    504 @defgroup approx Approximation Algorithms
    505 @ingroup algs
    506 \brief Approximation algorithms.
    507 
    508 This group contains the approximation and heuristic algorithms
    509 implemented in LEMON.
    510577*/
    511578
     
    520587
    521588/**
    522 @defgroup lp_group Lp and Mip Solvers
     589@defgroup lp_group LP and MIP Solvers
    523590@ingroup gen_opt_group
    524 \brief Lp and Mip solver interfaces for LEMON.
    525 
    526 This group contains Lp and Mip solver interfaces for LEMON. The
    527 various LP solvers could be used in the same manner with this
    528 interface.
     591\brief LP and MIP solver interfaces for LEMON.
     592
     593This group contains LP and MIP solver interfaces for LEMON.
     594Various LP solvers could be used in the same manner with this
     595high-level interface.
     596
     597The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
     598\ref cplex, \ref soplex.
    529599*/
    530600
     
    616686
    617687/**
    618 @defgroup dimacs_group DIMACS format
     688@defgroup dimacs_group DIMACS Format
    619689@ingroup io_group
    620690\brief Read and write files in DIMACS format
     
    665735\brief Skeleton and concept checking classes for graph structures
    666736
    667 This group contains the skeletons and concept checking classes of LEMON's
    668 graph structures and helper classes used to implement these.
     737This group contains the skeletons and concept checking classes of
     738graph structures.
    669739*/
    670740
     
    678748
    679749/**
     750@defgroup tools Standalone Utility Applications
     751
     752Some utility applications are listed here.
     753
     754The standard compilation procedure (<tt>./configure;make</tt>) will compile
     755them, as well.
     756*/
     757
     758/**
    680759\anchor demoprograms
    681760
     
    689768*/
    690769
    691 /**
    692 @defgroup tools Standalone Utility Applications
    693 
    694 Some utility applications are listed here.
    695 
    696 The standard compilation procedure (<tt>./configure;make</tt>) will compile
    697 them, as well.
    698 */
    699 
    700770}
  • doc/groups.dox

    r873 r874  
    387387problem of maximum flow.
    388388
    389 \ref Circulation is a preflow push-relabel algorithm implemented directly 
     389\ref Circulation is a preflow push-relabel algorithm implemented directly
    390390for finding feasible circulations, which is a somewhat different problem,
    391391but it is strongly related to maximum flow.
     
    523523  Edmond's blossom shrinking algorithm for calculating maximum weighted
    524524  perfect matching in general graphs.
     525- \ref MaxFractionalMatching Push-relabel algorithm for calculating
     526  maximum cardinality fractional matching in general graphs.
     527- \ref MaxWeightedFractionalMatching Augmenting path algorithm for calculating
     528  maximum weighted fractional matching in general graphs.
     529- \ref MaxWeightedPerfectFractionalMatching
     530  Augmenting path algorithm for calculating maximum weighted
     531  perfect fractional matching in general graphs.
    525532
    526533\image html matching.png
  • lemon/Makefile.am

    r869 r874  
    6161        lemon/bfs.h \
    6262        lemon/bin_heap.h \
    63         lemon/binom_heap.h \
     63        lemon/binomial_heap.h \
    6464        lemon/bucket_heap.h \
     65        lemon/capacity_scaling.h \
    6566        lemon/cbc.h \
    6667        lemon/circulation.h \
     
    6970        lemon/concept_check.h \
    7071        lemon/connectivity.h \
     72        lemon/core.h \
     73        lemon/cost_scaling.h \
    7174        lemon/counter.h \
    72         lemon/core.h \
    7375        lemon/cplex.h \
     76        lemon/cycle_canceling.h \
    7477        lemon/dfs.h \
     78        lemon/dheap.h \
    7579        lemon/dijkstra.h \
    7680        lemon/dim2.h \
     
    8185        lemon/euler.h \
    8286        lemon/fib_heap.h \
    83         lemon/fourary_heap.h \
    8487        lemon/fractional_matching.h \
    8588        lemon/full_graph.h \
     
    8891        lemon/graph_to_eps.h \
    8992        lemon/grid_graph.h \
     93        lemon/hartmann_orlin_mmc.h \
     94        lemon/howard_mmc.h \
    9095        lemon/hypercube_graph.h \
    91         lemon/kary_heap.h \
     96        lemon/karp_mmc.h \
    9297        lemon/kruskal.h \
    9398        lemon/hao_orlin.h \
     
    106111        lemon/pairing_heap.h \
    107112        lemon/path.h \
     113        lemon/planarity.h \
    108114        lemon/preflow.h \
     115        lemon/quad_heap.h \
    109116        lemon/radix_heap.h \
    110117        lemon/radix_sort.h \
     
    112119        lemon/smart_graph.h \
    113120        lemon/soplex.h \
     121        lemon/static_graph.h \
    114122        lemon/suurballe.h \
    115123        lemon/time_measure.h \
  • lemon/Makefile.am

    r864 r874  
    8585        lemon/euler.h \
    8686        lemon/fib_heap.h \
     87        lemon/fractional_matching.h \
    8788        lemon/full_graph.h \
    8889        lemon/glpk.h \
  • test/CMakeLists.txt

    r869 r874  
    3434  min_cost_arborescence_test
    3535  min_cost_flow_test
     36  min_mean_cycle_test
    3637  path_test
     38  planarity_test
    3739  preflow_test
    3840  radix_sort_test
  • test/CMakeLists.txt

    r799 r874  
    2222  error_test
    2323  euler_test
     24  fractional_matching_test
    2425  gomory_hu_test
    2526  graph_copy_test
  • test/Makefile.am

    r869 r874  
     1if USE_VALGRIND
     2TESTS_ENVIRONMENT=$(top_srcdir)/scripts/valgrind-wrapper.sh
     3endif
     4
    15EXTRA_DIST += \
    26        test/CMakeLists.txt
     
    3236        test/min_cost_arborescence_test \
    3337        test/min_cost_flow_test \
     38        test/min_mean_cycle_test \
    3439        test/path_test \
     40        test/planarity_test \
    3541        test/preflow_test \
    3642        test/radix_sort_test \
     
    8187test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8288test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
     89test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
    8390test_path_test_SOURCES = test/path_test.cc
     91test_planarity_test_SOURCES = test/planarity_test.cc
    8492test_preflow_test_SOURCES = test/preflow_test.cc
    8593test_radix_sort_test_SOURCES = test/radix_sort_test.cc
  • test/Makefile.am

    r799 r874  
    2424        test/error_test \
    2525        test/euler_test \
     26        test/fractional_matching_test \
    2627        test/gomory_hu_test \
    2728        test/graph_copy_test \
     
    7273test_error_test_SOURCES = test/error_test.cc
    7374test_euler_test_SOURCES = test/euler_test.cc
     75test_fractional_matching_test_SOURCES = test/fractional_matching_test.cc
    7476test_gomory_hu_test_SOURCES = test/gomory_hu_test.cc
    7577test_graph_copy_test_SOURCES = test/graph_copy_test.cc
Note: See TracChangeset for help on using the changeset viewer.