Changeset 603:425cc8328c0e in lemon-main

Timestamp:

03/23/09 23:54:42 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Internal restructuring and renamings in NetworkSimplex? (#234)

File:

• lemon/network_simplex.h (modified) (46 diffs)

lemon/network_simplex.h

@@ -29 +29 @@
 #include <algorithm>
 
+#include <lemon/core.h>
 #include <lemon/math.h>
 
@@ -121 +122 @@
 
     // References for the original data
-    const Digraph &_orig_graph;
+    const Digraph &_graph;
     const LowerMap *_orig_lower;
     const CapacityMap &_orig_cap;
@@ -131 +132 @@
 
     // Result maps
-    FlowMap *_flow_result;
-    PotentialMap *_potential_result;
+    FlowMap *_flow_map;
+    PotentialMap *_potential_map;
     bool _local_flow;
     bool _local_potential;
-
-    // Data structures for storing the graph
-    ArcVector _arc;
-    NodeVector _node;
-    IntNodeMap _node_id;
-    IntVector _source;
-    IntVector _target;
 
     // The number of nodes and arcs in the original graph
     int _node_num;
     int _arc_num;
+
+    // Data structures for storing the graph
+    IntNodeMap _node_id;
+    ArcVector _arc_ref;
+    IntVector _source;
+    IntVector _target;
 
     // Node and arc maps
@@ -154 +154 @@
     CostVector _pi;
 
-    // Node and arc maps for the spanning tree structure
+    // Data for storing the spanning tree structure
     IntVector _depth;
     IntVector _parent;
@@ -161 +161 @@
     BoolVector _forward;
     IntVector _state;
-
-    // The root node
     int _root;
 
-    // The entering arc in the current pivot iteration
-    int _in_arc;
-
     // Temporary data used in the current pivot iteration
-    int join, u_in, v_in, u_out, v_out;
-    int right, first, second, last;
+    int in_arc, join, u_in, v_in, u_out, v_out;
+    int first, second, right, last;
     int stem, par_stem, new_stem;
     Capacity delta;
@@ -188 +183 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -204 +198 @@
       /// Constructor
       FirstEligiblePivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
       {}
 
@@ -246 +240 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -259 +252 @@
       /// Constructor
       BestEligiblePivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num)
       {}
 
