Changeset 646:bd7a69231cf8 in lemon-0.x for src/work

Timestamp:

05/19/04 18:06:57 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

max_flow.h: status flags for actMinCut
leda_graph_wrapper.h: NodeMapWrapper?, EdgeMapWrapper?

Location:

src/work/marci

Files:

• bfs_dfs.h (modified) (3 diffs)
• leda/leda_graph_wrapper.h (modified) (2 diffs)
• max_flow_demo.cc (modified) (6 diffs)

src/work/marci/bfs_dfs.h

@@ -107 +107 @@
       return *this;
     }
-    /// Guess what?
+    /// Returns true iff the algorithm is finished.
     bool finished() const { return bfs_queue.empty(); }
     /// The conversion operator makes for converting the bfs-iterator 
@@ -113 +113 @@
     ///\bug Edge have to be in HUGO 0.2
     operator OutEdgeIt() const { return actual_edge; }
-    /// Guess what?
+    /// Returns if b-node has been reached just now.
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    /// Guess what?
+    /// Returns if a-node is examined.
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    /// Guess what?
+    /// Returns a-node of the actual edge, so does if the edge is invalid.
     Node aNode() const { return bfs_queue.front(); }
-    /// Guess what?
+    /// \pre The actual edge have to be valid.
     Node bNode() const { return graph->bNode(actual_edge); }
     /// Guess what?
@@ -250 +250 @@
       return *this;
     }
-    /// Guess what?
+    /// Returns true iff the algorithm is finished.
     bool finished() const { return dfs_stack.empty(); }
-    /// Guess what?
+    /// The conversion operator makes for converting the bfs-iterator 
+    /// to an \c out-edge-iterator.
+    ///\bug Edge have to be in HUGO 0.2
     operator OutEdgeIt() const { return actual_edge; }
-    /// Guess what?
+    /// Returns if b-node has been reached just now.
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
-    /// Guess what?
+    /// Returns if a-node is examined.
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
-    /// Guess what?
+    /// Returns a-node of the actual edge, so does if the edge is invalid.
     Node aNode() const { return actual_node; /*FIXME*/}
-    /// Guess what?
+    /// Returns b-node of the actual edge. 
+    /// \pre The actual edge have to be valid.
     Node bNode() const { return graph->bNode(actual_edge); }
     /// Guess what?

src/work/marci/leda/leda_graph_wrapper.h

@@ -41 +41 @@
     template <typename T> class NodeMap;
     template <typename T> class EdgeMap;
+    template <typename T> class NodeMapWrapper;
+    template <typename T> class EdgeMapWrapper;
 
     class Node;
@@ -292 +294 @@
     };
 
+
+    ///Read/write map from the nodes to type \c T.
+    template<typename T> class NodeMapWrapper
+    {
+      leda_node_map<T>* leda_stuff;
+    public:
+      typedef T ValueType;
+      typedef Node KeyType;
+
+      NodeMapWrapper(leda_node_map<T>& _leda_stuff) : 
+        leda_stuff(&_leda_stuff) { }
+      //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
+
+      void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
+      T get(Node i) const { return (*leda_stuff)[i.l_n]; }  //FIXME: Is it necessary
+      T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
+      const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
+
+      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
+      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
+    };
+
+    ///Read/write map from the edges to type \c T.
+    template<typename T> class EdgeMapWrapper
+    {
+      leda_edge_map<T>* leda_stuff;
+    public:
+      typedef T ValueType;
+      typedef Edge KeyType;
+
+      EdgeMapWrapper(leda_edge_map<T>& _leda_stuff) : 
+        leda_stuff(_leda_stuff) { }
+      //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
+
+      void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
+      T get(Edge i) const { return (*leda_stuff)[i.l_e]; }  //FIXME: Is it necessary
+      T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
+      const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
+
+      void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
+      //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); }   //FIXME: Is it necessary
+    };
+
   };
 

src/work/marci/max_flow_demo.cc

@@ -73 +73 @@
   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
     max_flow_test(g, s, t, cap, flow);
+  Graph::NodeMap<bool> cut(g);
 
   {
@@ -80 +81 @@
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+    max_flow_test.actMinCut(cut);
+
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
   }
 
@@ -89 +98 @@
     std::cout << "elapsed time: " << ts << std::endl;
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
   }
 
@@ -109 +125 @@
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
   }
 
@@ -131 +154 @@
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
   }
 
@@ -142 +172 @@
     std::cout << "number of augmentation phases: " << i << std::endl; 
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
-  }
-
+
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
+  }
+
+  {
+    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
+    ts.reset();
+    int i=0;
+    while (max_flow_test.augmentOnShortestPath2()) { ++i; }
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+
+    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
+      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
+        std::cout << "Slackness does not hold!" << std::endl;
+      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
+        std::cout << "Slackness does not hold!" << std::endl;
+    }
+  }
 
   return 0;