1.1 --- a/src/work/edmonds_karp.hh	Wed Feb 18 15:58:28 2004 +0000
     1.2 +++ b/src/work/edmonds_karp.hh	Wed Feb 18 17:27:13 2004 +0000
     1.3 @@ -6,6 +6,7 @@
     1.4  #include <iterator>
     1.5  
     1.6  #include <bfs_iterator.hh>
     1.7 +#include <time_measure.h>
     1.8  
     1.9  namespace marci {
    1.10  
    1.11 @@ -443,8 +444,51 @@
    1.12  
    1.13        return _augment;
    1.14      }
    1.15 +    bool augmentWithBlockingFlow() {
    1.16 +      BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G);
    1.17 +      bfs.pushAndSetReached(s);
    1.18 +      typename Graph::NodeMap<int> dist(G); //filled up with 0's
    1.19 +      while ( !bfs.finished() ) { 
    1.20 +	OutEdgeIt e=OutEdgeIt(bfs);
    1.21 +	if (e.valid() && bfs.isBNodeNewlyReached()) {
    1.22 +	  dist.set(G.head(e), dist.get(G.tail(e))+1);
    1.23 +	  //NodeIt v=res_graph.tail(e);
    1.24 +	  //NodeIt w=res_graph.head(e);
    1.25 +	  //pred.set(w, e);
    1.26 +	  //if (pred.get(v).valid()) {
    1.27 +	  //  free.set(w, std::min(free.get(v), e.free()));
    1.28 +	  //} else {
    1.29 +	  //  free.set(w, e.free()); 
    1.30 +	  //}
    1.31 +	  //if (res_graph.head(e)==t) { _augment=true; break; }
    1.32 +	}
    1.33 +	
    1.34 +	++bfs;
    1.35 +      } //end of searching augmenting path
    1.36 +
    1.37 +      double pre_time_copy=currTime();
    1.38 +      typedef Graph MutableGraph;
    1.39 +      MutableGraph F;
    1.40 +      typename Graph::NodeMap<NodeIt> G_to_F(G);
    1.41 +      for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) {
    1.42 +	G_to_F.set(n, F.addNode());
    1.43 +      }
    1.44 +      for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) {
    1.45 +	if (dist.get(G.head(e))==dist.get(G.tail(e))+1) {
    1.46 +	  F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
    1.47 +	}
    1.48 +      }
    1.49 +      double post_time_copy=currTime();
    1.50 +      std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl; 
    1.51 +
    1.52 +      return 0;
    1.53 +    }
    1.54      void run() {
    1.55 -      while (augment()) { } 
    1.56 +      //int num_of_augmentations=0;
    1.57 +      while (augment()) { 
    1.58 +	//std::cout << ++num_of_augmentations << " ";
    1.59 +	//std::cout<<std::endl;
    1.60 +      } 
    1.61      }
    1.62      Number flowValue() { 
    1.63        Number a=0;

     2.1 --- a/src/work/marci/edmonds_karp_demo.cc	Wed Feb 18 15:58:28 2004 +0000
     2.2 +++ b/src/work/marci/edmonds_karp_demo.cc	Wed Feb 18 17:27:13 2004 +0000
     2.3 @@ -19,11 +19,27 @@
     2.4    ListGraph::EdgeMap<int> cap(G);
     2.5    readDimacsMaxFlow(std::cin, G, s, t, cap);
     2.6  
     2.7 +/*
     2.8 +  double pre_time_copy=currTime();
     2.9 +  ListGraph F;
    2.10 +  ListGraph::NodeMap<NodeIt> G_to_F(G);
    2.11 +  typedef ListGraph::EachNodeIt EachNodeIt;
    2.12 +  for(EachNodeIt n=G.first<EachNodeIt>(); n.valid(); ++n) {
    2.13 +    G_to_F.set(n, F.addNode());
    2.14 +  }
    2.15 +  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    2.16 +    F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
    2.17 +  }
    2.18 +  double post_time_copy=currTime();
    2.19 +  std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl; 
    2.20 +*/
    2.21 +
    2.22    std::cout << "edmonds karp demo..." << std::endl;
    2.23    ListGraph::EdgeMap<int> flow(G); //0 flow
    2.24  
    2.25    double pre_time=currTime();
    2.26    MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    2.27 +  max_flow_test.augmentWithBlockingFlow();
    2.28    max_flow_test.run();
    2.29    double post_time=currTime();
    2.30    //std::cout << "maximum flow: "<< std::endl;

     3.1 --- a/src/work/marci/preflow_demo_jacint.cc	Wed Feb 18 15:58:28 2004 +0000
     3.2 +++ b/src/work/marci/preflow_demo_jacint.cc	Wed Feb 18 17:27:13 2004 +0000
     3.3 @@ -27,7 +27,8 @@
     3.4    double pre_time=currTime();
     3.5    preflow_push_max_flow<ListGraph, int> max_flow_test(G, s, t, cap);
     3.6    max_flow_test.run();
     3.7 -  ListGraph::NodeMap<bool> cut=max_flow_test.mincut();
     3.8 +  ListGraph::NodeMap<bool> cut(G); 
     3.9 +  max_flow_test.mincut(cut);
    3.10    int cut_value=0;
    3.11    for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    3.12      if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
    3.13 @@ -50,7 +51,8 @@
    3.14    double pre_time=currTime();
    3.15    preflow_push_hl<ListGraph, int> max_flow_test(G, s, t, cap);
    3.16    max_flow_test.run();
    3.17 -  ListGraph::NodeMap<bool> cut=max_flow_test.mincut();
    3.18 +  ListGraph::NodeMap<bool> cut(G);
    3.19 +  max_flow_test.mincut(cut);
    3.20    int cut_value=0;
    3.21    for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    3.22      if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);