equal
deleted
inserted
replaced
57 ///\param Num The number type of the capacities and the flow values. |
57 ///\param Num The number type of the capacities and the flow values. |
58 ///\param CapacityMap The capacity map type. |
58 ///\param CapacityMap The capacity map type. |
59 ///\param FlowMap The flow map type. |
59 ///\param FlowMap The flow map type. |
60 /// |
60 /// |
61 ///\author Jacint Szabo |
61 ///\author Jacint Szabo |
|
62 ///\todo Second template parameter is superfluous |
62 template <typename Graph, typename Num, |
63 template <typename Graph, typename Num, |
63 typename CapacityMap=typename Graph::template EdgeMap<Num>, |
64 typename CapacityMap=typename Graph::template EdgeMap<Num>, |
64 typename FlowMap=typename Graph::template EdgeMap<Num> > |
65 typename FlowMap=typename Graph::template EdgeMap<Num> > |
65 class Preflow { |
66 class Preflow { |
66 protected: |
67 protected: |
405 template<typename _CutMap> |
406 template<typename _CutMap> |
406 void minMinCut(_CutMap& M) const { |
407 void minMinCut(_CutMap& M) const { |
407 |
408 |
408 std::queue<Node> queue; |
409 std::queue<Node> queue; |
409 M.set(_source,true); |
410 M.set(_source,true); |
410 queue.push(s); |
411 queue.push(_source); |
411 |
412 |
412 while (!queue.empty()) { |
413 while (!queue.empty()) { |
413 Node w=queue.front(); |
414 Node w=queue.front(); |
414 queue.pop(); |
415 queue.pop(); |
415 |
416 |
843 } |
844 } |
844 } |
845 } |
845 } //relabel |
846 } //relabel |
846 |
847 |
847 }; |
848 }; |
|
849 |
|
850 ///Function type interface for Preflow algorithm. |
|
851 |
|
852 /// \ingroup flowalgs |
|
853 ///Function type interface for Preflow algorithm. |
|
854 ///\sa Preflow |
|
855 template<class GR, class CM, class FM> |
|
856 Preflow<GR,typename CM::Value,CM,FM> preflow(const GR &g, |
|
857 typename GR::Node source, |
|
858 typename GR::Node target, |
|
859 const CM &cap, |
|
860 FM &flow |
|
861 ) |
|
862 { |
|
863 return Preflow<GR,typename CM::Value,CM,FM>(g,source,target,cap,flow); |
|
864 } |
|
865 |
848 } //namespace lemon |
866 } //namespace lemon |
849 |
867 |
850 #endif //LEMON_PREFLOW_H |
868 #endif //LEMON_PREFLOW_H |
851 |
|
852 |
|
853 |
|
854 |
|