COIN-OR::LEMON - Graph Library

Changeset 992:10d378f2821c in lemon-0.x


Ignore:
Timestamp:
11/15/04 13:25:39 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1382
Message:

GraphWrapper? changes for factory

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r987 r992  
    2828#include <lemon/invalid.h>
    2929#include <lemon/maps.h>
     30#include <lemon/iterable_graph_extender.h>
    3031#include <lemon/map_defines.h>
    3132#include <iostream>
     
    124125  public:
    125126    GraphWrapperBase(Graph& _graph) : graph(&_graph) { }
    126     GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }
     127//     GraphWrapperBase(const GraphWrapperBase<_Graph>& gw) : graph(gw.graph) { }
    127128 
    128129    typedef typename Graph::Node Node;
     
    300301  };
    301302
    302 
     303 
     304  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
     305  class SubGraphWrapperBase : public GraphWrapperBase<_Graph> {
     306  public:
     307    typedef _Graph Graph;
     308    typedef GraphWrapperBase<_Graph> Parent;
     309  protected:
     310    NodeFilterMap* node_filter_map;
     311    EdgeFilterMap* edge_filter_map;
     312    SubGraphWrapperBase() : Parent(),
     313                            node_filter_map(0), edge_filter_map(0) { }
     314
     315    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
     316      node_filter_map=&_node_filter_map;
     317    }
     318    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
     319      edge_filter_map=&_edge_filter_map;
     320    }
     321
     322  public:
     323//     SubGraphWrapperBase(Graph& _graph,
     324//                      NodeFilterMap& _node_filter_map,
     325//                      EdgeFilterMap& _edge_filter_map) :
     326//       Parent(&_graph),
     327//       node_filter_map(&node_filter_map),
     328//       edge_filter_map(&edge_filter_map) { }
     329
     330    typedef typename Parent::Node Node;
     331    typedef typename Parent::Edge Edge;
     332
     333    void first(Node& i) const {
     334      Parent::first(i);
     335      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
     336    }
     337    void first(Edge& i) const {
     338      Parent::first(i);
     339      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
     340    }
     341    void firstIn(Edge& i, const Node& n) const {
     342      Parent::firstIn(i, n);
     343      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
     344    }
     345    void firstOut(Edge& i, const Node& n) const {
     346      Parent::firstOut(i, n);
     347      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
     348    }
     349
     350    void next(Node& i) const {
     351      Parent::next(i);
     352      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);
     353    }
     354    void next(Edge& i) const {
     355      Parent::next(i);
     356      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i);
     357    }
     358    void nextIn(Edge& i) const {
     359      Parent::nextIn(i);
     360      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i);
     361    }
     362    void nextOut(Edge& i) const {
     363      Parent::nextOut(i);
     364      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i);
     365    }
     366
     367    /// This function hides \c n in the graph, i.e. the iteration
     368    /// jumps over it. This is done by simply setting the value of \c n 
     369    /// to be false in the corresponding node-map.
     370    void hide(const Node& n) const { node_filter_map->set(n, false); }
     371
     372    /// This function hides \c e in the graph, i.e. the iteration
     373    /// jumps over it. This is done by simply setting the value of \c e 
     374    /// to be false in the corresponding edge-map.
     375    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
     376
     377    /// The value of \c n is set to be true in the node-map which stores
     378    /// hide information. If \c n was hidden previuosly, then it is shown
     379    /// again
     380     void unHide(const Node& n) const { node_filter_map->set(n, true); }
     381
     382    /// The value of \c e is set to be true in the edge-map which stores
     383    /// hide information. If \c e was hidden previuosly, then it is shown
     384    /// again
     385    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
     386
     387    /// Returns true if \c n is hidden.
     388    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
     389
     390    /// Returns true if \c n is hidden.
     391    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
     392
     393    /// \warning This is a linear time operation and works only if s
     394    /// \c Graph::NodeIt is defined.
     395    /// \todo assign tags.
     396    int nodeNum() const {
     397      int i=0;
     398      Node n;
     399      for (first(n); n!=INVALID; next(n)) ++i;
     400      return i;
     401    }
     402
     403    /// \warning This is a linear time operation and works only if
     404    /// \c Graph::EdgeIt is defined.
     405    /// \todo assign tags.
     406    int edgeNum() const {
     407      int i=0;
     408      Edge e;
     409      for (first(e); e!=INVALID; next(e)) ++i;
     410      return i;
     411    }
     412
     413
     414  };
    303415
    304416  /*! \brief A graph wrapper for hiding nodes and edges from a graph.
     
    348460  \author Marton Makai
    349461  */
    350   template<typename Graph, typename NodeFilterMap,
     462  template<typename _Graph, typename NodeFilterMap,
    351463           typename EdgeFilterMap>
    352   class SubGraphWrapper : public GraphWrapper<Graph> {
    353   public:
    354     typedef GraphWrapper<Graph> Parent;
     464  class SubGraphWrapper :
     465    public IterableGraphExtender<
     466    SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
     467  public:
     468    typedef _Graph Graph;
     469    typedef IterableGraphExtender<
     470      SubGraphWrapperBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
    355471  protected:
    356     NodeFilterMap* node_filter_map;
    357     EdgeFilterMap* edge_filter_map;
    358 
    359     SubGraphWrapper() : GraphWrapper<Graph>(),
    360                         node_filter_map(0), edge_filter_map(0) { }
    361     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
    362       node_filter_map=&_node_filter_map;
    363     }
    364     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
    365       edge_filter_map=&_edge_filter_map;
    366     }
     472    SubGraphWrapper() { }
     473  public:
     474    SubGraphWrapper(_Graph& _graph, NodeFilterMap& _node_filter_map,
     475                    EdgeFilterMap& _edge_filter_map) {
     476      setGraph(_graph);
     477      setNodeFilterMap(_node_filter_map);
     478      setEdgeFilterMap(_edge_filter_map);
     479    }
     480  };
     481
     482//   template<typename Graph, typename NodeFilterMap,
     483//         typename EdgeFilterMap>
     484//   class SubGraphWrapper : public GraphWrapper<Graph> {
     485//   public:
     486//     typedef GraphWrapper<Graph> Parent;
     487//   protected:
     488//     NodeFilterMap* node_filter_map;
     489//     EdgeFilterMap* edge_filter_map;
     490
     491//     SubGraphWrapper() : GraphWrapper<Graph>(),
     492//                      node_filter_map(0), edge_filter_map(0) { }
     493//     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
     494//       node_filter_map=&_node_filter_map;
     495//     }
     496//     void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
     497//       edge_filter_map=&_edge_filter_map;
     498//     }
    367499   
    368   public:
    369     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
    370                     EdgeFilterMap& _edge_filter_map) :
    371       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
    372       edge_filter_map(&_edge_filter_map) { } 
    373 
    374     typedef typename GraphWrapper<Graph>::Node Node;
    375     class NodeIt : public Node {
    376       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    377       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    378     public:
    379       NodeIt() { }
    380       NodeIt(Invalid i) : Node(i) { }
    381       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
    382         Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
    383         while (*static_cast<Node*>(this)!=INVALID &&
    384                !(*(gw->node_filter_map))[*this])
    385           *(static_cast<Node*>(this))=
    386             ++(typename Graph::NodeIt(*(gw->graph), *this));
    387       }
    388       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    389              const Node& n) :
    390         Node(n), gw(&_gw) { }
    391       NodeIt& operator++() {
    392         *(static_cast<Node*>(this))=
    393           ++(typename Graph::NodeIt(*(gw->graph), *this));
    394         while (*static_cast<Node*>(this)!=INVALID &&
    395                !(*(gw->node_filter_map))[*this])
    396           *(static_cast<Node*>(this))=
    397             ++(typename Graph::NodeIt(*(gw->graph), *this));
    398         return *this;
    399       }
    400     };
    401     typedef typename GraphWrapper<Graph>::Edge Edge;
    402     class OutEdgeIt : public Edge {
    403       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    404       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    405     public:
    406       OutEdgeIt() { }
    407       OutEdgeIt(Invalid i) : Edge(i) { }
    408       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
    409         Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
    410         while (*static_cast<Edge*>(this)!=INVALID &&
    411                !(*(gw->edge_filter_map))[*this])
    412           *(static_cast<Edge*>(this))=
    413             ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    414       }
    415       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    416              const Edge& e) :
    417         Edge(e), gw(&_gw) { }
    418       OutEdgeIt& operator++() {
    419         *(static_cast<Edge*>(this))=
    420           ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    421         while (*static_cast<Edge*>(this)!=INVALID &&
    422                !(*(gw->edge_filter_map))[*this])
    423           *(static_cast<Edge*>(this))=
    424             ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    425         return *this;
    426       }
    427     };
    428     class InEdgeIt : public Edge {
    429       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    430       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    431     public:
    432       InEdgeIt() { }
    433       //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
    434       InEdgeIt(Invalid i) : Edge(i) { }
    435       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
    436         Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
    437         while (*static_cast<Edge*>(this)!=INVALID &&
    438                !(*(gw->edge_filter_map))[*this])
    439           *(static_cast<Edge*>(this))=
    440             ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    441       }
    442       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    443              const Edge& e) :
    444         Edge(e), gw(&_gw) { }
    445       InEdgeIt& operator++() {
    446         *(static_cast<Edge*>(this))=
    447           ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    448         while (*static_cast<Edge*>(this)!=INVALID &&
    449                !(*(gw->edge_filter_map))[*this])
    450           *(static_cast<Edge*>(this))=
    451             ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    452         return *this;
    453       }
    454     };
    455     class EdgeIt : public Edge {
    456       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
    457       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
    458     public:
    459       EdgeIt() { }
    460       EdgeIt(Invalid i) : Edge(i) { }
    461       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
    462         Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
    463         while (*static_cast<Edge*>(this)!=INVALID &&
    464                !(*(gw->edge_filter_map))[*this])
    465           *(static_cast<Edge*>(this))=
    466             ++(typename Graph::EdgeIt(*(gw->graph), *this));
    467       }
    468       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
    469              const Edge& e) :
    470         Edge(e), gw(&_gw) { }
    471       EdgeIt& operator++() {
    472         *(static_cast<Edge*>(this))=
    473           ++(typename Graph::EdgeIt(*(gw->graph), *this));
    474         while (*static_cast<Edge*>(this)!=INVALID &&
    475                !(*(gw->edge_filter_map))[*this])
    476           *(static_cast<Edge*>(this))=
    477             ++(typename Graph::EdgeIt(*(gw->graph), *this));
    478         return *this;
    479       }
    480     };
    481 
    482     NodeIt& first(NodeIt& i) const {
    483       i=NodeIt(*this); return i;
    484     }
    485     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    486       i=OutEdgeIt(*this, p); return i;
    487     }
    488     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    489       i=InEdgeIt(*this, p); return i;
    490     }
    491     EdgeIt& first(EdgeIt& i) const {
    492       i=EdgeIt(*this); return i;
    493     }
     500//   public:
     501//     SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
     502//                  EdgeFilterMap& _edge_filter_map) :
     503//       GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
     504//       edge_filter_map(&_edge_filter_map) { } 
     505
     506//     typedef typename GraphWrapper<Graph>::Node Node;
     507//     class NodeIt : public Node {
     508//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     509//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     510//     public:
     511//       NodeIt() { }
     512//       NodeIt(Invalid i) : Node(i) { }
     513//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     514//      Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
     515//      while (*static_cast<Node*>(this)!=INVALID &&
     516//             !(*(gw->node_filter_map))[*this])
     517//        *(static_cast<Node*>(this))=
     518//          ++(typename Graph::NodeIt(*(gw->graph), *this));
     519//       }
     520//       NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     521//           const Node& n) :
     522//      Node(n), gw(&_gw) { }
     523//       NodeIt& operator++() {
     524//      *(static_cast<Node*>(this))=
     525//        ++(typename Graph::NodeIt(*(gw->graph), *this));
     526//      while (*static_cast<Node*>(this)!=INVALID &&
     527//             !(*(gw->node_filter_map))[*this])
     528//        *(static_cast<Node*>(this))=
     529//          ++(typename Graph::NodeIt(*(gw->graph), *this));
     530//      return *this;
     531//       }
     532//     };
     533//     typedef typename GraphWrapper<Graph>::Edge Edge;
     534//     class OutEdgeIt : public Edge {
     535//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     536//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     537//     public:
     538//       OutEdgeIt() { }
     539//       OutEdgeIt(Invalid i) : Edge(i) { }
     540//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     541//      Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
     542//      while (*static_cast<Edge*>(this)!=INVALID &&
     543//             !(*(gw->edge_filter_map))[*this])
     544//        *(static_cast<Edge*>(this))=
     545//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     546//       }
     547//       OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     548//           const Edge& e) :
     549//      Edge(e), gw(&_gw) { }
     550//       OutEdgeIt& operator++() {
     551//      *(static_cast<Edge*>(this))=
     552//        ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     553//      while (*static_cast<Edge*>(this)!=INVALID &&
     554//             !(*(gw->edge_filter_map))[*this])
     555//        *(static_cast<Edge*>(this))=
     556//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     557//      return *this;
     558//       }
     559//     };
     560//     class InEdgeIt : public Edge {
     561//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     562//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     563//     public:
     564//       InEdgeIt() { }
     565//       //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     566//       InEdgeIt(Invalid i) : Edge(i) { }
     567//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     568//      Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
     569//      while (*static_cast<Edge*>(this)!=INVALID &&
     570//             !(*(gw->edge_filter_map))[*this])
     571//        *(static_cast<Edge*>(this))=
     572//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     573//       }
     574//       InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     575//           const Edge& e) :
     576//      Edge(e), gw(&_gw) { }
     577//       InEdgeIt& operator++() {
     578//      *(static_cast<Edge*>(this))=
     579//        ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     580//      while (*static_cast<Edge*>(this)!=INVALID &&
     581//             !(*(gw->edge_filter_map))[*this])
     582//        *(static_cast<Edge*>(this))=
     583//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     584//      return *this;
     585//       }
     586//     };
     587//     class EdgeIt : public Edge {
     588//       const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     589//       friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     590//     public:
     591//       EdgeIt() { }
     592//       EdgeIt(Invalid i) : Edge(i) { }
     593//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     594//      Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
     595//      while (*static_cast<Edge*>(this)!=INVALID &&
     596//             !(*(gw->edge_filter_map))[*this])
     597//        *(static_cast<Edge*>(this))=
     598//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     599//       }
     600//       EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     601//           const Edge& e) :
     602//      Edge(e), gw(&_gw) { }
     603//       EdgeIt& operator++() {
     604//      *(static_cast<Edge*>(this))=
     605//        ++(typename Graph::EdgeIt(*(gw->graph), *this));
     606//      while (*static_cast<Edge*>(this)!=INVALID &&
     607//             !(*(gw->edge_filter_map))[*this])
     608//        *(static_cast<Edge*>(this))=
     609//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     610//      return *this;
     611//       }
     612//     };
     613
     614//     NodeIt& first(NodeIt& i) const {
     615//       i=NodeIt(*this); return i;
     616//     }
     617//     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     618//       i=OutEdgeIt(*this, p); return i;
     619//     }
     620//     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     621//       i=InEdgeIt(*this, p); return i;
     622//     }
     623//     EdgeIt& first(EdgeIt& i) const {
     624//       i=EdgeIt(*this); return i;
     625//     }
    494626   
    495     /// This function hides \c n in the graph, i.e. the iteration
    496     /// jumps over it. This is done by simply setting the value of \c n 
    497     /// to be false in the corresponding node-map.
    498     void hide(const Node& n) const { node_filter_map->set(n, false); }
    499 
    500     /// This function hides \c e in the graph, i.e. the iteration
    501     /// jumps over it. This is done by simply setting the value of \c e 
    502     /// to be false in the corresponding edge-map.
    503     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
    504 
    505     /// The value of \c n is set to be true in the node-map which stores
    506     /// hide information. If \c n was hidden previuosly, then it is shown
    507     /// again
    508      void unHide(const Node& n) const { node_filter_map->set(n, true); }
    509 
    510     /// The value of \c e is set to be true in the edge-map which stores
    511     /// hide information. If \c e was hidden previuosly, then it is shown
    512     /// again
    513     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
    514 
    515     /// Returns true if \c n is hidden.
    516     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
    517 
    518     /// Returns true if \c n is hidden.
    519     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
    520 
    521     /// \warning This is a linear time operation and works only if
    522     /// \c Graph::NodeIt is defined.
    523     int nodeNum() const {
    524       int i=0;
    525       for (NodeIt n(*this); n!=INVALID; ++n) ++i;
    526       return i;
    527     }
    528 
    529     /// \warning This is a linear time operation and works only if
    530     /// \c Graph::EdgeIt is defined.
    531     int edgeNum() const {
    532       int i=0;
    533       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
    534       return i;
    535     }
    536 
    537     //    KEEP_MAPS(Parent, SubGraphWrapper);
    538   };
     627//     /// This function hides \c n in the graph, i.e. the iteration
     628//     /// jumps over it. This is done by simply setting the value of \c n 
     629//     /// to be false in the corresponding node-map.
     630//     void hide(const Node& n) const { node_filter_map->set(n, false); }
     631
     632//     /// This function hides \c e in the graph, i.e. the iteration
     633//     /// jumps over it. This is done by simply setting the value of \c e 
     634//     /// to be false in the corresponding edge-map.
     635//     void hide(const Edge& e) const { edge_filter_map->set(e, false); }
     636
     637//     /// The value of \c n is set to be true in the node-map which stores
     638//     /// hide information. If \c n was hidden previuosly, then it is shown
     639//     /// again
     640//      void unHide(const Node& n) const { node_filter_map->set(n, true); }
     641
     642//     /// The value of \c e is set to be true in the edge-map which stores
     643//     /// hide information. If \c e was hidden previuosly, then it is shown
     644//     /// again
     645//     void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
     646
     647//     /// Returns true if \c n is hidden.
     648//     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
     649
     650//     /// Returns true if \c n is hidden.
     651//     bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
     652
     653//     /// \warning This is a linear time operation and works only if
     654//     /// \c Graph::NodeIt is defined.
     655//     int nodeNum() const {
     656//       int i=0;
     657//       for (NodeIt n(*this); n!=INVALID; ++n) ++i;
     658//       return i;
     659//     }
     660
     661//     /// \warning This is a linear time operation and works only if
     662//     /// \c Graph::EdgeIt is defined.
     663//     int edgeNum() const {
     664//       int i=0;
     665//       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
     666//       return i;
     667//     }
     668
     669//     //    KEEP_MAPS(Parent, SubGraphWrapper);
     670//   };
    539671
    540672
     
    800932  };
    801933
     934 
     935  template <typename _Graph,
     936            typename ForwardFilterMap, typename BackwardFilterMap>
     937  class SubBidirGraphWrapperBase : public GraphWrapperBase<_Graph> {
     938  public:
     939    typedef _Graph Graph;
     940    typedef GraphWrapperBase<_Graph> Parent;
     941  protected:
     942    ForwardFilterMap* forward_filter;
     943    BackwardFilterMap* backward_filter;
     944    SubBidirGraphWrapperBase() : Parent(),
     945                                 forward_filter(0), backward_filter(0) { }
     946
     947    void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
     948      forward_filter=&_forward_filter;
     949    }
     950    void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
     951      backward_filter=&_backward_filter;
     952    }
     953
     954  public:
     955//     SubGraphWrapperBase(Graph& _graph,
     956//                      NodeFilterMap& _node_filter_map,
     957//                      EdgeFilterMap& _edge_filter_map) :
     958//       Parent(&_graph),
     959//       node_filter_map(&node_filter_map),
     960//       edge_filter_map(&edge_filter_map) { }
     961
     962    typedef typename Parent::Node Node;
     963    typedef typename _Graph::Edge GraphEdge;
     964    template <typename T> class EdgeMap;
     965    /// SubBidirGraphWrapperBase<..., ..., ...>::Edge is inherited from
     966    /// _Graph::Edge. It contains an extra bool flag which is true
     967    /// if and only if the
     968    /// edge is the backward version of the original edge.
     969    class Edge : public _Graph::Edge {
     970      friend class SubBidirGraphWrapperBase<
     971        Graph, ForwardFilterMap, BackwardFilterMap>;
     972      template<typename T> friend class EdgeMap;
     973    protected:
     974      bool backward; //true, iff backward
     975    public:
     976      Edge() { }
     977      /// \todo =false is needed, or causes problems?
     978      /// If \c _backward is false, then we get an edge corresponding to the
     979      /// original one, otherwise its oppositely directed pair is obtained.
     980      Edge(const typename _Graph::Edge& e, bool _backward/*=false*/) :
     981        _Graph::Edge(e), backward(_backward) { }
     982      Edge(Invalid i) : _Graph::Edge(i), backward(true) { }
     983      bool operator==(const Edge& v) const {
     984        return (this->backward==v.backward &&
     985                static_cast<typename _Graph::Edge>(*this)==
     986                static_cast<typename _Graph::Edge>(v));
     987      }
     988      bool operator!=(const Edge& v) const {
     989        return (this->backward!=v.backward ||
     990                static_cast<typename _Graph::Edge>(*this)!=
     991                static_cast<typename _Graph::Edge>(v));
     992      }
     993    };
     994
     995    void first(Node& i) const {
     996      Parent::first(i);
     997    }
     998
     999    void first(Edge& i) const {
     1000      Parent::first(i);
     1001      i.backward=false;
     1002      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1003             !(*forward_filter)[i]) Parent::next(i);
     1004      if (*static_cast<GraphEdge*>(&i)==INVALID) {
     1005        Parent::first(i);
     1006        i.backward=true;
     1007        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1008               !(*backward_filter)[i]) Parent::next(i);
     1009      }
     1010    }
     1011
     1012    void firstIn(Edge& i, const Node& n) const {
     1013      Parent::firstIn(i, n);
     1014      i.backward=false;
     1015      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1016             !(*forward_filter)[i]) Parent::nextOut(i);
     1017      if (*static_cast<GraphEdge*>(&i)==INVALID) {
     1018        Parent::firstOut(i, n);
     1019        i.backward=true;
     1020        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1021               !(*backward_filter)[i]) Parent::nextOut(i);
     1022      }
     1023    }
     1024
     1025    void firstOut(Edge& i, const Node& n) const {
     1026      Parent::firstOut(i, n);
     1027      i.backward=false;
     1028      while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1029             !(*forward_filter)[i]) Parent::nextOut(i);
     1030      if (*static_cast<GraphEdge*>(&i)==INVALID) {
     1031        Parent::firstIn(i, n);
     1032        i.backward=true;
     1033        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1034               !(*backward_filter)[i]) Parent::nextIn(i);
     1035      }
     1036    }
     1037
     1038    void next(Node& i) const {
     1039      Parent::next(i);
     1040    }
     1041
     1042    void next(Edge& i) const {
     1043      if (!(i.backward)) {
     1044        Parent::next(i);
     1045        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1046               !(*forward_filter)[i]) Parent::next(i);
     1047        if (*static_cast<GraphEdge*>(&i)==INVALID) {
     1048          Parent::first(i);
     1049          i.backward=true;
     1050          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1051                 !(*backward_filter)[i]) Parent::next(i);
     1052        }
     1053      } else {
     1054        Parent::next(i);
     1055        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1056               !(*backward_filter)[i]) Parent::next(i);
     1057      }
     1058    }
     1059
     1060    void nextIn(Edge& i) const {
     1061      if (!(i.backward)) {
     1062        Node n=Parent::target(i);
     1063        Parent::nextIn(i);
     1064        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1065               !(*forward_filter)[i]) Parent::nextIn(i);
     1066        if (*static_cast<GraphEdge*>(&i)==INVALID) {
     1067          Parent::firstOut(i, n);
     1068          i.backward=true;
     1069          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1070                 !(*backward_filter)[i]) Parent::nextOut(i);
     1071        }
     1072      } else {
     1073        Parent::nextOut(i);
     1074        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1075               !(*backward_filter)[i]) Parent::nextOut(i);
     1076      }
     1077    }
     1078
     1079    void nextOut(Edge& i) const {
     1080      if (!(i.backward)) {
     1081        Node n=Parent::source(i);
     1082        Parent::nextOut(i);
     1083        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1084               !(*forward_filter)[i]) Parent::nextOut(i);
     1085        if (*static_cast<GraphEdge*>(&i)==INVALID) {
     1086          Parent::firstIn(i, n);
     1087          i.backward=true;
     1088          while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1089                 !(*backward_filter)[i]) Parent::nextIn(i);
     1090        }
     1091      } else {
     1092        Parent::nextIn(i);
     1093        while (*static_cast<GraphEdge*>(&i)!=INVALID &&
     1094               !(*backward_filter)[i]) Parent::nextIn(i);
     1095      }
     1096    }
     1097
     1098    Node source(Edge e) const {
     1099      return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
     1100    Node target(Edge e) const {
     1101      return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
     1102
     1103    /// Gives back the opposite edge.
     1104    Edge opposite(const Edge& e) const {
     1105      Edge f=e;
     1106      f.backward=!f.backward;
     1107      return f;
     1108    }
     1109
     1110    /// \warning This is a linear time operation and works only if
     1111    /// \c Graph::EdgeIt is defined.
     1112    /// \todo hmm
     1113    int edgeNum() const {
     1114      int i=0;
     1115      Edge e;
     1116      for (first(e); e!=INVALID; next(e)) ++i;
     1117      return i;
     1118    }
     1119
     1120    bool forward(const Edge& e) const { return !e.backward; }
     1121    bool backward(const Edge& e) const { return e.backward; }
     1122
     1123    template <typename T>
     1124    /// \c SubBidirGraphWrapperBase<..., ..., ...>::EdgeMap contains two
     1125    /// _Graph::EdgeMap one for the forward edges and
     1126    /// one for the backward edges.
     1127    class EdgeMap {
     1128      template <typename TT> friend class EdgeMap;
     1129      typename _Graph::template EdgeMap<T> forward_map, backward_map;
     1130    public:
     1131      typedef T Value;
     1132      typedef Edge Key;
     1133
     1134      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
     1135              ForwardFilterMap, BackwardFilterMap>& g) :
     1136        forward_map(*(g.graph)), backward_map(*(g.graph)) { }
     1137
     1138      EdgeMap(const SubBidirGraphWrapperBase<_Graph,
     1139              ForwardFilterMap, BackwardFilterMap>& g, T a) :
     1140        forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
     1141
     1142//       template <typename TT>
     1143//       EdgeMap(const EdgeMap<TT>& copy)
     1144//      : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
     1145
     1146//       template <typename TT>
     1147//       EdgeMap& operator=(const EdgeMap<TT>& copy) {
     1148//      forward_map = copy.forward_map;
     1149//      backward_map = copy.backward_map;
     1150//      return *this;
     1151//       }
     1152     
     1153      void set(Edge e, T a) {
     1154        if (!e.backward)
     1155          forward_map.set(e, a);
     1156        else
     1157          backward_map.set(e, a);
     1158      }
     1159
     1160//       typename _Graph::template EdgeMap<T>::ConstReference
     1161//       operator[](Edge e) const {
     1162//      if (!e.backward)
     1163//        return forward_map[e];
     1164//      else
     1165//        return backward_map[e];
     1166//       }
     1167
     1168//      typename _Graph::template EdgeMap<T>::Reference
     1169      T operator[](Edge e) {
     1170        if (!e.backward)
     1171          return forward_map[e];
     1172        else
     1173          return backward_map[e];
     1174      }
     1175
     1176      void update() {
     1177        forward_map.update();
     1178        backward_map.update();
     1179      }
     1180    };
     1181
     1182  };
    8021183
    8031184
     
    8391220  /// above mentioned graph structure without its physical storage,
    8401221  /// that is the whole stuff is stored in constant memory.
    841   template<typename Graph,
     1222  template<typename _Graph,
    8421223           typename ForwardFilterMap, typename BackwardFilterMap>
    843   class SubBidirGraphWrapper : public GraphWrapper<Graph> {
    844   public:
    845     typedef GraphWrapper<Graph> Parent;
     1224  class SubBidirGraphWrapper :
     1225    public IterableGraphExtender<
     1226    SubBidirGraphWrapperBase<_Graph, ForwardFilterMap, BackwardFilterMap> > {
     1227  public:
     1228    typedef _Graph Graph;
     1229    typedef IterableGraphExtender<
     1230      SubBidirGraphWrapperBase<
     1231      _Graph, ForwardFilterMap, BackwardFilterMap> > Parent;
    8461232  protected:
    847     ForwardFilterMap* forward_filter;
    848     BackwardFilterMap* backward_filter;
    849 
    850     SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
    851     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
    852       forward_filter=&_forward_filter;
    853     }
    854     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
    855       backward_filter=&_backward_filter;
    856     }
    857 
    858   public:
    859 
    860     SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
    861                          BackwardFilterMap& _backward_filter) :
    862       GraphWrapper<Graph>(_graph),
    863       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
    864     SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
    865                          ForwardFilterMap, BackwardFilterMap>& gw) :
    866       Parent(gw),
    867       forward_filter(gw.forward_filter),
    868       backward_filter(gw.backward_filter) { }
    869 
    870     class Edge;
    871     class OutEdgeIt;
    872     friend class Edge;
    873     friend class OutEdgeIt;
    874 
    875     template<typename T> class EdgeMap;
    876 
    877     typedef typename GraphWrapper<Graph>::Node Node;
    878 
    879     typedef typename Graph::Edge GraphEdge;
    880     /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
    881     /// Graph::Edge. It contains an extra bool flag which is true
    882     /// if and only if the
    883     /// edge is the backward version of the original edge.
    884     class Edge : public Graph::Edge {
    885       friend class SubBidirGraphWrapper<Graph,
    886                                         ForwardFilterMap, BackwardFilterMap>;
    887       template<typename T> friend class EdgeMap;
    888     protected:
    889       bool backward; //true, iff backward
    890     public:
    891       Edge() { }
    892       /// \todo =false is needed, or causes problems?
    893       /// If \c _backward is false, then we get an edge corresponding to the
    894       /// original one, otherwise its oppositely directed pair is obtained.
    895       Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
    896         Graph::Edge(e), backward(_backward) { }
    897       Edge(Invalid i) : Graph::Edge(i), backward(true) { }
    898       bool operator==(const Edge& v) const {
    899         return (this->backward==v.backward &&
    900                 static_cast<typename Graph::Edge>(*this)==
    901                 static_cast<typename Graph::Edge>(v));
    902       }
    903       bool operator!=(const Edge& v) const {
    904         return (this->backward!=v.backward ||
    905                 static_cast<typename Graph::Edge>(*this)!=
    906                 static_cast<typename Graph::Edge>(v));
    907       }
    908     };
    909 
    910     class OutEdgeIt : public Edge {
    911       friend class SubBidirGraphWrapper<Graph,
    912                                         ForwardFilterMap, BackwardFilterMap>;
    913     protected:
    914       const SubBidirGraphWrapper<Graph,
    915                                  ForwardFilterMap, BackwardFilterMap>* gw;
    916     public:
    917       OutEdgeIt() { }
    918       OutEdgeIt(Invalid i) : Edge(i) { }
    919       OutEdgeIt(const SubBidirGraphWrapper<Graph,
    920                 ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
    921         Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
    922         while (*static_cast<GraphEdge*>(this)!=INVALID &&
    923                !(*(gw->forward_filter))[*this])
    924           *(static_cast<GraphEdge*>(this))=
    925             ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    926         if (*static_cast<GraphEdge*>(this)==INVALID) {
    927           *static_cast<Edge*>(this)=
    928             Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
    929           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    930                  !(*(gw->backward_filter))[*this])
    931             *(static_cast<GraphEdge*>(this))=
    932               ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    933         }
    934       }
    935       OutEdgeIt(const SubBidirGraphWrapper<Graph,
    936                 ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
    937         Edge(e), gw(&_gw) { }
    938       OutEdgeIt& operator++() {
    939         if (!this->backward) {
    940           Node n=gw->source(*this);
    941           *(static_cast<GraphEdge*>(this))=
    942             ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    943           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    944                  !(*(gw->forward_filter))[*this])
    945             *(static_cast<GraphEdge*>(this))=
    946               ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    947           if (*static_cast<GraphEdge*>(this)==INVALID) {
    948             *static_cast<Edge*>(this)=
    949               Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
    950             while (*static_cast<GraphEdge*>(this)!=INVALID &&
    951                    !(*(gw->backward_filter))[*this])
    952               *(static_cast<GraphEdge*>(this))=
    953                 ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    954           }
    955         } else {
    956           *(static_cast<GraphEdge*>(this))=
    957             ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    958           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    959                  !(*(gw->backward_filter))[*this])
    960             *(static_cast<GraphEdge*>(this))=
    961               ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    962         }
    963         return *this;
    964       }
    965     };
    966 
    967     class InEdgeIt : public Edge {
    968       friend class SubBidirGraphWrapper<Graph,
    969                                         ForwardFilterMap, BackwardFilterMap>;
    970     protected:
    971       const SubBidirGraphWrapper<Graph,
    972                                  ForwardFilterMap, BackwardFilterMap>* gw;
    973     public:
    974       InEdgeIt() { }
    975       InEdgeIt(Invalid i) : Edge(i) { }
    976       InEdgeIt(const SubBidirGraphWrapper<Graph,
    977                ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
    978         Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
    979         while (*static_cast<GraphEdge*>(this)!=INVALID &&
    980                !(*(gw->forward_filter))[*this])
    981           *(static_cast<GraphEdge*>(this))=
    982             ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    983         if (*static_cast<GraphEdge*>(this)==INVALID) {
    984           *static_cast<Edge*>(this)=
    985             Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
    986           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    987                  !(*(gw->backward_filter))[*this])
    988             *(static_cast<GraphEdge*>(this))=
    989               ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    990         }
    991       }
    992       InEdgeIt(const SubBidirGraphWrapper<Graph,
    993                ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
    994         Edge(e), gw(&_gw) { }
    995       InEdgeIt& operator++() {
    996         if (!this->backward) {
    997           Node n=gw->source(*this);
    998           *(static_cast<GraphEdge*>(this))=
    999             ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    1000           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1001                  !(*(gw->forward_filter))[*this])
    1002             *(static_cast<GraphEdge*>(this))=
    1003               ++(typename Graph::InEdgeIt(*(gw->graph), *this));
    1004           if (*static_cast<GraphEdge*>(this)==INVALID) {
    1005             *static_cast<Edge*>(this)=
    1006               Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
    1007             while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1008                    !(*(gw->backward_filter))[*this])
    1009               *(static_cast<GraphEdge*>(this))=
    1010                 ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    1011           }
    1012         } else {
    1013           *(static_cast<GraphEdge*>(this))=
    1014             ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    1015           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1016                  !(*(gw->backward_filter))[*this])
    1017             *(static_cast<GraphEdge*>(this))=
    1018               ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
    1019         }
    1020         return *this;
    1021       }
    1022     };
    1023 
    1024     class EdgeIt : public Edge {
    1025       friend class SubBidirGraphWrapper<Graph,
    1026                                         ForwardFilterMap, BackwardFilterMap>;
    1027     protected:
    1028       const SubBidirGraphWrapper<Graph,
    1029                                  ForwardFilterMap, BackwardFilterMap>* gw;
    1030     public:
    1031       EdgeIt() { }
    1032       EdgeIt(Invalid i) : Edge(i) { }
    1033       EdgeIt(const SubBidirGraphWrapper<Graph,
    1034              ForwardFilterMap, BackwardFilterMap>& _gw) :
    1035         Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
    1036         while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1037                !(*(gw->forward_filter))[*this])
    1038           *(static_cast<GraphEdge*>(this))=
    1039             ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1040         if (*static_cast<GraphEdge*>(this)==INVALID) {
    1041           *static_cast<Edge*>(this)=
    1042             Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
    1043           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1044                  !(*(gw->backward_filter))[*this])
    1045             *(static_cast<GraphEdge*>(this))=
    1046               ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1047         }
    1048       }
    1049       EdgeIt(const SubBidirGraphWrapper<Graph,
    1050              ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
    1051         Edge(e), gw(&_gw) { }
    1052       EdgeIt& operator++() {
    1053         if (!this->backward) {
    1054           *(static_cast<GraphEdge*>(this))=
    1055             ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1056           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1057                  !(*(gw->forward_filter))[*this])
    1058             *(static_cast<GraphEdge*>(this))=
    1059               ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1060           if (*static_cast<GraphEdge*>(this)==INVALID) {
    1061             *static_cast<Edge*>(this)=
    1062               Edge(typename Graph::EdgeIt(*(gw->graph)), true);
    1063             while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1064                    !(*(gw->backward_filter))[*this])
    1065               *(static_cast<GraphEdge*>(this))=
    1066                 ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1067           }
    1068         } else {
    1069           *(static_cast<GraphEdge*>(this))=
    1070             ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1071           while (*static_cast<GraphEdge*>(this)!=INVALID &&
    1072                  !(*(gw->backward_filter))[*this])
    1073             *(static_cast<GraphEdge*>(this))=
    1074               ++(typename Graph::EdgeIt(*(gw->graph), *this));
    1075         }
    1076         return *this;
    1077       }
    1078     };
    1079 
    1080 //     using GraphWrapper<Graph>::first;
    1081 //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    1082 //       i=OutEdgeIt(*this, p); return i;
     1233    SubBidirGraphWrapper() { }
     1234  public:
     1235    SubBidirGraphWrapper(_Graph& _graph, ForwardFilterMap& _forward_filter,
     1236                         BackwardFilterMap& _backward_filter) {
     1237      setGraph(_graph);
     1238      setForwardFilterMap(_forward_filter);
     1239      setBackwardFilterMap(_backward_filter);
     1240    }
     1241  };
     1242
     1243//   template<typename Graph,
     1244//         typename ForwardFilterMap, typename BackwardFilterMap>
     1245//   class SubBidirGraphWrapper : public GraphWrapper<Graph> {
     1246//   public:
     1247//     typedef GraphWrapper<Graph> Parent;
     1248//   protected:
     1249//     ForwardFilterMap* forward_filter;
     1250//     BackwardFilterMap* backward_filter;
     1251
     1252//     SubBidirGraphWrapper() : GraphWrapper<Graph>() { }
     1253//     void setForwardFilterMap(ForwardFilterMap& _forward_filter) {
     1254//       forward_filter=&_forward_filter;
    10831255//     }
    1084 //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
    1085 //       i=InEdgeIt(*this, p); return i;
     1256//     void setBackwardFilterMap(BackwardFilterMap& _backward_filter) {
     1257//       backward_filter=&_backward_filter;
    10861258//     }
    1087 //     EdgeIt& first(EdgeIt& i) const {
    1088 //       i=EdgeIt(*this); return i;
     1259
     1260//   public:
     1261
     1262//     SubBidirGraphWrapper(Graph& _graph, ForwardFilterMap& _forward_filter,
     1263//                       BackwardFilterMap& _backward_filter) :
     1264//       GraphWrapper<Graph>(_graph),
     1265//       forward_filter(&_forward_filter), backward_filter(&_backward_filter) { }
     1266//     SubBidirGraphWrapper(const SubBidirGraphWrapper<Graph,
     1267//                       ForwardFilterMap, BackwardFilterMap>& gw) :
     1268//       Parent(gw),
     1269//       forward_filter(gw.forward_filter),
     1270//       backward_filter(gw.backward_filter) { }
     1271
     1272//     class Edge;
     1273//     class OutEdgeIt;
     1274//     friend class Edge;
     1275//     friend class OutEdgeIt;
     1276
     1277//     template<typename T> class EdgeMap;
     1278
     1279//     typedef typename GraphWrapper<Graph>::Node Node;
     1280
     1281//     typedef typename Graph::Edge GraphEdge;
     1282//     /// SubBidirGraphWrapper<..., ..., ...>::Edge is inherited from
     1283//     /// Graph::Edge. It contains an extra bool flag which is true
     1284//     /// if and only if the
     1285//     /// edge is the backward version of the original edge.
     1286//     class Edge : public Graph::Edge {
     1287//       friend class SubBidirGraphWrapper<Graph,
     1288//                                      ForwardFilterMap, BackwardFilterMap>;
     1289//       template<typename T> friend class EdgeMap;
     1290//     protected:
     1291//       bool backward; //true, iff backward
     1292//     public:
     1293//       Edge() { }
     1294//       /// \todo =false is needed, or causes problems?
     1295//       /// If \c _backward is false, then we get an edge corresponding to the
     1296//       /// original one, otherwise its oppositely directed pair is obtained.
     1297//       Edge(const typename Graph::Edge& e, bool _backward/*=false*/) :
     1298//      Graph::Edge(e), backward(_backward) { }
     1299//       Edge(Invalid i) : Graph::Edge(i), backward(true) { }
     1300//       bool operator==(const Edge& v) const {
     1301//      return (this->backward==v.backward &&
     1302//              static_cast<typename Graph::Edge>(*this)==
     1303//              static_cast<typename Graph::Edge>(v));
     1304//       }
     1305//       bool operator!=(const Edge& v) const {
     1306//      return (this->backward!=v.backward ||
     1307//              static_cast<typename Graph::Edge>(*this)!=
     1308//              static_cast<typename Graph::Edge>(v));
     1309//       }
     1310//     };
     1311
     1312//     class OutEdgeIt : public Edge {
     1313//       friend class SubBidirGraphWrapper<Graph,
     1314//                                      ForwardFilterMap, BackwardFilterMap>;
     1315//     protected:
     1316//       const SubBidirGraphWrapper<Graph,
     1317//                               ForwardFilterMap, BackwardFilterMap>* gw;
     1318//     public:
     1319//       OutEdgeIt() { }
     1320//       OutEdgeIt(Invalid i) : Edge(i) { }
     1321//       OutEdgeIt(const SubBidirGraphWrapper<Graph,
     1322//              ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     1323//      Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
     1324//      while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1325//             !(*(gw->forward_filter))[*this])
     1326//        *(static_cast<GraphEdge*>(this))=
     1327//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1328//      if (*static_cast<GraphEdge*>(this)==INVALID) {
     1329//        *static_cast<Edge*>(this)=
     1330//          Edge(typename Graph::InEdgeIt(*(_gw.graph), n), true);
     1331//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1332//               !(*(gw->backward_filter))[*this])
     1333//          *(static_cast<GraphEdge*>(this))=
     1334//            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1335//      }
     1336//       }
     1337//       OutEdgeIt(const SubBidirGraphWrapper<Graph,
     1338//              ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     1339//      Edge(e), gw(&_gw) { }
     1340//       OutEdgeIt& operator++() {
     1341//      if (!this->backward) {
     1342//        Node n=gw->source(*this);
     1343//        *(static_cast<GraphEdge*>(this))=
     1344//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1345//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1346//               !(*(gw->forward_filter))[*this])
     1347//          *(static_cast<GraphEdge*>(this))=
     1348//            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1349//        if (*static_cast<GraphEdge*>(this)==INVALID) {
     1350//          *static_cast<Edge*>(this)=
     1351//            Edge(typename Graph::InEdgeIt(*(gw->graph), n), true);
     1352//          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1353//                 !(*(gw->backward_filter))[*this])
     1354//            *(static_cast<GraphEdge*>(this))=
     1355//              ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1356//        }
     1357//      } else {
     1358//        *(static_cast<GraphEdge*>(this))=
     1359//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1360//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1361//               !(*(gw->backward_filter))[*this])
     1362//          *(static_cast<GraphEdge*>(this))=
     1363//            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1364//      }
     1365//      return *this;
     1366//       }
     1367//     };
     1368
     1369//     class InEdgeIt : public Edge {
     1370//       friend class SubBidirGraphWrapper<Graph,
     1371//                                      ForwardFilterMap, BackwardFilterMap>;
     1372//     protected:
     1373//       const SubBidirGraphWrapper<Graph,
     1374//                               ForwardFilterMap, BackwardFilterMap>* gw;
     1375//     public:
     1376//       InEdgeIt() { }
     1377//       InEdgeIt(Invalid i) : Edge(i) { }
     1378//       InEdgeIt(const SubBidirGraphWrapper<Graph,
     1379//             ForwardFilterMap, BackwardFilterMap>& _gw, const Node& n) :
     1380//      Edge(typename Graph::InEdgeIt(*(_gw.graph), n), false), gw(&_gw) {
     1381//      while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1382//             !(*(gw->forward_filter))[*this])
     1383//        *(static_cast<GraphEdge*>(this))=
     1384//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1385//      if (*static_cast<GraphEdge*>(this)==INVALID) {
     1386//        *static_cast<Edge*>(this)=
     1387//          Edge(typename Graph::OutEdgeIt(*(_gw.graph), n), true);
     1388//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1389//               !(*(gw->backward_filter))[*this])
     1390//          *(static_cast<GraphEdge*>(this))=
     1391//            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1392//      }
     1393//       }
     1394//       InEdgeIt(const SubBidirGraphWrapper<Graph,
     1395//             ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     1396//      Edge(e), gw(&_gw) { }
     1397//       InEdgeIt& operator++() {
     1398//      if (!this->backward) {
     1399//        Node n=gw->source(*this);
     1400//        *(static_cast<GraphEdge*>(this))=
     1401//          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1402//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1403//               !(*(gw->forward_filter))[*this])
     1404//          *(static_cast<GraphEdge*>(this))=
     1405//            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     1406//        if (*static_cast<GraphEdge*>(this)==INVALID) {
     1407//          *static_cast<Edge*>(this)=
     1408//            Edge(typename Graph::OutEdgeIt(*(gw->graph), n), true);
     1409//          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1410//                 !(*(gw->backward_filter))[*this])
     1411//            *(static_cast<GraphEdge*>(this))=
     1412//              ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1413//        }
     1414//      } else {
     1415//        *(static_cast<GraphEdge*>(this))=
     1416//          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1417//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1418//               !(*(gw->backward_filter))[*this])
     1419//          *(static_cast<GraphEdge*>(this))=
     1420//            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     1421//      }
     1422//      return *this;
     1423//       }
     1424//     };
     1425
     1426//     class EdgeIt : public Edge {
     1427//       friend class SubBidirGraphWrapper<Graph,
     1428//                                      ForwardFilterMap, BackwardFilterMap>;
     1429//     protected:
     1430//       const SubBidirGraphWrapper<Graph,
     1431//                               ForwardFilterMap, BackwardFilterMap>* gw;
     1432//     public:
     1433//       EdgeIt() { }
     1434//       EdgeIt(Invalid i) : Edge(i) { }
     1435//       EdgeIt(const SubBidirGraphWrapper<Graph,
     1436//           ForwardFilterMap, BackwardFilterMap>& _gw) :
     1437//      Edge(typename Graph::EdgeIt(*(_gw.graph)), false), gw(&_gw) {
     1438//      while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1439//             !(*(gw->forward_filter))[*this])
     1440//        *(static_cast<GraphEdge*>(this))=
     1441//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1442//      if (*static_cast<GraphEdge*>(this)==INVALID) {
     1443//        *static_cast<Edge*>(this)=
     1444//          Edge(typename Graph::EdgeIt(*(_gw.graph)), true);
     1445//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1446//               !(*(gw->backward_filter))[*this])
     1447//          *(static_cast<GraphEdge*>(this))=
     1448//            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1449//      }
     1450//       }
     1451//       EdgeIt(const SubBidirGraphWrapper<Graph,
     1452//           ForwardFilterMap, BackwardFilterMap>& _gw, const Edge& e) :
     1453//      Edge(e), gw(&_gw) { }
     1454//       EdgeIt& operator++() {
     1455//      if (!this->backward) {
     1456//        *(static_cast<GraphEdge*>(this))=
     1457//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1458//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1459//               !(*(gw->forward_filter))[*this])
     1460//          *(static_cast<GraphEdge*>(this))=
     1461//            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1462//        if (*static_cast<GraphEdge*>(this)==INVALID) {
     1463//          *static_cast<Edge*>(this)=
     1464//            Edge(typename Graph::EdgeIt(*(gw->graph)), true);
     1465//          while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1466//                 !(*(gw->backward_filter))[*this])
     1467//            *(static_cast<GraphEdge*>(this))=
     1468//              ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1469//        }
     1470//      } else {
     1471//        *(static_cast<GraphEdge*>(this))=
     1472//          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1473//        while (*static_cast<GraphEdge*>(this)!=INVALID &&
     1474//               !(*(gw->backward_filter))[*this])
     1475//          *(static_cast<GraphEdge*>(this))=
     1476//            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     1477//      }
     1478//      return *this;
     1479//       }
     1480//     };
     1481
     1482// //     using GraphWrapper<Graph>::first;
     1483// //     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     1484// //       i=OutEdgeIt(*this, p); return i;
     1485// //     }
     1486// //     InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     1487// //       i=InEdgeIt(*this, p); return i;
     1488// //     }
     1489// //     EdgeIt& first(EdgeIt& i) const {
     1490// //       i=EdgeIt(*this); return i;
     1491// //     }
     1492 
     1493
     1494//     Node source(Edge e) const {
     1495//       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
     1496//     Node target(Edge e) const {
     1497//       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
     1498
     1499//     /// Gives back the opposite edge.
     1500//     Edge opposite(const Edge& e) const {
     1501//       Edge f=e;
     1502//       f.backward=!f.backward;
     1503//       return f;
    10891504//     }
    1090  
    1091 
    1092     Node source(Edge e) const {
    1093       return ((!e.backward) ? this->graph->source(e) : this->graph->target(e)); }
    1094     Node target(Edge e) const {
    1095       return ((!e.backward) ? this->graph->target(e) : this->graph->source(e)); }
    1096 
    1097     /// Gives back the opposite edge.
    1098     Edge opposite(const Edge& e) const {
    1099       Edge f=e;
    1100       f.backward=!f.backward;
    1101       return f;
    1102     }
    1103 
    1104     /// \warning This is a linear time operation and works only if
    1105     /// \c Graph::EdgeIt is defined.
    1106     int edgeNum() const {
    1107       int i=0;
    1108       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
    1109       return i;
    1110     }
    1111 
    1112     bool forward(const Edge& e) const { return !e.backward; }
    1113     bool backward(const Edge& e) const { return e.backward; }
    1114 
    1115 
    1116     template <typename T>
    1117     /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
    1118     /// Graph::EdgeMap one for the forward edges and
    1119     /// one for the backward edges.
    1120     class EdgeMap {
    1121       template <typename TT> friend class EdgeMap;
    1122       typename Graph::template EdgeMap<T> forward_map, backward_map;
    1123     public:
    1124       typedef T Value;
    1125       typedef Edge Key;
    1126 
    1127       EdgeMap(const SubBidirGraphWrapper<Graph,
    1128               ForwardFilterMap, BackwardFilterMap>& g) :
    1129         forward_map(*(g.graph)), backward_map(*(g.graph)) { }
    1130 
    1131       EdgeMap(const SubBidirGraphWrapper<Graph,
    1132               ForwardFilterMap, BackwardFilterMap>& g, T a) :
    1133         forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
    1134 
    1135       template <typename TT>
    1136       EdgeMap(const EdgeMap<TT>& copy)
    1137         : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
    1138 
    1139       template <typename TT>
    1140       EdgeMap& operator=(const EdgeMap<TT>& copy) {
    1141         forward_map = copy.forward_map;
    1142         backward_map = copy.backward_map;
    1143         return *this;
    1144       }
     1505
     1506//     /// \warning This is a linear time operation and works only if
     1507//     /// \c Graph::EdgeIt is defined.
     1508//     int edgeNum() const {
     1509//       int i=0;
     1510//       for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
     1511//       return i;
     1512//     }
     1513
     1514//     bool forward(const Edge& e) const { return !e.backward; }
     1515//     bool backward(const Edge& e) const { return e.backward; }
     1516
     1517
     1518//     template <typename T>
     1519//     /// \c SubBidirGraphWrapper<..., ..., ...>::EdgeMap contains two
     1520//     /// Graph::EdgeMap one for the forward edges and
     1521//     /// one for the backward edges.
     1522//     class EdgeMap {
     1523//       template <typename TT> friend class EdgeMap;
     1524//       typename Graph::template EdgeMap<T> forward_map, backward_map;
     1525//     public:
     1526//       typedef T Value;
     1527//       typedef Edge Key;
     1528
     1529//       EdgeMap(const SubBidirGraphWrapper<Graph,
     1530//            ForwardFilterMap, BackwardFilterMap>& g) :
     1531//      forward_map(*(g.graph)), backward_map(*(g.graph)) { }
     1532
     1533//       EdgeMap(const SubBidirGraphWrapper<Graph,
     1534//            ForwardFilterMap, BackwardFilterMap>& g, T a) :
     1535//      forward_map(*(g.graph), a), backward_map(*(g.graph), a) { }
     1536
     1537//       template <typename TT>
     1538//       EdgeMap(const EdgeMap<TT>& copy)
     1539//      : forward_map(copy.forward_map), backward_map(copy.backward_map) {}
     1540
     1541//       template <typename TT>
     1542//       EdgeMap& operator=(const EdgeMap<TT>& copy) {
     1543//      forward_map = copy.forward_map;
     1544//      backward_map = copy.backward_map;
     1545//      return *this;
     1546//       }
    11451547     
    1146       void set(Edge e, T a) {
    1147         if (!e.backward)
    1148           forward_map.set(e, a);
    1149         else
    1150           backward_map.set(e, a);
    1151       }
    1152 
    1153       typename Graph::template EdgeMap<T>::ConstReference
    1154       operator[](Edge e) const {
    1155         if (!e.backward)
    1156           return forward_map[e];
    1157         else
    1158           return backward_map[e];
    1159       }
    1160 
    1161       typename Graph::template EdgeMap<T>::Reference
    1162       operator[](Edge e) {
    1163         if (!e.backward)
    1164           return forward_map[e];
    1165         else
    1166           return backward_map[e];
    1167       }
    1168 
    1169       void update() {
    1170         forward_map.update();
    1171         backward_map.update();
    1172       }
    1173     };
    1174 
    1175 
    1176     //    KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
    1177 
    1178   };
     1548//       void set(Edge e, T a) {
     1549//      if (!e.backward)
     1550//        forward_map.set(e, a);
     1551//      else
     1552//        backward_map.set(e, a);
     1553//       }
     1554
     1555//       typename Graph::template EdgeMap<T>::ConstReference
     1556//       operator[](Edge e) const {
     1557//      if (!e.backward)
     1558//        return forward_map[e];
     1559//      else
     1560//        return backward_map[e];
     1561//       }
     1562
     1563//       typename Graph::template EdgeMap<T>::Reference
     1564//       operator[](Edge e) {
     1565//      if (!e.backward)
     1566//        return forward_map[e];
     1567//      else
     1568//        return backward_map[e];
     1569//       }
     1570
     1571//       void update() {
     1572//      forward_map.update();
     1573//      backward_map.update();
     1574//       }
     1575//     };
     1576
     1577
     1578//     //    KEEP_NODE_MAP(Parent, SubBidirGraphWrapper);
     1579
     1580//   };
    11791581
    11801582
  • src/test/graph_wrapper_test.cc

    r989 r992  
    4747//     function_requires<StaticGraphConcept<RevGraphWrapper<Graph> > >();
    4848
    49 //     function_requires<StaticGraphConcept<SubGraphWrapper<Graph, Graph::NodeMap<bool> , Graph::EdgeMap<bool> > > >();
    50 //     function_requires<StaticGraphConcept<NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > > >();
    51 //     function_requires<StaticGraphConcept<EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > > >();
     49    checkConcept<StaticGraph, SubGraphWrapper<StaticGraph,
     50      StaticGraph::NodeMap<bool> , StaticGraph::EdgeMap<bool> > >();
     51    checkConcept<StaticGraph, NodeSubGraphWrapper<StaticGraph,
     52      StaticGraph::NodeMap<bool> > >();
     53    checkConcept<StaticGraph, EdgeSubGraphWrapper<StaticGraph,
     54      StaticGraph::EdgeMap<bool> > >();
     55   
     56    checkConcept<StaticGraph, SubBidirGraphWrapper<StaticGraph,
     57      StaticGraph::EdgeMap<bool>, StaticGraph::EdgeMap<bool> > >();
    5258
    53 //     function_requires<StaticGraphConcept<SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > > > ();
     59    checkConcept<StaticGraph, BidirGraph<StaticGraph> >();
    5460
    55 //     function_requires<StaticGraphConcept<BidirGraph<Graph> > >();
    56 
    57 //     function_requires<StaticGraphConcept<ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > > >();
     61    checkConcept<StaticGraph, ResGraphWrapper<StaticGraph, int,
     62      StaticGraph::EdgeMap<int>, StaticGraph::EdgeMap<int> > >();
    5863
    5964//     function_requires<StaticGraphConcept<ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > > >();
Note: See TracChangeset for help on using the changeset viewer.