# HG changeset patch # User kpeter # Date 1200220334 0 # Node ID 74c2c81055e182bb2c2381fcaa0bf50db75128cd # Parent a84e52e99f5726c81b9e86fc8a95375c13ed502b Cleanup in the minimum cost flow files. The changes only affects the documentation and the look of the source codes. diff -r a84e52e99f57 -r 74c2c81055e1 lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h Sun Jan 13 10:26:55 2008 +0000 +++ b/lemon/capacity_scaling.h Sun Jan 13 10:32:14 2008 +0000 @@ -22,8 +22,7 @@ /// \ingroup min_cost_flow /// /// \file -/// \brief The capacity scaling algorithm for finding a minimum cost -/// flow. +/// \brief The capacity scaling algorithm for finding a minimum cost flow. #include #include @@ -49,7 +48,7 @@ /// \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 @@ -66,32 +65,27 @@ > class CapacityScaling { - typedef typename Graph::Node Node; - 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; + GRAPH_TYPEDEFS(typename Graph); 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 CapacityRefMap; - typedef typename Graph::template NodeMap SupplyRefMap; + typedef typename Graph::template EdgeMap CapacityEdgeMap; + typedef typename Graph::template NodeMap SupplyNodeMap; typedef typename Graph::template NodeMap 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. - typedef CapacityRefMap FlowMap; - /// \brief The type of the potential map. + /// The type of the flow map. + typedef typename Graph::template EdgeMap FlowMap; + /// The type of the potential map. typedef typename Graph::template NodeMap PotentialMap; protected: @@ -110,34 +104,34 @@ 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. - const CapacityRefMap &res_cap; - /// \brief The cost map. + /// The residual capacity map. + const CapacityEdgeMap &res_cap; + /// The cost map. const CostMap &cost; - /// \brief The excess map. - const SupplyRefMap &excess; + /// The excess map. + 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 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, @@ -147,7 +141,7 @@ 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); @@ -222,46 +216,43 @@ 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. - CapacityRefMap capacity; - /// \brief The cost map. + /// The modified capacity map. + CapacityEdgeMap capacity; + /// The cost map. const CostMap &cost; - /// \brief The modified supply map. - SupplyRefMap supply; - /// \brief The sum of supply values equals zero. + /// The modified supply map. + SupplyNodeMap supply; 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. - CapacityRefMap res_cap; - /// \brief The excess map. - SupplyRefMap excess; - /// \brief The excess nodes (i.e. nodes with positive excess). + /// The residual capacity map. + CapacityEdgeMap res_cap; + /// The excess map. + SupplyNodeMap excess; + /// The excess nodes (i.e. the nodes with positive excess). std::vector excess_nodes; - /// \brief The index of the next excess node. - int next_node; + /// The deficit nodes (i.e. the nodes with negative excess). + std::vector 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. - Capacity phase_num; - /// \brief The deficit nodes. - std::vector deficit_nodes; + /// The maximum number of phases. + int phase_num; /// \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 : @@ -285,7 +276,7 @@ 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; @@ -335,8 +326,7 @@ /// \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 - /// \c _t). + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). CapacityScaling( const Graph &_graph, const LowerMap &_lower, const CapacityMap &_capacity, @@ -348,7 +338,7 @@ 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) { @@ -374,8 +364,7 @@ /// \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 - /// \c _t). + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). CapacityScaling( const Graph &_graph, const CapacityMap &_capacity, const CostMap &_cost, @@ -391,6 +380,22 @@ 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. @@ -424,24 +429,9 @@ 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; @@ -465,7 +455,7 @@ return true; } - /// \brief Executes the algorithm. + /// Executes the algorithm. bool start() { if (delta > 1) return startWithScaling(); @@ -506,7 +496,7 @@ 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()) { @@ -572,7 +562,7 @@ 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]; @@ -584,11 +574,10 @@ /// 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; @@ -631,7 +620,7 @@ 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]; diff -r a84e52e99f57 -r 74c2c81055e1 lemon/cycle_canceling.h --- a/lemon/cycle_canceling.h Sun Jan 13 10:26:55 2008 +0000 +++ b/lemon/cycle_canceling.h Sun Jan 13 10:32:14 2008 +0000 @@ -34,24 +34,17 @@ #ifdef LIMITED_CYCLE_CANCELING #include - /// \brief The maximum number of iterations for the first execution - /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm. - /// It should be at least 2. - #define STARTING_LIMIT 2 - /// \brief The iteration limit for the - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by - /// ALPHA_MUL / ALPHA_DIV in every round. - /// ALPHA_MUL / ALPHA_DIV must be greater than 1. - #define ALPHA_MUL 3 - /// \brief The iteration limit for the - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by - /// ALPHA_MUL / ALPHA_DIV in every round. - /// ALPHA_MUL / ALPHA_DIV must be greater than 1. - #define ALPHA_DIV 2 + // The maximum number of iterations for the first execution of the + // Bellman-Ford algorithm. It should be at least 2. + #define STARTING_LIMIT 2 + // The iteration limit for the Bellman-Ford algorithm is multiplied by + // ALPHA_MUL / ALPHA_DIV in every round. + // ALPHA_MUL / ALPHA_DIV must be greater than 1. + #define ALPHA_MUL 3 + #define ALPHA_DIV 2 //#define _ONLY_ONE_CYCLE_ //#define _NO_BACK_STEP_ -//#define _DEBUG_ITER_ #endif #ifdef MIN_MEAN_CYCLE_CANCELING @@ -59,16 +52,18 @@ #include #endif +//#define _DEBUG_ITER_ + namespace lemon { /// \addtogroup min_cost_flow /// @{ - /// \brief Implementation of a cycle-canceling algorithm for finding - /// a minimum cost flow. + /// \brief Implementation of a cycle-canceling algorithm for + /// finding a minimum cost flow. /// - /// \ref lemon::CycleCanceling "CycleCanceling" implements a - /// cycle-canceling algorithm for finding a minimum cost flow. + /// \ref CycleCanceling implements a cycle-canceling algorithm for + /// finding a minimum cost flow. /// /// \param Graph The directed graph type the algorithm runs on. /// \param LowerMap The type of the lower bound map. @@ -77,12 +72,12 @@ /// \param SupplyMap The type of the supply map. /// /// \warning - /// - Edge capacities and costs should be nonnegative integers. - /// However \c CostMap::Value should be signed type. + /// - 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. + /// \c CapacityMap::Value and \c CapacityMap::Value must be + /// convertible to \c SupplyMap::Value. /// /// \author Peter Kovacs @@ -94,22 +89,17 @@ > class CycleCanceling { - typedef typename Graph::Node Node; - 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; + GRAPH_TYPEDEFS(typename Graph); 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 CapacityRefMap; - typedef typename Graph::template NodeMap SupplyRefMap; + typedef typename Graph::template EdgeMap CapacityEdgeMap; + typedef typename Graph::template NodeMap SupplyNodeMap; typedef ResGraphAdaptor< const Graph, Capacity, - CapacityRefMap, CapacityRefMap > ResGraph; + CapacityEdgeMap, CapacityEdgeMap > ResGraph; typedef typename ResGraph::Node ResNode; typedef typename ResGraph::NodeIt ResNodeIt; typedef typename ResGraph::Edge ResEdge; @@ -117,12 +107,12 @@ public: - /// \brief The type of the flow map. - typedef CapacityRefMap FlowMap; + /// The type of the flow map. + typedef typename Graph::template EdgeMap FlowMap; protected: - /// \brief Map adaptor class for handling residual edge costs. + /// Map adaptor class for handling residual edge costs. class ResCostMap : public MapBase { private: @@ -134,31 +124,30 @@ ResCostMap(const CostMap &_cost) : cost_map(_cost) {} Cost operator[](const ResEdge &e) const { - return ResGraph::forward(e) ? cost_map[e] : -cost_map[e]; + return ResGraph::forward(e) ? cost_map[e] : -cost_map[e]; } }; //class ResCostMap 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. - CapacityRefMap capacity; - /// \brief The cost map. + /// The modified capacity map. + CapacityEdgeMap capacity; + /// The cost map. const CostMap &cost; - /// \brief The modified supply map. - SupplyRefMap supply; - /// \brief The sum of supply values equals zero. + /// The modified supply map. + SupplyNodeMap supply; bool valid_supply; - /// \brief The current flow. + /// The current flow. FlowMap flow; - /// \brief The residual graph. + /// The residual graph. ResGraph res_graph; - /// \brief The residual cost map. + /// The residual cost map. ResCostMap res_cost; public : @@ -173,24 +162,24 @@ /// \param _cost The cost (length) values of the edges. /// \param _supply The supply values of the nodes (signed). CycleCanceling( const Graph &_graph, - const LowerMap &_lower, - const CapacityMap &_capacity, - const CostMap &_cost, - const SupplyMap &_supply ) : + const LowerMap &_lower, + const CapacityMap &_capacity, + const CostMap &_cost, + const SupplyMap &_supply ) : graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), supply(_graph), flow(_graph, 0), res_graph(_graph, capacity, flow), res_cost(cost) { - // Removing nonzero lower bounds + // Removing non-zero lower bounds capacity = subMap(_capacity, _lower); Supply sum = 0; for (NodeIt n(graph); n != INVALID; ++n) { - Supply s = _supply[n]; - for (InEdgeIt e(graph, n); e != INVALID; ++e) - s += _lower[e]; - for (OutEdgeIt e(graph, n); e != INVALID; ++e) - s -= _lower[e]; - sum += (supply[n] = s); + Supply s = _supply[n]; + for (InEdgeIt e(graph, n); e != INVALID; ++e) + s += _lower[e]; + for (OutEdgeIt e(graph, n); e != INVALID; ++e) + s -= _lower[e]; + sum += (supply[n] = s); } valid_supply = sum == 0; } @@ -204,9 +193,9 @@ /// \param _cost The cost (length) values of the edges. /// \param _supply The supply values of the nodes (signed). CycleCanceling( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - const SupplyMap &_supply ) : + const CapacityMap &_capacity, + const CostMap &_cost, + const SupplyMap &_supply ) : graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), supply(_supply), flow(_graph, 0), res_graph(_graph, capacity, flow), res_cost(cost) @@ -217,7 +206,6 @@ valid_supply = sum == 0; } - /// \brief Simple constructor of the class (with lower bounds). /// /// Simple constructor of the class (with lower bounds). @@ -229,29 +217,28 @@ /// \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 - /// \c _t). + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). CycleCanceling( const Graph &_graph, - const LowerMap &_lower, - const CapacityMap &_capacity, - const CostMap &_cost, - Node _s, Node _t, - Supply _flow_value ) : + const LowerMap &_lower, + const CapacityMap &_capacity, + const CostMap &_cost, + Node _s, Node _t, + Supply _flow_value ) : graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), supply(_graph), flow(_graph, 0), res_graph(_graph, capacity, flow), res_cost(cost) { - // Removing nonzero lower bounds + // Removing non-zero lower bounds capacity = subMap(_capacity, _lower); for (NodeIt n(graph); n != INVALID; ++n) { - Supply s = 0; - if (n == _s) s = _flow_value; - if (n == _t) s = -_flow_value; - for (InEdgeIt e(graph, n); e != INVALID; ++e) - s += _lower[e]; - for (OutEdgeIt e(graph, n); e != INVALID; ++e) - s -= _lower[e]; - supply[n] = s; + Supply s = 0; + if (n == _s) s = _flow_value; + if (n == _t) s = -_flow_value; + for (InEdgeIt e(graph, n); e != INVALID; ++e) + s += _lower[e]; + for (OutEdgeIt e(graph, n); e != INVALID; ++e) + s -= _lower[e]; + supply[n] = s; } valid_supply = true; } @@ -266,13 +253,12 @@ /// \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 - /// \c _t). + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). CycleCanceling( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - Node _s, Node _t, - Supply _flow_value ) : + const CapacityMap &_capacity, + const CostMap &_cost, + Node _s, Node _t, + Supply _flow_value ) : graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), supply(_graph, 0), flow(_graph, 0), res_graph(_graph, capacity, flow), res_cost(cost) @@ -282,6 +268,15 @@ valid_supply = true; } + /// \brief Runs the algorithm. + /// + /// Runs the algorithm. + /// + /// \return \c true if a feasible flow can be found. + bool run() { + return init() && start(); + } + /// \brief Returns a const reference to the flow map. /// /// Returns a const reference to the flow map. @@ -300,22 +295,13 @@ Cost totalCost() const { Cost c = 0; for (EdgeIt e(graph); e != INVALID; ++e) - c += flow[e] * cost[e]; + c += flow[e] * cost[e]; return c; } - /// \brief Runs the algorithm. - /// - /// Runs the algorithm. - /// - /// \return \c true if a feasible flow can be found. - bool run() { - return init() && start(); - } - protected: - /// \brief Initializes the algorithm. + /// Initializes the algorithm. bool init() { // Checking the sum of supply values Supply sum = 0; @@ -323,18 +309,17 @@ if (sum != 0) return false; // Finding a feasible flow - Circulation< Graph, ConstMap, CapacityRefMap, - SupplyMap > - circulation( graph, constMap((Capacity)0), capacity, - supply ); + Circulation< Graph, ConstMap, CapacityEdgeMap, + SupplyMap > + circulation( graph, constMap((Capacity)0), capacity, + supply ); circulation.flowMap(flow); return circulation.run(); } #ifdef LIMITED_CYCLE_CANCELING /// \brief Executes a cycle-canceling algorithm using - /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited - /// iteration count. + /// \ref Bellman-Ford algorithm with limited iteration count. bool start() { typename BellmanFord::PredMap pred(res_graph); typename ResGraph::template NodeMap visited(res_graph); @@ -347,85 +332,85 @@ int length_bound = STARTING_LIMIT; bool optimal = false; while (!optimal) { - BellmanFord bf(res_graph, res_cost); - bf.predMap(pred); - bf.init(0); - int iter_num = 0; - bool cycle_found = false; - while (!cycle_found) { + BellmanFord bf(res_graph, res_cost); + bf.predMap(pred); + bf.init(0); + int iter_num = 0; + bool cycle_found = false; + while (!cycle_found) { #ifdef _NO_BACK_STEP_ - int curr_iter_num = length_bound <= node_num ? - length_bound - iter_num : node_num - iter_num; + int curr_iter_num = length_bound <= node_num ? + length_bound - iter_num : node_num - iter_num; #else - int curr_iter_num = iter_num + length_bound <= node_num ? - length_bound : node_num - iter_num; + int curr_iter_num = iter_num + length_bound <= node_num ? + length_bound : node_num - iter_num; #endif - iter_num += curr_iter_num; - int real_iter_num = curr_iter_num; - for (int i = 0; i < curr_iter_num; ++i) { - if (bf.processNextWeakRound()) { - real_iter_num = i; - break; - } - } - if (real_iter_num < curr_iter_num) { - optimal = true; - break; - } else { - // Searching for node disjoint negative cycles - for (ResNodeIt n(res_graph); n != INVALID; ++n) - visited[n] = 0; - int id = 0; - for (ResNodeIt n(res_graph); n != INVALID; ++n) { - if (visited[n] > 0) continue; - visited[n] = ++id; - ResNode u = pred[n] == INVALID ? - INVALID : res_graph.source(pred[n]); - while (u != INVALID && visited[u] == 0) { - visited[u] = id; - u = pred[u] == INVALID ? - INVALID : res_graph.source(pred[u]); - } - if (u != INVALID && visited[u] == id) { - // Finding the negative cycle - cycle_found = true; - cycle.clear(); - ResEdge e = pred[u]; - cycle.push_back(e); - Capacity d = res_graph.rescap(e); - while (res_graph.source(e) != u) { - cycle.push_back(e = pred[res_graph.source(e)]); - if (res_graph.rescap(e) < d) - d = res_graph.rescap(e); - } + iter_num += curr_iter_num; + int real_iter_num = curr_iter_num; + for (int i = 0; i < curr_iter_num; ++i) { + if (bf.processNextWeakRound()) { + real_iter_num = i; + break; + } + } + if (real_iter_num < curr_iter_num) { + optimal = true; + break; + } else { + // Searching for node disjoint negative cycles + for (ResNodeIt n(res_graph); n != INVALID; ++n) + visited[n] = 0; + int id = 0; + for (ResNodeIt n(res_graph); n != INVALID; ++n) { + if (visited[n] > 0) continue; + visited[n] = ++id; + ResNode u = pred[n] == INVALID ? + INVALID : res_graph.source(pred[n]); + while (u != INVALID && visited[u] == 0) { + visited[u] = id; + u = pred[u] == INVALID ? + INVALID : res_graph.source(pred[u]); + } + if (u != INVALID && visited[u] == id) { + // Finding the negative cycle + cycle_found = true; + cycle.clear(); + ResEdge e = pred[u]; + cycle.push_back(e); + Capacity d = res_graph.rescap(e); + while (res_graph.source(e) != u) { + cycle.push_back(e = pred[res_graph.source(e)]); + if (res_graph.rescap(e) < d) + d = res_graph.rescap(e); + } #ifdef _DEBUG_ITER_ - ++cycle_num; + ++cycle_num; #endif - // Augmenting along the cycle - for (int i = 0; i < cycle.size(); ++i) - res_graph.augment(cycle[i], d); + // Augmenting along the cycle + for (int i = 0; i < cycle.size(); ++i) + res_graph.augment(cycle[i], d); #ifdef _ONLY_ONE_CYCLE_ - break; + break; #endif - } - } - } + } + } + } - if (!cycle_found) - length_bound = length_bound * ALPHA_MUL / ALPHA_DIV; - } + if (!cycle_found) + length_bound = length_bound * ALPHA_MUL / ALPHA_DIV; + } } #ifdef _DEBUG_ITER_ std::cout << "Limited cycle-canceling algorithm finished. " - << "Found " << cycle_num << " negative cycles." - << std::endl; + << "Found " << cycle_num << " negative cycles." + << std::endl; #endif - // Handling nonzero lower bounds + // Handling non-zero lower bounds if (lower) { - for (EdgeIt e(graph); e != INVALID; ++e) - flow[e] += (*lower)[e]; + for (EdgeIt e(graph); e != INVALID; ++e) + flow[e] += (*lower)[e]; } return true; } @@ -433,7 +418,7 @@ #ifdef MIN_MEAN_CYCLE_CANCELING /// \brief Executes the minimum mean cycle-canceling algorithm - /// using \ref lemon::MinMeanCycle "MinMeanCycle" class. + /// using \ref MinMeanCycle. bool start() { typedef Path ResPath; MinMeanCycle mmc(res_graph, res_cost); @@ -444,42 +429,42 @@ #endif mmc.cyclePath(cycle).init(); if (mmc.findMinMean()) { - while (mmc.cycleLength() < 0) { + while (mmc.cycleLength() < 0) { #ifdef _DEBUG_ITER_ - ++iter; + ++cycle_num; #endif - // Finding the cycle - mmc.findCycle(); + // Finding the cycle + mmc.findCycle(); - // Finding the largest flow amount that can be augmented - // along the cycle - Capacity delta = 0; - for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) { - if (delta == 0 || res_graph.rescap(e) < delta) - delta = res_graph.rescap(e); - } + // Finding the largest flow amount that can be augmented + // along the cycle + Capacity delta = 0; + for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) { + if (delta == 0 || res_graph.rescap(e) < delta) + delta = res_graph.rescap(e); + } - // Augmenting along the cycle - for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) - res_graph.augment(e, delta); + // Augmenting along the cycle + for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) + res_graph.augment(e, delta); - // Finding the minimum cycle mean for the modified residual - // graph - mmc.reset(); - if (!mmc.findMinMean()) break; - } + // Finding the minimum cycle mean for the modified residual + // graph + mmc.reset(); + if (!mmc.findMinMean()) break; + } } #ifdef _DEBUG_ITER_ std::cout << "Minimum mean cycle-canceling algorithm finished. " - << "Found " << cycle_num << " negative cycles." - << std::endl; + << "Found " << cycle_num << " negative cycles." + << std::endl; #endif - // Handling nonzero lower bounds + // Handling non-zero lower bounds if (lower) { - for (EdgeIt e(graph); e != INVALID; ++e) - flow[e] += (*lower)[e]; + for (EdgeIt e(graph); e != INVALID; ++e) + flow[e] += (*lower)[e]; } return true; } diff -r a84e52e99f57 -r 74c2c81055e1 lemon/min_cost_flow.h --- a/lemon/min_cost_flow.h Sun Jan 13 10:26:55 2008 +0000 +++ b/lemon/min_cost_flow.h Sun Jan 13 10:32:14 2008 +0000 @@ -33,19 +33,22 @@ /// \brief An efficient algorithm for finding a minimum cost flow. /// - /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient - /// algorithm for finding a minimum cost flow. + /// \ref MinCostFlow provides an efficient algorithm for finding + /// a minimum cost flow. /// - /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for - /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most - /// efficient implementation for the minimum cost flow problem in the - /// LEMON library according to our benchmark tests. + /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex, + /// which is the most efficient implementation for the minimum cost + /// flow problem in the LEMON library according to our benchmark + /// tests. /// /// \note There are three implementations for the minimum cost flow - /// problem, that can be used in the same way. - /// - \ref lemon::CapacityScaling "CapacityScaling" - /// - \ref lemon::CycleCanceling "CycleCanceling" - /// - \ref lemon::NetworkSimplex "NetworkSimplex" + /// problem, that can be used exactly the same way. + /// - \ref CapacityScaling + /// - \ref CycleCanceling + /// - \ref NetworkSimplex + /// + /// \note For the detailed documentation of this class see + /// \ref NetworkSimplex. /// /// \param Graph The directed graph type the algorithm runs on. /// \param LowerMap The type of the lower bound map. @@ -54,12 +57,12 @@ /// \param SupplyMap The type of the supply map. /// /// \warning - /// - Edge capacities and costs should be nonnegative integers. - /// However \c CostMap::Value should be signed type. + /// - 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. + /// \c CapacityMap::Value and \c CapacityMap::Value must be + /// convertible to \c SupplyMap::Value. /// /// \author Peter Kovacs @@ -70,53 +73,49 @@ typename SupplyMap = typename Graph::template NodeMap > class MinCostFlow : - public NetworkSimplex< Graph, - LowerMap, - CapacityMap, - CostMap, - SupplyMap > + public NetworkSimplex< Graph, LowerMap, CapacityMap, + CostMap, SupplyMap > { typedef NetworkSimplex< Graph, LowerMap, CapacityMap, - CostMap, SupplyMap > - MinCostFlowImpl; + CostMap, SupplyMap > MinCostFlowImpl; typedef typename Graph::Node Node; typedef typename SupplyMap::Value Supply; public: - /// \brief General constructor of the class (with lower bounds). - MinCostFlow( const Graph &_graph, - const LowerMap &_lower, - const CapacityMap &_capacity, - const CostMap &_cost, - const SupplyMap &_supply ) : - MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {} + /// General constructor of the class (with lower bounds). + MinCostFlow( const Graph &graph, + const LowerMap &lower, + const CapacityMap &capacity, + const CostMap &cost, + const SupplyMap &supply ) : + MinCostFlowImpl(graph, lower, capacity, cost, supply) {} - /// \brief General constructor of the class (without lower bounds). - MinCostFlow( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - const SupplyMap &_supply ) : - MinCostFlowImpl(_graph, _capacity, _cost, _supply) {} + /// General constructor of the class (without lower bounds). + MinCostFlow( const Graph &graph, + const CapacityMap &capacity, + const CostMap &_ost, + const SupplyMap &supply ) : + MinCostFlowImpl(graph, capacity, cost, supply) {} - /// \brief Simple constructor of the class (with lower bounds). - MinCostFlow( const Graph &_graph, - const LowerMap &_lower, - const CapacityMap &_capacity, - const CostMap &_cost, - Node _s, Node _t, - Supply _flow_value ) : - MinCostFlowImpl( _graph, _lower, _capacity, _cost, - _s, _t, _flow_value ) {} + /// Simple constructor of the class (with lower bounds). + MinCostFlow( const Graph &graph, + const LowerMap &lower, + const CapacityMap &capacity, + const CostMap &_ost, + Node s, Node t, + Supply flow_value ) : + MinCostFlowImpl( graph, lower, capacity, cost, + s, t, flow_value ) {} - /// \brief Simple constructor of the class (without lower bounds). - MinCostFlow( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - Node _s, Node _t, - Supply _flow_value ) : - MinCostFlowImpl( _graph, _capacity, _cost, - _s, _t, _flow_value ) {} + /// Simple constructor of the class (without lower bounds). + MinCostFlow( const Graph &graph, + const CapacityMap &capacity, + const CostMap &cost, + Node s, Node t, + Supply flow_value ) : + MinCostFlowImpl( graph, capacity, cost, + s, t, flow_value ) {} }; //class MinCostFlow diff -r a84e52e99f57 -r 74c2c81055e1 lemon/min_cost_max_flow.h --- a/lemon/min_cost_max_flow.h Sun Jan 13 10:26:55 2008 +0000 +++ b/lemon/min_cost_max_flow.h Sun Jan 13 10:32:14 2008 +0000 @@ -22,8 +22,7 @@ /// \ingroup min_cost_flow /// /// \file -/// \brief An efficient algorithm for finding a minimum cost maximum -/// flow. +/// \brief An efficient algorithm for finding a minimum cost maximum flow. #include #include @@ -34,68 +33,65 @@ /// \addtogroup min_cost_flow /// @{ - /// \brief An efficient algorithm for finding a minimum cost maximum - /// flow. + /// \brief An efficient algorithm for finding a minimum cost + /// maximum flow. /// - /// \ref lemon::MinCostFlow "MinCostMaxFlow" implements an efficient - /// algorithm for finding a maximum flow having minimal total cost - /// from a given source node to a given target node in a directed - /// graph. + /// \ref MinCostMaxFlow implements an efficient algorithm for + /// finding a maximum flow having minimal total cost from a given + /// source node to a given target node in a directed graph. /// - /// \note \ref lemon::MinCostMaxFlow "MinCostMaxFlow" uses - /// \ref lemon::Preflow "Preflow" algorithm for finding the maximum - /// flow value and \ref lemon::NetworkSimplex "NetworkSimplex" - /// algorithm for finding a minimum cost flow of that value. + /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding + /// the maximum flow value and \ref NetworkSimplex algorithm for + /// finding a minimum cost flow of that value. /// /// \param Graph The directed graph type the algorithm runs on. /// \param CapacityMap The type of the capacity (upper bound) map. /// \param CostMap The type of the cost (length) map. /// /// \warning - /// - Edge capacities and costs should be nonnegative integers. - /// However \c CostMap::Value should be signed type. + /// - Edge capacities and costs should be non-negative integers. + /// However \c CostMap::Value should be signed type. /// /// \author Peter Kovacs template < typename Graph, - typename CapacityMap = typename Graph::template EdgeMap, - typename CostMap = typename Graph::template EdgeMap > + typename CapacityMap = typename Graph::template EdgeMap, + typename CostMap = typename Graph::template EdgeMap > class MinCostMaxFlow { typedef typename Graph::Node Node; typedef typename Graph::Edge Edge; typedef typename CapacityMap::Value Capacity; + typedef typename CostMap::Value Cost; typedef typename Graph::template NodeMap SupplyMap; typedef NetworkSimplex< Graph, CapacityMap, CapacityMap, - CostMap, SupplyMap > + CostMap, SupplyMap > MinCostFlowImpl; public: - /// \brief The type of the flow map. + /// The type of the flow map. typedef typename Graph::template EdgeMap FlowMap; - typedef typename CostMap::Value Cost; private: - /// \brief The directed graph the algorithm runs on. + /// The directed graph the algorithm runs on. const Graph &graph; - /// \brief The modified capacity map. + /// The modified capacity map. const CapacityMap &capacity; - /// \brief The cost map. + /// The cost map. const CostMap &cost; - /// \brief The source node. + /// The edge map of the found flow. + FlowMap flow; + /// The source node. Node source; - /// \brief The target node. + /// The target node. Node target; - /// \brief The edge map of the found flow. - FlowMap flow; - typedef Preflow PreflowImpl; - /// \brief \ref lemon::Preflow "Preflow" class for finding the - /// maximum flow value. - PreflowImpl preflow; + typedef Preflow MaxFlowImpl; + /// \brief \ref Preflow class for finding the maximum flow value. + MaxFlowImpl preflow; public: @@ -109,9 +105,9 @@ /// \param _s The source node. /// \param _t The target node. MinCostMaxFlow( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - Node _s, Node _t ) : + const CapacityMap &_capacity, + const CostMap &_cost, + Node _s, Node _t ) : graph(_graph), capacity(_capacity), cost(_cost), source(_s), target(_t), flow(_graph), preflow(_graph, _capacity, _s, _t) @@ -135,7 +131,7 @@ Cost totalCost() const { Cost c = 0; for (typename Graph::EdgeIt e(graph); e != INVALID; ++e) - c += flow[e] * cost[e]; + c += flow[e] * cost[e]; return c; } @@ -144,7 +140,7 @@ preflow.flowMap(flow); preflow.runMinCut(); MinCostFlowImpl mcf_impl( graph, capacity, cost, - source, target, preflow.flowValue() ); + source, target, preflow.flowValue() ); mcf_impl.run(); flow = mcf_impl.flowMap(); } diff -r a84e52e99f57 -r 74c2c81055e1 lemon/network_simplex.h --- a/lemon/network_simplex.h Sun Jan 13 10:26:55 2008 +0000 +++ b/lemon/network_simplex.h Sun Jan 13 10:32:14 2008 +0000 @@ -22,8 +22,7 @@ /// \ingroup min_cost_flow /// /// \file -/// \brief The network simplex algorithm for finding a minimum cost -/// flow. +/// \brief The network simplex algorithm for finding a minimum cost flow. #include #include @@ -40,30 +39,29 @@ //#define _DEBUG_ITER_ -/// \brief State constant for edges at their lower bounds. -#define LOWER 1 -/// \brief State constant for edges in the spanning tree. -#define TREE 0 -/// \brief State constant for edges at their upper bounds. -#define UPPER -1 +// State constant for edges at their lower bounds. +#define LOWER 1 +// State constant for edges in the spanning tree. +#define TREE 0 +// State constant for edges at their upper bounds. +#define UPPER -1 #ifdef EDGE_BLOCK_PIVOT #include - /// \brief Lower bound for the size of blocks. - #define MIN_BLOCK_SIZE 10 + #define MIN_BLOCK_SIZE 10 #endif #ifdef CANDIDATE_LIST_PIVOT #include - #define LIST_LENGTH_DIV 50 - #define MINOR_LIMIT_DIV 200 + #define LIST_LENGTH_DIV 50 + #define MINOR_LIMIT_DIV 200 #endif #ifdef SORTED_LIST_PIVOT #include #include #define LIST_LENGTH_DIV 100 - #define LOWER_DIV 4 + #define LOWER_DIV 4 #endif namespace lemon { @@ -74,8 +72,8 @@ /// \brief Implementation of the network simplex algorithm for /// finding a minimum cost flow. /// - /// \ref lemon::NetworkSimplex "NetworkSimplex" implements the - /// network simplex algorithm for finding a minimum cost flow. + /// \ref NetworkSimplex implements the network simplex algorithm for + /// finding a minimum cost flow. /// /// \param Graph The directed graph type the algorithm runs on. /// \param LowerMap The type of the lower bound map. @@ -84,12 +82,12 @@ /// \param SupplyMap The type of the supply map. /// /// \warning - /// - Edge capacities and costs should be nonnegative integers. - /// However \c CostMap::Value should be signed type. + /// - 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. + /// \c CapacityMap::Value and \c CapacityMap::Value must be + /// convertible to \c SupplyMap::Value. /// /// \author Peter Kovacs @@ -107,12 +105,7 @@ typedef typename SupplyMap::Value Supply; typedef SmartGraph SGraph; - typedef typename SGraph::Node Node; - typedef typename SGraph::NodeIt NodeIt; - typedef typename SGraph::Edge Edge; - typedef typename SGraph::EdgeIt EdgeIt; - typedef typename SGraph::InEdgeIt InEdgeIt; - typedef typename SGraph::OutEdgeIt OutEdgeIt; + GRAPH_TYPEDEFS(typename SGraph); typedef typename SGraph::template EdgeMap SLowerMap; typedef typename SGraph::template EdgeMap SCapacityMap; @@ -131,14 +124,14 @@ public: - /// \brief The type of the flow map. + /// The type of the flow map. typedef typename Graph::template EdgeMap FlowMap; - /// \brief The type of the potential map. + /// The type of the potential map. typedef typename Graph::template NodeMap PotentialMap; protected: - /// \brief Map adaptor class for handling reduced edge costs. + /// Map adaptor class for handling reduced edge costs. class ReducedCostMap : public MapBase { private: @@ -150,65 +143,73 @@ public: ReducedCostMap( const SGraph &_gr, - const SCostMap &_cm, - const SPotentialMap &_pm ) : - gr(_gr), cost_map(_cm), pot_map(_pm) {} + const SCostMap &_cm, + const SPotentialMap &_pm ) : + gr(_gr), cost_map(_cm), pot_map(_pm) {} Cost operator[](const Edge &e) const { - return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; + return cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)]; } }; //class ReducedCostMap protected: - /// \brief The directed graph the algorithm runs on. + /// The directed graph the algorithm runs on. SGraph graph; - /// \brief The original graph. + /// The original graph. const Graph &graph_ref; - /// \brief The original lower bound map. + /// The original lower bound map. const LowerMap *lower; - /// \brief The capacity map. + /// The capacity map. SCapacityMap capacity; - /// \brief The cost map. + /// The cost map. SCostMap cost; - /// \brief The supply map. + /// The supply map. SSupplyMap supply; - /// \brief The reduced cost map. + /// The reduced cost map. ReducedCostMap red_cost; - /// \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. SCapacityMap flow; - /// \brief The edge map of the found flow on the original graph. + /// The potential node map. + SPotentialMap potential; FlowMap flow_result; - /// \brief The potential node map. - SPotentialMap potential; - /// \brief The potential node map on the original graph. PotentialMap potential_result; - /// \brief Node reference for the original graph. + /// Node reference for the original graph. NodeRefMap node_ref; - /// \brief Edge reference for the original graph. + /// Edge reference for the original graph. EdgeRefMap edge_ref; - /// \brief The depth node map of the spanning tree structure. + /// The \c depth node map of the spanning tree structure. IntNodeMap depth; - /// \brief The parent node map of the spanning tree structure. + /// The \c parent node map of the spanning tree structure. NodeNodeMap parent; - /// \brief The pred_edge node map of the spanning tree structure. + /// The \c pred_edge node map of the spanning tree structure. EdgeNodeMap pred_edge; - /// \brief The thread node map of the spanning tree structure. + /// The \c thread node map of the spanning tree structure. NodeNodeMap thread; - /// \brief The forward node map of the spanning tree structure. + /// The \c forward node map of the spanning tree structure. BoolNodeMap forward; - /// \brief The state edge map. + /// The state edge map. IntEdgeMap state; + /// The root node of the starting spanning tree. + Node root; + // The entering edge of the current pivot iteration. + Edge in_edge; + // Temporary nodes used in the current pivot iteration. + Node join, u_in, v_in, u_out, v_out; + Node right, first, second, last; + Node stem, par_stem, new_stem; + // The maximum augment amount along the found cycle in the current + // pivot iteration. + Capacity delta; #ifdef EDGE_BLOCK_PIVOT - /// \brief The size of blocks for the "Edge Block" pivot rule. + /// The size of blocks for the "Edge Block" pivot rule. int block_size; #endif #ifdef CANDIDATE_LIST_PIVOT @@ -234,18 +235,6 @@ int list_index; #endif - // Root node of the starting spanning tree. - Node root; - // The entering edge of the current pivot iteration. - Edge in_edge; - // Temporary nodes used in the current pivot iteration. - Node join, u_in, v_in, u_out, v_out; - Node right, first, second, last; - Node stem, par_stem, new_stem; - // The maximum augment amount along the cycle in the current pivot - // iteration. - Capacity delta; - public : /// \brief General constructor of the class (with lower bounds). @@ -258,10 +247,10 @@ /// \param _cost The cost (length) values of the edges. /// \param _supply The supply values of the nodes (signed). NetworkSimplex( const Graph &_graph, - const LowerMap &_lower, - const CapacityMap &_capacity, - const CostMap &_cost, - const SupplyMap &_supply ) : + const LowerMap &_lower, + const CapacityMap &_capacity, + const CostMap &_cost, + const SupplyMap &_supply ) : graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph), supply(graph), flow(graph), flow_result(_graph), potential(graph), potential_result(_graph), depth(graph), parent(graph), @@ -272,29 +261,29 @@ // Checking the sum of supply values Supply sum = 0; for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) - sum += _supply[n]; + sum += _supply[n]; if (!(valid_supply = sum == 0)) return; // Copying graph_ref to graph graph.reserveNode(countNodes(graph_ref) + 1); graph.reserveEdge(countEdges(graph_ref) + countNodes(graph_ref)); copyGraph(graph, graph_ref) - .edgeMap(cost, _cost) - .nodeRef(node_ref) - .edgeRef(edge_ref) - .run(); + .edgeMap(cost, _cost) + .nodeRef(node_ref) + .edgeRef(edge_ref) + .run(); - // Removing nonzero lower bounds + // Removing non-zero lower bounds for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) { - capacity[edge_ref[e]] = _capacity[e] - _lower[e]; + capacity[edge_ref[e]] = _capacity[e] - _lower[e]; } for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) { - Supply s = _supply[n]; - for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e) - s += _lower[e]; - for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e) - s -= _lower[e]; - supply[node_ref[n]] = s; + Supply s = _supply[n]; + for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e) + s += _lower[e]; + for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e) + s -= _lower[e]; + supply[node_ref[n]] = s; } } @@ -307,9 +296,9 @@ /// \param _cost The cost (length) values of the edges. /// \param _supply The supply values of the nodes (signed). NetworkSimplex( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - const SupplyMap &_supply ) : + const CapacityMap &_capacity, + const CostMap &_cost, + const SupplyMap &_supply ) : graph_ref(_graph), lower(NULL), capacity(graph), cost(graph), supply(graph), flow(graph), flow_result(_graph), potential(graph), potential_result(_graph), depth(graph), parent(graph), @@ -320,17 +309,17 @@ // Checking the sum of supply values Supply sum = 0; for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) - sum += _supply[n]; + sum += _supply[n]; if (!(valid_supply = sum == 0)) return; // Copying graph_ref to graph copyGraph(graph, graph_ref) - .edgeMap(capacity, _capacity) - .edgeMap(cost, _cost) - .nodeMap(supply, _supply) - .nodeRef(node_ref) - .edgeRef(edge_ref) - .run(); + .edgeMap(capacity, _capacity) + .edgeMap(cost, _cost) + .nodeMap(supply, _supply) + .nodeRef(node_ref) + .edgeRef(edge_ref) + .run(); } /// \brief Simple constructor of the class (with lower bounds). @@ -344,15 +333,14 @@ /// \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 - /// \c _t). + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). NetworkSimplex( const Graph &_graph, - const LowerMap &_lower, - const CapacityMap &_capacity, - const CostMap &_cost, - typename Graph::Node _s, - typename Graph::Node _t, - typename SupplyMap::Value _flow_value ) : + const LowerMap &_lower, + const CapacityMap &_capacity, + const CostMap &_cost, + typename Graph::Node _s, + typename Graph::Node _t, + typename SupplyMap::Value _flow_value ) : graph_ref(_graph), lower(&_lower), capacity(graph), cost(graph), supply(graph), flow(graph), flow_result(_graph), potential(graph), potential_result(_graph), depth(graph), parent(graph), @@ -362,24 +350,24 @@ { // Copying graph_ref to graph copyGraph(graph, graph_ref) - .edgeMap(cost, _cost) - .nodeRef(node_ref) - .edgeRef(edge_ref) - .run(); + .edgeMap(cost, _cost) + .nodeRef(node_ref) + .edgeRef(edge_ref) + .run(); - // Removing nonzero lower bounds + // Removing non-zero lower bounds for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) { - capacity[edge_ref[e]] = _capacity[e] - _lower[e]; + capacity[edge_ref[e]] = _capacity[e] - _lower[e]; } for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) { - Supply s = 0; - if (n == _s) s = _flow_value; - if (n == _t) s = -_flow_value; - for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e) - s += _lower[e]; - for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e) - s -= _lower[e]; - supply[node_ref[n]] = s; + Supply s = 0; + if (n == _s) s = _flow_value; + if (n == _t) s = -_flow_value; + for (typename Graph::InEdgeIt e(graph_ref, n); e != INVALID; ++e) + s += _lower[e]; + for (typename Graph::OutEdgeIt e(graph_ref, n); e != INVALID; ++e) + s -= _lower[e]; + supply[node_ref[n]] = s; } valid_supply = true; } @@ -394,14 +382,13 @@ /// \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 - /// \c _t). + /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). NetworkSimplex( const Graph &_graph, - const CapacityMap &_capacity, - const CostMap &_cost, - typename Graph::Node _s, - typename Graph::Node _t, - typename SupplyMap::Value _flow_value ) : + const CapacityMap &_capacity, + const CostMap &_cost, + typename Graph::Node _s, + typename Graph::Node _t, + typename SupplyMap::Value _flow_value ) : graph_ref(_graph), lower(NULL), capacity(graph), cost(graph), supply(graph, 0), flow(graph), flow_result(_graph), potential(graph), potential_result(_graph), depth(graph), parent(graph), @@ -411,16 +398,25 @@ { // Copying graph_ref to graph copyGraph(graph, graph_ref) - .edgeMap(capacity, _capacity) - .edgeMap(cost, _cost) - .nodeRef(node_ref) - .edgeRef(edge_ref) - .run(); + .edgeMap(capacity, _capacity) + .edgeMap(cost, _cost) + .nodeRef(node_ref) + .edgeRef(edge_ref) + .run(); supply[node_ref[_s]] = _flow_value; supply[node_ref[_t]] = -_flow_value; valid_supply = true; } + /// \brief Runs the algorithm. + /// + /// Runs the algorithm. + /// + /// \return \c true if a feasible flow can be found. + bool run() { + return init() && start(); + } + /// \brief Returns a const reference to the flow map. /// /// Returns a const reference to the flow map. @@ -450,19 +446,10 @@ Cost totalCost() const { Cost c = 0; for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) - c += flow_result[e] * cost[edge_ref[e]]; + c += flow_result[e] * cost[edge_ref[e]]; return c; } - /// \brief Runs the algorithm. - /// - /// Runs the algorithm. - /// - /// \return \c true if a feasible flow can be found. - bool run() { - return init() && start(); - } - protected: /// \brief Extends the underlaying graph and initializes all the @@ -472,8 +459,8 @@ // Initializing state and flow maps for (EdgeIt e(graph); e != INVALID; ++e) { - flow[e] = 0; - state[e] = LOWER; + flow[e] = 0; + state[e] = LOWER; } // Adding an artificial root node to the graph @@ -491,27 +478,27 @@ Edge e; Cost max_cost = std::numeric_limits::max() / 4; for (NodeIt u(graph); u != INVALID; ++u) { - if (u == root) continue; - thread[last] = u; - last = u; - parent[u] = root; - depth[u] = 1; - sum += supply[u]; - if (supply[u] >= 0) { - e = graph.addEdge(u, root); - flow[e] = supply[u]; - forward[u] = true; - potential[u] = max_cost; - } else { - e = graph.addEdge(root, u); - flow[e] = -supply[u]; - forward[u] = false; - potential[u] = -max_cost; - } - cost[e] = max_cost; - capacity[e] = std::numeric_limits::max(); - state[e] = TREE; - pred_edge[u] = e; + if (u == root) continue; + thread[last] = u; + last = u; + parent[u] = root; + depth[u] = 1; + sum += supply[u]; + if (supply[u] >= 0) { + e = graph.addEdge(u, root); + flow[e] = supply[u]; + forward[u] = true; + potential[u] = max_cost; + } else { + e = graph.addEdge(root, u); + flow[e] = -supply[u]; + forward[u] = false; + potential[u] = -max_cost; + } + cost[e] = max_cost; + capacity[e] = std::numeric_limits::max(); + state[e] = TREE; + pred_edge[u] = e; } thread[last] = root; @@ -520,8 +507,6 @@ int edge_num = countEdges(graph); block_size = 2 * int(sqrt(countEdges(graph))); if (block_size < MIN_BLOCK_SIZE) block_size = MIN_BLOCK_SIZE; -// block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ? -// edge_num / BLOCK_NUM : MIN_BLOCK_SIZE; #endif #ifdef CANDIDATE_LIST_PIVOT int edge_num = countEdges(graph); @@ -543,18 +528,18 @@ /// pivot rule. bool findEnteringEdge(EdgeIt &next_edge) { for (EdgeIt e = next_edge; e != INVALID; ++e) { - if (state[e] * red_cost[e] < 0) { - in_edge = e; - next_edge = ++e; - return true; - } + if (state[e] * red_cost[e] < 0) { + in_edge = e; + next_edge = ++e; + return true; + } } for (EdgeIt e(graph); e != next_edge; ++e) { - if (state[e] * red_cost[e] < 0) { - in_edge = e; - next_edge = ++e; - return true; - } + if (state[e] * red_cost[e] < 0) { + in_edge = e; + next_edge = ++e; + return true; + } } return false; } @@ -566,10 +551,10 @@ bool findEnteringEdge() { Cost min = 0; for (EdgeIt e(graph); e != INVALID; ++e) { - if (state[e] * red_cost[e] < min) { - min = state[e] * red_cost[e]; - in_edge = e; - } + if (state[e] * red_cost[e] < min) { + min = state[e] * red_cost[e]; + in_edge = e; + } } return min < 0; } @@ -584,30 +569,30 @@ EdgeIt min_edge(graph); int cnt = 0; for (EdgeIt e = next_edge; e != INVALID; ++e) { - if ((curr = state[e] * red_cost[e]) < min) { - min = curr; - min_edge = e; - } - if (++cnt == block_size) { - if (min < 0) break; - cnt = 0; - } + if ((curr = state[e] * red_cost[e]) < min) { + min = curr; + min_edge = e; + } + if (++cnt == block_size) { + if (min < 0) break; + cnt = 0; + } } if (!(min < 0)) { - for (EdgeIt e(graph); e != next_edge; ++e) { - if ((curr = state[e] * red_cost[e]) < min) { - min = curr; - min_edge = e; - } - if (++cnt == block_size) { - if (min < 0) break; - cnt = 0; - } - } + for (EdgeIt e(graph); e != next_edge; ++e) { + if ((curr = state[e] * red_cost[e]) < min) { + min = curr; + min_edge = e; + } + if (++cnt == block_size) { + if (min < 0) break; + cnt = 0; + } + } } in_edge = min_edge; if ((next_edge = ++min_edge) == INVALID) - next_edge = EdgeIt(graph); + next_edge = EdgeIt(graph); return min < 0; } #endif @@ -619,15 +604,15 @@ typedef typename std::vector::iterator ListIt; if (minor_count >= minor_limit || candidates.size() == 0) { - // Major iteration - candidates.clear(); - for (EdgeIt e(graph); e != INVALID; ++e) { - if (state[e] * red_cost[e] < 0) { - candidates.push_back(e); - if (candidates.size() == list_length) break; - } - } - if (candidates.size() == 0) return false; + // Major iteration + candidates.clear(); + for (EdgeIt e(graph); e != INVALID; ++e) { + if (state[e] * red_cost[e] < 0) { + candidates.push_back(e); + if (candidates.size() == list_length) break; + } + } + if (candidates.size() == 0) return false; } // Minor iteration @@ -636,10 +621,10 @@ Edge e; for (int i = 0; i < candidates.size(); ++i) { e = candidates[i]; - if (state[e] * red_cost[e] < min) { - min = state[e] * red_cost[e]; - in_edge = e; - } + if (state[e] * red_cost[e] < min) { + min = state[e] * red_cost[e]; + in_edge = e; + } } return true; } @@ -655,9 +640,9 @@ const ReducedCostMap &rc; public: SortFunc(const IntEdgeMap &_st, const ReducedCostMap &_rc) : - st(_st), rc(_rc) {} + st(_st), rc(_rc) {} bool operator()(const Edge &e1, const Edge &e2) { - return st[e1] * rc[e1] < st[e2] * rc[e2]; + return st[e1] * rc[e1] < st[e2] * rc[e2]; } }; @@ -668,19 +653,19 @@ // Minor iteration while (list_index < candidates.size()) { - in_edge = candidates[list_index++]; - if (state[in_edge] * red_cost[in_edge] < 0) return true; + in_edge = candidates[list_index++]; + if (state[in_edge] * red_cost[in_edge] < 0) return true; } // Major iteration candidates.clear(); Cost curr, min = 0; for (EdgeIt e(graph); e != INVALID; ++e) { - if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) { - candidates.push_back(e); - if (curr < min) min = curr; - if (candidates.size() == list_length) break; - } + if ((curr = state[e] * red_cost[e]) < min / LOWER_DIV) { + candidates.push_back(e); + if (curr < min) min = curr; + if (candidates.size() == list_length) break; + } } if (candidates.size() == 0) return false; sort(candidates.begin(), candidates.end(), sort_func); @@ -696,12 +681,12 @@ Node u = graph.source(in_edge); Node v = graph.target(in_edge); while (u != v) { - if (depth[u] == depth[v]) { - u = parent[u]; - v = parent[v]; - } - else if (depth[u] > depth[v]) u = parent[u]; - else v = parent[v]; + if (depth[u] == depth[v]) { + u = parent[u]; + v = parent[v]; + } + else if (depth[u] > depth[v]) u = parent[u]; + else v = parent[v]; } return u; } @@ -712,11 +697,11 @@ // Initializing first and second nodes according to the direction // of the cycle if (state[in_edge] == LOWER) { - first = graph.source(in_edge); - second = graph.target(in_edge); + first = graph.source(in_edge); + second = graph.target(in_edge); } else { - first = graph.target(in_edge); - second = graph.source(in_edge); + first = graph.target(in_edge); + second = graph.source(in_edge); } delta = capacity[in_edge]; bool result = false; @@ -726,56 +711,56 @@ // Searching the cycle along the path form the first node to the // root node for (Node u = first; u != join; u = parent[u]) { - e = pred_edge[u]; - d = forward[u] ? flow[e] : capacity[e] - flow[e]; - if (d < delta) { - delta = d; - u_out = u; - u_in = first; - v_in = second; - result = true; - } + e = pred_edge[u]; + d = forward[u] ? flow[e] : capacity[e] - flow[e]; + if (d < delta) { + delta = d; + u_out = u; + u_in = first; + v_in = second; + result = true; + } } // Searching the cycle along the path form the second node to the // root node for (Node u = second; u != join; u = parent[u]) { - e = pred_edge[u]; - d = forward[u] ? capacity[e] - flow[e] : flow[e]; - if (d <= delta) { - delta = d; - u_out = u; - u_in = second; - v_in = first; - result = true; - } + e = pred_edge[u]; + d = forward[u] ? capacity[e] - flow[e] : flow[e]; + if (d <= delta) { + delta = d; + u_out = u; + u_in = second; + v_in = first; + result = true; + } } return result; } - /// \brief Changes flow and state edge maps. + /// \brief Changes \c flow and \c state edge maps. void changeFlows(bool change) { // Augmenting along the cycle if (delta > 0) { - Capacity val = state[in_edge] * delta; - flow[in_edge] += val; - for (Node u = graph.source(in_edge); u != join; u = parent[u]) { - flow[pred_edge[u]] += forward[u] ? -val : val; - } - for (Node u = graph.target(in_edge); u != join; u = parent[u]) { - flow[pred_edge[u]] += forward[u] ? val : -val; - } + Capacity val = state[in_edge] * delta; + flow[in_edge] += val; + for (Node u = graph.source(in_edge); u != join; u = parent[u]) { + flow[pred_edge[u]] += forward[u] ? -val : val; + } + for (Node u = graph.target(in_edge); u != join; u = parent[u]) { + flow[pred_edge[u]] += forward[u] ? val : -val; + } } // Updating the state of the entering and leaving edges if (change) { - state[in_edge] = TREE; - state[pred_edge[u_out]] = - (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER; + state[in_edge] = TREE; + state[pred_edge[u_out]] = + (flow[pred_edge[u_out]] == 0) ? LOWER : UPPER; } else { - state[in_edge] = -state[in_edge]; + state[in_edge] = -state[in_edge]; } } - /// \brief Updates thread and parent node maps. + /// \brief Updates \c thread and \c parent node maps. void updateThreadParent() { Node u; v_out = parent[u_out]; @@ -783,12 +768,12 @@ // Handling the case when join and v_out coincide bool par_first = false; if (join == v_out) { - for (u = join; u != u_in && u != v_in; u = thread[u]) ; - if (u == v_in) { - par_first = true; - while (thread[u] != u_out) u = thread[u]; - first = u; - } + for (u = join; u != u_in && u != v_in; u = thread[u]) ; + if (u == v_in) { + par_first = true; + while (thread[u] != u_out) u = thread[u]; + first = u; + } } // Finding the last successor of u_in (u) and the node after it @@ -796,8 +781,8 @@ for (u = u_in; depth[thread[u]] > depth[u_in]; u = thread[u]) ; right = thread[u]; if (thread[v_in] == u_out) { - for (last = u; depth[last] > depth[u_out]; last = thread[last]) ; - if (last == u_out) last = thread[last]; + for (last = u; depth[last] > depth[u_out]; last = thread[last]) ; + if (last == u_out) last = thread[last]; } else last = thread[v_in]; @@ -805,65 +790,65 @@ thread[v_in] = stem = u_in; par_stem = v_in; while (stem != u_out) { - thread[u] = new_stem = parent[stem]; + thread[u] = new_stem = parent[stem]; - // Finding the node just before the stem node (u) according to - // the original thread index - for (u = new_stem; thread[u] != stem; u = thread[u]) ; - thread[u] = right; + // Finding the node just before the stem node (u) according to + // the original thread index + for (u = new_stem; thread[u] != stem; u = thread[u]) ; + thread[u] = right; - // Changing the parent node of stem and shifting stem and - // par_stem nodes - parent[stem] = par_stem; - par_stem = stem; - stem = new_stem; + // Changing the parent node of stem and shifting stem and + // par_stem nodes + parent[stem] = par_stem; + par_stem = stem; + stem = new_stem; - // Finding the last successor of stem (u) and the node after it - // (right) according to the thread index - for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ; - right = thread[u]; + // Finding the last successor of stem (u) and the node after it + // (right) according to the thread index + for (u = stem; depth[thread[u]] > depth[stem]; u = thread[u]) ; + right = thread[u]; } parent[u_out] = par_stem; thread[u] = last; if (join == v_out && par_first) { - if (first != v_in) thread[first] = right; + if (first != v_in) thread[first] = right; } else { - for (u = v_out; thread[u] != u_out; u = thread[u]) ; - thread[u] = right; + for (u = v_out; thread[u] != u_out; u = thread[u]) ; + thread[u] = right; } } - /// \brief Updates pred_edge and forward node maps. + /// \brief Updates \c pred_edge and \c forward node maps. void updatePredEdge() { Node u = u_out, v; while (u != u_in) { - v = parent[u]; - pred_edge[u] = pred_edge[v]; - forward[u] = !forward[v]; - u = v; + v = parent[u]; + pred_edge[u] = pred_edge[v]; + forward[u] = !forward[v]; + u = v; } pred_edge[u_in] = in_edge; forward[u_in] = (u_in == graph.source(in_edge)); } - /// \brief Updates depth and potential node maps. + /// \brief Updates \c depth and \c potential node maps. void updateDepthPotential() { depth[u_in] = depth[v_in] + 1; potential[u_in] = forward[u_in] ? - potential[v_in] + cost[pred_edge[u_in]] : - potential[v_in] - cost[pred_edge[u_in]]; + potential[v_in] + cost[pred_edge[u_in]] : + potential[v_in] - cost[pred_edge[u_in]]; Node u = thread[u_in], v; while (true) { - v = parent[u]; - if (v == INVALID) break; - depth[u] = depth[v] + 1; - potential[u] = forward[u] ? - potential[v] + cost[pred_edge[u]] : - potential[v] - cost[pred_edge[u]]; - if (depth[u] <= depth[v_in]) break; - u = thread[u]; + v = parent[u]; + if (v == INVALID) break; + depth[u] = depth[v] + 1; + potential[u] = forward[u] ? + potential[v] + cost[pred_edge[u]] : + potential[v] - cost[pred_edge[u]]; + if (depth[u] <= depth[v_in]) break; + u = thread[u]; } } @@ -880,42 +865,42 @@ while (findEnteringEdge()) #endif { - join = findJoinNode(); - bool change = findLeavingEdge(); - changeFlows(change); - if (change) { - updateThreadParent(); - updatePredEdge(); - updateDepthPotential(); - } + join = findJoinNode(); + bool change = findLeavingEdge(); + changeFlows(change); + if (change) { + updateThreadParent(); + updatePredEdge(); + updateDepthPotential(); + } #ifdef _DEBUG_ITER_ - ++iter_num; + ++iter_num; #endif } #ifdef _DEBUG_ITER_ std::cout << "Network Simplex algorithm finished. " << iter_num - << " pivot iterations performed." << std::endl; + << " pivot iterations performed." << std::endl; #endif // Checking if the flow amount equals zero on all the // artificial edges for (InEdgeIt e(graph, root); e != INVALID; ++e) - if (flow[e] > 0) return false; + if (flow[e] > 0) return false; for (OutEdgeIt e(graph, root); e != INVALID; ++e) - if (flow[e] > 0) return false; + if (flow[e] > 0) return false; // Copying flow values to flow_result if (lower) { - for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) - flow_result[e] = (*lower)[e] + flow[edge_ref[e]]; + for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) + flow_result[e] = (*lower)[e] + flow[edge_ref[e]]; } else { - for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) - flow_result[e] = flow[edge_ref[e]]; + for (typename Graph::EdgeIt e(graph_ref); e != INVALID; ++e) + flow_result[e] = flow[edge_ref[e]]; } // Copying potential values to potential_result for (typename Graph::NodeIt n(graph_ref); n != INVALID; ++n) - potential_result[n] = potential[node_ref[n]]; + potential_result[n] = potential[node_ref[n]]; return true; }