lemon-0.x: comparison src/work/marci/augmenting

equal deleted inserted replaced

-:1e771fa295d2
+:643a0607aa0c
 #include <hugo/graph_wrapper.h>
 #include <bfs_dfs.h>
 #include <hugo/invalid.h>
 #include <hugo/maps.h>
-#include <for_each_macros.h>
+//#include <for_each_macros.h>
 /// \file
 /// \brief Maximum flow algorithms.
 /// \ingroup galgs
 while (!bfs.finished()) ++bfs;
 }
 Num flowValue() const {
 Num a=0;
-FOR_EACH_INC_LOC(InEdgeIt, e, *g, t) a+=(*flow)[e];
+for (InEdgeIt e(*g, t); e!=INVALID; ++e) a+=(*flow)[e];
-FOR_EACH_INC_LOC(OutEdgeIt, e, *g, t) a-=(*flow)[e];
+for (OutEdgeIt e(*g, t); e!=INVALID; ++e) a-=(*flow)[e];
 return a;
 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
 }
 template<typename MapGraphWrapper>
 {
 ResGW res_graph(*g, *capacity, *flow);
 bool _augment=false;
 //ReachedMap level(res_graph);
-FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 bfs.pushAndSetReached(s);
 typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
 pred.set(s, INVALID);
 typename ResGW::template NodeMap<Num> free(res_graph);
 //searching for augmenting path
 while ( !bfs.finished() ) {
-ResGWOutEdgeIt e=bfs;
+ResGWEdge e=bfs;
 if (e!=INVALID && bfs.isBNodeNewlyReached()) {
 	Node v=res_graph.tail(e);
 	Node w=res_graph.head(e);
 	pred.set(w, e);
 	if (pred[v]!=INVALID) {
 {
 ResGW res_graph(*g, *capacity, *flow);
 bool _augment=false;
 if (status!=AFTER_FAST_AUGMENTING) {
-FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
 number_of_augmentations=1;
 } else {
 ++number_of_augmentations;
 }
 TrickyReachedMap<ReachedMap>
 typename ResGW::template NodeMap<Num> free(res_graph);
 //searching for augmenting path
 while ( !bfs.finished() ) {
-ResGWOutEdgeIt e=bfs;
+ResGWEdge e=bfs;
 if (e!=INVALID && bfs.isBNodeNewlyReached()) {
 	Node v=res_graph.tail(e);
 	Node w=res_graph.head(e);
 	pred.set(w, e);
 	if (pred[v]!=INVALID) {
 ResGW res_graph(*g, *capacity, *flow);
 //bfs for distances on the residual graph
 //ReachedMap level(res_graph);
-FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 bfs.pushAndSetReached(s);
 typename ResGW::template NodeMap<int>
 dist(res_graph); //filled up with 0's
 typename MG::Node tF=res_graph_to_F[t];
 typename MG::template EdgeMap<ResGWEdge> original_edge(F);
 typename MG::template EdgeMap<Num> residual_capacity(F);
 while ( !bfs.finished() ) {
-ResGWOutEdgeIt e=bfs;
+ResGWEdge e=bfs;
 if (e!=INVALID) {
 	if (bfs.isBNodeNewlyReached()) {
 	  dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
 	  typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)],
 					res_graph_to_F[res_graph.head(e)]);
 dfs.pushAndSetReached(sF);
 while (!dfs.finished()) {
 	++dfs;
 	if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
 	  if (dfs.isBNodeNewlyReached()) {
-	    typename MG::Node v=F.aNode(dfs);
+	    typename MG::Node v=F.tail(dfs);
-	    typename MG::Node w=F.bNode(dfs);
+	    typename MG::Node w=F.head(dfs);
 	    pred.set(w, dfs);
 	    if (pred[v]!=INVALID) {
 	      free.set(w, std::min(free[v], residual_capacity[dfs]));
 	    } else {
 	      free.set(w, residual_capacity[dfs]);
 bool _augment=false;
 ResGW res_graph(*g, *capacity, *flow);
 //ReachedMap level(res_graph);
-FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+for (typename Graph::NodeIt n(*g); n!=INVALID; ++n) level.set(n, 0);
 BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 bfs.pushAndSetReached(s);
 DistanceMap<ResGW> dist(res_graph);
 while ( !bfs.finished() ) {
-ResGWOutEdgeIt e=bfs;
+ResGWEdge e=bfs;
 if (e!=INVALID && bfs.isBNodeNewlyReached()) {
 	dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
 }
 ++bfs;
 } //computing distances from s in the residual graph
 //Subgraph containing the edges on some shortest paths
 ConstMap<typename ResGW::Node, bool> true_map(true);
 typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
 DistanceMap<ResGW> > FilterResGW;
 FilterResGW filter_res_graph(res_graph, true_map, dist);
 //Subgraph, which is able to delete edges which are already
 //met by the dfs
-typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
+typename FilterResGW::template NodeMap<typename FilterResGW::Edge>
 first_out_edges(filter_res_graph);
 typename FilterResGW::NodeIt v;
 for(filter_res_graph.first(v); v!=INVALID; ++v)
 {
 	typename FilterResGW::OutEdgeIt e;
 	filter_res_graph.first(e, v);
 	first_out_edges.set(v, e);
 }
 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
-template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
+template NodeMap<typename FilterResGW::Edge> > ErasingResGW;
 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
 bool __augment=true;
 while (__augment) {
 //computing blocking flow with dfs
 DfsIterator< ErasingResGW,
 	typename ErasingResGW::template NodeMap<bool> >
 	dfs(erasing_res_graph);
 typename ErasingResGW::
-	template NodeMap<typename ErasingResGW::OutEdgeIt>
+	template NodeMap<typename ErasingResGW::Edge> pred(erasing_res_graph);
-	pred(erasing_res_graph);
 pred.set(s, INVALID);
 //invalid iterators for sources
 typename ErasingResGW::template NodeMap<Num>
 	free1(erasing_res_graph);
 dfs.pushAndSetReached
-	///\bug hugo 0.2
+	/// \bug hugo 0.2
 	(typename ErasingResGW::Node
 	 (typename FilterResGW::Node
 	  (typename ResGW::Node(s)
 	   )
 	  )
 	 );
 while (!dfs.finished()) {
 	++dfs;
-	if (erasing_res_graph.valid(typename ErasingResGW::OutEdgeIt(dfs)))
+	if (typename ErasingResGW::Edge(dfs)!=INVALID)
 	  {
 	    if (dfs.isBNodeNewlyReached()) {
-	      typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
+	      typename ErasingResGW::Node v=erasing_res_graph.tail(dfs);
-	      typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
+	      typename ErasingResGW::Node w=erasing_res_graph.head(dfs);
-	      pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
+	      pred.set(w, typename ErasingResGW::Edge(dfs));
 	      if (pred[v]!=INVALID) {
 		free1.set
 		  (w, std::min(free1[v], res_graph.resCap
-			       (typename ErasingResGW::OutEdgeIt(dfs))));
+			       (typename ErasingResGW::Edge(dfs))));
 	      } else {
 		free1.set
 		  (w, res_graph.resCap
-		   (typename ErasingResGW::OutEdgeIt(dfs)));
+		   (typename ErasingResGW::Edge(dfs)));
 	      }
 	      if (w==t) {
 		__augment=true;
 		_augment=true;
 	// 	  Num j1=a1[b1];
 	// 	  typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
 	// 	  typename ErasingResGW::Node b2;
 	// 	  Num j2=a2[b2];
 	Num augment_value=free1[n];
-	while (erasing_res_graph.valid(pred[n])) {
+	while (pred[n]!=INVALID) {
-	  typename ErasingResGW::OutEdgeIt e=pred[n];
+	  typename ErasingResGW::Edge e=pred[n];
 	  res_graph.augment(e, augment_value);
 	  n=erasing_res_graph.tail(e);
 	  if (res_graph.resCap(e)==0)
 	    erasing_res_graph.erase(e);
 	}

changeset 842	a4bb28813570
parent 775	e46a1f0623a0
child 854	baf0b6e40211