# Changeset 817:432c54cec63c in lemon

Ignore:
Timestamp:
11/05/09 08:39:49 (13 years ago)
Branch:
default
Parents:
816:e746fb14e680 (diff), 804: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

Unmodified
Removed
• ## doc/groups.dox

 r802 /** @defgroup min_mean_cycle Minimum Mean Cycle Algorithms @ingroup algs \brief Algorithms for finding minimum mean cycles. This group contains the algorithms for finding minimum mean cycles. The \e minimum \e mean \e cycle \e problem is to find a directed cycle of minimum mean length (cost) in a digraph. The mean length of a cycle is the average length of its arcs, i.e. the ratio between the total length of the cycle and the number of arcs on it. This problem has an important connection to \e conservative \e length \e functions, too. A length function on the arcs of a digraph is called conservative if and only if there is no directed cycle of negative total length. For an arbitrary length function, the negative of the minimum cycle mean is the smallest \f$\epsilon\f$ value so that increasing the arc lengths uniformly by \f$\epsilon\f$ results in a conservative length function. LEMON contains three algorithms for solving the minimum mean cycle problem: - \ref Karp "Karp"'s original algorithm. - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved version of Karp's algorithm. - \ref Howard "Howard"'s policy iteration algorithm. In practice, the Howard algorithm proved to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. Both Karp and HartmannOrlin algorithms run in time O(ne) and use space O(n2+e), but the latter one is typically faster due to the applied early termination scheme. */ /** @defgroup matching Matching Algorithms @ingroup algs

• ## lemon/Makefile.am

 r755 lemon/graph_to_eps.h \ lemon/grid_graph.h \ lemon/hartmann_orlin.h \ lemon/howard.h \ lemon/hypercube_graph.h \ lemon/karp.h \ lemon/kary_heap.h \ lemon/kruskal.h \
• ## lemon/Makefile.am

 r813 lemon/arg_parser.h \ lemon/assert.h \ lemon/bellman_ford.h \ lemon/bfs.h \ lemon/bin_heap.h \ lemon/binom_heap.h \ lemon/bucket_heap.h \ lemon/cbc.h \ lemon/euler.h \ lemon/fib_heap.h \ lemon/fourary_heap.h \ lemon/full_graph.h \ lemon/glpk.h \ lemon/hypercube_graph.h \ lemon/karp.h \ lemon/kary_heap.h \ lemon/kruskal.h \ lemon/hao_orlin.h \ lemon/lp_base.h \ lemon/lp_skeleton.h \ lemon/list_graph.h \ lemon/maps.h \ lemon/matching.h \ lemon/nauty_reader.h \ lemon/network_simplex.h \ lemon/pairing_heap.h \ lemon/path.h \ lemon/preflow.h \
• ## test/CMakeLists.txt

 r745 min_cost_arborescence_test min_cost_flow_test min_mean_cycle_test path_test preflow_test
• ## test/CMakeLists.txt

 r810 SET(TESTS adaptors_test bellman_ford_test bfs_test circulation_test
• ## test/Makefile.am

 r745 test/min_cost_arborescence_test \ test/min_cost_flow_test \ test/min_mean_cycle_test \ test/path_test \ test/preflow_test \ test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc test_path_test_SOURCES = test/path_test.cc test_preflow_test_SOURCES = test/preflow_test.cc
• ## test/Makefile.am

 r810 check_PROGRAMS += \ test/adaptors_test \ test/bellman_ford_test \ test/bfs_test \ test/circulation_test \ test_adaptors_test_SOURCES = test/adaptors_test.cc test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc test_bfs_test_SOURCES = test/bfs_test.cc test_circulation_test_SOURCES = test/circulation_test.cc
Note: See TracChangeset for help on using the changeset viewer.