Changeset 1030:a80381c43760 in lemon
 Timestamp:
 02/28/11 10:19:34 (13 years ago)
 Branch:
 default
 Parents:
 1026:9312d6c89d02 (diff), 1027:30d5f950aa5f (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
 Files:

 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/preflow.h
r985 r1029 544 544 _flow>set(e, (*_capacity)[e]); 545 545 (*_excess)[u] += rem; 546 if (u != _target && !_level>active(u)) {547 _level>activate(u);548 }549 546 } 550 547 } … … 556 553 _flow>set(e, 0); 557 554 (*_excess)[v] += rem; 558 if (v != _target && !_level>active(v)) { 559 _level>activate(v); 560 } 561 } 562 } 555 } 556 } 557 for (NodeIt n(_graph); n != INVALID; ++n) 558 if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) 559 _level>activate(n); 560 563 561 return true; 564 562 } 
lemon/preflow.h
r1027 r1029 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 095 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 53 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 #ifdef DOXYGEN 56 typedef GR::ArcMap<Value> FlowMap; 57 #else 55 58 typedef typename Digraph::template ArcMap<Value> FlowMap; 59 #endif 56 60 57 61 /// \brief Instantiates a FlowMap. … … 68 72 /// The elevator type used by Preflow algorithm. 69 73 /// 70 /// \sa Elevator 71 /// \sa LinkedElevator 72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; 74 /// \sa Elevator, LinkedElevator 75 #ifdef DOXYGEN 76 typedef lemon::Elevator<GR, GR::Node> Elevator; 77 #else 78 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 79 #endif 73 80 74 81 /// \brief Instantiates an Elevator. … … 96 103 /// This class provides an implementation of GoldbergTarjan's \e preflow 97 104 /// \e pushrelabel algorithm producing a \ref max_flow 98 /// "flow of maximum value" in a digraph. 105 /// "flow of maximum value" in a digraph \ref clrs01algorithms, 106 /// \ref amo93networkflows, \ref goldberg88newapproach. 99 107 /// The preflow algorithms are the fastest known maximum 100 /// flow algorithms. The current implementation use a mixture of the108 /// flow algorithms. The current implementation uses a mixture of the 101 109 /// \e "highest label" and the \e "bound decrease" heuristics. 102 110 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. … … 106 114 /// second phase constructs a feasible maximum flow on each arc. 107 115 /// 116 /// \warning This implementation cannot handle infinite or very large 117 /// capacities (e.g. the maximum value of \c CAP::Value). 118 /// 108 119 /// \tparam GR The type of the digraph the algorithm runs on. 109 120 /// \tparam CAP The type of the capacity map. The default map 110 121 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 122 /// \tparam TR The traits class that defines various types used by the 123 /// algorithm. By default, it is \ref PreflowDefaultTraits 124 /// "PreflowDefaultTraits<GR, CAP>". 125 /// In most cases, this parameter should not be set directly, 126 /// consider to use the named template parameters instead. 111 127 #ifdef DOXYGEN 112 128 template <typename GR, typename CAP, typename TR> … … 258 274 /// able to automatically created by the algorithm (i.e. the 259 275 /// digraph and the maximum level should be passed to it). 260 /// However an external elevator object could also be passed to the276 /// However, an external elevator object could also be passed to the 261 277 /// algorithm with the \ref elevator(Elevator&) "elevator()" function 262 278 /// before calling \ref run() or \ref init(). … … 372 388 } 373 389 374 /// \brief Sets the tolerance used by algorithm. 375 /// 376 /// Sets the tolerance used by algorithm. 390 /// \brief Sets the tolerance used by the algorithm. 391 /// 392 /// Sets the tolerance object used by the algorithm. 393 /// \return <tt>(*this)</tt> 377 394 Preflow& tolerance(const Tolerance& tolerance) { 378 395 _tolerance = tolerance; … … 382 399 /// \brief Returns a const reference to the tolerance. 383 400 /// 384 /// Returns a const reference to the tolerance. 401 /// Returns a const reference to the tolerance object used by 402 /// the algorithm. 385 403 const Tolerance& tolerance() const { 386 404 return _tolerance; … … 390 408 /// The simplest way to execute the preflow algorithm is to use 391 409 /// \ref run() or \ref runMinCut().\n 392 /// If you need morecontrol on the initial solution or the execution,393 /// first you have to call one of the \ref init() functions, then410 /// If you need better control on the initial solution or the execution, 411 /// you have to call one of the \ref init() functions first, then 394 412 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). 395 413 
test/preflow_test.cc
r956 r1029 157 157 } 158 158 159 void initFlowTest() 160 { 161 DIGRAPH_TYPEDEFS(SmartDigraph); 162 163 SmartDigraph g; 164 SmartDigraph::ArcMap<int> cap(g),iflow(g); 165 Node s=g.addNode(); Node t=g.addNode(); 166 Node n1=g.addNode(); Node n2=g.addNode(); 167 Arc a; 168 a=g.addArc(s,n1); cap[a]=20; iflow[a]=20; 169 a=g.addArc(n1,n2); cap[a]=10; iflow[a]=0; 170 a=g.addArc(n2,t); cap[a]=20; iflow[a]=0; 171 172 Preflow<SmartDigraph> pre(g,cap,s,t); 173 pre.init(iflow); 174 pre.startFirstPhase(); 175 check(pre.flowValue() == 10, "The incorrect max flow value."); 176 check(pre.minCut(s), "Wrong min cut (Node s)."); 177 check(pre.minCut(n1), "Wrong min cut (Node n1)."); 178 check(!pre.minCut(n2), "Wrong min cut (Node n2)."); 179 check(!pre.minCut(t), "Wrong min cut (Node t)."); 180 } 181 182 159 183 int main() { 160 184 … … 247 271 "The max flow value or the three min cut values are incorrect."); 248 272 273 initFlowTest(); 274 249 275 return 0; 250 276 } 
test/preflow_test.cc
r1027 r1029 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 200320 095 * Copyright (C) 20032010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 96 96 const PreflowType& const_preflow_test = preflow_test; 97 97 98 const PreflowType::Elevator& elev = const_preflow_test.elevator(); 99 preflow_test.elevator(const_cast<PreflowType::Elevator&>(elev)); 100 PreflowType::Tolerance tol = const_preflow_test.tolerance(); 101 preflow_test.tolerance(tol); 102 98 103 preflow_test 99 104 .capacityMap(cap) … … 114 119 b = const_preflow_test.minCut(n); 115 120 const_preflow_test.minCutMap(cut); 116 121 117 122 ignore_unused_variable_warning(fm); 118 123 }
Note: See TracChangeset
for help on using the changeset viewer.