Changeset 770:432c54cec63c in lemon-main

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:

• doc/groups.dox (modified) (1 diff)
• doc/groups.dox (modified) (18 diffs)
• lemon/Makefile.am (modified) (1 diff)
• lemon/Makefile.am (modified) (5 diffs)
• test/CMakeLists.txt (modified) (1 diff)
• test/CMakeLists.txt (modified) (1 diff)
• test/Makefile.am (modified) (2 diffs)
• test/Makefile.am (modified) (2 diffs)

doc/groups.dox

@@ -454 +454 @@
 
 /**
+@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(n<sup>2</sup>+e), but the latter one is typically faster due to the
+applied early termination scheme.
+*/
+
+/**
 @defgroup matching Matching Algorithms
 @ingroup algs

doc/groups.dox

@@ -227 +227 @@
 
 /**
-@defgroup matrices Matrices
-@ingroup datas
-\brief Two dimensional data storages implemented in LEMON.
-
-This group contains two dimensional data storages implemented in LEMON.
-*/
-
-/**
 @defgroup paths Path Structures
 @ingroup datas
@@ -247 +239 @@
 any kind of path structure.
 
-\sa lemon::concepts::Path
+\sa \ref concepts::Path "Path concept"
+*/
+
+/**
+@defgroup heaps Heap Structures
+@ingroup datas
+\brief %Heap structures implemented in LEMON.
+
+This group contains the heap structures implemented in LEMON.
+
+LEMON provides several heap classes. They are efficient implementations
+of the abstract data type \e priority \e queue. They store items with
+specified values called \e priorities in such a way that finding and
+removing the item with minimum priority are efficient.
+The basic operations are adding and erasing items, changing the priority
+of an item, etc.
+
+Heaps are crucial in several algorithms, such as Dijkstra and Prim.
+The heap implementations have the same interface, thus any of them can be
+used easily in such algorithms.
+
+\sa \ref concepts::Heap "Heap concept"
+*/
+
+/**
+@defgroup matrices Matrices
+@ingroup datas
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
 */
 
@@ -260 +281 @@
 
 /**
+@defgroup geomdat Geometric Data Structures
+@ingroup auxdat
+\brief Geometric data structures implemented in LEMON.
+
+This group contains geometric data structures implemented in LEMON.
+
+ - \ref lemon::dim2::Point "dim2::Point" implements a two dimensional
+   vector with the usual operations.
+ - \ref lemon::dim2::Box "dim2::Box" can be used to determine the
+   rectangular bounding box of a set of \ref lemon::dim2::Point
+   "dim2::Point"'s.
+*/
+
+/**
+@defgroup matrices Matrices
+@ingroup auxdat
+\brief Two dimensional data storages implemented in LEMON.
+
+This group contains two dimensional data storages implemented in LEMON.
+*/
+
+/**
 @defgroup algs Algorithms
 \brief This group contains the several algorithms
@@ -274 +317 @@
 
 This group contains the common graph search algorithms, namely
-\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
+\e breadth-first \e search (BFS) and \e depth-first \e search (DFS)
+\ref clrs01algorithms.
 */
 
@@ -282 +326 @@
 \brief Algorithms for finding shortest paths.
 
-This group contains the algorithms for finding shortest paths in digraphs.
+This group contains the algorithms for finding shortest paths in digraphs
+\ref clrs01algorithms.
 
  - \ref Dijkstra algorithm for finding shortest paths from a source node
