Changeset 69:24c2c2989e0f in lemon-0.x for src

Timestamp:

02/09/04 14:11:10 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

Location:

src/work

Files:

• edmonds_karp.hh (modified) (4 diffs)
• list_graph.hh (modified) (2 diffs)
• marci/dimacs.hh (added)
• marci/flow0.dim (added)
• marci/flow1.dim (added)
• marci/flow2.dim (added)
• marci/flow3.dim (added)
• marci/max_flow2.dat (added)
• marci/read_dimacs_demo.cc (added)
• marci_graph_demo.cc (modified) (1 diff)

src/work/edmonds_karp.hh

@@ -97 +97 @@
     int id(NodeIt v) const { return G.id(v); }
 
-    template <typename ValueType>
+    template <typename S>
     class NodeMap {
-      typename Graph::NodeMap<ValueType> node_map; 
+      typename Graph::NodeMap<S> node_map; 
     public:
       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
-      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, ValueType a) : node_map(_G.G, a) { }
-      void set(NodeIt nit, ValueType a) { node_map.set(nit, a); }
-      ValueType get(NodeIt nit) const { return node_map.get(nit); }
+      NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
+      void set(NodeIt nit, S a) { node_map.set(nit, a); }
+      S get(NodeIt nit) const { return node_map.get(nit); }
     };
 
@@ -141 +141 @@
       //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()) {
@@ -177 +160 @@
         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;
@@ -197 +172 @@
       while (augment()) { } 
     }
+    T flowValue() { 
+      T a=0;
+      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
+        a+=flow.get(i);
+      }
+      return a;
+    }
   };
 

src/work/list_graph.hh

@@ -27 +27 @@
     class InEdgeIt;
     class SymEdgeIt;
-    template <typename ValueType> class NodeMap;
-    template <typename ValueType> class EdgeMap;
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
     
   private:
     
-    template <typename ValueType> friend class NodeMap;
-    template <typename ValueType> friend class EdgeMap;
-
-    template <typename ValueType>
+    template <typename T> friend class NodeMap;
+    template <typename T> friend class EdgeMap;
+
+    template <typename T>
     class NodeMap {
       const ListGraph& G; 
-      std::vector<ValueType> container;
-    public:
-      NodeMap(const ListGraph& _G) : G(_G), container(_G.node_id) { }
-      NodeMap(const ListGraph& _G, ValueType a) : 
-        G(_G), container(_G.node_id, a) { }
-      void set(NodeIt nit, ValueType a) { container[G.id(nit)]=a; }
-      ValueType get(NodeIt nit) const { return container[G.id(nit)]; }
-    };
-
-    template <typename ValueType>
+      std::vector<T> container;
+    public:
+      typedef T ValueType;
+      typedef NodeIt KeyType;
+      NodeMap(const ListGraph& _G) : G(_G), container(G.node_id) { }
+      NodeMap(const ListGraph& _G, T a) : 
+        G(_G), container(G.node_id, a) { }
+      void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
+      T get(NodeIt nit) const { return container[G.id(nit)]; }
+      void resize() { container.resize(G.node_id); }
+      void resize(T a) { container.resize(G.node_id, a); }
+    };
+
+    template <typename T>
     class EdgeMap {
       const ListGraph& G; 
-      std::vector<ValueType> container;
-    public:
-      EdgeMap(const ListGraph& _G) : G(_G), container(_G.edge_id) { }
-      EdgeMap(const ListGraph& _G, ValueType a) : 
-        G(_G), container(_G.edge_id, a) { }
-      void set(EdgeIt eit, ValueType a) { container[G.id(eit)]=a; }
-      ValueType get(EdgeIt eit) const { return container[G.id(eit)]; }
+      std::vector<T> container;
+    public:
+      typedef T ValueType;
+      typedef EdgeIt KeyType;
+      EdgeMap(const ListGraph& _G) : G(_G), container(G.edge_id) { }
+      EdgeMap(const ListGraph& _G, T a) : 
+        G(_G), container(G.edge_id, a) { }
+      void set(EdgeIt eit, T a) { container[G.id(eit)]=a; }
+      T get(EdgeIt eit) const { return container[G.id(eit)]; }
+      void resize() { container.resize(G.edge_id); }
+      void resize(T a) { container.resize(G.edge_id, a); }
     };
 
@@ -302 +310 @@
     void erase(EdgeIt e) { _delete_edge(e.edge); }
 
+    void clear() { 
+      while (first<EachNodeIt>().valid()) erase(first<EachNodeIt>());
+    }
+
     void setTail(EdgeIt e, NodeIt tail) {
       _set_tail(e.edge, tail.node); 

src/work/marci_graph_demo.cc

@@ -232 +232 @@
   }
   std::cout<<std::endl;
+  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   return 0;