# HG changeset patch # User kpeter # Date 1204167267 0 # Node ID 054566ac093441af707d591fe758075f32e348d8 # Parent fa71d9612c4209fadfcd78d29b50b9924ac34020 Query improvements in the min cost flow algorithms. - External flow and potential maps can be used. - New query functions: flow() and potential(). - CycleCanceling also provides dual solution (node potentials). - Doc improvements. diff -r fa71d9612c42 -r 054566ac0934 lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h Wed Feb 27 11:39:03 2008 +0000 +++ b/lemon/capacity_scaling.h Thu Feb 28 02:54:27 2008 +0000 @@ -50,11 +50,8 @@ /// \warning /// - Edge capacities and costs should be \e non-negative \e integers. /// - Supply values should be \e signed \e integers. - /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. - /// - \c CapacityMap::Value and \c SupplyMap::Value must be - /// convertible to each other. - /// - All value types must be convertible to \c CostMap::Value, which - /// must be signed type. + /// - The value types of the maps should be convertible to each other. + /// - \c CostMap::Value must be signed type. /// /// \author Peter Kovacs @@ -120,7 +117,7 @@ public: - /// The constructor of the class. + /// Constructor. ResidualDijkstra( const Graph &graph, const FlowMap &flow, const CapacityEdgeMap &res_cap, @@ -221,9 +218,11 @@ bool _valid_supply; // Edge map of the current flow - FlowMap _flow; + FlowMap *_flow; + bool _local_flow; // Node map of the current potentials - PotentialMap _potential; + PotentialMap *_potential; + bool _local_potential; // The residual capacity map CapacityEdgeMap _res_cap; @@ -243,13 +242,13 @@ PredMap _pred; // Implementation of the Dijkstra algorithm for finding augmenting // shortest paths in the residual network - ResidualDijkstra _dijkstra; + ResidualDijkstra *_dijkstra; - public : + public: - /// \brief General constructor of the class (with lower bounds). + /// \brief General constructor (with lower bounds). /// - /// General constructor of the class (with lower bounds). + /// General constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -262,9 +261,9 @@ const CostMap &cost, const SupplyMap &supply ) : _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) + _supply(graph), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), + _res_cap(graph), _excess(graph), _pred(graph) { // Removing non-zero lower bounds _capacity = subMap(capacity, lower); @@ -282,9 +281,9 @@ _valid_supply = sum == 0; } - /// \brief General constructor of the class (without lower bounds). + /// \brief General constructor (without lower bounds). /// - /// General constructor of the class (without lower bounds). + /// General constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -295,9 +294,9 @@ const CostMap &cost, const SupplyMap &supply ) : _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), - _supply(supply), _flow(graph, 0), _potential(graph, 0), - _res_cap(capacity), _excess(graph), _pred(graph), - _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred) + _supply(supply), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), + _res_cap(capacity), _excess(graph), _pred(graph) { // Checking the sum of supply values Supply sum = 0; @@ -305,9 +304,9 @@ _valid_supply = sum == 0; } - /// \brief Simple constructor of the class (with lower bounds). + /// \brief Simple constructor (with lower bounds). /// - /// Simple constructor of the class (with lower bounds). + /// Simple constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -324,9 +323,9 @@ Node s, Node t, Supply flow_value ) : _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) + _supply(graph), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), + _res_cap(graph), _excess(graph), _pred(graph) { // Removing non-zero lower bounds _capacity = subMap(capacity, lower); @@ -344,9 +343,9 @@ _valid_supply = true; } - /// \brief Simple constructor of the class (without lower bounds). + /// \brief Simple constructor (without lower bounds). /// - /// Simple constructor of the class (without lower bounds). + /// Simple constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -361,15 +360,56 @@ Node s, Node t, Supply flow_value ) : _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), - _supply(graph, 0), _flow(graph, 0), _potential(graph, 0), - _res_cap(capacity), _excess(graph), _pred(graph), - _dijkstra(_graph, _flow, _res_cap, _cost, _excess, _potential, _pred) + _supply(graph, 0), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), + _res_cap(capacity), _excess(graph), _pred(graph) { _supply[s] = flow_value; _supply[t] = -flow_value; _valid_supply = true; } + /// Destructor. + ~CapacityScaling() { + if (_local_flow) delete _flow; + if (_local_potential) delete _potential; + delete _dijkstra; + } + + /// \brief Sets the flow map. + /// + /// Sets the flow map. + /// + /// \return \c (*this) + CapacityScaling& flowMap(FlowMap &map) { + if (_local_flow) { + delete _flow; + _local_flow = false; + } + _flow = ↦ + return *this; + } + + /// \brief Sets the potential map. + /// + /// Sets the potential map. + /// + /// \return \c (*this) + CapacityScaling& potentialMap(PotentialMap &map) { + if (_local_potential) { + delete _potential; + _local_potential = false; + } + _potential = ↦ + return *this; + } + + /// \name Execution control + /// The only way to execute the algorithm is to call the run() + /// function. + + /// @{ + /// \brief Runs the algorithm. /// /// Runs the algorithm. @@ -384,6 +424,15 @@ return init(scaling) && start(); } + /// @} + + /// \name Query Functions + /// The result of the algorithm can be obtained using these + /// functions. + /// \n run() must be called before using them. + + /// @{ + /// \brief Returns a const reference to the edge map storing the /// found flow. /// @@ -391,7 +440,7 @@ /// /// \pre \ref run() must be called before using this function. const FlowMap& flowMap() const { - return _flow; + return *_flow; } /// \brief Returns a const reference to the node map storing the @@ -402,7 +451,25 @@ /// /// \pre \ref run() must be called before using this function. const PotentialMap& potentialMap() const { - return _potential; + return *_potential; + } + + /// \brief Returns the flow on the edge. + /// + /// Returns the flow on the edge. + /// + /// \pre \ref run() must be called before using this function. + Capacity flow(const Edge& edge) const { + return (*_flow)[edge]; + } + + /// \brief Returns the potential of the node. + /// + /// Returns the potential of the node. + /// + /// \pre \ref run() must be called before using this function. + Cost potential(const Node& node) const { + return (*_potential)[node]; } /// \brief Returns the total cost of the found flow. @@ -414,18 +481,35 @@ 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; } + /// @} + private: /// Initializes the algorithm. bool init(bool scaling) { if (!_valid_supply) return false; + + // Initializing maps + if (!_flow) { + _flow = new FlowMap(_graph); + _local_flow = true; + } + if (!_potential) { + _potential = new PotentialMap(_graph); + _local_potential = true; + } + for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; + for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; _excess = _supply; - // Initilaizing delta value + _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost, + _excess, *_potential, _pred ); + + // Initializing delta value if (scaling) { // With scaling Supply max_sup = 0, max_dem = 0; @@ -441,6 +525,7 @@ // Without scaling _delta = 1; } + return true; } @@ -461,17 +546,17 @@ // Saturating all edges not satisfying the optimality condition for (EdgeIt e(_graph); e != INVALID; ++e) { Node u = _graph.source(e), v = _graph.target(e); - Cost c = _cost[e] + _potential[u] - _potential[v]; + Cost c = _cost[e] + (*_potential)[u] - (*_potential)[v]; if (c < 0 && _res_cap[e] >= _delta) { _excess[u] -= _res_cap[e]; _excess[v] += _res_cap[e]; - _flow[e] = _capacity[e]; + (*_flow)[e] = _capacity[e]; _res_cap[e] = 0; } - else if (c > 0 && _flow[e] >= _delta) { - _excess[u] += _flow[e]; - _excess[v] -= _flow[e]; - _flow[e] = 0; + else if (c > 0 && (*_flow)[e] >= _delta) { + _excess[u] += (*_flow)[e]; + _excess[v] -= (*_flow)[e]; + (*_flow)[e] = 0; _res_cap[e] = _capacity[e]; } } @@ -501,7 +586,7 @@ // Running Dijkstra s = _excess_nodes[next_node]; - if ((t = _dijkstra.run(s, _delta)) == INVALID) { + if ((t = _dijkstra->run(s, _delta)) == INVALID) { if (_delta > 1) { ++next_node; continue; @@ -520,7 +605,7 @@ rc = _res_cap[e]; u = _graph.source(e); } else { - rc = _flow[e]; + rc = (*_flow)[e]; u = _graph.target(e); } if (rc < d) d = rc; @@ -529,11 +614,11 @@ u = t; while ((e = _pred[u]) != INVALID) { if (u == _graph.target(e)) { - _flow[e] += d; + (*_flow)[e] += d; _res_cap[e] -= d; u = _graph.source(e); } else { - _flow[e] -= d; + (*_flow)[e] -= d; _res_cap[e] += d; u = _graph.target(e); } @@ -552,7 +637,7 @@ // Handling non-zero lower bounds if (_lower) { for (EdgeIt e(_graph); e != INVALID; ++e) - _flow[e] += (*_lower)[e]; + (*_flow)[e] += (*_lower)[e]; } return true; } @@ -572,7 +657,7 @@ { // Running Dijkstra s = _excess_nodes[next_node]; - if ((t = _dijkstra.run(s, 1)) == INVALID) + if ((t = _dijkstra->run(s, 1)) == INVALID) return false; // Augmenting along a shortest path from s to t @@ -585,7 +670,7 @@ rc = _res_cap[e]; u = _graph.source(e); } else { - rc = _flow[e]; + rc = (*_flow)[e]; u = _graph.target(e); } if (rc < d) d = rc; @@ -593,11 +678,11 @@ u = t; while ((e = _pred[u]) != INVALID) { if (u == _graph.target(e)) { - _flow[e] += d; + (*_flow)[e] += d; _res_cap[e] -= d; u = _graph.source(e); } else { - _flow[e] -= d; + (*_flow)[e] -= d; _res_cap[e] += d; u = _graph.target(e); } @@ -609,7 +694,7 @@ // Handling non-zero lower bounds if (_lower) { for (EdgeIt e(_graph); e != INVALID; ++e) - _flow[e] += (*_lower)[e]; + (*_flow)[e] += (*_lower)[e]; } return true; } diff -r fa71d9612c42 -r 054566ac0934 lemon/cost_scaling.h --- a/lemon/cost_scaling.h Wed Feb 27 11:39:03 2008 +0000 +++ b/lemon/cost_scaling.h Thu Feb 28 02:54:27 2008 +0000 @@ -54,11 +54,8 @@ /// \warning /// - Edge capacities and costs should be \e non-negative \e integers. /// - Supply values should be \e signed \e integers. - /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. - /// - \c CapacityMap::Value and \c SupplyMap::Value must be - /// convertible to each other. - /// - All value types must be convertible to \c CostMap::Value, which - /// must be signed type. + /// - The value types of the maps should be convertible to each other. + /// - \c CostMap::Value must be signed type. /// /// \note Edge costs are multiplied with the number of nodes during /// the algorithm so overflow problems may arise more easily than with @@ -97,7 +94,7 @@ public: /// The type of the flow map. - typedef CapacityEdgeMap FlowMap; + typedef typename Graph::template EdgeMap FlowMap; /// The type of the potential map. typedef typename Graph::template NodeMap PotentialMap; @@ -107,20 +104,21 @@ /// /// \ref ResidualCostMap is a map adaptor class for handling /// residual edge costs. - class ResidualCostMap : public MapBase + template + class ResidualCostMap : public MapBase { private: - const LargeCostMap &_cost_map; + const Map &_cost_map; public: ///\e - ResidualCostMap(const LargeCostMap &cost_map) : + ResidualCostMap(const Map &cost_map) : _cost_map(cost_map) {} ///\e - LCost operator[](const ResEdge &e) const { + typename Map::Value operator[](const ResEdge &e) const { return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e]; } @@ -160,8 +158,8 @@ static const int ALPHA = 4; // Paramters for heuristics - static const int BF_HEURISTIC_EPSILON_BOUND = 5000; - static const int BF_HEURISTIC_BOUND_FACTOR = 3; + static const int BF_HEURISTIC_EPSILON_BOUND = 5000; + static const int BF_HEURISTIC_BOUND_FACTOR = 3; private: @@ -180,16 +178,18 @@ bool _valid_supply; // Edge map of the current flow - FlowMap _flow; + FlowMap *_flow; + bool _local_flow; // Node map of the current potentials - PotentialMap _potential; + PotentialMap *_potential; + bool _local_potential; // The residual graph - ResGraph _res_graph; + ResGraph *_res_graph; // The residual cost map - ResidualCostMap _res_cost; + ResidualCostMap _res_cost; // The reduced cost map - ReducedCostMap _red_cost; + ReducedCostMap *_red_cost; // The excess map SupplyNodeMap _excess; // The epsilon parameter used for cost scaling @@ -197,9 +197,9 @@ public: - /// \brief General constructor of the class (with lower bounds). + /// \brief General constructor (with lower bounds). /// - /// General constructor of the class (with lower bounds). + /// General constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -212,9 +212,9 @@ const CostMap &cost, const SupplyMap &supply ) : _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), - _cost(graph), _supply(graph), _flow(graph, 0), _potential(graph, 0), - _res_graph(graph, _capacity, _flow), _res_cost(_cost), - _red_cost(graph, _cost, _potential), _excess(graph, 0) + _cost(graph), _supply(graph), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost), + _excess(graph, 0) { // Removing non-zero lower bounds _capacity = subMap(capacity, lower); @@ -231,9 +231,9 @@ _valid_supply = sum == 0; } - /// \brief General constructor of the class (without lower bounds). + /// \brief General constructor (without lower bounds). /// - /// General constructor of the class (without lower bounds). + /// General constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -244,9 +244,9 @@ const CostMap &cost, const SupplyMap &supply ) : _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), - _cost(graph), _supply(supply), _flow(graph, 0), _potential(graph, 0), - _res_graph(graph, _capacity, _flow), _res_cost(_cost), - _red_cost(graph, _cost, _potential), _excess(graph, 0) + _cost(graph), _supply(supply), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost), + _excess(graph, 0) { // Checking the sum of supply values Supply sum = 0; @@ -254,9 +254,9 @@ _valid_supply = sum == 0; } - /// \brief Simple constructor of the class (with lower bounds). + /// \brief Simple constructor (with lower bounds). /// - /// Simple constructor of the class (with lower bounds). + /// Simple constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -273,9 +273,9 @@ Node s, Node t, Supply flow_value ) : _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost), - _cost(graph), _supply(graph), _flow(graph, 0), _potential(graph, 0), - _res_graph(graph, _capacity, _flow), _res_cost(_cost), - _red_cost(graph, _cost, _potential), _excess(graph, 0) + _cost(graph), _supply(graph), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost), + _excess(graph, 0) { // Removing nonzero lower bounds _capacity = subMap(capacity, lower); @@ -292,9 +292,9 @@ _valid_supply = true; } - /// \brief Simple constructor of the class (without lower bounds). + /// \brief Simple constructor (without lower bounds). /// - /// Simple constructor of the class (without lower bounds). + /// Simple constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -309,24 +309,75 @@ Node s, Node t, Supply flow_value ) : _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost), - _cost(graph), _supply(graph, 0), _flow(graph, 0), _potential(graph, 0), - _res_graph(graph, _capacity, _flow), _res_cost(_cost), - _red_cost(graph, _cost, _potential), _excess(graph, 0) + _cost(graph), _supply(graph, 0), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost), + _excess(graph, 0) { _supply[s] = flow_value; _supply[t] = -flow_value; _valid_supply = true; } + /// Destructor. + ~CostScaling() { + if (_local_flow) delete _flow; + if (_local_potential) delete _potential; + delete _res_graph; + delete _red_cost; + } + + /// \brief Sets the flow map. + /// + /// Sets the flow map. + /// + /// \return \c (*this) + CostScaling& flowMap(FlowMap &map) { + if (_local_flow) { + delete _flow; + _local_flow = false; + } + _flow = ↦ + return *this; + } + + /// \brief Sets the potential map. + /// + /// Sets the potential map. + /// + /// \return \c (*this) + CostScaling& potentialMap(PotentialMap &map) { + if (_local_potential) { + delete _potential; + _local_potential = false; + } + _potential = ↦ + return *this; + } + + /// \name Execution control + /// The only way to execute the algorithm is to call the run() + /// function. + + /// @{ + /// \brief Runs the algorithm. /// /// Runs the algorithm. /// /// \return \c true if a feasible flow can be found. bool run() { - init() && start(); + return init() && start(); } + /// @} + + /// \name Query Functions + /// The result of the algorithm can be obtained using these + /// functions. + /// \n run() must be called before using them. + + /// @{ + /// \brief Returns a const reference to the edge map storing the /// found flow. /// @@ -334,7 +385,7 @@ /// /// \pre \ref run() must be called before using this function. const FlowMap& flowMap() const { - return _flow; + return *_flow; } /// \brief Returns a const reference to the node map storing the @@ -345,7 +396,25 @@ /// /// \pre \ref run() must be called before using this function. const PotentialMap& potentialMap() const { - return _potential; + return *_potential; + } + + /// \brief Returns the flow on the edge. + /// + /// Returns the flow on the edge. + /// + /// \pre \ref run() must be called before using this function. + Capacity flow(const Edge& edge) const { + return (*_flow)[edge]; + } + + /// \brief Returns the potential of the node. + /// + /// Returns the potential of the node. + /// + /// \pre \ref run() must be called before using this function. + Cost potential(const Node& node) const { + return (*_potential)[node]; } /// \brief Returns the total cost of the found flow. @@ -357,16 +426,31 @@ Cost totalCost() const { Cost c = 0; for (EdgeIt e(_graph); e != INVALID; ++e) - c += _flow[e] * _orig_cost[e]; + c += (*_flow)[e] * _orig_cost[e]; return c; } + /// @} + private: /// Initializes the algorithm. bool init() { if (!_valid_supply) return false; + // Initializing flow and potential maps + if (!_flow) { + _flow = new FlowMap(_graph); + _local_flow = true; + } + if (!_potential) { + _potential = new PotentialMap(_graph); + _local_potential = true; + } + + _red_cost = new ReducedCostMap(_graph, _cost, *_potential); + _res_graph = new ResGraph(_graph, _capacity, *_flow); + // Initializing the scaled cost map and the epsilon parameter Cost max_cost = 0; int node_num = countNodes(_graph); @@ -379,9 +463,9 @@ // Finding a feasible flow using Circulation Circulation< Graph, ConstMap, CapacityEdgeMap, SupplyMap > - circulation( _graph, constMap((Capacity)0), _capacity, + circulation( _graph, constMap(Capacity(0)), _capacity, _supply ); - return circulation.flowMap(_flow).run(); + return circulation.flowMap(*_flow).run(); } @@ -397,9 +481,9 @@ // Performing price refinement heuristic using Bellman-Ford // algorithm if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { - typedef ShiftMap ShiftCostMap; + typedef ShiftMap< ResidualCostMap > ShiftCostMap; ShiftCostMap shift_cost(_res_cost, _epsilon); - BellmanFord bf(_res_graph, shift_cost); + BellmanFord bf(*_res_graph, shift_cost); bf.init(0); bool done = false; int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(node_num)); @@ -407,7 +491,7 @@ done = bf.processNextWeakRound(); if (done) { for (NodeIt n(_graph); n != INVALID; ++n) - _potential[n] = bf.dist(n); + (*_potential)[n] = bf.dist(n); continue; } } @@ -415,16 +499,16 @@ // Saturating edges not satisfying the optimality condition Capacity delta; for (EdgeIt e(_graph); e != INVALID; ++e) { - if (_capacity[e] - _flow[e] > 0 && _red_cost[e] < 0) { - delta = _capacity[e] - _flow[e]; + if (_capacity[e] - (*_flow)[e] > 0 && (*_red_cost)[e] < 0) { + delta = _capacity[e] - (*_flow)[e]; _excess[_graph.source(e)] -= delta; _excess[_graph.target(e)] += delta; - _flow[e] = _capacity[e]; + (*_flow)[e] = _capacity[e]; } - if (_flow[e] > 0 && -_red_cost[e] < 0) { - _excess[_graph.target(e)] -= _flow[e]; - _excess[_graph.source(e)] += _flow[e]; - _flow[e] = 0; + if ((*_flow)[e] > 0 && -(*_red_cost)[e] < 0) { + _excess[_graph.target(e)] -= (*_flow)[e]; + _excess[_graph.source(e)] += (*_flow)[e]; + (*_flow)[e] = 0; } } @@ -440,26 +524,26 @@ // Performing push operations if there are admissible edges if (_excess[n] > 0) { for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { - if (_capacity[e] - _flow[e] > 0 && _red_cost[e] < 0) { - delta = _capacity[e] - _flow[e] <= _excess[n] ? - _capacity[e] - _flow[e] : _excess[n]; + if (_capacity[e] - (*_flow)[e] > 0 && (*_red_cost)[e] < 0) { + delta = _capacity[e] - (*_flow)[e] <= _excess[n] ? + _capacity[e] - (*_flow)[e] : _excess[n]; t = _graph.target(e); // Push-look-ahead heuristic Capacity ahead = -_excess[t]; for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) { - if (_capacity[oe] - _flow[oe] > 0 && _red_cost[oe] < 0) - ahead += _capacity[oe] - _flow[oe]; + if (_capacity[oe] - (*_flow)[oe] > 0 && (*_red_cost)[oe] < 0) + ahead += _capacity[oe] - (*_flow)[oe]; } for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) { - if (_flow[ie] > 0 && -_red_cost[ie] < 0) - ahead += _flow[ie]; + if ((*_flow)[ie] > 0 && -(*_red_cost)[ie] < 0) + ahead += (*_flow)[ie]; } if (ahead < 0) ahead = 0; // Pushing flow along the edge if (ahead < delta) { - _flow[e] += ahead; + (*_flow)[e] += ahead; _excess[n] -= ahead; _excess[t] += ahead; active_nodes.push_front(t); @@ -467,7 +551,7 @@ relabel_enabled = false; break; } else { - _flow[e] += delta; + (*_flow)[e] += delta; _excess[n] -= delta; _excess[t] += delta; if (_excess[t] > 0 && _excess[t] <= delta) @@ -481,25 +565,25 @@ if (_excess[n] > 0) { for (InEdgeIt e(_graph, n); e != INVALID; ++e) { - if (_flow[e] > 0 && -_red_cost[e] < 0) { - delta = _flow[e] <= _excess[n] ? _flow[e] : _excess[n]; + if ((*_flow)[e] > 0 && -(*_red_cost)[e] < 0) { + delta = (*_flow)[e] <= _excess[n] ? (*_flow)[e] : _excess[n]; t = _graph.source(e); // Push-look-ahead heuristic Capacity ahead = -_excess[t]; for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) { - if (_capacity[oe] - _flow[oe] > 0 && _red_cost[oe] < 0) - ahead += _capacity[oe] - _flow[oe]; + if (_capacity[oe] - (*_flow)[oe] > 0 && (*_red_cost)[oe] < 0) + ahead += _capacity[oe] - (*_flow)[oe]; } for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) { - if (_flow[ie] > 0 && -_red_cost[ie] < 0) - ahead += _flow[ie]; + if ((*_flow)[ie] > 0 && -(*_red_cost)[ie] < 0) + ahead += (*_flow)[ie]; } if (ahead < 0) ahead = 0; // Pushing flow along the edge if (ahead < delta) { - _flow[e] -= ahead; + (*_flow)[e] -= ahead; _excess[n] -= ahead; _excess[t] += ahead; active_nodes.push_front(t); @@ -507,7 +591,7 @@ relabel_enabled = false; break; } else { - _flow[e] -= delta; + (*_flow)[e] -= delta; _excess[n] -= delta; _excess[t] += delta; if (_excess[t] > 0 && _excess[t] <= delta) @@ -523,15 +607,15 @@ // Performing relabel operation if the node is still active LCost min_red_cost = std::numeric_limits::max(); for (OutEdgeIt oe(_graph, n); oe != INVALID; ++oe) { - if ( _capacity[oe] - _flow[oe] > 0 && - _red_cost[oe] < min_red_cost ) - min_red_cost = _red_cost[oe]; + if ( _capacity[oe] - (*_flow)[oe] > 0 && + (*_red_cost)[oe] < min_red_cost ) + min_red_cost = (*_red_cost)[oe]; } for (InEdgeIt ie(_graph, n); ie != INVALID; ++ie) { - if (_flow[ie] > 0 && -_red_cost[ie] < min_red_cost) - min_red_cost = -_red_cost[ie]; + if ((*_flow)[ie] > 0 && -(*_red_cost)[ie] < min_red_cost) + min_red_cost = -(*_red_cost)[ie]; } - _potential[n] -= min_red_cost + _epsilon; + (*_potential)[n] -= min_red_cost + _epsilon; hyper[n] = false; } @@ -544,10 +628,18 @@ } } + // Computing node potentials for the original costs + ResidualCostMap res_cost(_orig_cost); + BellmanFord< ResGraph, ResidualCostMap > + bf(*_res_graph, res_cost); + bf.init(0); bf.start(); + for (NodeIt n(_graph); n != INVALID; ++n) + (*_potential)[n] = bf.dist(n); + // Handling non-zero lower bounds if (_lower) { for (EdgeIt e(_graph); e != INVALID; ++e) - _flow[e] += (*_lower)[e]; + (*_flow)[e] += (*_lower)[e]; } return true; } diff -r fa71d9612c42 -r 054566ac0934 lemon/cycle_canceling.h --- a/lemon/cycle_canceling.h Wed Feb 27 11:39:03 2008 +0000 +++ b/lemon/cycle_canceling.h Thu Feb 28 02:54:27 2008 +0000 @@ -52,11 +52,8 @@ /// \warning /// - Edge capacities and costs should be \e non-negative \e integers. /// - Supply values should be \e signed \e integers. - /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. - /// - \c CapacityMap::Value and \c SupplyMap::Value must be - /// convertible to each other. - /// - All value types must be convertible to \c CostMap::Value, which - /// must be signed type. + /// - The value types of the maps should be convertible to each other. + /// - \c CostMap::Value must be signed type. /// /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is /// used for negative cycle detection with limited iteration number. @@ -94,6 +91,8 @@ /// The type of the flow map. typedef typename Graph::template EdgeMap FlowMap; + /// The type of the potential map. + typedef typename Graph::template NodeMap PotentialMap; private: @@ -143,18 +142,22 @@ bool _valid_supply; // Edge map of the current flow - FlowMap _flow; + FlowMap *_flow; + bool _local_flow; + // Node map of the current potentials + PotentialMap *_potential; + bool _local_potential; // The residual graph - ResGraph _res_graph; + ResGraph *_res_graph; // The residual cost map ResidualCostMap _res_cost; public: - /// \brief General constructor of the class (with lower bounds). + /// \brief General constructor (with lower bounds). /// - /// General constructor of the class (with lower bounds). + /// General constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -167,8 +170,8 @@ 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) + _supply(graph), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost) { // Removing non-zero lower bounds _capacity = subMap(capacity, lower); @@ -184,9 +187,9 @@ _valid_supply = sum == 0; } - /// \brief General constructor of the class (without lower bounds). + /// \brief General constructor (without lower bounds). /// - /// General constructor of the class (without lower bounds). + /// General constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -197,8 +200,8 @@ 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) + _supply(supply), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost) { // Checking the sum of supply values Supply sum = 0; @@ -206,9 +209,9 @@ _valid_supply = sum == 0; } - /// \brief Simple constructor of the class (with lower bounds). + /// \brief Simple constructor (with lower bounds). /// - /// Simple constructor of the class (with lower bounds). + /// Simple constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -225,8 +228,8 @@ 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) + _supply(graph), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost) { // Removing non-zero lower bounds _capacity = subMap(capacity, lower); @@ -243,9 +246,9 @@ _valid_supply = true; } - /// \brief Simple constructor of the class (without lower bounds). + /// \brief Simple constructor (without lower bounds). /// - /// Simple constructor of the class (without lower bounds). + /// Simple constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -260,14 +263,55 @@ 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) + _supply(graph, 0), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _res_cost(_cost) { _supply[s] = flow_value; _supply[t] = -flow_value; _valid_supply = true; } + /// Destructor. + ~CycleCanceling() { + if (_local_flow) delete _flow; + if (_local_potential) delete _potential; + delete _res_graph; + } + + /// \brief Sets the flow map. + /// + /// Sets the flow map. + /// + /// \return \c (*this) + CycleCanceling& flowMap(FlowMap &map) { + if (_local_flow) { + delete _flow; + _local_flow = false; + } + _flow = ↦ + return *this; + } + + /// \brief Sets the potential map. + /// + /// Sets the potential map. + /// + /// \return \c (*this) + CycleCanceling& potentialMap(PotentialMap &map) { + if (_local_potential) { + delete _potential; + _local_potential = false; + } + _potential = ↦ + return *this; + } + + /// \name Execution control + /// The only way to execute the algorithm is to call the run() + /// function. + + /// @{ + /// \brief Runs the algorithm. /// /// Runs the algorithm. @@ -281,6 +325,15 @@ return init() && start(min_mean_cc); } + /// @} + + /// \name Query Functions + /// The result of the algorithm can be obtained using these + /// functions. + /// \n run() must be called before using them. + + /// @{ + /// \brief Returns a const reference to the edge map storing the /// found flow. /// @@ -288,7 +341,36 @@ /// /// \pre \ref run() must be called before using this function. const FlowMap& flowMap() const { - return _flow; + return *_flow; + } + + /// \brief Returns a const reference to the node map storing the + /// found potentials (the dual solution). + /// + /// Returns a const reference to the node map storing the found + /// potentials (the dual solution). + /// + /// \pre \ref run() must be called before using this function. + const PotentialMap& potentialMap() const { + return *_potential; + } + + /// \brief Returns the flow on the edge. + /// + /// Returns the flow on the edge. + /// + /// \pre \ref run() must be called before using this function. + Capacity flow(const Edge& edge) const { + return (*_flow)[edge]; + } + + /// \brief Returns the potential of the node. + /// + /// Returns the potential of the node. + /// + /// \pre \ref run() must be called before using this function. + Cost potential(const Node& node) const { + return (*_potential)[node]; } /// \brief Returns the total cost of the found flow. @@ -300,29 +382,50 @@ 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; } + /// @} + private: /// Initializes the algorithm. bool init() { if (!_valid_supply) return false; + // Initializing flow and potential maps + if (!_flow) { + _flow = new FlowMap(_graph); + _local_flow = true; + } + if (!_potential) { + _potential = new PotentialMap(_graph); + _local_potential = true; + } + + _res_graph = new ResGraph(_graph, _capacity, *_flow); + // Finding a feasible flow using Circulation Circulation< Graph, ConstMap, CapacityEdgeMap, SupplyMap > - circulation( _graph, constMap((Capacity)0), _capacity, + circulation( _graph, constMap(Capacity(0)), _capacity, _supply ); - return circulation.flowMap(_flow).run(); + return circulation.flowMap(*_flow).run(); } bool start(bool min_mean_cc) { if (min_mean_cc) - return startMinMean(); + startMinMean(); else - return start(); + start(); + + // Handling non-zero lower bounds + if (_lower) { + for (EdgeIt e(_graph); e != INVALID; ++e) + (*_flow)[e] += (*_lower)[e]; + } + return true; } /// \brief Executes the algorithm using \ref BellmanFord. @@ -330,16 +433,16 @@ /// Executes the algorithm using the \ref BellmanFord /// "Bellman-Ford" algorithm for negative cycle detection with /// successively larger limit for the number of iterations. - bool start() { - typename BellmanFord::PredMap pred(_res_graph); - typename ResGraph::template NodeMap visited(_res_graph); + void start() { + typename BellmanFord::PredMap pred(*_res_graph); + typename ResGraph::template NodeMap visited(*_res_graph); std::vector cycle; int node_num = countNodes(_graph); int length_bound = BF_FIRST_LIMIT; bool optimal = false; while (!optimal) { - BellmanFord bf(_res_graph, _res_cost); + BellmanFord bf(*_res_graph, _res_cost); bf.predMap(pred); bf.init(0); int iter_num = 0; @@ -356,22 +459,26 @@ } } if (real_iter_num < curr_iter_num) { + // Optimal flow is found optimal = true; + // Setting node potentials + for (NodeIt n(_graph); n != INVALID; ++n) + (*_potential)[n] = bf.dist(n); break; } else { // Searching for node disjoint negative cycles - for (ResNodeIt n(_res_graph); n != INVALID; ++n) + for (ResNodeIt n(*_res_graph); n != INVALID; ++n) visited[n] = 0; int id = 0; - for (ResNodeIt n(_res_graph); n != INVALID; ++n) { + 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]); + 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]); + INVALID : _res_graph->source(pred[u]); } if (u != INVALID && visited[u] == id) { // Finding the negative cycle @@ -379,16 +486,16 @@ 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); + 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); } // Augmenting along the cycle for (int i = 0; i < int(cycle.size()); ++i) - _res_graph.augment(cycle[i], d); + _res_graph->augment(cycle[i], d); } } } @@ -397,22 +504,15 @@ length_bound = int(length_bound * BF_ALPHA); } } - - // Handling non-zero lower bounds - if (_lower) { - for (EdgeIt e(_graph); e != INVALID; ++e) - _flow[e] += (*_lower)[e]; - } - return true; } /// \brief Executes the algorithm using \ref MinMeanCycle. /// /// Executes the algorithm using \ref MinMeanCycle for negative /// cycle detection. - bool startMinMean() { + void startMinMean() { typedef Path ResPath; - MinMeanCycle mmc(_res_graph, _res_cost); + MinMeanCycle mmc(*_res_graph, _res_cost); ResPath cycle; mmc.cyclePath(cycle).init(); @@ -425,13 +525,13 @@ // 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); + 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); + _res_graph->augment(e, delta); // Finding the minimum cycle mean for the modified residual // graph @@ -440,12 +540,11 @@ } } - // Handling non-zero lower bounds - if (_lower) { - for (EdgeIt e(_graph); e != INVALID; ++e) - _flow[e] += (*_lower)[e]; - } - return true; + // Computing node potentials + BellmanFord bf(*_res_graph, _res_cost); + bf.init(0); bf.start(); + for (NodeIt n(_graph); n != INVALID; ++n) + (*_potential)[n] = bf.dist(n); } }; //class CycleCanceling diff -r fa71d9612c42 -r 054566ac0934 lemon/min_cost_flow.h --- a/lemon/min_cost_flow.h Wed Feb 27 11:39:03 2008 +0000 +++ b/lemon/min_cost_flow.h Thu Feb 28 02:54:27 2008 +0000 @@ -43,9 +43,7 @@ /// \ref NetworkSimplex. /// /// There are four implementations for the minimum cost flow problem, - /// which can be used exactly the same way except for the fact that - /// \ref CycleCanceling does not provide dual solution (node - /// potentials) since it is a pure primal method. + /// which can be used exactly the same way. /// - \ref CapacityScaling The capacity scaling algorithm. /// - \ref CostScaling The cost scaling algorithm. /// - \ref CycleCanceling A cycle-canceling algorithm. @@ -60,20 +58,16 @@ /// \warning /// - Edge capacities and costs should be \e non-negative \e integers. /// - Supply values should be \e signed \e integers. - /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. - /// - \c CapacityMap::Value and \c SupplyMap::Value must be - /// convertible to each other. - /// - All value types must be convertible to \c CostMap::Value, which - /// must be signed type. + /// - The value types of the maps should be convertible to each other. + /// - \c CostMap::Value must be signed type. /// /// \author Peter Kovacs template < typename Graph, typename LowerMap = typename Graph::template EdgeMap, - typename CapacityMap = LowerMap, + typename CapacityMap = typename Graph::template EdgeMap, typename CostMap = typename Graph::template EdgeMap, - typename SupplyMap = typename Graph::template NodeMap - > + typename SupplyMap = typename Graph::template NodeMap > class MinCostFlow : public NetworkSimplex< Graph, LowerMap, CapacityMap, CostMap, SupplyMap > @@ -85,7 +79,7 @@ public: - /// General constructor of the class (with lower bounds). + /// General constructor (with lower bounds). MinCostFlow( const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, @@ -100,7 +94,7 @@ const SupplyMap &supply ) : MinCostFlowImpl(graph, capacity, cost, supply) {} - /// Simple constructor of the class (with lower bounds). + /// Simple constructor (with lower bounds). MinCostFlow( const Graph &graph, const LowerMap &lower, const CapacityMap &capacity, @@ -110,7 +104,7 @@ MinCostFlowImpl( graph, lower, capacity, cost, s, t, flow_value ) {} - /// Simple constructor of the class (without lower bounds). + /// Simple constructor (without lower bounds). MinCostFlow( const Graph &graph, const CapacityMap &capacity, const CostMap &cost, diff -r fa71d9612c42 -r 054566ac0934 lemon/network_simplex.h --- a/lemon/network_simplex.h Wed Feb 27 11:39:03 2008 +0000 +++ b/lemon/network_simplex.h Thu Feb 28 02:54:27 2008 +0000 @@ -52,11 +52,8 @@ /// \warning /// - Edge capacities and costs should be \e non-negative \e integers. /// - Supply values should be \e signed \e integers. - /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value. - /// - \c CapacityMap::Value and \c SupplyMap::Value must be - /// convertible to each other. - /// - All value types must be convertible to \c CostMap::Value, which - /// must be signed type. + /// - The value types of the maps should be convertible to each other. + /// - \c CostMap::Value must be signed type. /// /// \note \ref NetworkSimplex provides six different pivot rule /// implementations that significantly affect the efficiency of the @@ -469,8 +466,10 @@ ReducedCostMap _red_cost; // Members for handling the original graph - FlowMap _flow_result; - PotentialMap _potential_result; + FlowMap *_flow_result; + PotentialMap *_potential_result; + bool _local_flow; + bool _local_potential; NodeRefMap _node_ref; EdgeRefMap _edge_ref; @@ -487,9 +486,9 @@ public : - /// \brief General constructor of the class (with lower bounds). + /// \brief General constructor (with lower bounds). /// - /// General constructor of the class (with lower bounds). + /// General constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -506,7 +505,8 @@ _potential(_graph), _depth(_graph), _parent(_graph), _pred_edge(_graph), _thread(_graph), _forward(_graph), _state(_graph), _red_cost(_graph, _cost, _potential), - _flow_result(graph), _potential_result(graph), + _flow_result(0), _potential_result(0), + _local_flow(false), _local_potential(false), _node_ref(graph), _edge_ref(graph) { // Checking the sum of supply values @@ -538,9 +538,9 @@ } } - /// \brief General constructor of the class (without lower bounds). + /// \brief General constructor (without lower bounds). /// - /// General constructor of the class (without lower bounds). + /// General constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -555,7 +555,8 @@ _potential(_graph), _depth(_graph), _parent(_graph), _pred_edge(_graph), _thread(_graph), _forward(_graph), _state(_graph), _red_cost(_graph, _cost, _potential), - _flow_result(graph), _potential_result(graph), + _flow_result(0), _potential_result(0), + _local_flow(false), _local_potential(false), _node_ref(graph), _edge_ref(graph) { // Checking the sum of supply values @@ -574,9 +575,9 @@ .run(); } - /// \brief Simple constructor of the class (with lower bounds). + /// \brief Simple constructor (with lower bounds). /// - /// Simple constructor of the class (with lower bounds). + /// Simple constructor (with lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param lower The lower bounds of the edges. @@ -598,7 +599,8 @@ _potential(_graph), _depth(_graph), _parent(_graph), _pred_edge(_graph), _thread(_graph), _forward(_graph), _state(_graph), _red_cost(_graph, _cost, _potential), - _flow_result(graph), _potential_result(graph), + _flow_result(0), _potential_result(0), + _local_flow(false), _local_potential(false), _node_ref(graph), _edge_ref(graph) { // Copying _graph_ref to graph @@ -625,9 +627,9 @@ _valid_supply = true; } - /// \brief Simple constructor of the class (without lower bounds). + /// \brief Simple constructor (without lower bounds). /// - /// Simple constructor of the class (without lower bounds). + /// Simple constructor (without lower bounds). /// /// \param graph The directed graph the algorithm runs on. /// \param capacity The capacities (upper bounds) of the edges. @@ -647,7 +649,8 @@ _potential(_graph), _depth(_graph), _parent(_graph), _pred_edge(_graph), _thread(_graph), _forward(_graph), _state(_graph), _red_cost(_graph, _cost, _potential), - _flow_result(graph), _potential_result(graph), + _flow_result(0), _potential_result(0), + _local_flow(false), _local_potential(false), _node_ref(graph), _edge_ref(graph) { // Copying _graph_ref to graph @@ -662,6 +665,46 @@ _valid_supply = true; } + /// Destructor. + ~NetworkSimplex() { + if (_local_flow) delete _flow_result; + if (_local_potential) delete _potential_result; + } + + /// \brief Sets the flow map. + /// + /// Sets the flow map. + /// + /// \return \c (*this) + NetworkSimplex& flowMap(FlowMap &map) { + if (_local_flow) { + delete _flow_result; + _local_flow = false; + } + _flow_result = ↦ + return *this; + } + + /// \brief Sets the potential map. + /// + /// Sets the potential map. + /// + /// \return \c (*this) + NetworkSimplex& potentialMap(PotentialMap &map) { + if (_local_potential) { + delete _potential_result; + _local_potential = false; + } + _potential_result = ↦ + return *this; + } + + /// \name Execution control + /// The only way to execute the algorithm is to call the run() + /// function. + + /// @{ + /// \brief Runs the algorithm. /// /// Runs the algorithm. @@ -703,6 +746,15 @@ return init() && start(pivot_rule); } + /// @} + + /// \name Query Functions + /// The result of the algorithm can be obtained using these + /// functions. + /// \n run() must be called before using them. + + /// @{ + /// \brief Returns a const reference to the edge map storing the /// found flow. /// @@ -710,7 +762,7 @@ /// /// \pre \ref run() must be called before using this function. const FlowMap& flowMap() const { - return _flow_result; + return *_flow_result; } /// \brief Returns a const reference to the node map storing the @@ -721,7 +773,25 @@ /// /// \pre \ref run() must be called before using this function. const PotentialMap& potentialMap() const { - return _potential_result; + return *_potential_result; + } + + /// \brief Returns the flow on the edge. + /// + /// Returns the flow on the edge. + /// + /// \pre \ref run() must be called before using this function. + Capacity flow(const typename Graph::Edge& edge) const { + return (*_flow_result)[edge]; + } + + /// \brief Returns the potential of the node. + /// + /// Returns the potential of the node. + /// + /// \pre \ref run() must be called before using this function. + Cost potential(const typename Graph::Node& node) const { + return (*_potential_result)[node]; } /// \brief Returns the total cost of the found flow. @@ -733,10 +803,12 @@ 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; } + /// @} + private: /// \brief Extends the underlaying graph and initializes all the @@ -744,6 +816,16 @@ bool init() { if (!_valid_supply) return false; + // Initializing result maps + if (!_flow_result) { + _flow_result = new FlowMap(_graph_ref); + _local_flow = true; + } + if (!_potential_result) { + _potential_result = new PotentialMap(_graph_ref); + _local_potential = true; + } + // Initializing state and flow maps for (EdgeIt e(_graph); e != INVALID; ++e) { _flow[e] = 0; @@ -1015,14 +1097,14 @@ // 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]]; + (*_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]]; + (*_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; }