lemon-0.x: comparison src/work/edmonds

equal deleted inserted replaced

-:1bb8dd30d045
+:f0d33e345494
 #include <algorithm>
 #include <list>
 #include <iterator>
 #include <bfs_iterator.hh>
-#include <time_measure.h>
+//#include <time_measure.h>
 namespace hugo {
 template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
 class ResGraph {
 OldOutEdgeIt out;
 OldInEdgeIt in;
 bool out_or_in; //1, iff out
 public:
 EdgeIt() : out_or_in(1) { }
+//EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
 Number free() const {
 	if (out_or_in) {
 	  return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
 	} else {
 	  return (/*resG->*/flow->get(in));
 	  /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
 	} else {
 	  /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
 	}
 }
+void print() {
+	if (out_or_in) {
+	  std::cout << "out ";
+	  if (out.valid())
+	    std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
+	  else
+	    std::cout << "invalid";
+	}
+	else {
+	  std::cout << "in ";
+	  if (in.valid())
+	    std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
+	  else
+	    std::cout << "invalid";
+	}
+	std::cout << std::endl;
+}
 };
 class OutEdgeIt : public EdgeIt {
 friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
 public:
 private:
 OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
 	G=&_G;
 	flow=&_flow;
 	capacity=&_capacity;
-	out=/*resG->*/G->template first<OldOutEdgeIt>(v);
+	//out=/*resG->*/G->template first<OldOutEdgeIt>(v);
+	G->getFirst(out, v);
 	while( out.valid() && !(free()>0) ) { ++out; }
 	if (!out.valid()) {
 	  out_or_in=0;
-	  in=/*resG->*/G->template first<OldInEdgeIt>(v);
+	  //in=/*resG->*/G->template first<OldInEdgeIt>(v);
+	  G->getFirst(in, v);
 	  while( in.valid() && !(free()>0) ) { ++in; }
 	}
 }
 public:
 OutEdgeIt& operator++() {
 	  NodeIt v=/*resG->*/G->aNode(out);
 	  ++out;
 	  while( out.valid() && !(free()>0) ) { ++out; }
 	  if (!out.valid()) {
 	    out_or_in=0;
-	    in=/*resG->*/G->template first<OldInEdgeIt>(v);
+	    G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
 	    while( in.valid() && !(free()>0) ) { ++in; }
 	  }
 	} else {
 	  ++in;
 	  while( in.valid() && !(free()>0) ) { ++in; }
 	}
 	return *this;
 }
 };
