1.1 --- a/lemon/capacity_scaling.h	Thu Nov 08 14:21:28 2007 +0000
     1.2 +++ b/lemon/capacity_scaling.h	Wed Nov 14 06:28:08 2007 +0000
     1.3 @@ -26,8 +26,8 @@
     1.4  /// flow.
     1.5  
     1.6  #include <vector>
     1.7 +#include <lemon/graph_adaptor.h>
     1.8  #include <lemon/dijkstra.h>
     1.9 -#include <lemon/graph_adaptor.h>
    1.10  
    1.11  #define WITH_SCALING
    1.12  
    1.13 @@ -43,10 +43,12 @@
    1.14    /// @{
    1.15  
    1.16    /// \brief Implementation of the capacity scaling version of the
    1.17 -  /// successive shortest path algorithm for finding a minimum cost flow.
    1.18 +  /// successive shortest path algorithm for finding a minimum cost
    1.19 +  /// flow.
    1.20    ///
    1.21 -  /// \ref lemon::CapacityScaling "CapacityScaling" implements a
    1.22 -  /// capacity scaling algorithm for finding a minimum cost flow.
    1.23 +  /// \ref lemon::CapacityScaling "CapacityScaling" implements the
    1.24 +  /// capacity scaling version of the successive shortest path
    1.25 +  /// algorithm for finding a minimum cost flow.
    1.26    ///
    1.27    /// \param Graph The directed graph type the algorithm runs on.
    1.28    /// \param LowerMap The type of the lower bound map.
    1.29 @@ -57,7 +59,7 @@
    1.30    /// \warning
    1.31    /// - Edge capacities and costs should be nonnegative integers.
    1.32    ///	However \c CostMap::Value should be signed type.
    1.33 -  /// - Supply values should be integers.
    1.34 +  /// - Supply values should be signed integers.
    1.35    /// - \c LowerMap::Value must be convertible to
    1.36    ///	\c CapacityMap::Value and \c CapacityMap::Value must be
    1.37    ///	convertible to \c SupplyMap::Value.
    1.38 @@ -113,15 +115,12 @@
    1.39  
    1.40      public:
    1.41  
    1.42 -      typedef typename MapBase<ResEdge, Cost>::Value Value;
    1.43 -      typedef typename MapBase<ResEdge, Cost>::Key Key;
    1.44 -
    1.45        ReducedCostMap( const ResGraph &_gr,
    1.46  		      const CostMap &_cost,
    1.47  		      const PotentialMap &_pot ) :
    1.48  	gr(_gr), cost_map(_cost), pot_map(_pot) {}
    1.49  
    1.50 -      Value operator[](const Key &e) const {
    1.51 +      Cost operator[](const ResEdge &e) const {
    1.52  	return ResGraph::forward(e) ?
    1.53  	   cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
    1.54  	  -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
    1.55 @@ -129,8 +128,8 @@
    1.56  
    1.57      }; //class ReducedCostMap
    1.58  
    1.59 -    /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to
    1.60 -    /// update node potentials.
    1.61 +    /// \brief Map class for the \ref lemon::Dijkstra "Dijkstra"
    1.62 +    /// algorithm to update node potentials.
    1.63      class PotentialUpdateMap : public MapBase<ResNode, Cost>
    1.64      {
    1.65      private:
    1.66 @@ -141,9 +140,6 @@
    1.67  
    1.68      public:
    1.69  
    1.70 -      typedef typename MapBase<ResNode, Cost>::Value Value;
    1.71 -      typedef typename MapBase<ResNode, Cost>::Key Key;
    1.72 -
    1.73        void potentialMap(PotentialMap &_pot) {
    1.74  	pot = &_pot;
    1.75        }
    1.76 @@ -152,7 +148,7 @@
    1.77  	data.clear();
    1.78        }
    1.79  
    1.80 -      void set(const Key &n, const Value &v) {
    1.81 +      void set(const ResNode &n, const Cost &v) {
    1.82  	data.push_back(Pair(n, v));
    1.83        }
    1.84  
    1.85 @@ -185,7 +181,7 @@
    1.86      }; //class DeficitBoolMap
    1.87  
    1.88      /// \brief Map adaptor class for filtering edges with at least
    1.89 -    /// \c delta residual capacity
    1.90 +    /// \c delta residual capacity.
    1.91      class DeltaFilterMap : public MapBase<ResEdge, bool>
    1.92      {
    1.93      private:
    1.94 @@ -195,13 +191,10 @@
    1.95  
    1.96      public:
    1.97  
    1.98 -      typedef typename MapBase<ResEdge, Cost>::Value Value;
    1.99 -      typedef typename MapBase<ResEdge, Cost>::Key Key;
   1.100 -
   1.101        DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
   1.102  	gr(_gr), delta(_delta) {}
   1.103  
   1.104 -      Value operator[](const Key &e) const {
   1.105 +      bool operator[](const ResEdge &e) const {
   1.106  	return gr.rescap(e) >= delta;
   1.107        }
   1.108  
   1.109 @@ -298,9 +291,12 @@
   1.110  
   1.111      /// \brief The delta parameter used for capacity scaling.
   1.112      Capacity delta;
   1.113 -    /// \brief Edge filter map.
   1.114 +    /// \brief Edge filter map for filtering edges with at least
   1.115 +    /// \c delta residual capacity.
   1.116      DeltaFilterMap delta_filter;
   1.117 -    /// \brief The delta residual graph.
   1.118 +    /// \brief The delta residual graph (i.e. the subgraph of the
   1.119 +    /// residual graph consisting of edges with at least \c delta
   1.120 +    /// residual capacity).
   1.121      DeltaResGraph dres_graph;
   1.122      /// \brief Map for identifing deficit nodes.
   1.123      DeficitBoolMap delta_deficit;
   1.124 @@ -573,8 +569,8 @@
   1.125  	for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {
   1.126  	  if (red_cost[e] < 0) {
   1.127  	    res_graph.augment(e, r = res_graph.rescap(e));
   1.128 +	    imbalance[dres_graph.source(e)] -= r;
   1.129  	    imbalance[dres_graph.target(e)] += r;
   1.130 -	    imbalance[dres_graph.source(e)] -= r;
   1.131  	  }
   1.132  	}
   1.133  

     2.1 --- a/lemon/cycle_canceling.h	Thu Nov 08 14:21:28 2007 +0000
     2.2 +++ b/lemon/cycle_canceling.h	Wed Nov 14 06:28:08 2007 +0000
     2.3 @@ -25,8 +25,8 @@
     2.4  /// \brief A cycle-canceling algorithm for finding a minimum cost flow.
     2.5  
     2.6  #include <vector>
     2.7 +#include <lemon/graph_adaptor.h>
     2.8  #include <lemon/circulation.h>
     2.9 -#include <lemon/graph_adaptor.h>
    2.10  
    2.11  /// \brief The used cycle-canceling method.
    2.12  #define LIMITED_CYCLE_CANCELING
    2.13 @@ -79,7 +79,7 @@
    2.14    /// \warning
    2.15    /// - Edge capacities and costs should be nonnegative integers.
    2.16    ///	However \c CostMap::Value should be signed type.
    2.17 -  /// - Supply values should be integers.
    2.18 +  /// - Supply values should be signed integers.
    2.19    /// - \c LowerMap::Value must be convertible to
    2.20    ///	\c CapacityMap::Value and \c CapacityMap::Value must be
    2.21    ///	convertible to \c SupplyMap::Value.
    2.22 @@ -131,12 +131,9 @@
    2.23  
    2.24      public:
    2.25  
    2.26 -      typedef typename MapBase<ResEdge, Cost>::Value Value;
    2.27 -      typedef typename MapBase<ResEdge, Cost>::Key Key;
    2.28 -
    2.29        ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
    2.30  
    2.31 -      Value operator[](const Key &e) const {
    2.32 +      Cost operator[](const ResEdge &e) const {
    2.33  	return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
    2.34        }
    2.35  

     3.1 --- a/lemon/min_cost_flow.h	Thu Nov 08 14:21:28 2007 +0000
     3.2 +++ b/lemon/min_cost_flow.h	Wed Nov 14 06:28:08 2007 +0000
     3.3 @@ -56,7 +56,7 @@
     3.4    /// \warning
     3.5    /// - Edge capacities and costs should be nonnegative integers.
     3.6    ///	However \c CostMap::Value should be signed type.
     3.7 -  /// - Supply values should be integers.
     3.8 +  /// - Supply values should be signed integers.
     3.9    /// - \c LowerMap::Value must be convertible to
    3.10    ///	\c CapacityMap::Value and \c CapacityMap::Value must be
    3.11    ///	convertible to \c SupplyMap::Value.

     4.1 --- a/lemon/min_mean_cycle.h	Thu Nov 08 14:21:28 2007 +0000
     4.2 +++ b/lemon/min_mean_cycle.h	Wed Nov 14 06:28:08 2007 +0000
     4.3 @@ -22,8 +22,9 @@
     4.4  /// \ingroup min_cost_flow
     4.5  ///
     4.6  /// \file
     4.7 -/// \brief Karp algorithm for finding a minimum mean cycle.
     4.8 +/// \brief Karp's algorithm for finding a minimum mean (directed) cycle.
     4.9  
    4.10 +#include <vector>
    4.11  #include <lemon/graph_utils.h>
    4.12  #include <lemon/topology.h>
    4.13  #include <lemon/path.h>
    4.14 @@ -63,7 +64,7 @@
    4.15  
    4.16    protected:
    4.17  
    4.18 -    /// \brief Data sturcture for path data.
    4.19 +    /// \brief Data structure for path data.
    4.20      struct PathData
    4.21      {
    4.22        bool found;
    4.23 @@ -150,7 +151,7 @@
    4.24        }
    4.25        // Creating vectors for all nodes
    4.26        int n = nodes.size();
    4.27 -      for (int i = 0; i < nodes.size(); ++i) {
    4.28 +      for (int i = 0; i < n; ++i) {
    4.29  	dmap[nodes[i]].resize(n + 1);
    4.30        }
    4.31      }

     5.1 --- a/lemon/network_simplex.h	Thu Nov 08 14:21:28 2007 +0000
     5.2 +++ b/lemon/network_simplex.h	Wed Nov 14 06:28:08 2007 +0000
     5.3 @@ -26,8 +26,9 @@
     5.4  /// flow.
     5.5  
     5.6  #include <limits>
     5.7 +#include <lemon/graph_adaptor.h>
     5.8 +#include <lemon/graph_utils.h>
     5.9  #include <lemon/smart_graph.h>
    5.10 -#include <lemon/graph_utils.h>
    5.11  
    5.12  /// \brief The pivot rule used in the algorithm.
    5.13  //#define FIRST_ELIGIBLE_PIVOT
    5.14 @@ -85,7 +86,7 @@
    5.15    /// \warning
    5.16    /// - Edge capacities and costs should be nonnegative integers.
    5.17    ///	However \c CostMap::Value should be signed type.
    5.18 -  /// - Supply values should be integers.
    5.19 +  /// - Supply values should be signed integers.
    5.20    /// - \c LowerMap::Value must be convertible to
    5.21    ///	\c CapacityMap::Value and \c CapacityMap::Value must be
    5.22    ///	convertible to \c SupplyMap::Value.
    5.23 @@ -148,15 +149,12 @@
    5.24  
    5.25      public:
    5.26  
    5.27 -      typedef typename MapBase<Edge, Cost>::Value Value;
    5.28 -      typedef typename MapBase<Edge, Cost>::Key Key;
    5.29 -
    5.30        ReducedCostMap( const SGraph &_gr,
    5.31  		      const SCostMap &_cm,
    5.32  		      const SPotentialMap &_pm ) :
    5.33  	gr(_gr), cost_map(_cm), pot_map(_pm) {}
    5.34  
    5.35 -      Value operator[](const Key &e) const {
    5.36 +      Cost operator[](const Edge &e) const {
    5.37  	return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
    5.38        }
    5.39