@@ -292 +285 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -309 +301 @@
       /// Constructor
       BlockSearchPivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
       {
         // The main parameters of the pivot rule
@@ -371 +363 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -390 +381 @@
       /// Constructor
       CandidateListPivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num), _next_arc(0)
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0)
       {
         // The main parameters of the pivot rule
@@ -483 +474 @@
 
       // References to the NetworkSimplex class
-      const ArcVector &_arc;
       const IntVector  &_source;
       const IntVector  &_target;
@@ -516 +506 @@
       /// Constructor
       AlteringListPivotRule(NetworkSimplex &ns) :
-        _arc(ns._arc), _source(ns._source), _target(ns._target),
+        _source(ns._source), _target(ns._target),
         _cost(ns._cost), _state(ns._state), _pi(ns._pi),
-        _in_arc(ns._in_arc), _arc_num(ns._arc_num),
+        _in_arc(ns.in_arc), _arc_num(ns._arc_num),
         _next_arc(0), _cand_cost(ns._arc_num), _sort_func(_cand_cost)
       {
@@ -550 +540 @@
         // Extend the list
         int cnt = _block_size;
-        int last_edge = 0;
+        int last_arc = 0;
         int limit = _head_length;
 
@@ -558 +548 @@
           if (_cand_cost[e] < 0) {
             _candidates[_curr_length++] = e;
-            last_edge = e;
+            last_arc = e;
           }
           if (--cnt == 0) {
@@ -572 +562 @@
             if (_cand_cost[e] < 0) {
               _candidates[_curr_length++] = e;
-              last_edge = e;
+              last_arc = e;
             }
             if (--cnt == 0) {
@@ -582 +572 @@
         }
         if (_curr_length == 0) return false;
-        _next_arc = last_edge + 1;
+        _next_arc = last_arc + 1;
 
         // Make heap of the candidate list (approximating a partial sort)
@@ -604 +594 @@
     /// General constructor (with lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param lower The lower bounds of the arcs.
     /// \param capacity The capacities (upper bounds) of the arcs.
     /// \param cost The cost (length) values of the arcs.
     /// \param supply The supply values of the nodes (signed).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const LowerMap &lower,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     const SupplyMap &supply ) :
-      _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
+      _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(&supply),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
@@ -625 +615 @@
     /// General constructor (without lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param capacity The capacities (upper bounds) of the arcs.
     /// \param cost The cost (length) values of the arcs.
     /// \param supply The supply values of the nodes (signed).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     const SupplyMap &supply ) :
-      _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
+      _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(&supply),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
@@ -644 +634 @@
     /// Simple constructor (with lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param lower The lower bounds of the arcs.
     /// \param capacity The capacities (upper bounds) of the arcs.
@@ -652 +642 @@
     /// \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).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const LowerMap &lower,
                     const CapacityMap &capacity,
@@ -658 +648 @@
                     Node s, Node t,
                     Capacity flow_value ) :
-      _orig_graph(digraph), _orig_lower(&lower), _orig_cap(capacity),
+      _graph(graph), _orig_lower(&lower), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(NULL),
       _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
@@ -670 +660 @@
     /// Simple constructor (without lower bounds).
     ///
-    /// \param digraph The digraph the algorithm runs on.
+    /// \param graph The digraph the algorithm runs on.
     /// \param capacity The capacities (upper bounds) of the arcs.
     /// \param cost The cost (length) values of the arcs.
@@ -677 +667 @@
     /// \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).
-    NetworkSimplex( const Digraph &digraph,
+    NetworkSimplex( const Digraph &graph,
                     const CapacityMap &capacity,
                     const CostMap &cost,
                     Node s, Node t,
                     Capacity flow_value ) :
-      _orig_graph(digraph), _orig_lower(NULL), _orig_cap(capacity),
+      _graph(graph), _orig_lower(NULL), _orig_cap(capacity),
       _orig_cost(cost), _orig_supply(NULL),
       _orig_source(s), _orig_target(t), _orig_flow_value(flow_value),
-      _flow_result(NULL), _potential_result(NULL),
+      _flow_map(NULL), _potential_map(NULL),
       _local_flow(false), _local_potential(false),
-      _node_id(digraph)
+      _node_id(graph)
     {}
 
     /// Destructor.
     ~NetworkSimplex() {
-      if (_local_flow) delete _flow_result;
-      if (_local_potential) delete _potential_result;
+      if (_local_flow) delete _flow_map;
+      if (_local_potential) delete _potential_map;
     }
 
@@ -703 +693 @@
     NetworkSimplex& flowMap(FlowMap &map) {
       if (_local_flow) {
-        delete _flow_result;
+        delete _flow_map;
         _local_flow = false;
       }
-      _flow_result = &map;
+      _flow_map = &map;
       return *this;
     }
@@ -717 +707 @@
     NetworkSimplex& potentialMap(PotentialMap &map) {
       if (_local_potential) {
-        delete _potential_result;
+        delete _potential_map;
         _local_potential = false;
       }
-      _potential_result = &map;
+      _potential_map = &map;
       return *this;
     }
@@ -784 +774 @@
     /// \pre \ref run() must be called before using this function.
     const FlowMap& flowMap() const {
-      return *_flow_result;
+      return *_flow_map;
     }
 
@@ -795 +785 @@
     /// \pre \ref run() must be called before using this function.
     const PotentialMap& potentialMap() const {
-      return *_potential_result;
+      return *_potential_map;
     }
 
@@ -804 +794 @@
     /// \pre \ref run() must be called before using this function.
     Capacity flow(const Arc& arc) const {
-      return (*_flow_result)[arc];
+      return (*_flow_map)[arc];
     }
 
@@ -813 +803 @@
     /// \pre \ref run() must be called before using this function.
     Cost potential(const Node& node) const {
-      return (*_potential_result)[node];
+      return (*_potential_map)[node];
     }
 
@@ -824 +814 @@
     Cost totalCost() const {
       Cost c = 0;
-      for (ArcIt e(_orig_graph); e != INVALID; ++e)
-        c += (*_flow_result)[e] * _orig_cost[e];
+      for (ArcIt e(_graph); e != INVALID; ++e)
+        c += (*_flow_map)[e] * _orig_cost[e];
       return c;
     }
@@ -836 +826 @@
     bool init() {
       // Initialize result maps
-      if (!_flow_result) {
-        _flow_result = new FlowMap(_orig_graph);
+      if (!_flow_map) {
+        _flow_map = new FlowMap(_graph);
         _local_flow = true;
       }
-      if (!_potential_result) {
-        _potential_result = new PotentialMap(_orig_graph);
+      if (!_potential_map) {
+        _potential_map = new PotentialMap(_graph);
         _local_potential = true;
       }
 
       // Initialize vectors
-      _node_num = countNodes(_orig_graph);
-      _arc_num = countArcs(_orig_graph);
+      _node_num = countNodes(_graph);
+      _arc_num = countArcs(_graph);
       int all_node_num = _node_num + 1;
-      int all_edge_num = _arc_num + _node_num;
-
-      _arc.resize(_arc_num);
-      _node.reserve(_node_num);
-      _source.resize(all_edge_num);
-      _target.resize(all_edge_num);
-
-      _cap.resize(all_edge_num);
-      _cost.resize(all_edge_num);
+      int all_arc_num = _arc_num + _node_num;
+
+      _arc_ref.resize(_arc_num);
+      _source.resize(all_arc_num);
+      _target.resize(all_arc_num);
+
+      _cap.resize(all_arc_num);
+      _cost.resize(all_arc_num);
       _supply.resize(all_node_num);
-      _flow.resize(all_edge_num, 0);
+      _flow.resize(all_arc_num, 0);
       _pi.resize(all_node_num, 0);
 
@@ -865 +854 @@
       _parent.resize(all_node_num);
       _pred.resize(all_node_num);
+      _forward.resize(all_node_num);
       _thread.resize(all_node_num);
-      _forward.resize(all_node_num);
-      _state.resize(all_edge_num, STATE_LOWER);
+      _state.resize(all_arc_num, STATE_LOWER);
 
       // Initialize node related data
@@ -874 +863 @@
         Supply sum = 0;
         int i = 0;
-        for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
-          _node.push_back(n);
+        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
           _node_id[n] = i;
           _supply[i] = (*_orig_supply)[n];
@@ -883 +871 @@
       } else {
         int i = 0;
-        for (NodeIt n(_orig_graph); n != INVALID; ++n, ++i) {
-          _node.push_back(n);
+        for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
           _node_id[n] = i;
           _supply[i] = 0;
@@ -905 +892 @@
       int k = std::max(int(sqrt(_arc_num)), 10);
       int i = 0;
-      for (ArcIt e(_orig_graph); e != INVALID; ++e) {
-        _arc[i] = e;
+      for (ArcIt e(_graph); e != INVALID; ++e) {
+        _arc_ref[i] = e;
         if ((i += k) >= _arc_num) i = (i % k) + 1;
       }
@@ -912 +899 @@
       // Initialize arc maps
       for (int i = 0; i != _arc_num; ++i) {
-        Arc e = _arc[i];
-        _source[i] = _node_id[_orig_graph.source(e)];
-        _target[i] = _node_id[_orig_graph.target(e)];
+        Arc e = _arc_ref[i];
+        _source[i] = _node_id[_graph.source(e)];
+        _target[i] = _node_id[_graph.target(e)];
         _cost[i] = _orig_cost[e];
         _cap[i] = _orig_cap[e];
@@ -922 +909 @@
       if (_orig_lower) {
         for (int i = 0; i != _arc_num; ++i) {
-          Capacity c = (*_orig_lower)[_arc[i]];
+          Capacity c = (*_orig_lower)[_arc_ref[i]];
           if (c != 0) {
             _cap[i] -= c;
@@ -958 +945 @@
     // Find the join node
     void findJoinNode() {
-      int u = _source[_in_arc];
-      int v = _target[_in_arc];
+      int u = _source[in_arc];
+      int v = _target[in_arc];
       while (_depth[u] > _depth[v]) u = _parent[u];
       while (_depth[v] > _depth[u]) v = _parent[v];
@@ -974 +961 @@
       // Initialize first and second nodes according to the direction
       // of the cycle
-      if (_state[_in_arc] == STATE_LOWER) {
-        first  = _source[_in_arc];
-        second = _target[_in_arc];
+      if (_state[in_arc] == STATE_LOWER) {
+        first  = _source[in_arc];
+        second = _target[in_arc];
       } else {
-        first  = _target[_in_arc];
-        second = _source[_in_arc];
-      }
-      delta = _cap[_in_arc];
+        first  = _target[in_arc];
+        second = _source[in_arc];
+      }
+      delta = _cap[in_arc];
       int result = 0;
       Capacity d;
@@ -1021 +1008 @@
       // Augment along the cycle
       if (delta > 0) {
-        Capacity val = _state[_in_arc] * delta;
-        _flow[_in_arc] += val;
-        for (int u = _source[_in_arc]; u != join; u = _parent[u]) {
+        Capacity val = _state[in_arc] * delta;
+        _flow[in_arc] += val;
+        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
           _flow[_pred[u]] += _forward[u] ? -val : val;
         }
-        for (int u = _target[_in_arc]; u != join; u = _parent[u]) {
+        for (int u = _target[in_arc]; u != join; u = _parent[u]) {
           _flow[_pred[u]] += _forward[u] ? val : -val;
         }
@@ -1032 +1019 @@
       // Update the state of the entering and leaving arcs
       if (change) {
-        _state[_in_arc] = STATE_TREE;
+        _state[in_arc] = STATE_TREE;
         _state[_pred[u_out]] =
           (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER;
       } else {
-        _state[_in_arc] = -_state[_in_arc];
+        _state[in_arc] = -_state[in_arc];
       }
     }
@@ -1107 +1094 @@
         u = v;
       }
-      _pred[u_in] = _in_arc;
-      _forward[u_in] = (u_in == _source[_in_arc]);
+      _pred[u_in] = in_arc;
+      _forward[u_in] = (u_in == _source[in_arc]);
     }
 
@@ -1164 +1151 @@
       }
 
-      // Copy flow values to _flow_result
+      // Copy flow values to _flow_map
       if (_orig_lower) {
         for (int i = 0; i != _arc_num; ++i) {
-          Arc e = _arc[i];
-          (*_flow_result)[e] = (*_orig_lower)[e] + _flow[i];
+          Arc e = _arc_ref[i];
+          _flow_map->set(e, (*_orig_lower)[e] + _flow[i]);
         }
       } else {
         for (int i = 0; i != _arc_num; ++i) {
-          (*_flow_result)[_arc[i]] = _flow[i];
-        }
-      }
-      // Copy potential values to _potential_result
-      for (int i = 0; i != _node_num; ++i) {
-        (*_potential_result)[_node[i]] = _pi[i];
+          _flow_map->set(_arc_ref[i], _flow[i]);
+        }
+      }
+      // Copy potential values to _potential_map
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        _potential_map->set(n, _pi[_node_id[n]]);
       }