Changeset 14:99014d576aed in lemon-0.x

Timestamp:

01/12/04 12:50:52 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

reimplemented max_flow algorithm class with bfs_iterator1

File:

• src/work/marci_max_flow.hh (modified) (3 diffs)

src/work/marci_max_flow.hh

@@ -95 +95 @@
   };
 
-  template <typename graph_type, typename pred_type, typename free_type>
-  struct flow_visitor {
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-    graph_type& G;
-    pred_type& pred;
-    free_type& free;
-    flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
-    void at_previously_reached(out_edge_iterator& e) { 
-      //node_iterator v=G.tail(e);
-      //node_iterator w=G.head(e);
-      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
-      //std::cout<<std::endl;
-   }
-    void at_newly_reached(out_edge_iterator& e) { 
-      node_iterator v=G.tail(e);
-      node_iterator w=G.head(e);
-      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
-      pred.put(w, e);
-      if (pred.get(v).is_valid()) {
-        free.put(w, std::min(free.get(v), e.free()));
-        //std::cout <<" nem elso csucs: ";
-        //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-      } else {
-        free.put(w, e.free()); 
-        //std::cout <<" elso csucs: ";
-        //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-      }
-      //std::cout<<std::endl;
-    }
-  };
-
   template <typename graph_type, typename T>
   struct max_flow_type {
@@ -153 +119 @@
       aug_graph_type res_graph(G, flow, capacity);
 
-      typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
-      bfs_queue_type bfs_queue;
-      //bfs_queue.push(res_graph.first_out_edge(s));
-
-      typedef node_property_vector<aug_graph_type, bool> reached_type;
-      //reached_type reached(res_graph, false);
-      reached_type reached(res_graph);
-      //reached.put(s, true);
-
-      typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
-      pred_type pred(res_graph);
-      pred.put(s, res_graph.invalid_edge());
-      
-      typedef node_property_vector<aug_graph_type, int> free_type;
-      free_type free(res_graph);
-
-      typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
-      visitor_type vis(res_graph, pred, free);
-      
-      bfs_iterator< aug_graph_type, reached_type, visitor_type > 
-        res_bfs(res_graph, bfs_queue, reached, vis);
-
-      //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { 
-      //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
-      //  std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
-      //}
-      //}
-      //std::cout<<std::endl;
-
-      //char c; 
       bool augment;
       do {
         augment=false;
-        
-        while (!bfs_queue.empty()) { bfs_queue.pop(); }
+
+        typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
+        bfs_queue_type bfs_queue;
         bfs_queue.push(res_graph.first_out_edge(s));
-        
-        for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
+
+        typedef node_property_vector<aug_graph_type, bool> reached_type;
+        //reached_type reached(res_graph);
+        //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
+        reached_type reached(res_graph, false);
         reached.put(s, true); 
         
+        bfs_iterator1< aug_graph_type, reached_type > 
+        res_bfs(res_graph, bfs_queue, reached);
+
+        typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
+        pred_type pred(res_graph);
+        pred.put(s, res_graph.invalid_edge());
+
+        typedef node_property_vector<aug_graph_type, int> free_type;
+        free_type free(res_graph);
+        
         //searching for augmenting path
-        while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { 
-          res_bfs.process(); 
-          //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
+        while ( res_bfs.is_valid() ) { 
+          //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
+          if (res_bfs.is_newly_reached()) {
+            graph_traits<aug_graph_type>::edge_iterator e;
+            e=res_bfs;
+            node_iterator v=res_graph.tail(e);
+            node_iterator w=res_graph.head(e);
+            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
+            pred.put(w, e);
+            if (pred.get(v).is_valid()) {
+              free.put(w, std::min(free.get(v), e.free()));
+              //std::cout <<" nem elso csucs: ";
+              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
+            } else {
+              free.put(w, e.free()); 
+              //std::cout <<" elso csucs: ";
+              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
+            }
+            //std::cout<<std::endl;
+          }
+        
           if (res_graph.head(res_bfs)==t) break;
-          //res_bfs.next();
           ++res_bfs;
         }
-        //for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); } 
         if (reached.get(t)) {
           augment=true;
@@ -216 +182 @@
         }
 
-        std::cout << "max flow:"<< std::endl;
+        std::cout << "actual flow: "<< std::endl;
         for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { 
           std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";