Changeset 409:7ab7f083760a in lemon-0.x for src/work/marci

Timestamp:

04/26/04 11:54:24 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

stGraphWrapper is almost working

Location:

src/work/marci

Files:

• bfs_iterator.h (modified) (4 diffs)
• bipartite_graph_wrapper_test.cc (modified) (2 diffs)
• edmonds_karp.h (modified) (1 diff)
• for_each_macros.h (modified) (1 diff)
• graph_wrapper.h (modified) (15 diffs)
• leda_graph_wrapper.h (modified) (2 diffs)
• macro_test.cc (modified) (1 diff)
• makefile (modified) (1 diff)

src/work/marci/bfs_iterator.h

@@ -29 +29 @@
       own_reached_map(true) { }
     ~BfsIterator() { if (own_reached_map) delete &reached; }
+    //s is marcked reached.
+    //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
+    //is the queue is not empty, then is it pushed.
     void pushAndSetReached(Node s) { 
       reached.set(s, true);
@@ -81 +84 @@
     }
     bool finished() const { return bfs_queue.empty(); }
-    operator OutEdgeIt () const { return actual_edge; }
+    operator OutEdgeIt() const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
@@ -89 +92 @@
     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
   };  
+
+  /// Bfs searches from s for the nodes wich are not marked in 
+  /// reachedmap
+  template <typename Graph, 
+            typename ReachedMap=typename Graph::template NodeMap<bool>, 
+            typename PredMap
+            =typename Graph::template NodeMap<typename Graph::Edge>, 
+            typename DistMap=typename Graph::template NodeMap<int> > 
+  class Bfs : public BfsIterator<Graph, ReachedMap> {
+    typedef BfsIterator<Graph, ReachedMap> Parent;
+  protected:
+    typedef typename Parent::Node Node;
+    PredMap& pred;
+    DistMap& dist;
+  public:
+    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
+    //s is marked to be reached and pushed in the bfs queue.
+    //if the queue is empty, then the first out-edge is processed
+    //If s was not marked previously, then 
+    //in addition its pred is set to be INVALID, and dist to 0. 
+    //if s was marked previuosly, then it is simply pushed.
+    void push(Node s) { 
+      if (this->reached[s]) {
+        Parent::pushAndSetReached(s);
+      } else {
+        Parent::pushAndSetReached(s);
+        pred.set(s, INVALID);
+        dist.set(s, 0);
+      }
+    }
+    void run(Node s) {
+      push(s);
+      while (!this->finished()) this->operator++();
+    }
+    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
+      Parent::operator++();
+      if (this->graph->valid(actual_edge) && this->b_node_newly_reached) {
+        pred.set(s, actual_edge);
+        dist.set(s, dist[this->aNode()]);
+      }
+      return *this;
+    }
+    const PredMap& getPredMap() const { return pred; }
+    const DistMap& getDistMap() const { return dist; }
+  };
 
   template <typename Graph, /*typename OutEdgeIt,*/ 
@@ -143 +191 @@
     }
     bool finished() const { return dfs_stack.empty(); }
-    operator OutEdgeIt () const { return actual_edge; }
+    operator OutEdgeIt() const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }

src/work/marci/bipartite_graph_wrapper_test.cc

@@ -25 +25 @@
 
   Graph g;
-  //Node s, t;
-  //Graph::EdgeMap<int> cap(g);
-  //readDimacsMaxFlow(std::cin, g, s, t, cap);
-  std::vector<Graph::Node> s_nodes;
-  std::vector<Graph::Node> t_nodes;
-  for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
-  for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
-  g.addEdge(s_nodes[0], t_nodes[2]);
-  g.addEdge(t_nodes[1], s_nodes[2]);
+//   std::vector<Graph::Node> s_nodes;
+//   std::vector<Graph::Node> t_nodes;
+//   for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
+//   for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
+//   g.addEdge(s_nodes[0], t_nodes[2]);
+//   g.addEdge(t_nodes[1], s_nodes[2]);
+//   g.addEdge(s_nodes[0], t_nodes[1]);
+  
+//   Graph::NodeMap<int> ref_map(g, -1);
+//   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
+//   for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
+//   for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
+
+  std::vector<Graph::Node> nodes;
+  for (int i=0; i<3; ++i) nodes.push_back(g.addNode());
+  for (int i=3; i<6; ++i) nodes.push_back(g.addNode());
+  g.addEdge(nodes[0], nodes[3+2]);
+  g.addEdge(nodes[3+1], nodes[2]);
+  g.addEdge(nodes[0], nodes[3+1]);
   
   Graph::NodeMap<int> ref_map(g, -1);
   IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
