COIN-OR::LEMON - Graph Library

Changes in / [770:432c54cec63c:757:9fbbd802020f] in lemon-1.2


Ignore:
Files:
4 deleted
5 edited

Legend:

Unmodified
Added
Removed
  • doc/groups.dox

    r770 r755  
    454454
    455455/**
    456 @defgroup min_mean_cycle Minimum Mean Cycle Algorithms
    457 @ingroup algs
    458 \brief Algorithms for finding minimum mean cycles.
    459 
    460 This group contains the algorithms for finding minimum mean cycles.
    461 
    462 The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    463 of minimum mean length (cost) in a digraph.
    464 The mean length of a cycle is the average length of its arcs, i.e. the
    465 ratio between the total length of the cycle and the number of arcs on it.
    466 
    467 This 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
    469 conservative if and only if there is no directed cycle of negative total
    470 length. For an arbitrary length function, the negative of the minimum
    471 cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
    472 arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
    473 function.
    474 
    475 LEMON 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 
    481 In practice, the Howard algorithm proved to be by far the most efficient
    482 one, though the best known theoretical bound on its running time is
    483 exponential.
    484 Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    485 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    486 applied early termination scheme.
    487 */
    488 
    489 /**
    490456@defgroup matching Matching Algorithms
    491457@ingroup algs
  • lemon/Makefile.am

    r770 r708  
    8787        lemon/graph_to_eps.h \
    8888        lemon/grid_graph.h \
    89         lemon/hartmann_orlin.h \
    90         lemon/howard.h \
    9189        lemon/hypercube_graph.h \
    92         lemon/karp.h \
    9390        lemon/kary_heap.h \
    9491        lemon/kruskal.h \
  • test/CMakeLists.txt

    r770 r698  
    3333  min_cost_arborescence_test
    3434  min_cost_flow_test
    35   min_mean_cycle_test
    3635  path_test
    3736  preflow_test
  • test/Makefile.am

    r770 r698  
    3131        test/min_cost_arborescence_test \
    3232        test/min_cost_flow_test \
    33         test/min_mean_cycle_test \
    3433        test/path_test \
    3534        test/preflow_test \
     
    8079test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
    8180test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
    82 test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
    8381test_path_test_SOURCES = test/path_test.cc
    8482test_preflow_test_SOURCES = test/preflow_test.cc
  • test/test_tools.h

    r763 r440  
    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   {                                                                     \
    42     if(!(rc)) {                                                         \
    43       std::cerr << __FILE__ ":" << __LINE__ << ": error: "              \
    44                 << msg << std::endl;                                    \
    45       abort();                                                          \
    46     } else { }                                                          \
    47   }                                                                     \
    48    
     40#define check(rc, msg) \
     41  if(!(rc)) { \
     42    std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
     43    abort(); \
     44  } else { } \
    4945
    5046#endif
Note: See TracChangeset for help on using the changeset viewer.