+class EachEdgeIt : public EdgeIt {
+typename Graph::EachNodeIt v;
+public:
+EachEdgeIt() { }
+//EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
+EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
+	G=&_G;
+	flow=&_flow;
+	capacity=&_capacity;
+	out_or_in=1;
+	G->getFirst(v);
+	if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
+	while (out.valid() && !(free()>0) ) { ++out; }
+	while (v.valid() && !out.valid()) {
+	  ++v;
+	  if (v.valid()) G->getFirst(out, v);
+	  while (out.valid() && !(free()>0) ) { ++out; }
+	}
+	if (!out.valid()) {
+	  out_or_in=0;
+	  G->getFirst(v);
+	  if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
+	  while (in.valid() && !(free()>0) ) { ++in; }
+	  while (v.valid() && !in.valid()) {
+	    ++v;
+	    if (v.valid()) G->getFirst(in, v);
+	    while (in.valid() && !(free()>0) ) { ++in; }
+	  }
+	}
+}
+EachEdgeIt& operator++() {
+	if (out_or_in) {
+	  ++out;
+	  while (out.valid() && !(free()>0) ) { ++out; }
+	  while (v.valid() && !out.valid()) {
+	    ++v;
+	    if (v.valid()) G->getFirst(out, v);
+	    while (out.valid() && !(free()>0) ) { ++out; }
+	  }
+	  if (!out.valid()) {
+	    out_or_in=0;
+	    G->getFirst(v);
+	    if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
+	    while (in.valid() && !(free()>0) ) { ++in; }
+	    while (v.valid() && !in.valid()) {
+	      ++v;
+	      if (v.valid()) G->getFirst(in, v);
+	      while (in.valid() && !(free()>0) ) { ++in; }
+	    }
+	  }
+	} else {
+	  ++in;
+	  while (in.valid() && !(free()>0) ) { ++in; }
+	  while (v.valid() && !in.valid()) {
+	    ++v;
+	    if (v.valid()) G->getFirst(in, v);
+	    while (in.valid() && !(free()>0) ) { ++in; }
+	  }
+	}
+	return *this;
+}
+};
 void getFirst(OutEdgeIt& e, NodeIt v) const {
 e=OutEdgeIt(G, v, flow, capacity);
+}
+void getFirst(EachEdgeIt& e) const {
+e=EachEdgeIt(G, flow, capacity);
 }
 void getFirst(EachNodeIt& v) const { G.getFirst(v); }
 template< typename It >
 It first() const {
 typedef typename AugGraph::EdgeIt AugEdgeIt;
 //AugGraph res_graph;
 //typedef typename AugGraph::NodeMap<bool> ReachedMap;
 //typename AugGraph::NodeMap<AugEdgeIt> pred;
-//typename AugGraph::NodeMap<int> free;
+//typename AugGraph::NodeMap<Number> free;
 public:
 MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
 G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,
 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
 { }
-bool augment() {
+bool augmentOnShortestPath() {
 AugGraph res_graph(G, flow, capacity);
 bool _augment=false;
 typedef typename AugGraph::NodeMap<bool> ReachedMap;
 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
 //filled up with invalid iterators
 //pred.set(s, AugEdgeIt());
-typename AugGraph::NodeMap<int> free(res_graph);
+typename AugGraph::NodeMap<Number> free(res_graph);
 //searching for augmenting path
 while ( !res_bfs.finished() ) {
 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {
 	}
 }
 return _augment;
 }
-bool augmentWithBlockingFlow() {
+template<typename MutableGraph> bool augmentOnBlockingFlow() {
-BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
+bool _augment=false;
+AugGraph res_graph(G, flow, capacity);
+typedef typename AugGraph::NodeMap<bool> ReachedMap;
+BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
 bfs.pushAndSetReached(s);
-typename Graph::NodeMap<int> dist(G); //filled up with 0's
+typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
 while ( !bfs.finished() ) {
-	OutEdgeIt e=OutEdgeIt(bfs);
+	AugOutEdgeIt e=AugOutEdgeIt(bfs);
 	if (e.valid() && bfs.isBNodeNewlyReached()) {
-	  dist.set(G.head(e), dist.get(G.tail(e))+1);
+	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-	  //NodeIt v=res_graph.tail(e);
-	  //NodeIt w=res_graph.head(e);
-	  //pred.set(w, e);
-	  //if (pred.get(v).valid()) {
-	  //  free.set(w, std::min(free.get(v), e.free()));
-	  //} else {
-	  //  free.set(w, e.free());
-	  //}
-	  //if (res_graph.head(e)==t) { _augment=true; break; }
 	}
 	++bfs;
-} //end of searching augmenting path
+} //computing distances from s in the residual graph
-double pre_time_copy=currTime();
-typedef Graph MutableGraph;
 MutableGraph F;
-typename Graph::NodeMap<NodeIt> G_to_F(G);
+typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
-for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
+for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
-	G_to_F.set(n, F.addNode());
+	res_graph_to_F.set(n, F.addNode());
 }
-for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
-	if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
+typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
-	  F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
+typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
-	}
-}
+typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
-double post_time_copy=currTime();
+typename MutableGraph::EdgeMap<Number> free_on_edge(F);
-std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
+//Making F to the graph containing the edges of the residual graph
-return 0;
+//which are in some shortest paths
+for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
+	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
+	  typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+	  original_edge.update();
+	  original_edge.set(f, e);
+	  free_on_edge.update();
+	  free_on_edge.set(f, e.free());
+	}
+}
+bool __augment=true;
+while (__augment) {
+	__augment=false;
+	//computing blocking flow with dfs
+	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
+	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
+	typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
+	typename MutableGraph::NodeMap<Number> free(F);
+	dfs.pushAndSetReached(sF);
+	while (!dfs.finished()) {
+	  ++dfs;
+	  if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
+	    //std::cout << "OutEdgeIt: " << dfs;
+	    //std::cout << " aNode: " << F.aNode(dfs);
+	    //std::cout << " bNode: " << F.bNode(dfs) << " ";
+	    typename MutableGraph::NodeIt v=F.aNode(dfs);
+	    typename MutableGraph::NodeIt w=F.bNode(dfs);
+	    pred.set(w, dfs);
+	    if (pred.get(v).valid()) {
+	      free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
+	    } else {
+	      free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
+	    }
+	    if (w==tF) {
+	      //std::cout << "AUGMENTATION"<<std::endl;
+	      __augment=true;
+	      _augment=true;
+	      break;
+	    }
+	  } else {
+	    //std::cout << "OutEdgeIt: " << "invalid";
+	    //std::cout << " aNode: " << dfs.aNode();
+	    //std::cout << " bNode: " << "invalid" << " ";
+	  }
+	  if (dfs.isBNodeNewlyReached()) {
+	    //std::cout << "bNodeIsNewlyReached ";
+	  } else {
+	    //std::cout << "bNodeIsNotNewlyReached ";
+	    if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
+	      //std::cout << "DELETE ";
+	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
+	    }
+	  }
+	  //if (dfs.isANodeExamined()) {
+	    //std::cout << "aNodeIsExamined ";
+	    //} else {
+	    //std::cout << "aNodeIsNotExamined ";
+	    //}
+	  //std::cout<<std::endl;
+	}
+	if (__augment) {
+	  typename MutableGraph::NodeIt n=tF;
+	  Number augment_value=free.get(tF);
+	  while (pred.get(n).valid()) {
+	    typename MutableGraph::EdgeIt e=pred.get(n);
+	    original_edge.get(e).augment(augment_value);
+	    n=F.tail(e);
+	    F.erase(e);
+	  }
+	}
+}
+return _augment;
 }
 void run() {
 //int num_of_augmentations=0;
-while (augment()) {
+while (augmentOnShortestPath()) {
+	//while (augmentOnBlockingFlow<MutableGraph>()) {
+	//std::cout << ++num_of_augmentations << " ";
+	//std::cout<<std::endl;
+}
+}
+template<typename MutableGraph> void run() {
+//int num_of_augmentations=0;
+//while (augmentOnShortestPath()) {
+	while (augmentOnBlockingFlow<MutableGraph>()) {
 	//std::cout << ++num_of_augmentations << " ";
 	//std::cout<<std::endl;
 }
 }
 Number flowValue() {
 //res_bfs.pushAndSetReached(s);
 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
 //filled up with invalid iterators
-typename AugGraph::NodeMap<int> free(res_graph);
+typename AugGraph::NodeMap<Number> free(res_graph);
 //searching for augmenting path
 while ( !res_bfs.finished() ) {
 	AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
 	if (e.valid() && res_bfs.isBNodeNewlyReached()) {

changeset 133	0631992fe7a1
parent 127	dcace15b1874
child 135	1e5060d1fa1d