# HG changeset patch
# User marci
# Date 1083234591 0
# Node ID 8cab0547eeaeddb6ec273af7965826f8feae6652
# Parent  cd40ecf4d2a9ae6f864661bc8eb61e70303a85b7
preflow maxflow ...

diff -r cd40ecf4d2a9 -r 8cab0547eeae src/work/marci/edmonds_karp.h
--- a/src/work/marci/edmonds_karp.h	Thu Apr 29 10:16:46 2004 +0000
+++ b/src/work/marci/edmonds_karp.h	Thu Apr 29 10:29:51 2004 +0000
@@ -14,8 +14,8 @@
 
 namespace hugo {
 
-  template <typename Graph, typename Number, 
-	    typename CapacityMap, typename FlowMap>
+  template <typename Graph, typename Num, 
+	    typename CapMap, typename FlowMap>
   class MaxFlow {
   protected:
     typedef typename Graph::Node Node;
@@ -26,9 +26,9 @@
     const Graph* g;
     Node s;
     Node t;
-    const CapacityMap* capacity;
+    const CapMap* capacity;
     FlowMap* flow;
-    typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
+    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     typedef typename ResGW::Edge ResGWEdge;
     //typedef typename ResGW::template NodeMap<bool> ReachedMap;
@@ -37,7 +37,7 @@
     //reached is called level because of compatibility with preflow
   public:
 
-    MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity, 
+    MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity, 
 	    FlowMap& _flow) : 
       g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
 
@@ -53,7 +53,7 @@
       typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 
       pred.set(s, INVALID);
       
-      typename ResGW::template NodeMap<Number> free(res_graph);
+      typename ResGW::template NodeMap<Num> free(res_graph);
 	
       //searching for augmenting path
       while ( !bfs.finished() ) { 
@@ -75,7 +75,7 @@
 
       if (_augment) {
 	Node n=t;
-	Number augment_value=free[t];
+	Num augment_value=free[t];
 	while (res_graph.valid(pred[n])) { 
 	  ResGWEdge e=pred[n];
 	  res_graph.augment(e, augment_value); 
@@ -145,7 +145,7 @@
       typename MG::Node sF=res_graph_to_F[s];
       typename MG::Node tF=res_graph_to_F[t];
       typename MG::template EdgeMap<ResGWEdge> original_edge(F);
-      typename MG::template EdgeMap<Number> residual_capacity(F);
+      typename MG::template EdgeMap<Num> residual_capacity(F);
 
       //Making F to the graph containing the edges of the residual graph 
       //which are in some shortest paths
@@ -173,7 +173,7 @@
 	pred.set(sF, INVALID);
 	//invalid iterators for sources
 
-	typename MG::template NodeMap<Number> free(F);
+	typename MG::template NodeMap<Num> free(F);
 
 	dfs.pushAndSetReached(sF);      
 	while (!dfs.finished()) {
@@ -202,7 +202,7 @@
 
 	if (__augment) {
 	  typename MG::Node n=tF;
-	  Number augment_value=free[tF];
+	  Num augment_value=free[tF];
 	  while (F.valid(pred[n])) { 
 	    typename MG::Edge e=pred[n];
 	    res_graph.augment(original_edge[e], augment_value); 
@@ -248,7 +248,7 @@
       typename MG::Node sF=res_graph_to_F[s];
       typename MG::Node tF=res_graph_to_F[t];
       typename MG::template EdgeMap<ResGWEdge> original_edge(F);
-      typename MG::template EdgeMap<Number> residual_capacity(F);
+      typename MG::template EdgeMap<Num> residual_capacity(F);
 
       while ( !bfs.finished() ) { 
 	ResGWOutEdgeIt e=bfs;
@@ -283,7 +283,7 @@
 	pred.set(sF, INVALID);
 	//invalid iterators for sources
 
-	typename MG::template NodeMap<Number> free(F);
+	typename MG::template NodeMap<Num> free(F);
 
 	dfs.pushAndSetReached(sF);      
 	while (!dfs.finished()) {
@@ -312,7 +312,7 @@
 
 	if (__augment) {
 	  typename MG::Node n=tF;
-	  Number augment_value=free[tF];
+	  Num augment_value=free[tF];
 	  while (F.valid(pred[n])) { 
 	    typename MG::Edge e=pred[n];
 	    res_graph.augment(original_edge[e], augment_value); 
@@ -385,7 +385,7 @@
  	pred.set(s, INVALID);
   	//invalid iterators for sources
 
-  	typename ErasingResGW::template NodeMap<Number> 
+  	typename ErasingResGW::template NodeMap<Num> 
 	  free1(erasing_res_graph);
 
  	dfs.pushAndSetReached(
@@ -427,16 +427,16 @@
 
   	if (__augment) {
    	  typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
-// 	  typename ResGW::NodeMap<Number> a(res_graph);
+// 	  typename ResGW::NodeMap<Num> a(res_graph);
 // 	  typename ResGW::Node b;
-// 	  Number j=a[b];
-// 	  typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
+// 	  Num j=a[b];
+// 	  typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
 // 	  typename FilterResGW::Node b1;
-// 	  Number j1=a1[b1];
-// 	  typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
+// 	  Num j1=a1[b1];
+// 	  typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
 // 	  typename ErasingResGW::Node b2;
-// 	  Number j2=a2[b2];
- 	  Number augment_value=free1[n];
+// 	  Num j2=a2[b2];
+ 	  Num augment_value=free1[n];
  	  while (erasing_res_graph.valid(pred[n])) { 
  	    typename ErasingResGW::OutEdgeIt e=pred[n];
  	    res_graph.augment(e, augment_value);
@@ -469,8 +469,8 @@
       } 
     }
 
-    Number flowValue() { 
-      Number a=0;
+    Num flowValue() { 
+      Num a=0;
       OutEdgeIt e;
       for(g->first(e, s); g->valid(e); g->next(e)) {
 	a+=(*flow)[e];
@@ -481,7 +481,7 @@
   };
 
 
-//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+//   template <typename Graph, typename Num, typename FlowMap, typename CapMap>
 //   class MaxMatching {
 //   public:
 //     typedef typename Graph::Node Node;
@@ -500,14 +500,14 @@
 //     //Node s;
 //     //Node t;
 //     FlowMap* flow;
-//     const CapacityMap* capacity;
-//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
+//     const CapMap* capacity;
+//     typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
 //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
 //     typedef typename AugGraph::Edge AugEdge;
 //     typename Graph::NodeMap<int> used; //0
 
 //   public:
-//     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 
+//     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapMap& _capacity) : 
 //       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
 //     bool augmentOnShortestPath() {
 //       AugGraph res_graph(*G, *flow, *capacity);
@@ -518,7 +518,7 @@
 //       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
 // 	if ((S->get(s)) && (used.get(s)<1) ) {
-// 	  //Number u=0;
+// 	  //Num u=0;
 // 	  //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
 // 	  //u+=flow->get(e);
 // 	  //if (u<1) {
@@ -528,7 +528,7 @@
 // 	}
 //       }
       
-//       typename AugGraph::NodeMap<Number> free(res_graph);
+//       typename AugGraph::NodeMap<Num> free(res_graph);
 	
 //       Node n;
 //       //searching for augmenting path
@@ -545,7 +545,7 @@
 // 	  }
 // 	  n=res_graph.head(e);
 // 	  if (T->get(n) && (used.get(n)<1) ) { 
-// 	    //Number u=0;
+// 	    //Num u=0;
 // 	    //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
 // 	    //u+=flow->get(f);
 // 	    //if (u<1) {
@@ -561,7 +561,7 @@
 //       if (_augment) {
 // 	//Node n=t;
 // 	used.set(n, 1); //mind2 vegen jav
-// 	Number augment_value=free.get(n);
+// 	Num augment_value=free.get(n);
 // 	while (res_graph.valid(pred.get(n))) { 
 // 	  AugEdge e=pred.get(n);
 // 	  res_graph.augment(e, augment_value); 
@@ -588,7 +588,7 @@
 // //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
 // //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
 // // 	if (S->get(s)) {
-// // 	  Number u=0;
+// // 	  Num u=0;
 // // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
 // // 	    u+=flow->get(e);
 // // 	  if (u<1) {
@@ -623,7 +623,7 @@
 // //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
 
 // //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
-// //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
+// //       typename MutableGraph::EdgeMap<Num> residual_capacity(F);
 
 // //       //Making F to the graph containing the edges of the residual graph 
 // //       //which are in some shortest paths
@@ -648,7 +648,7 @@
 // // 	pred.set(sF, typename MutableGraph::Edge(INVALID));
 // // 	//invalid iterators for sources
 
-// // 	typename MutableGraph::NodeMap<Number> free(F);
+// // 	typename MutableGraph::NodeMap<Num> free(F);
 
 // // 	dfs.pushAndSetReached(sF);      
 // // 	while (!dfs.finished()) {
@@ -677,7 +677,7 @@
 
 // // 	if (__augment) {
 // // 	  typename MutableGraph::Node n=tF;
-// // 	  Number augment_value=free.get(tF);
+// // 	  Num augment_value=free.get(tF);
 // // 	  while (F.valid(pred.get(n))) { 
 // // 	    typename MutableGraph::Edge e=pred.get(n);
 // // 	    res_graph.augment(original_edge.get(e), augment_value); 
@@ -696,8 +696,8 @@
 //     bool augmentOnBlockingFlow2() {
 //       bool _augment=false;
 
-//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
-//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
+//       //typedef ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> EAugGraph;
+//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> > EAugGraph;
 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
 //       typedef typename EAugGraph::Edge EAugEdge;
 
@@ -705,15 +705,15 @@
 
 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
 //       BfsIterator< 
-// 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
-// 	/*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/ 
-// 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
+// 	ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>, 
+// 	/*typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt,*/ 
+// 	ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::NodeMap<bool> > bfs(res_graph);
 
 
 //       //typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
 // 	if (S->get(s)) {
-// 	  Number u=0;
+// 	  Num u=0;
 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
 // 	    u+=flow->get(e);
 // 	  if (u<1) {
@@ -726,11 +726,11 @@
       
 //       //bfs.pushAndSetReached(s);
 
-//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
+//       typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::
 // 	NodeMap<int>& dist=res_graph.dist;
 
 //       while ( !bfs.finished() ) {
-// 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
+// 	typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
 // 	}
@@ -750,13 +750,13 @@
 // 	//pred.set(s, EAugEdge(INVALID));
 // 	//invalid iterators for sources
 
-// 	typename EAugGraph::NodeMap<Number> free(res_graph);
+// 	typename EAugGraph::NodeMap<Num> free(res_graph);
 
 
 // 	//typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
 //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
 // 	if (S->get(s)) {
-// 	  Number u=0;
+// 	  Num u=0;
 // 	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
 // 	    u+=flow->get(e);
 // 	  if (u<1) {
@@ -787,7 +787,7 @@
 	     
 // 	      n=w;
 // 	      if (T->get(w)) {
-// 		Number u=0;
+// 		Num u=0;
 // 		for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
 // 		  u+=flow->get(f);
 // 		if (u<1) {
@@ -805,7 +805,7 @@
 
 // 	if (__augment) {
 // 	  // typename EAugGraph::Node n=t;
-// 	  Number augment_value=free.get(n);
+// 	  Num augment_value=free.get(n);
 // 	  while (res_graph.valid(pred.get(n))) { 
 // 	    EAugEdge e=pred.get(n);
 // 	    res_graph.augment(e, augment_value);
@@ -835,8 +835,8 @@
 // // 	//std::cout<<std::endl;
 // //       } 
 // //     } 
-//     Number flowValue() { 
-//       Number a=0;
+//     Num flowValue() { 
+//       Num a=0;
 //       EdgeIt e;
 //       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
 // 	a+=flow->get(e);
@@ -850,7 +850,7 @@
 
 
   
-// //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
+// //   template <typename Graph, typename Num, typename FlowMap, typename CapMap>
 // //   class MaxFlow2 {
 // //   public:
 // //     typedef typename Graph::Node Node;
@@ -863,14 +863,14 @@
 // //     std::list<Node>& S;
 // //     std::list<Node>& T;
 // //     FlowMap& flow;
-// //     const CapacityMap& capacity;
-// //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
+// //     const CapMap& capacity;
+// //     typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
 // //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
 // //     typedef typename AugGraph::Edge AugEdge;
 // //     typename Graph::NodeMap<bool> SMap;
 // //     typename Graph::NodeMap<bool> TMap;
 // //   public:
-// //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 
+// //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) { 
 // //       for(typename std::list<Node>::const_iterator i=S.begin(); 
 // // 	  i!=S.end(); ++i) { 
 // // 	SMap.set(*i, true); 
@@ -896,7 +896,7 @@
 // //       typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
 // //       //filled up with invalid iterators
       
-// //       typename AugGraph::NodeMap<Number> free(res_graph);
+// //       typename AugGraph::NodeMap<Num> free(res_graph);
 	
 // //       //searching for augmenting path
 // //       while ( !bfs.finished() ) { 
@@ -922,7 +922,7 @@
 
 // //       if (_augment) {
 // // 	Node n=reached_t_node;
-// // 	Number augment_value=free.get(reached_t_node);
+// // 	Num augment_value=free.get(reached_t_node);
 // // 	while (pred.get(n).valid()) { 
 // // 	  AugEdge e=pred.get(n);
 // // 	  e.augment(augment_value); 
@@ -935,8 +935,8 @@
 // //     void run() {
 // //       while (augment()) { } 
 // //     }
-// //     Number flowValue() { 
-// //       Number a=0;
+// //     Num flowValue() { 
+// //       Num a=0;
 // //       for(typename std::list<Node>::const_iterator i=S.begin(); 
 // // 	  i!=S.end(); ++i) { 
 // // 	for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {