COIN-OR::LEMON - Graph Library

Changeset 2630:d239741cfd44 in lemon-0.x


Ignore:
Timestamp:
11/13/08 17:17:50 (15 years ago)
Author:
Peter Kovacs
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3515
Message:

Various improvements in NetworkSimplex?.

  • Faster variant of "Altering Candidate List" pivot rule using make_heap instead of partial_sort.
  • Doc improvements.
  • Removing unecessary inline keywords.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r2629 r2630  
    2727#include <vector>
    2828#include <limits>
     29#include <algorithm>
    2930
    3031#include <lemon/graph_adaptor.h>
     
    138139      Cost operator[](const Edge &e) const {
    139140        return _cost_map[e] + _pot_map[_gr.source(e)]
    140                            - _pot_map[_gr.target(e)];
     141                            - _pot_map[_gr.target(e)];
    141142      }
    142143
     
    169170
    170171      /// Find next entering edge
    171       inline bool findEnteringEdge() {
     172      bool findEnteringEdge() {
    172173        Edge e;
    173174        for (int i = _next_edge; i < int(_edges.size()); ++i) {
     
    213214
    214215      /// Find next entering edge
    215       inline bool findEnteringEdge() {
     216      bool findEnteringEdge() {
    216217        Cost min = 0;
    217218        Edge e;
     
    260261
    261262      /// Find next entering edge
    262       inline bool findEnteringEdge() {
     263      bool findEnteringEdge() {
    263264        Cost curr, min = 0;
    264265        Edge e;
     
    337338
    338339      /// Find next entering edge
    339       inline bool findEnteringEdge() {
     340      bool findEnteringEdge() {
    340341        Cost min, curr;
    341342        if (_curr_length > 0 && _minor_count < _minor_limit) {
    342           // Minor iteration: selecting the best eligible edge from
    343           // the current candidate list
     343          // Minor iteration: select the best eligible edge from the
     344          // current candidate list
    344345          ++_minor_count;
    345346          Edge e;
     
    359360        }
    360361
    361         // Major iteration: building a new candidate list
     362        // Major iteration: build a new candidate list
    362363        Edge e;
    363364        min = 0;
     
    424425        SortFunc(const SCostMap &map) : _map(map) {}
    425426        bool operator()(const Edge &e1, const Edge &e2) {
    426           return _map[e1] < _map[e2];
     427          return _map[e1] > _map[e2];
    427428        }
    428429      };
     
    438439      {
    439440        // The main parameters of the pivot rule
    440         const double BLOCK_SIZE_FACTOR = 1.0;
     441        const double BLOCK_SIZE_FACTOR = 1.5;
    441442        const int MIN_BLOCK_SIZE = 10;
    442443        const double HEAD_LENGTH_FACTOR = 0.1;
    443         const int MIN_HEAD_LENGTH = 5;
     444        const int MIN_HEAD_LENGTH = 3;
    444445
    445446        _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_edges.size())),
     
    452453
    453454      /// Find next entering edge
    454       inline bool findEnteringEdge() {
    455         // Checking the current candidate list
     455      bool findEnteringEdge() {
     456        // Check the current candidate list
    456457        Edge e;
    457         for (int idx = 0; idx < _curr_length; ++idx) {
    458           e = _candidates[idx];
     458        for (int ix = 0; ix < _curr_length; ++ix) {
     459          e = _candidates[ix];
    459460          if ((_cand_cost[e] = _ns._state[e] * _ns._red_cost[e]) >= 0) {
    460             _candidates[idx--] = _candidates[--_curr_length];
    461           }
    462         }
    463 
    464         // Extending the list
     461            _candidates[ix--] = _candidates[--_curr_length];
     462          }
     463        }
     464
     465        // Extend the list
    465466        int cnt = _block_size;
    466467        int last_edge = 0;
     
    495496        _next_edge = last_edge + 1;
    496497
    497         // Sorting the list partially
    498         EdgeVector::iterator sort_end = _candidates.begin();
    499         EdgeVector::iterator vector_end = _candidates.begin();
    500         for (int idx = 0; idx < _curr_length; ++idx) {
    501           ++vector_end;
    502           if (idx <= _head_length) ++sort_end;
    503         }
    504         partial_sort(_candidates.begin(), sort_end, vector_end, _sort_func);
    505 
     498        // Make heap of the candidate list (approximating a partial sort)
     499        make_heap( _candidates.begin(), _candidates.begin() + _curr_length,
     500                   _sort_func );
     501
     502        // Pop the first element of the heap
    506503        _ns._in_edge = _candidates[0];
    507         if (_curr_length > _head_length) {
    508           _candidates[0] = _candidates[_head_length - 1];
    509           _curr_length = _head_length - 1;
    510         } else {
    511           _candidates[0] = _candidates[_curr_length - 1];
    512           --_curr_length;
    513         }
    514 
     504        pop_heap( _candidates.begin(), _candidates.begin() + _curr_length,
     505                  _sort_func );
     506        _curr_length = std::min(_head_length, _curr_length - 1);
    515507        return true;
    516508      }
     
    559551    // The state edge map
    560552    IntEdgeMap _state;
    561     // The root node of the starting spanning tree
     553    // The artificial root node of the spanning tree structure
    562554    Node _root;
    563555
     
    576568    EdgeRefMap _edge_ref;
    577569
    578     // The entering edge of the current pivot iteration.
     570    // The entering edge of the current pivot iteration
    579571    Edge _in_edge;
    580572
    581     // Temporary nodes used in the current pivot iteration.
     573    // Temporary nodes used in the current pivot iteration
    582574    Node join, u_in, v_in, u_out, v_out;
    583575    Node right, first, second, last;
    584576    Node stem, par_stem, new_stem;
    585577    // The maximum augment amount along the found cycle in the current
    586     // pivot iteration.
     578    // pivot iteration
    587579    Capacity delta;
    588580
     
    838830    ///
    839831    /// According to our comprehensive benchmark tests the "Block Search"
    840     /// pivot rule proved to be by far the fastest and the most robust
    841     /// on various test inputs. Thus it is the default option.
     832    /// pivot rule proved to be the fastest and the most robust on
     833    /// various test inputs. Thus it is the default option.
    842834    ///
    843835    /// \return \c true if a feasible flow can be found.
     
    912904  private:
    913905
    914     /// \brief Extend the underlying graph and initialize all the
    915     /// node and edge maps.
     906    // Extend the underlying graph and initialize all the node and edge maps
    916907    bool init() {
    917908      if (!_valid_supply) return false;
    918909
    919       // Initializing result maps
     910      // Initialize result maps
    920911      if (!_flow_result) {
    921912        _flow_result = new FlowMap(_graph_ref);
     
    927918      }
    928919
    929       // Initializing the edge vector and the edge maps
     920      // Initialize the edge vector and the edge maps
    930921      _edges.reserve(countEdges(_graph));
    931922      for (EdgeIt e(_graph); e != INVALID; ++e) {
     
    935926      }
    936927
    937       // Adding an artificial root node to the graph
     928      // Add an artificial root node to the graph
    938929      _root = _graph.addNode();
    939930      _parent[_root] = INVALID;
     
    943934      _potential[_root] = 0;
    944935
    945       // Adding artificial edges to the graph and initializing the node
    946       // maps of the spanning tree data structure
     936      // Add artificial edges to the graph and initialize the node maps
     937      // of the spanning tree data structure
    947938      Node last = _root;
    948939      Edge e;
     
    975966    }
    976967
    977     /// Find the join node.
    978     inline Node findJoinNode() {
     968    // Find the join node
     969    void findJoinNode() {
    979970      Node u = _graph.source(_in_edge);
    980971      Node v = _graph.target(_in_edge);
     
    987978        else v = _parent[v];
    988979      }
    989       return u;
    990     }
    991 
    992     /// \brief Find the leaving edge of the cycle.
    993     /// \return \c true if the leaving edge is not the same as the
    994     /// entering edge.
    995     inline bool findLeavingEdge() {
    996       // Initializing first and second nodes according to the direction
     980      join = u;
     981    }
     982
     983    // Find the leaving edge of the cycle and returns true if the
     984    // leaving edge is not the same as the entering edge
     985    bool findLeavingEdge() {
     986      // Initialize first and second nodes according to the direction
    997987      // of the cycle
    998988      if (_state[_in_edge] == STATE_LOWER) {
     
    1008998      Edge e;
    1009999
    1010       // Searching the cycle along the path form the first node to the
    1011       // root node
     1000      // Search the cycle along the path form the first node to the root
    10121001      for (Node u = first; u != join; u = _parent[u]) {
    10131002        e = _pred_edge[u];
     
    10211010        }
    10221011      }
    1023       // Searching the cycle along the path form the second node to the
    1024       // root node
     1012      // Search the cycle along the path form the second node to the root
    10251013      for (Node u = second; u != join; u = _parent[u]) {
    10261014        e = _pred_edge[u];
     
    10371025    }
    10381026
    1039     /// Change \c flow and \c state edge maps.
    1040     inline void changeFlows(bool change) {
    1041       // Augmenting along the cycle
     1027    // Change _flow and _state edge maps
     1028    void changeFlows(bool change) {
     1029      // Augment along the cycle
    10421030      if (delta > 0) {
    10431031        Capacity val = _state[_in_edge] * delta;
     
    10501038        }
    10511039      }
    1052       // Updating the state of the entering and leaving edges
     1040      // Update the state of the entering and leaving edges
    10531041      if (change) {
    10541042        _state[_in_edge] = STATE_TREE;
     
    10601048    }
    10611049
    1062     /// Update \c thread and \c parent node maps.
    1063     inline void updateThreadParent() {
     1050    // Update _thread and _parent node maps
     1051    void updateThreadParent() {
    10641052      Node u;
    10651053      v_out = _parent[u_out];
    10661054
    1067       // Handling the case when join and v_out coincide
     1055      // Handle the case when join and v_out coincide
    10681056      bool par_first = false;
    10691057      if (join == v_out) {
     
    10761064      }
    10771065
    1078       // Finding the last successor of u_in (u) and the node after it
    1079       // (right) according to the thread index
     1066      // Find the last successor of u_in (u) and the node after it (right)
     1067      // according to the thread index
    10801068      for (u = u_in; _depth[_thread[u]] > _depth[u_in]; u = _thread[u]) ;
    10811069      right = _thread[u];
     
    10861074      else last = _thread[v_in];
    10871075
    1088       // Updating stem nodes
     1076      // Update stem nodes
    10891077      _thread[v_in] = stem = u_in;
    10901078      par_stem = v_in;
     
    10921080        _thread[u] = new_stem = _parent[stem];
    10931081
    1094         // Finding the node just before the stem node (u) according to
     1082        // Find the node just before the stem node (u) according to
    10951083        // the original thread index
    10961084        for (u = new_stem; _thread[u] != stem; u = _thread[u]) ;
    10971085        _thread[u] = right;
    10981086
    1099         // Changing the parent node of stem and shifting stem and
    1100         // par_stem nodes
     1087        // Change the parent node of stem and shift stem and par_stem nodes
    11011088        _parent[stem] = par_stem;
    11021089        par_stem = stem;
    11031090        stem = new_stem;
    11041091
    1105         // Finding the last successor of stem (u) and the node after it
    1106         // (right) according to the thread index
     1092        // Find the last successor of stem (u) and the node after it (right)
     1093        // according to the thread index
    11071094        for (u = stem; _depth[_thread[u]] > _depth[stem]; u = _thread[u]) ;
    11081095        right = _thread[u];
     
    11191106    }
    11201107
    1121     /// Update \c pred_edge and \c forward node maps.
    1122     inline void updatePredEdge() {
     1108    // Update _pred_edge and _forward node maps.
     1109    void updatePredEdge() {
    11231110      Node u = u_out, v;
    11241111      while (u != u_in) {
     
    11321119    }
    11331120
    1134     /// Update \c depth and \c potential node maps.
    1135     inline void updateDepthPotential() {
     1121    // Update _depth and _potential node maps
     1122    void updateDepthPotential() {
    11361123      _depth[u_in] = _depth[v_in] + 1;
    11371124      Cost sigma = _forward[u_in] ?
     
    11461133    }
    11471134
    1148     /// Execute the algorithm.
     1135    // Execute the algorithm
    11491136    bool start(PivotRuleEnum pivot_rule) {
    1150       // Selecting the pivot rule implementation
     1137      // Select the pivot rule implementation
    11511138      switch (pivot_rule) {
    11521139        case FIRST_ELIGIBLE_PIVOT:
     
    11681155      PivotRuleImplementation pivot(*this, _edges);
    11691156
    1170       // Executing the network simplex algorithm
     1157      // Execute the network simplex algorithm
    11711158      while (pivot.findEnteringEdge()) {
    1172         join = findJoinNode();
     1159        findJoinNode();
    11731160        bool change = findLeavingEdge();
    11741161        changeFlows(change);
     
    11801167      }
    11811168
    1182       // Checking if the flow amount equals zero on all the artificial
    1183       // edges
     1169      // Check if the flow amount equals zero on all the artificial edges
    11841170      for (InEdgeIt e(_graph, _root); e != INVALID; ++e)
    11851171        if (_flow[e] > 0) return false;
     
    11871173        if (_flow[e] > 0) return false;
    11881174
    1189       // Copying flow values to _flow_result
     1175      // Copy flow values to _flow_result
    11901176      if (_lower) {
    11911177        for (typename Graph::EdgeIt e(_graph_ref); e != INVALID; ++e)
     
    11951181          (*_flow_result)[e] = _flow[_edge_ref[e]];
    11961182      }
    1197       // Copying potential values to _potential_result
     1183      // Copy potential values to _potential_result
    11981184      for (typename Graph::NodeIt n(_graph_ref); n != INVALID; ++n)
    11991185        (*_potential_result)[n] = _potential[_node_ref[n]];
Note: See TracChangeset for help on using the changeset viewer.