# Changeset 1166:d59484d5fc1f in lemon for lemon

Ignore:
Timestamp:
11/07/12 17:39:39 (8 years ago)
Branch:
default
Parents:
1163:e344f0887c59 (diff), 1165:16f55008c863 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge docfix #437

Location:
lemon
Files:
4 edited

Unmodified
Removed
• ## lemon/capacity_scaling.h

 r1137 /// \ref edmondskarp72theoretical. It is an efficient dual /// solution method. /// /// This algorithm is typically slower than \ref CostScaling and /// \ref NetworkSimplex, but in special cases, it can be more /// efficient than them. /// (For more information, see \ref min_cost_flow_algs "the module page".) /// /// Most of the parameters of the problem (except for the digraph) } /// \brief Return the flow map (the primal solution). /// \brief Copy the flow values (the primal solution) into the /// given map. /// /// This function copies the flow value on each arc into the given } /// \brief Return the potential map (the dual solution). /// \brief Copy the potential values (the dual solution) into the /// given map. /// /// This function copies the potential (dual value) of each node
• ## lemon/capacity_scaling.h

 r1165 /// /// \warning Both \c V and \c C must be signed number types. /// \warning All input data (capacities, supply values, and costs) must /// be integer. /// \warning Capacity bounds and supply values must be integer, but /// arc costs can be arbitrary real numbers. /// \warning This algorithm does not support negative costs for /// arcs having infinite upper bound.
• ## lemon/network_simplex.h

 r1136 /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest /// implementations available in LEMON for this problem. /// implementations available in LEMON for solving this problem. /// (For more information, see \ref min_cost_flow_algs "the module page".) /// Furthermore, this class supports both directions of the supply/demand /// inequality constraints. For more information, see \ref SupplyType. } /// \brief Return the flow map (the primal solution). /// \brief Copy the flow values (the primal solution) into the /// given map. /// /// This function copies the flow value on each arc into the given } /// \brief Return the potential map (the dual solution). /// \brief Copy the potential values (the dual solution) into the /// given map. /// /// This function copies the potential (dual value) of each node
• ## lemon/network_simplex.h

 r1165 /// the \ref run() function. /// /// \ref NetworkSimplex provides five different pivot rule /// implementations that significantly affect the running time /// \ref NetworkSimplex provides five different implementations for /// the pivot strategy that significantly affects the running time /// of the algorithm. /// By default, \ref BLOCK_SEARCH "Block Search" is used, which /// turend out to be the most efficient and the most robust on various /// test inputs. /// However, another pivot rule can be selected using the \ref run() /// function with the proper parameter. /// According to experimental tests conducted on various problem /// instances, \ref BLOCK_SEARCH "Block Search" and /// \ref ALTERING_LIST "Altering Candidate List" rules turned out /// to be the most efficient. /// Since \ref BLOCK_SEARCH "Block Search" is a simpler strategy that /// seemed to be slightly more robust, it is used by default. /// However, another pivot rule can easily be selected using the /// \ref run() function with the proper parameter. enum PivotRule { /// The \e Altering \e Candidate \e List pivot rule. /// It is a modified version of the Candidate List method. /// It keeps only the several best eligible arcs from the former /// It keeps only a few of the best eligible arcs from the former /// candidate list and extends this list in every iteration. ALTERING_LIST SortFunc(const CostVector &map) : _map(map) {} bool operator()(int left, int right) { return _map[left] > _map[right]; return _map[left] < _map[right]; } }; const double BLOCK_SIZE_FACTOR = 1.0; const int MIN_BLOCK_SIZE = 10; const double HEAD_LENGTH_FACTOR = 0.1; const double HEAD_LENGTH_FACTOR = 0.01; const int MIN_HEAD_LENGTH = 3; } for (e = 0; e != _next_arc; ++e) { _cand_cost[e] = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); if (_cand_cost[e] < 0) { c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); if (c < 0) { _cand_cost[e] = c; _candidates[_curr_length++] = e; } search_end: // Make heap of the candidate list (approximating a partial sort) make_heap( _candidates.begin(), _candidates.begin() + _curr_length, _sort_func ); // Pop the first element of the heap // Perform partial sort operation on the candidate list int new_length = std::min(_head_length + 1, _curr_length); std::partial_sort(_candidates.begin(), _candidates.begin() + new_length, _candidates.begin() + _curr_length, _sort_func); // Select the entering arc and remove it from the list _in_arc = _candidates; _next_arc = e; pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, _sort_func ); _curr_length = std::min(_head_length, _curr_length - 1); _candidates = _candidates[new_length - 1]; _curr_length = new_length - 1; return true; }
Note: See TracChangeset for help on using the changeset viewer.