-  for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
-  for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
+  for (int i=0; i<3; ++i) bipartite_map.insert(nodes[i], false);
+  for (int i=3; i<6; ++i) bipartite_map.insert(nodes[i], true);
+
+  Graph::Node u;
+  std::cout << "These nodes will be in S:\n";
+  //FIXME azert kellene ++, es invalid vizsgalat u-bol, hogy ezt le lehessen 
+  //irni 1etlen FOR_EACH-csel.
+  for (bipartite_map.first(u, false); g.valid(u); bipartite_map.next(u)) 
+    std::cout << u << " ";
+  std::cout << "\n";
+  std::cout << "These nodes will be in T:\n";
+  for (bipartite_map.first(u, true); g.valid(u); bipartite_map.next(u)) 
+    std::cout << u << " ";
+  std::cout << "\n";
+
   typedef BipartiteGraphWrapper<Graph> BGW;
   BGW bgw(g, bipartite_map);
+
+  std::cout << "Nodes by NodeIt:\n";
+  FOR_EACH_LOC(BGW::NodeIt, n, bgw) {
+    std::cout << n << " ";
+  }
+  std::cout << "\n";
+  std::cout << "Nodes in S by ClassNodeIt:\n";
+  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.S_CLASS) {
+    std::cout << n << " ";
+  }
+  std::cout << "\n";
+  std::cout << "Nodes in T by ClassNodeIt:\n";
+  FOR_EACH_INC_LOC(BGW::ClassNodeIt, n, bgw, bgw.T_CLASS) {
+    std::cout << n << " ";
+  }
+  std::cout << "\n";
+  std::cout << "Edges of the bipartite graph:\n";
   FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
     std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
@@ -59 +99 @@
   s=g.first(si);
   bfs.pushAndSetReached(BGW::Node(s));
-  while (!bfs.finished()) ++bfs;
+  while (!bfs.finished()) { ++bfs; }
 
-  BGW::EdgeMap<bool> cap(bgw);
-  BGW::EdgeMap<bool> flow1(bgw);
+  FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
+    std::cout << "out-edges of " << n << ":\n"; 
+    FOR_EACH_INC_LOC(stGW::OutEdgeIt, e, stgw, n) { 
+      std::cout << " " << e << "\n";
+      std::cout << " aNode: " << stgw.aNode(e) << "\n";
+      std::cout << " bNode: " << stgw.bNode(e) << "\n";      
+    }
+    std::cout << "in-edges of " << n << ":\n"; 
+    FOR_EACH_INC_LOC(stGW::InEdgeIt, e, stgw, n) { 
+      std::cout << " " << e << "\n";
+      std::cout << " aNode: " << stgw.aNode(e) << "\n";
+      std::cout << " bNode: " << stgw.bNode(e) << "\n";     
+    }
+  }
+  std::cout << "Edges of the stGraphWrapper:\n"; 
+  FOR_EACH_LOC(stGW::EdgeIt, n, stgw) { 
+    std::cout << " " << n << "\n";
+  }
 
-  typedef ResGraphWrapper< BGW, int, BGW::EdgeMap<bool>, BGW::EdgeMap<bool> > 
-    RBGW;
-  RBGW rbgw(bgw, cap, flow1);
-  RBGW::NodeMap<int> u(rbgw);
+  stGW::NodeMap<bool> b(stgw);
+  FOR_EACH_LOC(stGW::NodeIt, n, stgw) { 
+    std::cout << n << ": " << b[n] <<"\n";
+  }
+
+  std::cout << "Bfs from s: \n";
+  BfsIterator< stGW, stGW::NodeMap<bool> > bfs_stgw(stgw);
+  bfs_stgw.pushAndSetReached(stgw.S_NODE);
+  while (!bfs_stgw.finished()) { 
+    std::cout << " " << stGW::OutEdgeIt(bfs_stgw) << "\n";
+    ++bfs_stgw; 
+  }
   
-
   MaxFlow<stGW, int, ConstMap<stGW::Edge, int>, stGW::EdgeMap<int> > 
     max_flow_test(stgw, stgw.S_NODE, stgw.T_NODE, const1map, flow);
-  max_flow_test.augmentOnShortestPath();
-  max_flow_test.augmentOnShortestPath();
+  while (max_flow_test.augmentOnShortestPath()) { }
 
   std::cout << max_flow_test.flowValue() << std::endl;

src/work/marci/edmonds_karp.h

