Changeset 631:26819ef1611f in lemon0.x for src
 Timestamp:
 05/13/04 12:30:20 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@822
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/max_flow.h
r615 r631 1 1 // * C++ * 2 3 /*4 Heuristics:5 2 phase6 gap7 list 'level_list' on the nodes on level i implemented by hand8 stack 'active' on the active nodes on level i9 runs heuristic 'highest label' for H1*n relabels10 runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'11 12 Parameters H0 and H1 are initialized to 20 and 1.13 14 Constructors:15 16 Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if17 FlowMap is not constant zero, and should be true if it is18 19 Members:20 21 void run()22 23 Num flowValue() : returns the value of a maximum flow24 25 void minMinCut(CutMap& M) : sets M to the characteristic vector of the26 minimum min cut. M should be a map of bools initialized to false. ??Is it OK?27 28 void maxMinCut(CutMap& M) : sets M to the characteristic vector of the29 maximum min cut. M should be a map of bools initialized to false.30 31 void minCut(CutMap& M) : sets M to the characteristic vector of32 a min cut. M should be a map of bools initialized to false.33 34 */35 36 2 #ifndef HUGO_MAX_FLOW_H 37 3 #define HUGO_MAX_FLOW_H … … 48 14 49 15 /// \file 50 /// \brief Maximum flow s.16 /// \brief Maximum flow algorithms. 51 17 /// \ingroup galgs 52 18 53 19 namespace hugo { 54 20 55 56 // ///\author Marton Makai, Jacint Szabo 57 /// A class for computing max flows and related quantities. 58 /// \ingroup galgs 21 /// \addtogroup galgs 22 /// @{ 23 ///Maximum flow algorithms class. 24 25 ///This class provides various algorithms for finding a flow of 26 ///maximum value in a directed graph. The \e source node, the \e 27 ///target node, the \e capacity of the edges and the \e starting \e 28 ///flow value of the edges can be passed to the algorithm through the 29 ///constructor. It is possible to change these quantities using the 30 ///functions \ref resetSource, \ref resetTarget, \ref resetCap and 31 ///\ref resetFlow. Before any subsequent runs of any algorithm of 32 ///the class \ref resetFlow should be called, otherwise it will 33 ///start from a maximum flow. 34 ///After running an algorithm of the class, the maximum value of a 35 ///value can be obtained by calling \ref flowValue(). The minimum 36 ///value cut can be written into a \c node map of \c bools by 37 ///calling \ref minCut. (\ref minMinCut and \ref maxMinCut writes 38 ///the inclusionwise minimum and maximum of the minimum value 39 ///cuts, resp.) 40 ///\param Graph The undirected graph type the algorithm runs on. 41 ///\param Num The number type of the capacities and the flow values. 42 ///\param CapMap The type of the capacity map. 43 ///\param FlowMap The type of the flow map. 44 ///\author Marton Makai, Jacint Szabo 59 45 template <typename Graph, typename Num, 60 46 typename CapMap=typename Graph::template EdgeMap<Num>, … … 64 50 typedef typename Graph::Node Node; 65 51 typedef typename Graph::NodeIt NodeIt; 52 typedef typename Graph::EdgeIt EdgeIt; 66 53 typedef typename Graph::OutEdgeIt OutEdgeIt; 67 54 typedef typename Graph::InEdgeIt InEdgeIt; … … 82 69 //typedef typename ResGW::template NodeMap<bool> ReachedMap; 83 70 typedef typename Graph::template NodeMap<int> ReachedMap; 71 72 73 //level works as a bool map in augmenting path algorithms and is 74 //used by bfs for storing reached information. In preflow, it 75 //shows the levels of nodes. 84 76 ReachedMap level; 85 //level works as a bool map in augmenting path algorithms 86 //and is used by bfs for storing reached information. 87 //In preflow, it shows levels of nodes. 88 //typename Graph::template NodeMap<int> level; 77 78 //excess is needed only in preflow 89 79 typename Graph::template NodeMap<Num> excess; 90 // protected: 80 81 //fixme 82 // protected: 91 83 // MaxFlow() { } 92 84 // void set(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, … … 109 101 public: 110 102 111 ///\todo Document this. 112 ///\todo Maybe, it should be PRE_FLOW instead. 113 /// \c NO_FLOW means nothing, 114 /// \c ZERO_FLOW means something, 115 /// \c GEN_FLOW means something else, 116 /// \c PRE_FLOW is something different. 103 ///Indicates the property of the starting flow. 104 105 ///Indicates the property of the starting flow. The meanings are as follows: 106 /// \c ZERO_FLOW: constant zero flow 107 /// \c GEN_FLOW: any flow, i.e. the sum of the inflows equals to 108 ///the sum of the outflows in every node except the \e source and 109 ///the \e target. 110 /// \c PRE_FLOW: any preflow, i.e. the sum of the inflows is at 111 ///least the sum of the outflows in every node except the \e source. 112 /// \c NO_FLOW: indicates an unspecified edge map. \ref flow will be 113 ///set to the constant zero flow in the beginning of the algorithm in this case. 117 114 enum flowEnum{ 118 115 ZERO_FLOW, … … 127 124 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} 128 125 129 /// A max flow algorithm is run. 130 /// \pre The flow have to satisfy the requirements 131 /// stated in fe. 126 ///Runs a maximum flow algorithm. 127 128 ///Runs a preflow algorithm, which is the fastest maximum flow 129 ///algorithm uptodate. The default for \c fe is ZERO_FLOW. 130 ///\pre The starting flow must be 131 ///  a constant zero flow if \c fe is \c ZERO_FLOW, 132 ///  an arbitary flow if \c fe is \c GEN_FLOW, 133 ///  an arbitary preflow if \c fe is \c PRE_FLOW, 134 ///  any map if \c fe is NO_FLOW. 132 135 void run(flowEnum fe=ZERO_FLOW) { 133 136 preflow(fe); 134 137 } 135 138 136 /// A preflow algorithm is run. 137 /// \pre The initial edgemap have to be a 138 /// zero flow if \c fe is \c ZERO_FLOW, 139 /// a flow if \c fe is \c GEN_FLOW, 140 /// a preflow if fe is \c PRE_FLOW and 141 /// anything if fe is NO_FLOW. 139 140 ///Runs a preflow algorithm. 141 142 ///Runs a preflow algorithm. The preflow algorithms provide the 143 ///fastest way to compute a maximum flow in a directed graph. 144 ///\pre The starting flow must be 145 ///  a constant zero flow if \c fe is \c ZERO_FLOW, 146 ///  an arbitary flow if \c fe is \c GEN_FLOW, 147 ///  an arbitary preflow if \c fe is \c PRE_FLOW, 148 ///  any map if \c fe is NO_FLOW. 142 149 void preflow(flowEnum fe) { 143 preflowPhase0(fe); 144 preflowPhase1(); 145 } 146 147 /// Run the first phase of preflow, starting from a 0 flow, from a flow, 148 /// or from a preflow, of from undefined value according to \c fe. 149 void preflowPhase0(flowEnum fe); 150 151 /// Second phase of preflow. 152 void preflowPhase1(); 150 preflowPhase1(fe); 151 preflowPhase2(); 152 } 153 // Heuristics: 154 // 2 phase 155 // gap 156 // list 'level_list' on the nodes on level i implemented by hand 157 // stack 'active' on the active nodes on level i 158 // runs heuristic 'highest label' for H1*n relabels 159 // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' 160 // Parameters H0 and H1 are initialized to 20 and 1. 161 162 ///Runs the first phase of the preflow algorithm. 163 164 ///The preflow algorithm consists of two phases, this method runs the 165 ///first phase. After the first phase the maximum flow value and a 166 ///minimum value cut can already be computed, though a maximum flow 167 ///is net yet obtained. So after calling this method \ref flowValue 168 ///and \ref actMinCut gives proper results. 169 ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not 170 ///give minimum value cuts unless calling \ref preflowPhase2. 171 ///\pre The starting flow must be 172 ///  a constant zero flow if \c fe is \c ZERO_FLOW, 173 ///  an arbitary flow if \c fe is \c GEN_FLOW, 174 ///  an arbitary preflow if \c fe is \c PRE_FLOW, 175 ///  any map if \c fe is NO_FLOW. 176 void preflowPhase1( flowEnum fe ); 177 178 ///Runs the second phase of the preflow algorithm. 179 180 ///The preflow algorithm consists of two phases, this method runs 181 ///the second phase. After calling \ref preflowPhase1 and then 182 ///\ref preflowPhase2 the methods \ref flowValue, \ref minCut, 183 ///\ref minMinCut and \ref maxMinCut give proper results. 184 ///\pre \ref preflowPhase1 must be called before. 185 void preflowPhase2(); 153 186 154 187 /// Starting from a flow, this method searches for an augmenting path … … 170 203 bool augmentOnBlockingFlow2(); 171 204 172 /// Returns the actual flow value. 173 /// More precisely, it returns the negative excess of s, thus 174 /// this works also for preflows. 205 /// Returns the maximum value of a flow. 206 207 /// Returns the maximum value of a flow, by counting the 208 /// overflow of the target node \ref t. 209 /// It can be called already after running \ref preflowPhase1. 175 210 Num flowValue() { 176 211 Num a=0; … … 178 213 FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a=(*flow)[e]; 179 214 return a; 180 } 181 182 /// Should be used between preflowPhase0 and preflowPhase1. 215 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan 216 } 217 218 ///Returns a minimum value cut after calling \ref preflowPhase1. 219 220 ///After the first phase of the preflow algorithm the maximum flow 221 ///value and a minimum value cut can already be computed. This 222 ///method can be called after running \ref preflowPhase1 for 223 ///obtaining a minimum value cut. 224 /// \warning Gives proper result only right after calling \ref 225 /// preflowPhase1. 183 226 /// \todo We have to make some status variable which shows the 184 227 /// actual state … … 197 240 } 198 241 199 /// The unique inclusionwise minimum cut is computed by 200 /// processing a bfs from s in the residual graph. 201 /// \pre flow have to be a max flow otherwise it will the whole nodeset. 242 ///Returns the inclusionwise minimum of the minimum value cuts. 243 244 ///Sets \c M to the characteristic vector of the minimum value cut 245 ///which is inclusionwise minimum. It is computed by processing 246 ///a bfs from the source node \c s in the residual graph. 247 ///\pre M should be a node map of bools initialized to false. 248 ///\pre \c flow must be a maximum flow. 202 249 template<typename _CutMap> 203 250 void minMinCut(_CutMap& M) { … … 232 279 } 233 280 234 235 /// The unique inclusionwise maximum cut is computed by 236 /// processing a reverse bfs from t in the residual graph. 237 /// \pre flow have to be a max flow otherwise it will be empty. 281 ///Returns the inclusionwise maximum of the minimum value cuts. 282 283 ///Sets \c M to the characteristic vector of the minimum value cut 284 ///which is inclusionwise maximum. It is computed by processing a 285 ///backward bfs from the target node \c t in the residual graph. 286 ///\pre M should be a node map of bools initialized to false. 287 ///\pre \c flow must be a maximum flow. 238 288 template<typename _CutMap> 239 289 void maxMinCut(_CutMap& M) { … … 273 323 } 274 324 275 276 /// A minimum cut is computed. 325 ///Returns a minimum value cut. 326 327 ///Sets \c M to the characteristic vector of a minimum value cut. 328 ///\pre M should be a node map of bools initialized to false. 329 ///\pre \c flow must be a maximum flow. 277 330 template<typename CutMap> 278 331 void minCut(CutMap& M) { minMinCut(M); } 279 332 280 /// 333 ///Resets the source node to \c _s. 334 335 ///Resets the source node to \c _s. 336 /// 281 337 void resetSource(Node _s) { s=_s; } 338 339 ///Resets the target node to \c _t. 340 341 ///Resets the target node to \c _t. 282 342 /// 283 343 void resetTarget(Node _t) { t=_t; } 284 344 285 /// capacitymap is changed. 345 /// Resets the edge map of the capacities to _cap. 346 347 /// Resets the edge map of the capacities to _cap. 348 /// 286 349 void resetCap(const CapMap& _cap) { capacity=&_cap; } 287 350 288 /// flowmap is changed. 351 /// Resets the edge map of the flows to _flow. 352 353 /// Resets the edge map of the flows to _flow. 354 /// 289 355 void resetFlow(FlowMap& _flow) { flow=&_flow; } 290 356 … … 375 441 376 442 switch (fe) { 443 case NO_FLOW: //flow is already set to const zero in this case 377 444 case ZERO_FLOW: 378 445 { … … 587 654 588 655 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 589 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase 0( flowEnum fe )656 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1( flowEnum fe ) 590 657 { 591 658 … … 616 683 //setting each node to level n 617 684 618 switch (fe) { 685 if ( fe == NO_FLOW ) { 686 EdgeIt e; 687 for(g>first(e); g>valid(e); g>next(e)) flow>set(e,0); 688 } 689 690 switch (fe) { //computing the excess 619 691 case PRE_FLOW: 620 692 { 621 //computing the excess622 693 NodeIt v; 623 694 for(g>first(v); g>valid(v); g>next(v)) { … … 639 710 case GEN_FLOW: 640 711 { 641 //computing the excess of t 712 NodeIt v; 713 for(g>first(v); g>valid(v); g>next(v)) excess.set(v,0); 714 642 715 Num exc=0; 643 644 716 InEdgeIt e; 645 717 for(g>first(e,t); g>valid(e); g>next(e)) exc+=(*flow)[e]; 646 718 OutEdgeIt f; 647 719 for(g>first(f,t); g>valid(f); g>next(f)) exc=(*flow)[f]; 648 649 720 excess.set(t,exc); 650 651 721 break; 652 722 } 653 default:; 723 case ZERO_FLOW: 724 case NO_FLOW: 725 { 726 NodeIt v; 727 for(g>first(v); g>valid(v); g>next(v)) excess.set(v,0); 728 break; 729 } 654 730 } 655 731 … … 696 772 697 773 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 698 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase 1()774 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase2() 699 775 { 700 776
Note: See TracChangeset
for help on using the changeset viewer.