1.1 --- a/src/work/edmonds_karp.h	Fri Mar 19 07:59:52 2004 +0000
     1.2 +++ b/src/work/edmonds_karp.h	Fri Mar 19 09:09:20 2004 +0000
     1.3 @@ -413,6 +413,109 @@
     1.4              
     1.5        return _augment;
     1.6      }
     1.7 +    template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
     1.8 +      bool _augment=false;
     1.9 +
    1.10 +      AugGraph res_graph(*G, *flow, *capacity);
    1.11 +
    1.12 +      //bfs for distances on the residual graph
    1.13 +      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1.14 +      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
    1.15 +      bfs.pushAndSetReached(s);
    1.16 +      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    1.17 +
    1.18 +      //F will contain the physical copy of the residual graph
    1.19 +      //with the set of edges which areon shortest paths
    1.20 +      MutableGraph F;
    1.21 +      typename AugGraph::NodeMap<typename MutableGraph::Node> 
    1.22 +	res_graph_to_F(res_graph);
    1.23 +      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    1.24 +	res_graph_to_F.set(n, F.addNode());
    1.25 +      }
    1.26 +      typename MutableGraph::Node sF=res_graph_to_F.get(s);
    1.27 +      typename MutableGraph::Node tF=res_graph_to_F.get(t);
    1.28 +      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    1.29 +      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    1.30 +
    1.31 +      while ( !bfs.finished() ) { 
    1.32 +	AugOutEdgeIt e=bfs;
    1.33 +	if (res_graph.valid(e)) {
    1.34 +	  if (bfs.isBNodeNewlyReached()) {
    1.35 +	    dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    1.36 +	    typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    1.37 +	    original_edge.update();
    1.38 +	    original_edge.set(f, e);
    1.39 +	    residual_capacity.update();
    1.40 +	    residual_capacity.set(f, res_graph.free(e));
    1.41 +	  } else {
    1.42 +	    if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
    1.43 +	      typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    1.44 +	      original_edge.update();
    1.45 +	      original_edge.set(f, e);
    1.46 +	      residual_capacity.update();
    1.47 +	      residual_capacity.set(f, res_graph.free(e));
    1.48 +	    }
    1.49 +	  }
    1.50 +	}
    1.51 +	++bfs;
    1.52 +      } //computing distances from s in the residual graph
    1.53 +
    1.54 +      bool __augment=true;
    1.55 +
    1.56 +      while (__augment) {
    1.57 +	__augment=false;
    1.58 +	//computing blocking flow with dfs
    1.59 +	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
    1.60 +	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
    1.61 +	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    1.62 +	pred.set(sF, typename MutableGraph::Edge(INVALID));
    1.63 +	//invalid iterators for sources
    1.64 +
    1.65 +	typename MutableGraph::NodeMap<Number> free(F);
    1.66 +
    1.67 +	dfs.pushAndSetReached(sF);      
    1.68 +	while (!dfs.finished()) {
    1.69 +	  ++dfs;
    1.70 +	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    1.71 +	    if (dfs.isBNodeNewlyReached()) {
    1.72 +	      typename MutableGraph::Node v=F.aNode(dfs);
    1.73 +	      typename MutableGraph::Node w=F.bNode(dfs);
    1.74 +	      pred.set(w, dfs);
    1.75 +	      if (F.valid(pred.get(v))) {
    1.76 +		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
    1.77 +	      } else {
    1.78 +		free.set(w, residual_capacity.get(dfs)); 
    1.79 +	      }
    1.80 +	      if (w==tF) { 
    1.81 +		__augment=true; 
    1.82 +		_augment=true;
    1.83 +		break; 
    1.84 +	      }
    1.85 +	      
    1.86 +	    } else {
    1.87 +	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
    1.88 +	    }
    1.89 +	  } 
    1.90 +	}
    1.91 +
    1.92 +	if (__augment) {
    1.93 +	  typename MutableGraph::Node n=tF;
    1.94 +	  Number augment_value=free.get(tF);
    1.95 +	  while (F.valid(pred.get(n))) { 
    1.96 +	    typename MutableGraph::Edge e=pred.get(n);
    1.97 +	    res_graph.augment(original_edge.get(e), augment_value); 
    1.98 +	    n=F.tail(e);
    1.99 +	    if (residual_capacity.get(e)==augment_value) 
   1.100 +	      F.erase(e); 
   1.101 +	    else 
   1.102 +	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
   1.103 +	  }
   1.104 +	}
   1.105 +	
   1.106 +      }
   1.107 +            
   1.108 +      return _augment;
   1.109 +    }
   1.110      bool augmentOnBlockingFlow2() {
   1.111        bool _augment=false;
   1.112  

     2.1 --- a/src/work/marci/dimacs.h	Fri Mar 19 07:59:52 2004 +0000
     2.2 +++ b/src/work/marci/dimacs.h	Fri Mar 19 09:09:20 2004 +0000
     2.3 @@ -25,9 +25,6 @@
     2.4        case 'c': //comment
     2.5  	getline(is, str);
     2.6  	break;
     2.7 -//       case 't': //type
     2.8 -// 	getline(is, str);
     2.9 -// 	break;
    2.10        case 'p': //problem definition
    2.11  	is >> problem >> n >> m;
    2.12  	getline(is, str);

     3.1 --- a/src/work/marci/edmonds_karp_demo.cc	Fri Mar 19 07:59:52 2004 +0000
     3.2 +++ b/src/work/marci/edmonds_karp_demo.cc	Fri Mar 19 09:09:20 2004 +0000
     3.3 @@ -34,8 +34,8 @@
     3.4  
     3.5    typedef ListGraph MutableGraph;
     3.6  
     3.7 -//  typedef SmartGraph Graph;
     3.8 -  typedef ListGraph Graph;
     3.9 +  typedef SmartGraph Graph;
    3.10 +  //typedef ListGraph Graph;
    3.11    typedef Graph::Node Node;
    3.12    typedef Graph::EdgeIt EdgeIt;
    3.13  
    3.14 @@ -114,6 +114,35 @@
    3.15    }
    3.16  
    3.17    {
    3.18 +    std::cout << "SmartGraph..." << std::endl;
    3.19 +    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
    3.20 +    Graph::EdgeMap<int> flow(G); //0 flow
    3.21 +
    3.22 +    Timer ts;
    3.23 +    ts.reset();
    3.24 +
    3.25 +    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    3.26 +    //max_flow_test.augmentWithBlockingFlow<Graph>();
    3.27 +    int i=0;
    3.28 +    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
    3.29 +//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
    3.30 +//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    3.31 +//     }
    3.32 +//     std::cout<<std::endl;
    3.33 +      ++i; 
    3.34 +    }
    3.35 +
    3.36 +//   std::cout << "maximum flow: "<< std::endl;
    3.37 +//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
    3.38 +//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    3.39 +//   }
    3.40 +//   std::cout<<std::endl;
    3.41 +    std::cout << "elapsed time: " << ts << std::endl;
    3.42 +    std::cout << "number of augmentation phases: " << i << std::endl; 
    3.43 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    3.44 +  }
    3.45 +
    3.46 +  {
    3.47      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    3.48      Graph::EdgeMap<int> flow(G); //0 flow
    3.49