COIN-OR::LEMON - Graph Library

Changeset 2444:06f3702bf18d in lemon-0.x


Ignore:
Timestamp:
05/11/07 18:03:20 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3281
Message:

Patch in network simplex

Patch from Peter Kovacs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/network_simplex.h

    r2440 r2444  
    3131
    3232/// \brief The pivot rule used in the algorithm.
    33 #define EDGE_BLOCK_PIVOT
    3433//#define FIRST_ELIGIBLE_PIVOT
    3534//#define BEST_ELIGIBLE_PIVOT
     35#define EDGE_BLOCK_PIVOT
    3636//#define CANDIDATE_LIST_PIVOT
    3737//#define SORTED_LIST_PIVOT
     38
     39//#define _DEBUG_ITER_
     40
    3841
    3942/// \brief State constant for edges at their lower bounds.
     
    4649#ifdef EDGE_BLOCK_PIVOT
    4750  /// \brief Number of blocks for the "Edge Block" pivot rule.
    48   #define BLOCK_NUM       100
    49   /// \brief Lower bound for the number of edges to use "Edge Block"
    50   // pivot rule instead of "First Eligible" pivot rule.
    51   #define MIN_BOUND       1000
     51  #define BLOCK_NUM             100
     52  /// \brief Lower bound for the size of blocks.
     53  #define MIN_BLOCK_SIZE        10
    5254#endif
    5355
     
    5658  /// \brief The maximum length of the edge list for the
    5759  /// "Candidate List" pivot rule.
    58   #define LIST_LENGTH     100
     60  #define LIST_LENGTH           100
    5961  /// \brief The maximum number of minor iterations between two major
    6062  /// itarations.
    61   #define MINOR_LIMIT     50
     63  #define MINOR_LIMIT           10
    6264#endif
    6365
     
    6769  /// \brief The maximum length of the edge list for the
    6870  /// "Sorted List" pivot rule.
    69   #define LIST_LENGTH     500
    70   #define LOWER_DIV       4
    71 #endif
    72 
    73 //#define _DEBUG_ITER_
     71  #define LIST_LENGTH           500
     72  #define LOWER_DIV             3
     73#endif
    7474
    7575namespace lemon {
     
    514514      // Initializing block_size for the edge block pivot rule
    515515      int edge_num = countEdges(graph);
    516       block_size = edge_num > MIN_BOUND ? edge_num / BLOCK_NUM + 1 : 1;
     516      block_size = edge_num >= BLOCK_NUM * MIN_BLOCK_SIZE ?
     517                   edge_num / BLOCK_NUM : MIN_BLOCK_SIZE;
    517518#endif
    518519#ifdef CANDIDATE_LIST_PIVOT
     
    564565    /// pivot rule.
    565566    bool findEnteringEdge(EdgeIt &next_edge) {
    566       if (block_size == 1) {
    567         // Performing first eligible selection
    568         for (EdgeIt e = next_edge; e != INVALID; ++e) {
    569           if (state[e] * red_cost[e] < 0) {
    570             in_edge = e;
    571             next_edge = ++e;
    572             return true;
    573           }
    574         }
     567      // Performing edge block selection
     568      Cost curr, min = 0;
     569      EdgeIt min_edge(graph);
     570      int cnt = 0;
     571      for (EdgeIt e = next_edge; e != INVALID; ++e) {
     572        if ((curr = state[e] * red_cost[e]) < min) {
     573          min = curr;
     574          min_edge = e;
     575        }
     576        if (++cnt == block_size) {
     577          if (min < 0) break;
     578          cnt = 0;
     579        }
     580      }
     581      if (!(min < 0)) {
    575582        for (EdgeIt e(graph); e != next_edge; ++e) {
    576           if (state[e] * red_cost[e] < 0) {
    577             in_edge = e;
    578             next_edge = ++e;
    579             return true;
    580           }
    581         }
    582         return false;
    583       } else {
    584         // Performing edge block selection
    585         Cost curr, min = 0;
    586         EdgeIt min_edge(graph);
    587         int cnt = 0;
    588         for (EdgeIt e = next_edge; e != INVALID; ++e) {
    589583          if ((curr = state[e] * red_cost[e]) < min) {
    590584            min = curr;
     
    596590          }
    597591        }
    598         if (!(min < 0)) {
    599           for (EdgeIt e(graph); e != next_edge; ++e) {
    600             if ((curr = state[e] * red_cost[e]) < min) {
    601               min = curr;
    602               min_edge = e;
    603             }
    604             if (++cnt == block_size) {
    605               if (min < 0) break;
    606               cnt = 0;
    607             }
    608           }
    609         }
    610         in_edge = min_edge;
    611         if ((next_edge = ++min_edge) == INVALID)
    612           next_edge = EdgeIt(graph);
    613         return min < 0;
    614       }
     592      }
     593      in_edge = min_edge;
     594      if ((next_edge = ++min_edge) == INVALID)
     595        next_edge = EdgeIt(graph);
     596      return min < 0;
    615597    }
    616598#endif
     
    697679          candidates.push_back(e);
    698680          if (curr < min) min = curr;
    699           if (candidates.size() >= LIST_LENGTH) break;
     681          if (candidates.size() == LIST_LENGTH) break;
    700682        }
    701683      }
    702684      if (candidates.size() == 0) return false;
    703685      sort(candidates.begin(), candidates.end(), sort_func);
     686      in_edge = candidates.front();
     687      candidates.pop_front();
    704688      return true;
    705689    }
     
    910894
    911895#ifdef _DEBUG_ITER_
    912       t_iter.stop();
    913896      std::cout << "Network Simplex algorithm finished. " << iter_num
    914                 << " pivot iterations performed.";
     897                << " pivot iterations performed." << std::endl;
    915898#endif
    916899
Note: See TracChangeset for help on using the changeset viewer.