Changeset 986:e997802b855c in lemon-0.x for src/work/marci/experiment/edmonds_karp.h

Timestamp:

11/13/04 13:53:28 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376

Message:

Naming changes:

• head -> target
• tail -> source

File:

• src/work/marci/experiment/edmonds_karp.h (modified) (29 diffs)

src/work/marci/experiment/edmonds_karp.h

@@ -41 +41 @@
       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
       Number free() const { 
-        if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
+        if (resG->G.aNode(sym)==resG->G.source(sym)) { 
           return (resG->capacity.get(sym)-resG->flow.get(sym)); 
         } else { 
@@ -49 +49 @@
       bool valid() const { return sym.valid(); }
       void augment(Number a) const {
-        if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
+        if (resG->G.aNode(sym)==resG->G.source(sym)) { 
           resG->flow.set(sym, resG->flow.get(sym)+a);
           //resG->flow[sym]+=a;
@@ -97 +97 @@
     }
 
-    Node tail(Edge e) const { return G.aNode(e.sym); }
-    Node head(Edge e) const { return G.bNode(e.sym); }
+    Node source(Edge e) const { return G.aNode(e.sym); }
+    Node target(Edge e) const { return G.bNode(e.sym); }
 
     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
@@ -224 +224 @@
     }
 
-    Node tail(Edge e) const { 
+    Node source(Edge e) const { 
       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
-    Node head(Edge e) const { 
+    Node target(Edge e) const { 
       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
 
@@ -288 +288 @@
         ResGWOutEdgeIt e=bfs;
         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-          Node v=res_graph.tail(e);
-          Node w=res_graph.head(e);
+          Node v=res_graph.source(e);
+          Node w=res_graph.target(e);
           pred.set(w, e);
           if (res_graph.valid(pred.get(v))) {
@@ -296 +296 @@
             free.set(w, res_graph.resCap(e)); 
           }
-          if (res_graph.head(e)==t) { _augment=true; break; }
+          if (res_graph.target(e)==t) { _augment=true; break; }
         }
         
@@ -308 +308 @@
           ResGWEdge e=pred.get(n);
           res_graph.augment(e, augment_value); 
-          n=res_graph.tail(e);
+          n=res_graph.source(e);
         }
       }
@@ -325 +325 @@
       int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
       bool get(const typename MapGraphWrapper::Edge& e) const { 
-        return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 
+        return (dist.get(gw.source(e))<dist.get(gw.target(e))); 
       }
     };
@@ -344 +344 @@
         ResGWOutEdgeIt e=bfs;
         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+          dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
         }
         ++bfs;
@@ -370 +370 @@
         typename FilterResGW::EdgeIt e;
         for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
-          //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
-          typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+          //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
+          typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
           original_edge.update();
           original_edge.set(f, e);
@@ -424 +424 @@
             typename MG::Edge e=pred.get(n);
             res_graph.augment(original_edge.get(e), augment_value); 
-            n=F.tail(e);
+            n=F.source(e);
             if (residual_capacity.get(e)==augment_value) 
               F.erase(e); 
@@ -469 +469 @@
         if (res_graph.valid(e)) {
           if (bfs.isBNodeNewlyReached()) {
-            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-            typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+            dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
+            typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
             original_edge.update();
             original_edge.set(f, e);
@@ -476 +476 @@
             residual_capacity.set(f, res_graph.resCap(e));
           } else {
-            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
-              typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+            if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) {
+              typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
               original_edge.update();
               original_edge.set(f, e);
@@ -532 +532 @@
             typename MG::Edge e=pred.get(n);
             res_graph.augment(original_edge.get(e), augment_value); 
-            n=F.tail(e);
+            n=F.source(e);
             if (residual_capacity.get(e)==augment_value) 
               F.erase(e); 
@@ -558 +558 @@
         ResGWOutEdgeIt e=bfs;
         if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+          dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
         }
         ++bfs;
@@ -634 +634 @@
             typename ErasingResGW::OutEdgeIt e=pred.get(n);
             res_graph.augment(e, augment_value);
-            n=erasing_res_graph.tail(e);
+            n=erasing_res_graph.source(e);
             if (res_graph.resCap(e)==0)
               erasing_res_graph.erase(e);
@@ -669 +669 @@
 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+//        dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
 //      }
 //      ++bfs;  
@@ -723 +723 @@
 //          EAugEdge e=pred.get(n);
 //          res_graph.augment(e, augment_value);
-//          n=res_graph.tail(e);
+//          n=res_graph.source(e);
 //          if (res_graph.free(e)==0)
 //            res_graph.erase(e);
@@ -818 +818 @@
 //      AugOutEdgeIt e=bfs;
 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-//        Node v=res_graph.tail(e);
-//        Node w=res_graph.head(e);
+//        Node v=res_graph.source(e);
+//        Node w=res_graph.target(e);
 //        pred.set(w, e);
 //        if (res_graph.valid(pred.get(v))) {
@@ -826 +826 @@
 //          free.set(w, res_graph.free(e)); 
 //        }
-//        n=res_graph.head(e);
+//        n=res_graph.target(e);
 //        if (T->get(n) && (used.get(n)<1) ) { 
 //          //Number u=0;
@@ -848 +848 @@
 //        AugEdge e=pred.get(n);
 //        res_graph.augment(e, augment_value); 
-//        n=res_graph.tail(e);
+//        n=res_graph.source(e);
 //      }
 //      used.set(n, 1); //mind2 vegen jav
@@ -889 +889 @@
 // //   AugOutEdgeIt e=bfs;
 // //   if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-// //     dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+// //     dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
 // //   }
         
@@ -911 +911 @@
 // //       //which are in some shortest paths
 // //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
-// //   if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
-// //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+// //   if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
+// //     typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
 // //     original_edge.update();
 // //     original_edge.set(f, e);
@@ -964 +964 @@
 // //       typename MutableGraph::Edge e=pred.get(n);
 // //       res_graph.augment(original_edge.get(e), augment_value); 
-// //       n=F.tail(e);
+// //       n=F.source(e);
 // //       if (residual_capacity.get(e)==augment_value) 
 // //         F.erase(e); 
@@ -1015 +1015 @@
 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
-//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+//        dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
 //      }
 //      ++bfs;  
@@ -1092 +1092 @@
 //          EAugEdge e=pred.get(n);
 //          res_graph.augment(e, augment_value);
-//          n=res_graph.tail(e);
+//          n=res_graph.source(e);
 //          if (res_graph.free(e)==0)
 //            res_graph.erase(e);
@@ -1185 +1185 @@
 // //   AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
 // //   if (e.valid() && bfs.isBNodeNewlyReached()) {
-// //     Node v=res_graph.tail(e);
-// //     Node w=res_graph.head(e);
+// //     Node v=res_graph.source(e);
+// //     Node w=res_graph.target(e);
 // //     pred.set(w, e);
 // //     if (pred.get(v).valid()) {
@@ -1193 +1193 @@
 // //       free.set(w, e.free()); 
 // //     }
-// //     if (TMap.get(res_graph.head(e))) { 
+// //     if (TMap.get(res_graph.target(e))) { 
 // //       _augment=true; 
-// //       reached_t_node=res_graph.head(e);
+// //       reached_t_node=res_graph.target(e);
 // //       break; 
 // //     }
@@ -1209 +1209 @@
 // //     AugEdge e=pred.get(n);
 // //     e.augment(augment_value); 
-// //     n=res_graph.tail(e);
+// //     n=res_graph.source(e);
 // //   }
 // //       }