Changeset 59:41c7f9c09a12 in lemon-0.x

Timestamp:

02/04/04 13:46:33 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work

Files:

• edmonds_karp.hh (modified) (9 diffs)
• iterator_bfs_dfs_demo.cc (modified) (1 diff)
• list_graph.hh (modified) (14 diffs)

src/work/edmonds_karp.hh

@@ -1 @@
-#ifndef MARCI_MAX_FLOW_HH
-#define MARCI_MAX_FLOW_HH
+#ifndef EDMONDS_KARP_HH
+#define EDMONDS_KARP_HH
 
 #include <algorithm>
@@ -8 +8 @@
 namespace marci {
 
-  template<typename Graph, typename T>
+  template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
   class ResGraph {
     typedef typename Graph::NodeIt NodeIt;
@@ -14 +14 @@
     typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     const Graph& G;
-    typename Graph::EdgeMap<T>& flow;
-    const typename Graph::EdgeMap<T>& capacity;
+    FlowMap& flow;
+    const CapacityMap& capacity;
   public:
-    ResGraph(const Graph& _G, typename Graph::EdgeMap<T>& _flow, 
-             const typename Graph::EdgeMap<T>& _capacity) : 
+    ResGraph(const Graph& _G, FlowMap& _flow, 
+             const CapacityMap& _capacity) : 
       G(_G), flow(_flow), capacity(_capacity) { }
 
@@ -27 +27 @@
 
     class EdgeIt {
-      friend class ResGraph<Graph, T>;
+      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     protected:
-      const ResGraph<Graph, T>* resG;
+      const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
       OldSymEdgeIt sym;
     public:
@@ -52 +52 @@
 
     class OutEdgeIt : public EdgeIt {
-      friend class ResGraph<Graph, T>;
+      friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     public:
       OutEdgeIt() { }
       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
     private:
-      OutEdgeIt(const ResGraph<Graph, T>& _resG, const NodeIt v) { 
+      OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, const NodeIt v) { 
         resG=&_resG;
         sym=resG->G.template first<OldSymEdgeIt>(v);
@@ -99 +99 @@
     template <typename ValueType>
     class NodeMap {
-      //const ResGraph<Graph, T>& G; 
       typename Graph::NodeMap<ValueType> node_map; 
     public:
-      NodeMap(const ResGraph<Graph, T>& _G) : node_map(_G.G)/*: G(_G)*/ { }
-      NodeMap(const ResGraph<Graph, T>& _G, const ValueType a) : node_map(_G.G, a) /*: G(_G)*/ { }
+      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
+      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, const ValueType a) : node_map(_G.G, a) { }
       void set(const NodeIt nit, const ValueType a) { node_map.set(nit, a); }
       ValueType get(const NodeIt nit) const { return node_map.get(nit); }
@@ -110 +109 @@
   };
 
-  template <typename Graph, typename T>
-  struct max_flow_type {
+  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
+  class MaxFlow {
     typedef typename Graph::NodeIt NodeIt;
     typedef typename Graph::EdgeIt EdgeIt;
@@ -118 +117 @@
     typedef typename Graph::InEdgeIt InEdgeIt;
     const Graph& G;
-    NodeIt s;
-    NodeIt t;
-    typename Graph::EdgeMap<T> flow;
-    const typename Graph::EdgeMap<T>& capacity;
-
-    max_flow_type(const Graph& _G, NodeIt _s, NodeIt _t, const typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
+    const NodeIt s;
+    const NodeIt t;
+    FlowMap& flow;
+    const CapacityMap& capacity;
+    typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
+    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
+    typedef typename AugGraph::EdgeIt AugEdgeIt;
+  public:
+    MaxFlow(const Graph& _G, const NodeIt _s, const NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
+    bool augment() {
+      AugGraph res_graph(G, flow, capacity);
+      bool _augment=false;
+      
+      typedef typename AugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
+      res_bfs.pushAndSetReached(s);
+        
+      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
+      //filled with invalid iterators
+      
+      typename AugGraph::NodeMap<int> free(res_graph);
+        
+      //searching for augmenting path
+      while ( !res_bfs.finished() ) { 
+        //std::queue<AugOutEdgeIt> bfs_copy(res_bfs.getBfsQueue());
+        //while (!bfs_copy.empty()) {
+        //  AugOutEdgeIt e=bfs_copy.front();
+        //  bfs_copy.pop();
+        //  if (e.valid()) {
+        //    std::cout<<"queue:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<" ";
+        //  } else {
+        //    std::cout<<"queue:"<<res_graph.aNode(e)<<"->"<<" ";
+        //  }
+        //}
+        //std::cout<<std::endl;
+        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
+        //if (e.valid()) {
+        //  std::cout<<"actual:"<<res_graph.tail(e)<<"->"<<res_graph.head(e)<<std::endl;
+        //} else {
+        //  std::cout<<"actual:"<<res_graph.aNode(e)<<"->"<<std::endl;
+        //}
+        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
+          NodeIt v=res_graph.tail(e);
+          NodeIt w=res_graph.head(e);
+          //std::cout<<v<<"->"<<w<<std::endl;
+          pred.set(w, e);
+          if (pred.get(v).valid()) {
+            free.set(w, std::min(free.get(v), e.free()));
+          } else {
+            free.set(w, e.free()); 
+          }
+          if (res_graph.head(e)==t) { _augment=true; break; }
+        }
+        
+        ++res_bfs;
+      } //end of searching augmenting path
+
+      if (_augment) {
+        NodeIt n=t;
+        T augment_value=free.get(t);
+        //std::cout<<"augmentation: ";
+        while (pred.get(n).valid()) { 
+          AugEdgeIt e=pred.get(n);
+          e.augment(augment_value); 
+          //std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
+          n=res_graph.tail(e);
+        }
+        //std::cout<<std::endl;
+      }
+      //std::cout << "actual flow: "<< std::endl;
+      //for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
+      //std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+      //}
+      //std::cout<<std::endl;
+
+      return _augment;
+    }
     void run() {
-      typedef ResGraph<Graph, T> AugGraph;
-      AugGraph res_graph(G, flow, capacity);
-
-      bool augment;
-      do {
-        augment=false;
-
-        typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
-        typedef typename AugGraph::EdgeIt AugEdgeIt;
-        typedef std::queue<AugOutEdgeIt> BfsQueue;
-        BfsQueue bfs_queue;
-        bfs_queue.push(res_graph.template first<AugOutEdgeIt>(s));
-
-        typedef typename AugGraph::NodeMap<bool> ReachedMap;
-        ReachedMap reached(res_graph, false);
-        reached.set(s, true); 
-        
-        bfs_iterator1< AugGraph, ReachedMap > 
-        res_bfs(res_graph, bfs_queue, reached);
-
-        typedef typename AugGraph::NodeMap<AugEdgeIt> PredMap;
-        PredMap pred(res_graph);
-        //typename AugGraph::EdgeIt a; //invalid
-        //a.makeInvalid();
-        //pred.set(s, a);
-
-        typedef typename AugGraph::NodeMap<int> FreeMap;
-        FreeMap free(res_graph);
-        
-        //searching for augmenting path
-        while ( res_bfs.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.newly_reached()) {
-            AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
-            NodeIt v=res_graph.tail(e);
-            NodeIt w=res_graph.head(e);
-            //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
-            pred.set(w, e);
-            if (pred.get(v).valid()) {
-              free.set(w, std::min(free.get(v), e.free()));
-              //std::cout <<" nem elso csucs: ";
-              //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
-            } else {
-              free.set(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;
-        } //end searching augmenting path
-        if (reached.get(t)) {
-          augment=true;
-          NodeIt n=t;
-          T augment_value=free.get(t);
-          std::cout<<"augmentation: ";
-          while (pred.get(n).valid()) { 
-            AugEdgeIt e=pred.get(n);
-            e.augment(augment_value); 
-            std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
-            n=res_graph.tail(e);
-          }
-          std::cout<<std::endl;
-        }
-
-        std::cout << "actual flow: "<< std::endl;
-        for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
-          std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-        }
-        std::cout<<std::endl;
-
-      } while (augment);
+      while (augment()) { } 
     }
   };
@@ -204 +201 @@
 } // namespace marci
 
-#endif //MARCI_MAX_FLOW_HH
+#endif //EDMONDS_KARP_HH

src/work/iterator_bfs_dfs_demo.cc

@@ -182 +182 @@
   }
   
+  {
+    std::cout << "iterator bfs demo 2 ..." << std::endl;
+    //ListGraph::NodeMap<bool> reached(G, false);
+    //reached.set(s, true);
+    //std::queue<ListGraph::OutEdgeIt> bfs_queue;
+    //bfs_queue.push(G.first<OutEdgeIt>(s));
+    BfsIterator2< ListGraph, ListGraph::OutEdgeIt, ListGraph::NodeMap<bool> > bfs(G);
+    bfs.pushAndSetReached(s);
+    while (!bfs.finished()) {
+      if (OutEdgeIt(bfs).valid()) {
+        std::cout << "OutEdgeIt: " << bfs; 
+        std::cout << " aNode: " << G.aNode(bfs); 
+        std::cout << " bNode: " << G.bNode(bfs) << " ";
+      } else { 
+        std::cout << "OutEdgeIt: " << "invalid"; 
+        std::cout << " aNode: " << G.aNode(bfs); 
+        std::cout << " bNode: " << "invalid" << " ";
+      }
+      if (bfs.isBNodeNewlyReached()) { 
+        std::cout << "bNodeIsNewlyReached ";
+      } else { 
+        std::cout << "bNodeIsNotNewlyReached ";
+      } 
+      if (bfs.isANodeExamined()) { 
+        std::cout << "aNodeIsExamined ";
+      } else { 
+        std::cout << "aNodeIsNotExamined ";
+      } 
+      std::cout<<std::endl;
+      ++bfs;
+    }
+  }
+  
+
+
 
   {

src/work/list_graph.hh

@@ -1 @@
-#ifndef MARCI_LIST_GRAPH_HH
-#define MARCI_LIST_GRAPH_HH
+#ifndef LIST_GRAPH_HH
+#define LIST_GRAPH_HH
 
 #include <iostream>
 
 namespace marci {
-
-  template <typename It>
-  int number_of(It _it) { 
-    int i=0;
-    for( ; _it.valid(); ++_it) { ++i; } 
-    return i;
-  }
 
   template <typename It>
@@ -21 +14 @@
 
   class ListGraph {
+
     class node_item;
     class edge_item;
+
   public:
+
     class NodeIt;
     class EachNodeIt;
@@ -31 +27 @@
     class InEdgeIt;
     class SymEdgeIt;
-
-    template <typename T>
+    template <typename ValueType> class NodeMap;
+    template <typename ValueType> class EdgeMap;
+    
+  private:
+    
+    template <typename ValueType> friend class NodeMap;
+    template <typename ValueType> friend class EdgeMap;
+
+    template <typename ValueType>
     class NodeMap {
-      //typedef typename Graph::NodeIt NodeIt;
-      //typedef typename Graph::EachNodeIt EachNodeIt;
       const ListGraph& G; 
-      std::vector<T> container;
-    public:
-      NodeMap(const ListGraph& _G) : G(_G) {
-        int i=0;
-        for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) ++i;
-        container.resize(i); 
-      }
-      NodeMap(const ListGraph& _G, const T a) : G(_G) {
-        for(EachNodeIt it=G.template first<EachNodeIt>(); it.valid(); ++it) { 
-          container.push_back(a); 
-        }
-      }
-      void set(const NodeIt nit, const T a) { container[G.id(nit)]=a; }
-      T get(const NodeIt nit) const { return container[G.id(nit)]; }
-    };
-
-    template <typename T>
+      std::vector<ValueType> container;
+    public:
+      NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
+      NodeMap(const ListGraph& _G, const ValueType a) : 
+        G(_G), container(_G.node_id, a) { }
+      void set(const NodeIt nit, const ValueType a) { container[G.id(nit)]=a; }
+      ValueType get(const NodeIt nit) const { return container[G.id(nit)]; }
+    };
+
+    template <typename ValueType>
     class EdgeMap {
-      //typedef typename Graph::EdgeIt EdgeIt;
-      //typedef typename Graph::EachEdgeIt EachEdgeIt;
       const ListGraph& G; 
-      std::vector<T> container;
-    public:
-      EdgeMap(const ListGraph& _G) : G(_G) {
-        int i=0;
-        for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) ++i;
-        container.resize(i); 
-      }
-      EdgeMap(const ListGraph& _G, const T a) : G(_G) {
-        for(EachEdgeIt it=G.template first<EachEdgeIt>(); it.valid(); ++it) { 
-          container.push_back(a); 
-        }
-      }
-      void set(const EdgeIt eit, const T a) { container[G.id(eit)]=a; }
-      T get(const EdgeIt eit) const { return container[G.id(eit)]; }
-    };
-
-    //typedef template<typename T> NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef typename NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef typename NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template typename NodePropertyVector<ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef template typename NodePropertyVector<typename ListGraph, T> NodeMap;
-    //template <typename T>
-    //typedef EdgePropertyVector<ListGraph, T> EdgeMap;
-
-  private:
+      std::vector<ValueType> container;
+    public:
+      EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
+      EdgeMap(const ListGraph& _G, const ValueType a) : 
+        G(_G), container(_G.edge_id, a) { }
+      void set(const EdgeIt eit, const ValueType a) { container[G.id(eit)]=a; }
+      ValueType get(const EdgeIt eit) const { return container[G.id(eit)]; }
+    };
+
     int node_id;
     int edge_id;
@@ -114 +78 @@
       friend std::ostream& operator<<(std::ostream& os, const NodeIt& i);
       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
-      ListGraph* G;
+      //ListGraph* G;
       int id;
       edge_item* _first_out_edge;
@@ -136 +100 @@
       friend class SymEdgeIt;
       friend std::ostream& operator<<(std::ostream& os, const EdgeIt& i);
-      ListGraph* G;
+      //ListGraph* G;
       int id;
       node_item* _tail;
@@ -257 +221 @@
     /* functions to construct iterators from the graph, or from each other */
 
-    EachNodeIt firstNode() const { return EachNodeIt(_first_node); }
-    EachEdgeIt firstEdge() const { 
-      node_item* v=_first_node;
-      edge_item* edge=v->_first_out_edge;
-      while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
-      return EachEdgeIt(v, edge); 
-    }
+    //EachNodeIt firstNode() const { return EachNodeIt(*this); }
+    //EachEdgeIt firstEdge() const { return EachEdgeIt(*this); }
     
     //OutEdgeIt firstOutEdge(const NodeIt v) const { return OutEdgeIt(v); }
-    InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
-    SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
+    //InEdgeIt firstInEdge(const NodeIt v) const { return InEdgeIt(v); }
+    //SymEdgeIt firstSymEdge(const NodeIt v) const { return SymEdgeIt(v); }
     NodeIt tail(const EdgeIt e) const { return e.tailNode(); }
     NodeIt head(const EdgeIt e) const { return e.headNode(); }
@@ -288 +247 @@
     /* for experimental purpose */
 
-    void getFirst(EachNodeIt& v) const { v=EachNodeIt(_first_node); }
-    void getFirst(EachEdgeIt& e) const { e=firstEdge(); }
+    void getFirst(EachNodeIt& v) const { v=EachNodeIt(*this); }
+    void getFirst(EachEdgeIt& e) const { e=EachEdgeIt(*this); }
     void getFirst(OutEdgeIt& e, const NodeIt& v) const { e=OutEdgeIt(v); }
     void getFirst(InEdgeIt& e, const NodeIt& v) const { e=InEdgeIt(v); }
@@ -387 +346 @@
     class EachNodeIt : public NodeIt {
       friend class ListGraph;
+    protected:
+      EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
     public:
       EachNodeIt() : NodeIt() { }
       EachNodeIt(node_item* v) : NodeIt(v) { }
-      EachNodeIt(const ListGraph& G) : NodeIt(G._first_node) { }
       EachNodeIt& operator++() { node=node->_next_node; return *this; }
     };
@@ -423 +383 @@
     class EachEdgeIt : public EdgeIt {
       friend class ListGraph;
-      node_item* v;
-    public:
-      EachEdgeIt() : EdgeIt(), v(0) { }
-      EachEdgeIt(node_item* _v, edge_item* _e) : EdgeIt(_e), v(_v) { }
+    protected:
       EachEdgeIt(const ListGraph& G) {
-        v=G._first_node;
-        edge=v->_first_out_edge;
+        node_item* v=G._first_node;
+        if (v) edge=v->_first_out_edge; else edge=0;
         while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
       }
+    public:
+      EachEdgeIt() : EdgeIt() { }
+      EachEdgeIt(edge_item* _e) : EdgeIt(_e) { }
       EachEdgeIt& operator++() { 
+        node_item* v=edge->_tail;
         edge=edge->_next_out; 
         while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
@@ -442 +403 @@
       friend class ListGraph;
       node_item* v;
+    protected:
+      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
     public:
       OutEdgeIt() : EdgeIt(), v(0) { }
-    protected:
-      OutEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_out_edge; }
-    public:
       OutEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_out_edge; }
       OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
@@ -458 +418 @@
       friend class ListGraph;
       node_item* v;
+    protected:
+      InEdgeIt(const NodeIt& _v) : v(_v.node) { edge=v->_first_in_edge; }
     public:
       InEdgeIt() : EdgeIt(), v(0) { }
-    protected:
-      InEdgeIt(const NodeIt& _v) : v(_v.node) { 
-        edge=v->_first_in_edge; 
-      }
-    public:
       InEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { edge=v->_first_in_edge; }
       InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
@@ -477 +434 @@
       bool out_or_in; //1 iff out, 0 iff in
       node_item* v;
-    public:
-      SymEdgeIt() : EdgeIt(), v(0) { }
     protected:
       SymEdgeIt(const NodeIt& _v) : v(_v.node) { 
@@ -486 +441 @@
       }
     public:
+      SymEdgeIt() : EdgeIt(), v(0) { }
       SymEdgeIt(const ListGraph& G, const NodeIt _v) : v(_v.node) { 
         out_or_in=1;
@@ -550 +506 @@
 } //namespace marci
 
-#endif //MARCI_LIST_GRAPH_HH
+#endif //LIST_GRAPH_HH