Changeset 569:3b6afd33c221 in lemon-0.x

Timestamp:

05/07/04 09:44:44 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

BidirGraphWrapper?<Graph>, the map values are different for the opposite edges.

Location:

src

Files:

• hugo/graph_wrapper.h (modified) (12 diffs)
• work/marci/iterator_bfs_demo.cc (modified) (1 diff)

src/hugo/graph_wrapper.h

@@ -219 +219 @@
   };
 
+
+
   /// A graph wrapper which reverses the orientation of the edges.
 
@@ -292 +294 @@
 
   };
+
+
 
   /// Wrapper for hiding nodes and edges from a graph.
@@ -464 +468 @@
   };
 
+
+
   /// A wrapper for forgetting the orientation of a graph.
 
@@ -561 +567 @@
   };
 
-  
-
-  /// A wrapper for composing the residual graph for directed flow and circulation problems.
-
-  /// A wrapper for composing the residual graph for directed flow and circulation problems.
-  template<typename Graph, typename Number, 
-           typename CapacityMap, typename FlowMap>
-  class ResGraphWrapper : public GraphWrapper<Graph> {
+
+
+  /// A wrapper for composing bidirected graph from a directed one. 
+  /// experimental, for fezso's sake.
+  template<typename Graph>
+  class BidirGraphWrapper : public GraphWrapper<Graph> {
   protected:
-    const CapacityMap* capacity;
-    FlowMap* flow;
-
-    ResGraphWrapper() : GraphWrapper<Graph>(0), 
-                        capacity(0), flow(0) { }
-    void setCapacityMap(const CapacityMap& _capacity) {
-      capacity=&_capacity;
-    }
-    void setFlowMap(FlowMap& _flow) {
-      flow=&_flow;
-    }
+    //const CapacityMap* capacity;
+    //FlowMap* flow;
+
+    BidirGraphWrapper() : GraphWrapper<Graph>()/*, 
+                                                 capacity(0), flow(0)*/ { }
+//     void setCapacityMap(const CapacityMap& _capacity) {
+//       capacity=&_capacity;
+//     }
+//     void setFlowMap(FlowMap& _flow) {
+//       flow=&_flow;
+//     }
 
   public:
 
-    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
-                    FlowMap& _flow) : 
-      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
+    BidirGraphWrapper(Graph& _graph/*, const CapacityMap& _capacity, 
+                                     FlowMap& _flow*/) : 
+      GraphWrapper<Graph>(_graph)/*, capacity(&_capacity), flow(&_flow)*/ { }
 
     class Edge; 
@@ -596 +600 @@
     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
     class Edge : public Graph::Edge {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+      friend class BidirGraphWrapper<Graph>;
     protected:
       bool backward; //true, iff backward
@@ -619 +623 @@
 
     class OutEdgeIt {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+      friend class BidirGraphWrapper<Graph>;
     protected:
       typename Graph::OutEdgeIt out;
@@ -630 +634 @@
       OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
 //the unique invalid iterator
-      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
+      OutEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
         backward=false;
-        resG.graph->first(out, v);
-        while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
-        if (!resG.graph->valid(out)) {
+        _G.graph->first(out, v);
+        while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
+        if (!_G.graph->valid(out)) {
           backward=true;
-          resG.graph->first(in, v);
-          while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
+          _G.graph->first(in, v);
+          while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
         }
       }
@@ -653 +657 @@
 
     class InEdgeIt {
-      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+      friend class BidirGraphWrapper<Graph>;
     protected:
       typename Graph::OutEdgeIt out;
@@ -664 +668 @@
       InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
 //the unique invalid iterator
-      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG, Node v) { 
+      InEdgeIt(const BidirGraphWrapper<Graph>& _G, Node v) { 
         backward=false;
-        resG.graph->first(in, v);
-        while( resG.graph->valid(in) && !(resG.resCap(*this)>0) ) { resG.graph->next(in); }
-        if (!resG.graph->valid(in)) {
+        _G.graph->first(in, v);
+        while(_G.graph->valid(in) && !_G.enabled(*this)) { _G.graph->next(in); }
+        if (!_G.graph->valid(in)) {
           backward=true;
-          resG.graph->first(out, v);
-          while( resG.graph->valid(out) && !(resG.resCap(*this)>0) ) { resG.graph->next(out); }
+          _G.graph->first(out, v);
+          while(_G.graph->valid(out) && !_G.enabled(*this)) { _G.graph->next(out); }
         }
       }
@@ -687 +691 @@
 
     class EdgeIt {
+      friend class BidirGraphWrapper<Graph>;
+    protected:
+      typename Graph::EdgeIt e;
+      bool backward;
+    public:
+      EdgeIt() { }
+      EdgeIt(const Invalid& i) : e(i), backward(true) { }
+      EdgeIt(const BidirGraphWrapper<Graph>& _G) { 
+        backward=false;
+        _G.graph->first(e);
+        while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
+        if (!_G.graph->valid(e)) {
+          backward=true;
+          _G.graph->first(e);
+          while (_G.graph->valid(e) && !_G.enabled(*this)) _G.graph->next(e);
+        }
+      }
+      operator Edge() const { 
+        return Edge(e, this->backward);
+      }
+    };
+
+    using GraphWrapper<Graph>::first;
+//     NodeIt& first(NodeIt& i) const { 
+//       i=NodeIt(*this); return i;
+//     }
+    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
+      i=OutEdgeIt(*this, p); return i;
+    }
+//    FIXME not tested
+    InEdgeIt& first(InEdgeIt& i, const Node& p) const { 
+      i=InEdgeIt(*this, p); return i;
+    }
+    EdgeIt& first(EdgeIt& i) const { 
+      i=EdgeIt(*this); return i;
+    }
+  
+    using GraphWrapper<Graph>::next;
+//    NodeIt& next(NodeIt& n) const { GraphWrapper<Graph>::next(n); return n; }
+    OutEdgeIt& next(OutEdgeIt& e) const { 
+      if (!e.backward) {
+        Node v=this->graph->aNode(e.out);
+        this->graph->next(e.out);
+        while(this->graph->valid(e.out) && !enabled(e)) { 
+          this->graph->next(e.out); }
+        if (!this->graph->valid(e.out)) {
+          e.backward=true;
+          this->graph->first(e.in, v); 
+          while(this->graph->valid(e.in) && !enabled(e)) { 
+            this->graph->next(e.in); }
+        }
+      } else {
+        this->graph->next(e.in);
+        while(this->graph->valid(e.in) && !enabled(e)) { 
+          this->graph->next(e.in); } 
+      }
+      return e;
+    }
+//     FIXME Not tested
+    InEdgeIt& next(InEdgeIt& e) const { 
+      if (!e.backward) {
+        Node v=this->graph->aNode(e.in);
+        this->graph->next(e.in);
+        while(this->graph->valid(e.in) && !enabled(e)) { 
+          this->graph->next(e.in); }
+        if (!this->graph->valid(e.in)) {
+          e.backward=true;
+          this->graph->first(e.out, v); 
+          while(this->graph->valid(e.out) && !enabled(e)) { 
+            this->graph->next(e.out); }
+        }
+      } else {
+        this->graph->next(e.out);
+        while(this->graph->valid(e.out) && !enabled(e)) { 
+          this->graph->next(e.out); } 
+      }
+      return e;
+    }
+    EdgeIt& next(EdgeIt& e) const {
+      if (!e.backward) {
+        this->graph->next(e.e);
+        while(this->graph->valid(e.e) && !enabled(e)) { 
+          this->graph->next(e.e); }
+        if (!this->graph->valid(e.e)) {
+          e.backward=true;
+          this->graph->first(e.e); 
+          while(this->graph->valid(e.e) && !enabled(e)) { 
+            this->graph->next(e.e); }
+        }
+      } else {
+        this->graph->next(e.e);
+        while(this->graph->valid(e.e) && !enabled(e)) { 
+          this->graph->next(e.e); } 
+      }
+      return e;
+    }
+
+    Node tail(Edge e) const { 
+      return ((!e.backward) ? this->graph->tail(e) : this->graph->head(e)); }
+    Node head(Edge e) const { 
+      return ((!e.backward) ? this->graph->head(e) : this->graph->tail(e)); }
+
+    Node aNode(OutEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->aNode(e.out) : 
+              this->graph->aNode(e.in)); }
+    Node bNode(OutEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->bNode(e.out) : 
+              this->graph->bNode(e.in)); }
+
+    Node aNode(InEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->aNode(e.in) : 
+              this->graph->aNode(e.out)); }
+    Node bNode(InEdgeIt e) const { 
+      return ((!e.backward) ? this->graph->bNode(e.in) : 
+              this->graph->bNode(e.out)); }
+
+//    int nodeNum() const { return graph->nodeNum(); }
+    //FIXME
+    void edgeNum() const { }
+    //int edgeNum() const { return graph->edgeNum(); }
+
+
+//    int id(Node v) const { return graph->id(v); }
+
+    bool valid(Node n) const { return GraphWrapper<Graph>::valid(n); }
+    bool valid(Edge e) const { 
+      return this->graph->valid(e);
+        //return e.forward ? graph->valid(e.out) : graph->valid(e.in); 
+    }
+
+    bool forward(const Edge& e) const { return !e.backward; }
+    bool backward(const Edge& e) const { return e.backward; }
+
+//     void augment(const Edge& e, Number a) const {
+//       if (!e.backward)  
+// //   flow->set(e.out, flow->get(e.out)+a);
+//      flow->set(e, (*flow)[e]+a);
+//       else  
+// //   flow->set(e.in, flow->get(e.in)-a);
+//      flow->set(e, (*flow)[e]-a);
+//     }
+
+    bool enabled(const Edge& e) const { 
+      if (!e.backward) 
+//      return (capacity->get(e.out)-flow->get(e.out)); 
+        //return ((*capacity)[e]-(*flow)[e]);
+        return true;
+      else 
+//      return (flow->get(e.in)); 
+        //return ((*flow)[e]); 
+        return true;
+    }
+
+//     Number enabled(typename Graph::OutEdgeIt out) const { 
+// //      return (capacity->get(out)-flow->get(out)); 
+//       return ((*capacity)[out]-(*flow)[out]); 
+//     }
+    
+//     Number enabled(typename Graph::InEdgeIt in) const { 
+// //      return (flow->get(in)); 
+//       return ((*flow)[in]); 
+//     }
+
+    template <typename T>
+    class EdgeMap {
+      typename Graph::template EdgeMap<T> forward_map, backward_map; 
+    public:
+      EdgeMap(const BidirGraphWrapper<Graph>& _G) : forward_map(*(_G.graph)), backward_map(*(_G.graph)) { }
+      EdgeMap(const BidirGraphWrapper<Graph>& _G, T a) : forward_map(*(_G.graph), a), backward_map(*(_G.graph), a) { }
+      void set(Edge e, T a) { 
+        if (!e.backward) 
+          forward_map.set(e.out, a); 
+        else 
+          backward_map.set(e.in, a); 
+      }
+      T operator[](Edge e) const { 
+        if (!e.backward) 
+          return forward_map[e.out]; 
+        else 
+          return backward_map[e.in]; 
+      }
+//       T get(Edge e) const { 
+//      if (e.out_or_in) 
+//        return forward_map.get(e.out); 
+//      else 
+//        return backward_map.get(e.in); 
+//       }
+    };
+  };
+
+
+
+  /// A wrapper for composing the residual graph for directed flow and circulation problems.
+
+  /// A wrapper for composing the residual graph for directed flow and circulation problems.
+  template<typename Graph, typename Number, 
+           typename CapacityMap, typename FlowMap>
+  class ResGraphWrapper : public GraphWrapper<Graph> {
+  protected:
+    const CapacityMap* capacity;
+    FlowMap* flow;
+
+    ResGraphWrapper() : GraphWrapper<Graph>(0), 
+                        capacity(0), flow(0) { }
+    void setCapacityMap(const CapacityMap& _capacity) {
+      capacity=&_capacity;
+    }
+    void setFlowMap(FlowMap& _flow) {
+      flow=&_flow;
+    }
+
+  public:
+
+    ResGraphWrapper(Graph& _graph, const CapacityMap& _capacity, 
+                    FlowMap& _flow) : 
+      GraphWrapper<Graph>(_graph), capacity(&_capacity), flow(&_flow) { }
+
+    class Edge; 
+    class OutEdgeIt; 
+    friend class Edge; 
+    friend class OutEdgeIt; 
+
+    typedef typename GraphWrapper<Graph>::Node Node;
+    typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
+    class Edge : public Graph::Edge {
+      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+    protected:
+      bool backward; //true, iff backward
+//      typename Graph::Edge e;
+    public:
+      Edge() { }
+      Edge(const typename Graph::Edge& _e, bool _backward) : 
+        Graph::Edge(_e), backward(_backward) { }
+      Edge(const Invalid& i) : Graph::Edge(i), backward(true) { }
+//the unique invalid iterator
+      friend bool operator==(const Edge& u, const Edge& v) { 
+        return (v.backward==u.backward && 
+                static_cast<typename Graph::Edge>(u)==
+                static_cast<typename Graph::Edge>(v));
+      } 
+      friend bool operator!=(const Edge& u, const Edge& v) { 
+        return (v.backward!=u.backward || 
+                static_cast<typename Graph::Edge>(u)!=
+                static_cast<typename Graph::Edge>(v));
+      } 
+    };
+
+    class OutEdgeIt {
+      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+    protected:
+      typename Graph::OutEdgeIt out;
+      typename Graph::InEdgeIt in;
+      bool backward;
+    public:
+      OutEdgeIt() { }
+      //FIXME
+//      OutEdgeIt(const Edge& e) : Edge(e) { }
+      OutEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
+//the unique invalid iterator
+      OutEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
+        backward=false;
+        _G.graph->first(out, v);
+        while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
+        if (!_G.graph->valid(out)) {
+          backward=true;
+          _G.graph->first(in, v);
+          while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
+        }
+      }
+      operator Edge() const { 
+//      Edge e;
+//      e.forward=this->forward;
+//      if (this->forward) e=out; else e=in;
+//      return e;
+        if (this->backward) 
+          return Edge(in, this->backward); 
+        else 
+          return Edge(out, this->backward);
+      }
+    };
+
+    class InEdgeIt {
+      friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
+    protected:
+      typename Graph::OutEdgeIt out;
+      typename Graph::InEdgeIt in;
+      bool backward;
+    public:
+      InEdgeIt() { }
+      //FIXME
+//      OutEdgeIt(const Edge& e) : Edge(e) { }
+      InEdgeIt(const Invalid& i) : out(i), in(i), backward(true) { }
+//the unique invalid iterator
+      InEdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G, Node v) { 
+        backward=false;
+        _G.graph->first(in, v);
+        while( _G.graph->valid(in) && !(_G.resCap(*this)>0) ) { _G.graph->next(in); }
+        if (!_G.graph->valid(in)) {
+          backward=true;
+          _G.graph->first(out, v);
+          while( _G.graph->valid(out) && !(_G.resCap(*this)>0) ) { _G.graph->next(out); }
+        }
+      }
+      operator Edge() const { 
+//      Edge e;
+//      e.forward=this->forward;
+//      if (this->forward) e=out; else e=in;
+//      return e;
+        if (this->backward) 
+          return Edge(out, this->backward); 
+        else 
+          return Edge(in, this->backward);
+      }
+    };
+
+    class EdgeIt {
       friend class ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>;
     protected:
@@ -694 +1014 @@
       EdgeIt() { }
       EdgeIt(const Invalid& i) : e(i), backward(true) { }
-      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& resG) { 
+      EdgeIt(const ResGraphWrapper<Graph, Number, CapacityMap, FlowMap>& _G) { 
         backward=false;
-        resG.graph->first(e);
-        while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
-        if (!resG.graph->valid(e)) {
+        _G.graph->first(e);
+        while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
+        if (!_G.graph->valid(e)) {
           backward=true;
-          resG.graph->first(e);
-          while (resG.graph->valid(e) && !(resG.resCap(*this)>0)) resG.graph->next(e);
+          _G.graph->first(e);
+          while (_G.graph->valid(e) && !(_G.resCap(*this)>0)) _G.graph->next(e);
         }
       }
@@ -875 +1195 @@
   };
 
+
+
   /// ErasingFirstGraphWrapper for blocking flows.
 

src/work/marci/iterator_bfs_demo.cc

@@ -315 +315 @@
   }
 