@@ -299 +344 @@
 
 /**
+@defgroup spantree Minimum Spanning Tree Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum cost spanning trees and arborescences.
+
+This group contains the algorithms for finding minimum cost spanning
+trees and arborescences \ref clrs01algorithms.
+*/
+
+/**
 @defgroup max_flow Maximum Flow Algorithms
 @ingroup algs
@@ -304 +358 @@
 
 This group contains the algorithms for finding maximum flows and
-feasible circulations.
+feasible circulations \ref clrs01algorithms, \ref amo93networkflows.
 
 The \e maximum \e flow \e problem is to find a flow of maximum value between
@@ -319 +373 @@
 
 LEMON contains several algorithms for solving maximum flow problems:
-- \ref EdmondsKarp Edmonds-Karp algorithm.
-- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
-- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
-- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
-
-In most cases the \ref Preflow "Preflow" algorithm provides the
+- \ref EdmondsKarp Edmonds-Karp algorithm
+  \ref edmondskarp72theoretical.
+- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm
+  \ref goldberg88newapproach.
+- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees
+  \ref dinic70algorithm, \ref sleator83dynamic.
+- \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees
+  \ref goldberg88newapproach, \ref sleator83dynamic.
+
+In most cases the \ref Preflow algorithm provides the
 fastest method for computing a maximum flow. All implementations
 also provide functions to query the minimum cut, which is the dual
@@ -342 +400 @@
 
 This group contains the algorithms for finding minimum cost flows and
-circulations. For more information about this problem and its dual
-solution see \ref min_cost_flow "Minimum Cost Flow Problem".
+circulations \ref amo93networkflows. For more information about this
+problem and its dual solution, see \ref min_cost_flow
+"Minimum Cost Flow Problem".
 
 LEMON contains several algorithms for this problem.
  - \ref NetworkSimplex Primal Network Simplex algorithm with various
-   pivot strategies.
+   pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex.
  - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on
-   cost scaling.
+   cost scaling \ref goldberg90approximation, \ref goldberg97efficient,
+   \ref bunnagel98efficient.
  - \ref CapacityScaling Successive Shortest %Path algorithm with optional
-   capacity scaling.
- - \ref CancelAndTighten The Cancel and Tighten algorithm.
- - \ref CycleCanceling Cycle-Canceling algorithms.
+   capacity scaling \ref edmondskarp72theoretical.
+ - \ref CancelAndTighten The Cancel and Tighten algorithm
+   \ref goldberg89cyclecanceling.
+ - \ref CycleCanceling Cycle-Canceling algorithms
+   \ref klein67primal, \ref goldberg89cyclecanceling.
 
 In general NetworkSimplex is the most efficient implementation,
@@ -376 +438 @@
 
 \f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
-    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
+    \sum_{uv\in A: u\in X, v\not\in X}cap(uv) \f]
 
 LEMON contains several algorithms related to minimum cut problems:
@@ -423 +485 @@
 O(n<sup>2</sup>+e), but the latter one is typically faster due to the
 applied early termination scheme.
-*/
-
-/**
-@defgroup graph_properties Connectivity and Other Graph Properties
-@ingroup algs
-\brief Algorithms for discovering the graph properties
-
-This group contains the algorithms for discovering the graph properties
-like connectivity, bipartiteness, euler property, simplicity etc.
-
-\image html edge_biconnected_components.png
-\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
-*/
-
-/**
-@defgroup planar Planarity Embedding and Drawing
-@ingroup algs
-\brief Algorithms for planarity checking, embedding and drawing
-
-This group contains the algorithms for planarity checking,
-embedding and drawing.
-
-\image html planar.png
-\image latex planar.eps "Plane graph" width=\textwidth
 */
 
@@ -490 +528 @@
 
 /**
-@defgroup spantree Minimum Spanning Tree Algorithms
-@ingroup algs
-\brief Algorithms for finding minimum cost spanning trees and arborescences.
-
-This group contains the algorithms for finding minimum cost spanning
-trees and arborescences.
+@defgroup graph_properties Connectivity and Other Graph Properties
+@ingroup algs
+\brief Algorithms for discovering the graph properties
+
+This group contains the algorithms for discovering the graph properties
+like connectivity, bipartiteness, euler property, simplicity etc.
+
+\image html connected_components.png
+\image latex connected_components.eps "Connected components" width=\textwidth
+*/
+
+/**
+@defgroup planar Planarity Embedding and Drawing
+@ingroup algs
+\brief Algorithms for planarity checking, embedding and drawing
+
+This group contains the algorithms for planarity checking,
+embedding and drawing.
+
+\image html planar.png
+\image latex planar.eps "Plane graph" width=\textwidth
+*/
+
+/**
+@defgroup approx Approximation Algorithms
+@ingroup algs
+\brief Approximation algorithms.
+
+This group contains the approximation and heuristic algorithms
+implemented in LEMON.
 */
 