@@ -323 +323 @@
     public:
       DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
-      void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
+      void set(const typename MapGraphWrapper::Node& n, int a) { 
+        dist.set(n, a); 
+      }
       int operator[](const typename MapGraphWrapper::Node& n) 
         { return dist[n]; }

src/work/marci/for_each_macros.h

@@ -5 +5 @@
 namespace hugo {
 
-#define FOR_EACH(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
-#define FOR_EACH_INC(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_INC_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
 
-#define FOR_EACH_EDGE(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
-#define FOR_EACH_NODE(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
-#define FOR_EACH_INEDGE(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
-#define FOR_EACH_OUTEDGE(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_EDGE_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_NODE_GLOB(e, g) for((g).first((e)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_INEDGE_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
+#define FOR_EACH_OUTEDGE_GLOB(e, g, v) for((g).first((e), (v)); (g).valid((e)); (g).next((e)))
 
 //   template<typename It, typename Graph> 

src/work/marci/graph_wrapper.h

@@ -924 +924 @@
 
   public:
-    static const bool S_CLASS=false;
-    static const bool T_CLASS=true;
+    //marci
+    //FIXME vhogy igy kellene, csak az en forditom nem eszi meg
+    //static const bool S_CLASS=false;
+    //static const bool T_CLASS=true;
     
+    bool S_CLASS;
+    bool T_CLASS;
+
     BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
-      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
-    }
+      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map), 
+      S_CLASS(false), T_CLASS(true) { }
     typedef typename GraphWrapper<Graph>::Node Node;
     //using GraphWrapper<Graph>::NodeIt;
@@ -1103 +1108 @@
 //invalid, 3, invalid)
     template <typename T> class NodeMap;
-    template <typename T> class EdgeMap;
+    template <typename T, typename Parent> class EdgeMap;
 
 //    template <typename T> friend class NodeMap;
@@ -1142 +1147 @@
                 static_cast<typename Graph::Node>(u)!=
                 static_cast<typename Graph::Node>(v));
-      } 
+      }
+      friend std::ostream& operator<<(std::ostream& os, const Node& i);
       int getSpec() const { return spec; }
     };
+
     class NodeIt { 
       friend class GraphWrapper<Graph>;
@@ -1156 +1163 @@
       NodeIt(const Invalid& i) : n(i), spec(3) { }
       NodeIt(const stGraphWrapper<Graph>& _G) : n(*(_G.graph)), spec(0) { 
-        if (!_G->valid(n)) spec=1;
+        if (!_G.graph->valid(n)) spec=1;
       }
       operator Node() const { return Node(n, spec); }
     };
+
     class Edge : public Graph::Edge {
       friend class GraphWrapper<Graph>;
       friend class stGraphWrapper<Graph>;
-      template <typename T> friend class EdgeMap;
+      template <typename T, typename Parent> friend class EdgeMap;
       int spec;
       typename Graph::Node n;
@@ -1185 +1193 @@
                 u.n!=v.n);
       } 
+      friend std::ostream& operator<<(std::ostream& os, const Edge& i);
       int getSpec() const { return spec; }
     };
+
     class OutEdgeIt { 
       friend class GraphWrapper<Graph>;
@@ -1230 +1240 @@
       operator Edge() const { return Edge(e, spec, n); }
     };
+
     class InEdgeIt { 
       friend class GraphWrapper<Graph>;
@@ -1262 +1273 @@
             spec=3;
             n=INVALID;
+            break;
           case 2:
             e=INVALID;
-            spec=1;
+            spec=2;
             _G.graph->first(n, T_CLASS); //vmi->t;
             if (!_G.graph->valid(n)) spec=3; //Ha T ures
@@ -1272 +1284 @@
       operator Edge() const { return Edge(e, spec, n); }
     };