+
+
+  {
+    typedef BidirGraphWrapper<const Graph> GW;
+    GW gw(G);
+    
+    EdgeNameMap< GW, Graph::NodeMap<string> > edge_name(gw, node_name);
+    
+    cout << "bfs and dfs iterator demo on the undirected graph" << endl;
+    for(GW::NodeIt n(gw); gw.valid(n); gw.next(n)) { 
+      cout << node_name[GW::Node(n)] << ": ";
+      cout << "out edges: ";
+      for(GW::OutEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+        cout << edge_name[e] << " ";
+      cout << "in edges: ";
+      for(GW::InEdgeIt e(gw, n); gw.valid(e); gw.next(e)) 
+        cout << edge_name[e] << " ";
+      cout << endl;
+    }
+//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) { 
+//       cout << edge_name.get(e) << " ";
+//     }
+//     cout << endl;
+
+    cout << "bfs from t ..." << endl;
+    BfsIterator< GW, GW::NodeMap<bool> > bfs(gw);
+    bfs.pushAndSetReached(t);
+    while (!bfs.finished()) {
+      //cout << "edge: ";
+      if (gw.valid(GW::OutEdgeIt(bfs))) {
+        cout << edge_name[GW::OutEdgeIt(bfs)] << /*endl*/", " << 
+          node_name[gw.aNode(bfs)] << 
+          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[gw.bNode(bfs)] << 
+          (bfs.isBNodeNewlyReached() ? ": is newly reached." : 
+           ": is not newly reached.");
+      } else { 
+        cout << "invalid" << /*endl*/", " << 
+          node_name[bfs.aNode()] << 
+          (bfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          
+          "invalid.";
+      }
+      cout << endl;
+      ++bfs;
+    }
+
+    cout << "    /-->    ------------->            "<< endl;
+    cout << "   / /-- v1 <-\\      /---- v3-\\      "<< endl;
+    cout << "  / |          |    /  /->     \\     "<< endl;
+    cout << " /  |          |   /  |    ^    \\  "<< endl;
+    cout << "s   |          |  /   |    |     \\->  t "<< endl;
+    cout << " \\  |          | /    |    |     /->  "<< endl;
+    cout << "  \\ |       --/ /     |    |    /     "<< endl;
+    cout << "   \\ \\-> v2 <--/       \\-- v4 -/      "<< endl;
+    cout << "    \\-->    ------------->         "<< endl;
+    
+    cout << "dfs from t ..." << endl;
+    DfsIterator< GW, GW::NodeMap<bool> > dfs(gw);
+    dfs.pushAndSetReached(t);
+    while (!dfs.finished()) {
+      ++dfs;
+      //cout << "edge: ";
+      if (gw.valid(GW::OutEdgeIt(dfs))) {
+        cout << edge_name[GW::OutEdgeIt(dfs)] << /*endl*/", " << 
+          node_name[gw.aNode(dfs)] << 
+          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          node_name[gw.bNode(dfs)] << 
+          (dfs.isBNodeNewlyReached() ? ": is newly reached." : 
+           ": is not newly reached.");
+      } else { 
+        cout << "invalid" << /*endl*/", " << 
+          node_name[dfs.aNode()] << 
+          (dfs.isANodeExamined() ? ": is examined, " : ": is not examined, ") << 
+          
+          "invalid.";
+      }
+      cout << endl;
+    }
+  }
+
+
+
   return 0;
 }