COIN-OR::LEMON - Graph Library

Ignore:
Files:
4 added
5 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r802 r817  
    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
  • lemon/Makefile.am

    r755 r817  
    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 \
  • test/CMakeLists.txt

    r745 r817  
    3333  min_cost_arborescence_test
    3434  min_cost_flow_test
     35  min_mean_cycle_test
    3536  path_test
    3637  preflow_test
  • test/Makefile.am

    r745 r817  
    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/test_tools.h

    r463 r810  
    3838///print something like this (and then exits).
    3939///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
    40 #define check(rc, msg) \
    41   if(!(rc)) { \
    42     std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
    43     abort(); \
    44   } else { } \
     40#define check(rc, msg)                                                  \
     41  {                                                                     \
     42    if(!(rc)) {                                                         \
     43      std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \
     44                << msg << std::endl;                                    \
     45      abort();                                                          \
     46    } else { }                                                          \
     47  }                                                                     \
     48   
    4549
    4650#endif
Note: See TracChangeset for help on using the changeset viewer.