@@ -505 +567 @@
 This group contains some algorithms implemented in LEMON
 in order to make it easier to implement complex algorithms.
-*/
-
-/**
-@defgroup approx Approximation Algorithms
-@ingroup algs
-\brief Approximation algorithms.
-
-This group contains the approximation and heuristic algorithms
-implemented in LEMON.
 */
 
@@ -526 +579 @@
 
 /**
-@defgroup lp_group Lp and Mip Solvers
+@defgroup lp_group LP and MIP Solvers
 @ingroup gen_opt_group
-\brief Lp and Mip solver interfaces for LEMON.
-
-This group contains Lp and Mip solver interfaces for LEMON. The
-various LP solvers could be used in the same manner with this
-interface.
+\brief LP and MIP solver interfaces for LEMON.
+
+This group contains LP and MIP solver interfaces for LEMON.
+Various LP solvers could be used in the same manner with this
+high-level interface.
+
+The currently supported solvers are \ref glpk, \ref clp, \ref cbc,
+\ref cplex, \ref soplex.
 */
 
@@ -622 +678 @@
 
 /**
-@defgroup dimacs_group DIMACS format
+@defgroup dimacs_group DIMACS Format
 @ingroup io_group
 \brief Read and write files in DIMACS format
@@ -671 +727 @@
 \brief Skeleton and concept checking classes for graph structures
 
-This group contains the skeletons and concept checking classes of LEMON's
-graph structures and helper classes used to implement these.
+This group contains the skeletons and concept checking classes of
+graph structures.
 */
 
@@ -684 +740 @@
 
 /**
+@defgroup tools Standalone Utility Applications
+
+Some utility applications are listed here.
+
+The standard compilation procedure (<tt>./configure;make</tt>) will compile
+them, as well.
+*/
+
+/**
 \anchor demoprograms
 
@@ -695 +760 @@
 */
 
-/**
-@defgroup tools Standalone Utility Applications
-
-Some utility applications are listed here.
-
-The standard compilation procedure (<tt>./configure;make</tt>) will compile
-them, as well.
-*/
-
 }

lemon/Makefile.am

@@ -87 +87 @@
         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

@@ -58 +58 @@
         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 \
@@ -79 +81 @@
         lemon/euler.h \
         lemon/fib_heap.h \
+        lemon/fourary_heap.h \
         lemon/full_graph.h \
         lemon/glpk.h \
@@ -88 +91 @@
         lemon/hypercube_graph.h \
         lemon/karp.h \
+        lemon/kary_heap.h \
         lemon/kruskal.h \
         lemon/hao_orlin.h \
@@ -96 +100 @@
         lemon/lp_base.h \
         lemon/lp_skeleton.h \
-        lemon/list_graph.h \
         lemon/maps.h \
         lemon/matching.h \
@@ -103 +106 @@
         lemon/nauty_reader.h \
         lemon/network_simplex.h \
+        lemon/pairing_heap.h \
         lemon/path.h \
         lemon/preflow.h \

test/CMakeLists.txt

@@ -33 +33 @@
   min_cost_arborescence_test
   min_cost_flow_test
+  min_mean_cycle_test
   path_test
   preflow_test

test/CMakeLists.txt

@@ -10 +10 @@
 SET(TESTS
   adaptors_test
+  bellman_ford_test
   bfs_test
   circulation_test

test/Makefile.am

@@ -31 +31 @@
         test/min_cost_arborescence_test \
         test/min_cost_flow_test \
+        test/min_mean_cycle_test \
         test/path_test \
         test/preflow_test \
@@ -79 +80 @@
 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

@@ -8 +8 @@
 check_PROGRAMS += \
         test/adaptors_test \
+        test/bellman_ford_test \
         test/bfs_test \
         test/circulation_test \
@@ -54 +55 @@
 
 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