lemon-0.x: comparison lemon/capacity

equal deleted inserted replaced

-:a9c67524c45e
+:985ac162a9a2
 #define LEMON_CAPACITY_SCALING_H
 /// \ingroup min_cost_flow
 ///
 /// \file
-/// \brief The capacity scaling algorithm for finding a minimum cost
+/// \brief The capacity scaling algorithm for finding a minimum cost flow.
-/// flow.
 #include <lemon/graph_adaptor.h>
 #include <lemon/bin_heap.h>
 #include <vector>
 /// \param CapacityMap The type of the capacity (upper bound) map.
 /// \param CostMap The type of the cost (length) map.
 /// \param SupplyMap The type of the supply map.
 ///
 /// \warning
-/// - Edge capacities and costs should be nonnegative integers.
+/// - Edge capacities and costs should be non-negative integers.
 ///   However \c CostMap::Value should be signed type.
 /// - Supply values should be signed integers.
 /// - \c LowerMap::Value must be convertible to
 ///   \c CapacityMap::Value and \c CapacityMap::Value must be
 ///   convertible to \c SupplyMap::Value.
 typename CostMap = typename Graph::template EdgeMap<int>,
 typename SupplyMap = typename Graph::template NodeMap
 <typename CapacityMap::Value> >
 class CapacityScaling
 {
-typedef typename Graph::Node Node;
+GRAPH_TYPEDEFS(typename Graph);
-typedef typename Graph::NodeIt NodeIt;
-typedef typename Graph::Edge Edge;
-typedef typename Graph::EdgeIt EdgeIt;
-typedef typename Graph::InEdgeIt InEdgeIt;
-typedef typename Graph::OutEdgeIt OutEdgeIt;
 typedef typename LowerMap::Value Lower;
 typedef typename CapacityMap::Value Capacity;
 typedef typename CostMap::Value Cost;
 typedef typename SupplyMap::Value Supply;
-typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
+typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
-typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
+typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
 typedef typename Graph::template NodeMap<Edge> PredMap;
 public:
-/// \brief Type to enable or disable capacity scaling.
+/// Type to enable or disable capacity scaling.
 enum ScalingEnum {
 WITH_SCALING = 0,
 WITHOUT_SCALING = -1
 };
-/// \brief The type of the flow map.
+/// The type of the flow map.
-typedef CapacityRefMap FlowMap;
+typedef typename Graph::template EdgeMap<Capacity> FlowMap;
-/// \brief The type of the potential map.
+/// The type of the potential map.
 typedef typename Graph::template NodeMap<Cost> PotentialMap;
 protected:
 /// \brief Special implementation of the \ref Dijkstra algorithm
 typedef typename Graph::template NodeMap<int> HeapCrossRef;
 typedef BinHeap<Cost, HeapCrossRef> Heap;
 protected:
-/// \brief The directed graph the algorithm runs on.
+/// The directed graph the algorithm runs on.
 const Graph &graph;
-/// \brief The flow map.
+/// The flow map.
 const FlowMap &flow;
-/// \brief The residual capacity map.
+/// The residual capacity map.
-const CapacityRefMap &res_cap;
+const CapacityEdgeMap &res_cap;
-/// \brief The cost map.
+/// The cost map.
 const CostMap &cost;
-/// \brief The excess map.
+/// The excess map.
-const SupplyRefMap &excess;
+const SupplyNodeMap &excess;
-/// \brief The potential map.
+/// The potential map.
 PotentialMap &potential;
-/// \brief The distance map.
+/// The distance map.
 CostNodeMap dist;
-/// \brief The map of predecessors edges.
+/// The map of predecessors edges.
 PredMap &pred;
-/// \brief The processed (i.e. permanently labeled) nodes.
+/// The processed (i.e. permanently labeled) nodes.
 std::vector<Node> proc_nodes;
 public:
-/// \brief The constructor of the class.
+/// The constructor of the class.
 ResidualDijkstra( const Graph &_graph,
 const FlowMap &_flow,
-const CapacityRefMap &_res_cap,
+const CapacityEdgeMap &_res_cap,
 const CostMap &_cost,
 const SupplyMap &_excess,
 PotentialMap &_potential,
 PredMap &_pred ) :
 graph(_graph), flow(_flow), res_cap(_res_cap), cost(_cost),
 excess(_excess), potential(_potential), dist(_graph),
 pred(_pred)
 {}
-/// \brief Runs the algorithm from the given source node.
+/// Runs the algorithm from the given source node.
 Node run(Node s, Capacity delta) {
 HeapCrossRef heap_cross_ref(graph, Heap::PRE_HEAP);
 Heap heap(heap_cross_ref);
 heap.push(s, 0);
 pred[s] = INVALID;
 }; //class ResidualDijkstra
 protected:
-/// \brief The directed graph the algorithm runs on.
+/// The directed graph the algorithm runs on.
 const Graph &graph;
-/// \brief The original lower bound map.
+/// The original lower bound map.
 const LowerMap *lower;
-/// \brief The modified capacity map.
+/// The modified capacity map.
-CapacityRefMap capacity;
+CapacityEdgeMap capacity;
-/// \brief The cost map.
+/// The cost map.
 const CostMap &cost;
-/// \brief The modified supply map.
+/// The modified supply map.
-SupplyRefMap supply;
+SupplyNodeMap supply;
-/// \brief The sum of supply values equals zero.
 bool valid_supply;
-/// \brief The edge map of the current flow.
+/// The edge map of the current flow.
 FlowMap flow;
-/// \brief The potential node map.
+/// The potential node map.
 PotentialMap potential;
-/// \brief The residual capacity map.
+/// The residual capacity map.
-CapacityRefMap res_cap;
+CapacityEdgeMap res_cap;
-/// \brief The excess map.
+/// The excess map.
-SupplyRefMap excess;
+SupplyNodeMap excess;
-/// \brief The excess nodes (i.e. nodes with positive excess).
+/// The excess nodes (i.e. the nodes with positive excess).
 std::vector<Node> excess_nodes;
-/// \brief The index of the next excess node.
+/// The deficit nodes (i.e. the nodes with negative excess).
-int next_node;
+std::vector<Node> deficit_nodes;
-/// \brief The scaling status (enabled or disabled).
+/// The scaling status (enabled or disabled).
 ScalingEnum scaling;
-/// \brief The delta parameter used for capacity scaling.
+/// The \c delta parameter used for capacity scaling.
 Capacity delta;
-/// \brief The maximum number of phases.
+/// The maximum number of phases.
-Capacity phase_num;
+int phase_num;
-/// \brief The deficit nodes.
-std::vector<Node> deficit_nodes;
 /// \brief Implementation of the \ref Dijkstra algorithm for
 /// finding augmenting shortest paths in the residual network.
 ResidualDijkstra dijkstra;
-/// \brief The map of predecessors edges.
+/// The map of predecessors edges.
 PredMap pred;
 public :
 /// \brief General constructor of the class (with lower bounds).
 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
 supply(_graph), flow(_graph, 0), potential(_graph, 0),
 res_cap(_graph), excess(_graph), pred(_graph),
 dijkstra(graph, flow, res_cap, cost, excess, potential, pred)
 {
-// Removing nonzero lower bounds
+// Removing non-zero lower bounds
 capacity = subMap(_capacity, _lower);
 res_cap = capacity;
 Supply sum = 0;
 for (NodeIt n(graph); n != INVALID; ++n) {
 Supply s = _supply[n];
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _s The source node.
 /// \param _t The target node.
 /// \param _flow_value The required amount of flow from node \c _s
-/// to node \c _t (i.e. the supply of \c _s and the demand of
+/// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
-/// \c _t).
 CapacityScaling( const Graph &_graph,
 const LowerMap &_lower,
 const CapacityMap &_capacity,
 const CostMap &_cost,
 Node _s, Node _t,
 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
 supply(_graph), flow(_graph, 0), potential(_graph, 0),
 res_cap(_graph), excess(_graph), pred(_graph),
 dijkstra(graph, flow, res_cap, cost, excess, potential)
 {
-// Removing nonzero lower bounds
+// Removing non-zero lower bounds
 capacity = subMap(_capacity, _lower);
 res_cap = capacity;
 for (NodeIt n(graph); n != INVALID; ++n) {
 Supply s = 0;
 if (n == _s) s =  _flow_value;
 /// \param _capacity The capacities (upper bounds) of the edges.
 /// \param _cost The cost (length) values of the edges.
 /// \param _s The source node.
 /// \param _t The target node.
 /// \param _flow_value The required amount of flow from node \c _s
-/// to node \c _t (i.e. the supply of \c _s and the demand of
+/// to node \c _t (i.e. the supply of \c _s and the demand of \c _t).
-/// \c _t).
 CapacityScaling( const Graph &_graph,
 const CapacityMap &_capacity,
 const CostMap &_cost,
 Node _s, Node _t,
 Supply _flow_value ) :
 supply[_s] =  _flow_value;
 supply[_t] = -_flow_value;
 valid_supply = true;
 }
+/// \brief Runs the algorithm.
+///
+/// Runs the algorithm.
+///
+/// \param scaling_mode The scaling mode. In case of WITH_SCALING
+/// capacity scaling is enabled in the algorithm (this is the
+/// default) otherwise it is disabled.
+/// If the maximum edge capacity and/or the amount of total supply
+/// is small, the algorithm could be slightly faster without
+/// scaling.
+///
+/// \return \c true if a feasible flow can be found.
+bool run(int scaling_mode = WITH_SCALING) {
+return init(scaling_mode) && start();
+}
 /// \brief Returns a const reference to the flow map.
 ///
 /// Returns a const reference to the flow map.
 ///
 /// \pre \ref run() must be called before using this function.
 for (EdgeIt e(graph); e != INVALID; ++e)
 c += flow[e] * cost[e];
 return c;
 }
-/// \brief Runs the algorithm.
-///
-/// Runs the algorithm.
-///
-/// \param scaling_mode The scaling mode. In case of WITH_SCALING
-/// capacity scaling is enabled in the algorithm (this is the
-/// default value) otherwise it is disabled.
-/// If the maximum edge capacity and/or the amount of total supply
-/// is small, the algorithm could be faster without scaling.
-///
-/// \return \c true if a feasible flow can be found.
-bool run(int scaling_mode = WITH_SCALING) {
-return init(scaling_mode) && start();
-}
 protected:
-/// \brief Initializes the algorithm.
+/// Initializes the algorithm.
 bool init(int scaling_mode) {
 if (!valid_supply) return false;
 excess = supply;
 // Initilaizing delta value
 delta = 1;
 }
 return true;
 }
-/// \brief Executes the algorithm.
+/// Executes the algorithm.
 bool start() {
 if (delta > 1)
 return startWithScaling();
 else
 return startWithoutScaling();
 deficit_nodes.clear();
 for (NodeIt n(graph); n != INVALID; ++n) {
 if (excess[n] >=  delta) excess_nodes.push_back(n);
 if (excess[n] <= -delta) deficit_nodes.push_back(n);
 }
-next_node = 0;
+int next_node = 0;
 // Finding augmenting shortest paths
 while (next_node < excess_nodes.size()) {
 // Checking deficit nodes
 if (delta > 1) {
 if (delta == 1) break;
 if (++phase_cnt > phase_num / 4) factor = 2;
 delta = delta <= factor ? 1 : delta / factor;
 }
-// Handling nonzero lower bounds
+// Handling non-zero lower bounds
 if (lower) {
 for (EdgeIt e(graph); e != INVALID; ++e)
 flow[e] += (*lower)[e];
 }
 return true;
 /// \brief Executes the successive shortest path algorithm without
 /// capacity scaling.
 bool startWithoutScaling() {
 // Finding excess nodes
-for (NodeIt n(graph); n != INVALID; ++n) {
+for (NodeIt n(graph); n != INVALID; ++n)
 if (excess[n] > 0) excess_nodes.push_back(n);
-}
 if (excess_nodes.size() == 0) return true;
-next_node = 0;
+int next_node = 0;
 // Finding shortest paths
 Node s, t;
 while ( excess[excess_nodes[next_node]] > 0 ||
 ++next_node < excess_nodes.size() )
 }
 excess[s] -= d;
 excess[t] += d;
 }
-// Handling nonzero lower bounds
+// Handling non-zero lower bounds
 if (lower) {
 for (EdgeIt e(graph); e != INVALID; ++e)
 flow[e] += (*lower)[e];
 }
 return true;

changeset 2557	673cb4d1060b
parent 2553	bfced05fa852
child 2574	7058c9690e7d