Changeset 2587:061be2e64eca in lemon-0.x

Timestamp:

02/29/08 16:55:39 (16 years ago)

Author:

Peter Kovacs

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3469

Message:

External flow and potential maps can be used in MinCostMaxFlow?.

File:

• lemon/min_cost_max_flow.h (modified) (8 diffs)

lemon/min_cost_max_flow.h

@@ -65 +65 @@
   class MinCostMaxFlow
   {
-    typedef typename Graph::Node Node;
-    typedef typename Graph::Edge Edge;
+    GRAPH_TYPEDEFS(typename Graph);
 
     typedef typename CapacityMap::Value Capacity;
@@ -87 +86 @@
     // The directed graph the algorithm runs on
     const Graph &_graph;
-    // The modified capacity map
+    // The capacity map
     const CapacityMap &_capacity;
     // The cost map
@@ -93 +92 @@
 
     // Edge map of the found flow
-    FlowMap _flow;
-    // Node map of the found potentials
-    PotentialMap _potential;
+    FlowMap *_flow;
+    bool _local_flow;
+    // Node map of the current potentials
+    PotentialMap *_potential;
+    bool _local_potential;
 
     // The source node
@@ -104 +105 @@
   public:
 
-    /// \brief The constructor of the class.
-    ///
-    /// The constructor of the class.
-    ///
-    /// \param _graph The directed graph the algorithm runs on.
-    /// \param _capacity The capacities (upper bounds) of the edges.
-    /// \param _cost The cost (length) values of the edges.
-    /// \param _s The source node.
-    /// \param _t The target node.
+    /// \brief Constructor.
+    ///
+    /// Constructor.
+    ///
+    /// \param graph The directed graph the algorithm runs on.
+    /// \param capacity The capacities (upper bounds) of the edges.
+    /// \param cost The cost (length) values of the edges.
+    /// \param s The source node.
+    /// \param t The target node.
     MinCostMaxFlow( const Graph &graph,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     Node s, Node t ) :
-      _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),
-      _potential(graph), _source(s), _target(t)
-    {}
+      _graph(graph), _capacity(capacity), _cost(cost), _flow(0),
+      _local_flow(false), _potential(0), _local_potential(false),
+      _source(s), _target(t) {}
+
+    /// Destructor.
+    ~MinCostMaxFlow() {
+      if (_local_flow) delete _flow;
+      if (_local_potential) delete _potential;
+    }
+
+    /// \brief Sets the flow map.
+    ///
+    /// Sets the flow map.
+    ///
+    /// \return \c (*this)
+    MinCostMaxFlow& 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)
+    MinCostMaxFlow& 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.
@@ -125 +166 @@
     /// Runs the algorithm.
     void run() {
+      // Initializing maps
+      if (!_flow) {
+        _flow = new FlowMap(_graph);
+        _local_flow = true;
+      }
+      if (!_potential) {
+        _potential = new PotentialMap(_graph);
+        _local_potential = true;
+      }
+      // Running Preflow
       MaxFlowImpl preflow(_graph, _capacity, _source, _target);
-      preflow.flowMap(_flow).runMinCut();
+      preflow.flowMap(*_flow).runMinCut();
+      // Running NetworkSimplex
       MinCostFlowImpl mcf( _graph, _capacity, _cost,
                            _source, _target, preflow.flowValue() );
-      mcf.flowMap(_flow).potentialMap(_potential).run();
-    }
+      mcf.flowMap(*_flow).potentialMap(*_potential).run();
+    }
+
+    /// @}
+
+    /// \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
@@ -139 +200 @@
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return _flow;
+      return *_flow;
     }
 
@@ -150 +211 @@
     /// \pre \ref run() must be called before using this function.
     const PotentialMap& potentialMap() const {
-      return _potential;
+      return *_potential;
+    }
+
+    /// \brief Returns the flow on the given edge.
+    ///
+    /// Returns the flow on the given 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 given node.
+    ///
+    /// Returns the potential of the given node.
+    ///
+    /// \pre \ref run() must be called before using this function.
+    Cost potential(const Node& node) const {
+      return (*_potential)[node];
     }
 
@@ -161 +240 @@
     Cost totalCost() const {
       Cost c = 0;
-      for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e)
-        c += _flow[e] * _cost[e];
+      for (EdgeIt e(_graph); e != INVALID; ++e)
+        c += (*_flow)[e] * _cost[e];
       return c;
     }
 
+    /// @}
+
   }; //class MinCostMaxFlow