+
     class EdgeIt { 
       friend class GraphWrapper<Graph>;
@@ -1335 +1348 @@
       switch (i.spec) {
         case 0: //normal edge
-          this->graph->aNode(i.e);
+          v=this->graph->aNode(i.e);
           this->graph->next(i.e);
           if (!this->graph->valid(i.e)) { //Az igazi elek vegere ertunk
@@ -1448 +1461 @@
     bool valid(const Edge& e) const { return (e.spec<3); }
 
-//    int nodeNum() const { return this->graph->nodeNum(); }
-//    int edgeNum() const { return this->graph->edgeNum(); }
+    int nodeNum() const { return this->graph->nodeNum()+2; }
+    int edgeNum() const { 
+      return this->graph->edgeNum()+this->graph->nodeNum(); 
+    }
   
     Node aNode(const OutEdgeIt& e) const { return tail(e); }
@@ -1455 +1470 @@
     Node bNode(const OutEdgeIt& e) const { return head(e); }
     Node bNode(const InEdgeIt& e) const { return tail(e); }
-  
+
+    void addNode() const { }
+    void addEdge() const { }
+    
 //    Node addNode() const { return Node(this->graph->addNode()); }
 //    Edge addEdge(const Node& tail, const Node& head) const { 
@@ -1469 +1487 @@
       T s_value, t_value;
     public:
-      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G) { }
+      NodeMap(const stGraphWrapper<Graph>& _G) :  Parent(_G), 
+                                                  s_value(), 
+                                                  t_value() { }
       NodeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
                                                       s_value(a), 
@@ -1503 +1523 @@
     };
 
-    template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
-      typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
+    template<typename T, 
+             typename Parent=
+             typename GraphWrapper<Graph>::template EdgeMap<T> > 
+    class EdgeMap : public Parent { 
+      //typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
     public:
@@ -1528 +1551 @@
         switch (e.spec) {
         case 0: 
-          GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
+          Parent::set(e, t);
           break;
         case 1:
@@ -1540 +1563 @@
       }
     };
+
+//     template<typename T> class EdgeMap : public GraphWrapper<Graph>::template EdgeMap<T> { 
+//       typedef typename GraphWrapper<Graph>::template EdgeMap<T> Parent;
+//       typename GraphWrapper<Graph>::template NodeMap<T> node_value;
+//     public:
+//       EdgeMap(const stGraphWrapper<Graph>& _G) : Parent(_G), 
+//                                               node_value(_G) { }
+//       EdgeMap(const stGraphWrapper<Graph>& _G, T a) : Parent(_G, a), 
+//                                                    node_value(_G, a) { }
+//       T operator[](const Edge& e) const { 
+//      switch (e.spec) {
+//      case 0: 
+//        return Parent::operator[](e);
+//        break;
+//      case 1:
+//        return node_value[e.n];
+//        break;
+//      case 2:
+//      default:
+//        return node_value[e.n];
+//        break;
+//      }
+//       }
+//       void set(const Edge& e, T t) { 
+//      switch (e.spec) {
+//      case 0: 
+//        GraphWrapper<Graph>::template EdgeMap<T>::set(e, t);
+//        break;
+//      case 1:
+//        node_value.set(e.n, t);
+//        break;
+//      case 2:
+//      default:
+//        node_value.set(e.n, t);
+//        break;
+//      }
+//       }
+//     };
+
+    friend std::ostream& operator<<(std::ostream& os, const Node& i) { 
+      os << "(node: " << typename Graph::Node(i) << " spec: " << i.spec <<")"; 
+      return os; 
+    }
+    friend std::ostream& operator<<(std::ostream& os, const Edge& i) { 
+      os << "(edge: " << typename Graph::Edge(i) << " spec: " << i.spec << 
+        " node: " << i.n << ")"; 
+      return os; 
+    }
+
   };
 

src/work/marci/leda_graph_wrapper.h

@@ -23 +23 @@
   // @{
 
-  /// An empty graph class.
+  /// A graph wrapperstructure for wrapping LEDA graphs in HUGO.
   
+  /// This graph wrapper class wraps LEDA graph and LEDA parametrized graph
+  /// and then the generic algorithms and wrappers of HUGO can be used 
+  /// with LEDA graphs. 
   /// This class provides all the common features of a grapf structure,
   /// however completely without implementations or real data structures
@@ -195 +198 @@
     }
 
-    template< typename It >
-    It first() const { 
-      It e;
-      first(e);
-      return e; 
-    }
-
-    template< typename It >
-    It first(Node v) const { 
-      It e;
-      first(e, v);
-      return e; 
-    }
+//     template< typename It >
+//     It first() const { 
+//       It e;
+//       first(e);
+//       return e; 
+//     }
+
+//     template< typename It >
+//     It first(Node v) const { 
+//       It e;
+//       first(e, v);
+//       return e; 
+//     }
 
     ///Gives back the head node of an edge.

src/work/marci/macro_test.cc

@@ -15 +15 @@
   Graph::Node n2=g.addNode();
   Graph::NodeIt n;
-  FOR_EACH(n, g) {
+  FOR_EACH_GLOB(n, g) {
     std::cout << g.id(n) << " ";
   }

src/work/marci/makefile

@@ -10 +10 @@
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test
+BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test bipartite_matching_try
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda