COIN-OR::LEMON - Graph Library

Changeset 830:75c97c3786d6 in lemon-1.2 for lemon/network_simplex.h


Ignore:
Timestamp:
02/10/10 19:05:20 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Handle graph changes in the MCF algorithms (#327)

The reset() functions are renamed to resetParams() and the new reset()
functions handle the graph chnages, as well.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r812 r830  
    195195    IntVector _source;
    196196    IntVector _target;
     197    bool _arc_mixing;
    197198
    198199    // Node and arc data
     
    634635    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    635636      _graph(graph), _node_id(graph), _arc_id(graph),
     637      _arc_mixing(arc_mixing),
    636638      MAX(std::numeric_limits<Value>::max()),
    637639      INF(std::numeric_limits<Value>::has_infinity ?
     
    644646        "The cost type of NetworkSimplex must be signed");
    645647       
    646       // Resize vectors
    647       _node_num = countNodes(_graph);
    648       _arc_num = countArcs(_graph);
    649       int all_node_num = _node_num + 1;
    650       int max_arc_num = _arc_num + 2 * _node_num;
    651 
    652       _source.resize(max_arc_num);
    653       _target.resize(max_arc_num);
    654 
    655       _lower.resize(_arc_num);
    656       _upper.resize(_arc_num);
    657       _cap.resize(max_arc_num);
    658       _cost.resize(max_arc_num);
    659       _supply.resize(all_node_num);
    660       _flow.resize(max_arc_num);
    661       _pi.resize(all_node_num);
    662 
    663       _parent.resize(all_node_num);
    664       _pred.resize(all_node_num);
    665       _forward.resize(all_node_num);
    666       _thread.resize(all_node_num);
    667       _rev_thread.resize(all_node_num);
    668       _succ_num.resize(all_node_num);
    669       _last_succ.resize(all_node_num);
    670       _state.resize(max_arc_num);
    671 
    672       // Copy the graph
    673       int i = 0;
    674       for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    675         _node_id[n] = i;
    676       }
    677       if (arc_mixing) {
    678         // Store the arcs in a mixed order
    679         int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    680         int i = 0, j = 0;
    681         for (ArcIt a(_graph); a != INVALID; ++a) {
    682           _arc_id[a] = i;
    683           _source[i] = _node_id[_graph.source(a)];
    684           _target[i] = _node_id[_graph.target(a)];
    685           if ((i += k) >= _arc_num) i = ++j;
    686         }
    687       } else {
    688         // Store the arcs in the original order
    689         int i = 0;
    690         for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
    691           _arc_id[a] = i;
    692           _source[i] = _node_id[_graph.source(a)];
    693           _target[i] = _node_id[_graph.target(a)];
    694         }
    695       }
    696      
    697       // Reset parameters
     648      // Reset data structures
    698649      reset();
    699650    }
     
    843794    /// \endcode
    844795    ///
    845     /// This function can be called more than once. All the parameters
    846     /// that have been given are kept for the next call, unless
    847     /// \ref reset() is called, thus only the modified parameters
    848     /// have to be set again. See \ref reset() for examples.
    849     /// However, the underlying digraph must not be modified after this
    850     /// class have been constructed, since it copies and extends the graph.
     796    /// This function can be called more than once. All the given parameters
     797    /// are kept for the next call, unless \ref resetParams() or \ref reset()
     798    /// is used, thus only the modified parameters have to be set again.
     799    /// If the underlying digraph was also modified after the construction
     800    /// of the class (or the last \ref reset() call), then the \ref reset()
     801    /// function must be called.
    851802    ///
    852803    /// \param pivot_rule The pivot rule that will be used during the
     
    862813    ///
    863814    /// \see ProblemType, PivotRule
     815    /// \see resetParams(), reset()
    864816    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
    865817      if (!init()) return INFEASIBLE;
     
    873825    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    874826    ///
    875     /// It is useful for multiple run() calls. If this function is not
    876     /// used, all the parameters given before are kept for the next
    877     /// \ref run() call.
    878     /// However, the underlying digraph must not be modified after this
    879     /// class have been constructed, since it copies and extends the graph.
     827    /// It is useful for multiple \ref run() calls. Basically, all the given
     828    /// parameters are kept for the next \ref run() call, unless
     829    /// \ref resetParams() or \ref reset() is used.
     830    /// If the underlying digraph was also modified after the construction
     831    /// of the class or the last \ref reset() call, then the \ref reset()
     832    /// function must be used, otherwise \ref resetParams() is sufficient.
    880833    ///
    881834    /// For example,
     
    887840    ///     .supplyMap(sup).run();
    888841    ///
    889     ///   // Run again with modified cost map (reset() is not called,
     842    ///   // Run again with modified cost map (resetParams() is not called,
    890843    ///   // so only the cost map have to be set again)
    891844    ///   cost[e] += 100;
    892845    ///   ns.costMap(cost).run();
    893846    ///
    894     ///   // Run again from scratch using reset()
     847    ///   // Run again from scratch using resetParams()
    895848    ///   // (the lower bounds will be set to zero on all arcs)
    896     ///   ns.reset();
     849    ///   ns.resetParams();
    897850    ///   ns.upperMap(capacity).costMap(cost)
    898851    ///     .supplyMap(sup).run();
     
    900853    ///
    901854    /// \return <tt>(*this)</tt>
    902     NetworkSimplex& reset() {
     855    ///
     856    /// \see reset(), run()
     857    NetworkSimplex& resetParams() {
    903858      for (int i = 0; i != _node_num; ++i) {
    904859        _supply[i] = 0;
     
    914869    }
    915870
     871    /// \brief Reset the internal data structures and all the parameters
     872    /// that have been given before.
     873    ///
     874    /// This function resets the internal data structures and all the
     875    /// paramaters that have been given before using functions \ref lowerMap(),
     876    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     877    /// \ref supplyType().
     878    ///
     879    /// It is useful for multiple \ref run() calls. Basically, all the given
     880    /// parameters are kept for the next \ref run() call, unless
     881    /// \ref resetParams() or \ref reset() is used.
     882    /// If the underlying digraph was also modified after the construction
     883    /// of the class or the last \ref reset() call, then the \ref reset()
     884    /// function must be used, otherwise \ref resetParams() is sufficient.
     885    ///
     886    /// See \ref resetParams() for examples.
     887    ///
     888    /// \return <tt>(*this)</tt>
     889    ///
     890    /// \see resetParams(), run()
     891    NetworkSimplex& reset() {
     892      // Resize vectors
     893      _node_num = countNodes(_graph);
     894      _arc_num = countArcs(_graph);
     895      int all_node_num = _node_num + 1;
     896      int max_arc_num = _arc_num + 2 * _node_num;
     897
     898      _source.resize(max_arc_num);
     899      _target.resize(max_arc_num);
     900
     901      _lower.resize(_arc_num);
     902      _upper.resize(_arc_num);
     903      _cap.resize(max_arc_num);
     904      _cost.resize(max_arc_num);
     905      _supply.resize(all_node_num);
     906      _flow.resize(max_arc_num);
     907      _pi.resize(all_node_num);
     908
     909      _parent.resize(all_node_num);
     910      _pred.resize(all_node_num);
     911      _forward.resize(all_node_num);
     912      _thread.resize(all_node_num);
     913      _rev_thread.resize(all_node_num);
     914      _succ_num.resize(all_node_num);
     915      _last_succ.resize(all_node_num);
     916      _state.resize(max_arc_num);
     917
     918      // Copy the graph
     919      int i = 0;
     920      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     921        _node_id[n] = i;
     922      }
     923      if (_arc_mixing) {
     924        // Store the arcs in a mixed order
     925        int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     926        int i = 0, j = 0;
     927        for (ArcIt a(_graph); a != INVALID; ++a) {
     928          _arc_id[a] = i;
     929          _source[i] = _node_id[_graph.source(a)];
     930          _target[i] = _node_id[_graph.target(a)];
     931          if ((i += k) >= _arc_num) i = ++j;
     932        }
     933      } else {
     934        // Store the arcs in the original order
     935        int i = 0;
     936        for (ArcIt a(_graph); a != INVALID; ++a, ++i) {
     937          _arc_id[a] = i;
     938          _source[i] = _node_id[_graph.source(a)];
     939          _target[i] = _node_id[_graph.target(a)];
     940        }
     941      }
     942     
     943      // Reset parameters
     944      resetParams();
     945      return *this;
     946    }
     947   
    916948    /// @}
    917949
Note: See TracChangeset for help on using the changeset viewer.