COIN-OR::LEMON - Graph Library

Changeset 933:1b7c88fbb950 in lemon-0.x


Ignore:
Timestamp:
10/01/04 13:31:03 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1258
Message:

NodeSubGraphWrapper?, test, and ducumentation modifications.

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r932 r933  
    369369  \c Graph::Node that is why \c g.id(n) can be applied.
    370370
    371   Consider now a mathematically more invloved problem, where the application
    372   of SubGraphWrapper is reasonable sure enough. If a shortest path is to be
     371  For other examples see also the documentation of NodeSubGraphWrapper and
     372  EdgeSubGraphWrapper.
     373
     374  \author Marton Makai
     375  */
     376  template<typename Graph, typename NodeFilterMap,
     377           typename EdgeFilterMap>
     378  class SubGraphWrapper : public GraphWrapper<Graph> {
     379  public:
     380    typedef GraphWrapper<Graph> Parent;
     381  protected:
     382    NodeFilterMap* node_filter_map;
     383    EdgeFilterMap* edge_filter_map;
     384
     385    SubGraphWrapper() : GraphWrapper<Graph>(),
     386                        node_filter_map(0), edge_filter_map(0) { }
     387    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
     388      node_filter_map=&_node_filter_map;
     389    }
     390    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
     391      edge_filter_map=&_edge_filter_map;
     392    }
     393   
     394  public:
     395    SubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map,
     396                    EdgeFilterMap& _edge_filter_map) :
     397      GraphWrapper<Graph>(_graph), node_filter_map(&_node_filter_map),
     398      edge_filter_map(&_edge_filter_map) { } 
     399
     400    typedef typename GraphWrapper<Graph>::Node Node;
     401    class NodeIt : public Node {
     402      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     403      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     404    public:
     405      NodeIt() { }
     406      NodeIt(Invalid i) : Node(i) { }
     407      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     408        Node(typename Graph::NodeIt(*(_gw.graph))), gw(&_gw) {
     409        while (*static_cast<Node*>(this)!=INVALID &&
     410               !(*(gw->node_filter_map))[*this])
     411          *(static_cast<Node*>(this))=
     412            ++(typename Graph::NodeIt(*(gw->graph), *this));
     413      }
     414      NodeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     415             const Node& n) :
     416        Node(n), gw(&_gw) { }
     417      NodeIt& operator++() {
     418        *(static_cast<Node*>(this))=
     419          ++(typename Graph::NodeIt(*(gw->graph), *this));
     420        while (*static_cast<Node*>(this)!=INVALID &&
     421               !(*(gw->node_filter_map))[*this])
     422          *(static_cast<Node*>(this))=
     423            ++(typename Graph::NodeIt(*(gw->graph), *this));
     424        return *this;
     425      }
     426    };
     427    typedef typename GraphWrapper<Graph>::Edge Edge;
     428    class OutEdgeIt : public Edge {
     429      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     430      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     431    public:
     432      OutEdgeIt() { }
     433      OutEdgeIt(Invalid i) : Edge(i) { }
     434      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     435        Edge(typename Graph::OutEdgeIt(*(_gw.graph), n)), gw(&_gw) {
     436        while (*static_cast<Edge*>(this)!=INVALID &&
     437               !(*(gw->edge_filter_map))[*this])
     438          *(static_cast<Edge*>(this))=
     439            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     440      }
     441      OutEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     442             const Edge& e) :
     443        Edge(e), gw(&_gw) { }
     444      OutEdgeIt& operator++() {
     445        *(static_cast<Edge*>(this))=
     446          ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     447        while (*static_cast<Edge*>(this)!=INVALID &&
     448               !(*(gw->edge_filter_map))[*this])
     449          *(static_cast<Edge*>(this))=
     450            ++(typename Graph::OutEdgeIt(*(gw->graph), *this));
     451        return *this;
     452      }
     453    };
     454    class InEdgeIt : public Edge {
     455      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     456      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     457    public:
     458      InEdgeIt() { }
     459      //      InEdgeIt(const InEdgeIt& e) : Edge(e), gw(e.gw) { }
     460      InEdgeIt(Invalid i) : Edge(i) { }
     461      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw, const Node& n) :
     462        Edge(typename Graph::InEdgeIt(*(_gw.graph), n)), gw(&_gw) {
     463        while (*static_cast<Edge*>(this)!=INVALID &&
     464               !(*(gw->edge_filter_map))[*this])
     465          *(static_cast<Edge*>(this))=
     466            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     467      }
     468      InEdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     469             const Edge& e) :
     470        Edge(e), gw(&_gw) { }
     471      InEdgeIt& operator++() {
     472        *(static_cast<Edge*>(this))=
     473          ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     474        while (*static_cast<Edge*>(this)!=INVALID &&
     475               !(*(gw->edge_filter_map))[*this])
     476          *(static_cast<Edge*>(this))=
     477            ++(typename Graph::InEdgeIt(*(gw->graph), *this));
     478        return *this;
     479      }
     480    };
     481    class EdgeIt : public Edge {
     482      const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>* gw;
     483      friend class SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>;
     484    public:
     485      EdgeIt() { }
     486      EdgeIt(Invalid i) : Edge(i) { }
     487      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw) :
     488        Edge(typename Graph::EdgeIt(*(_gw.graph))), gw(&_gw) {
     489        while (*static_cast<Edge*>(this)!=INVALID &&
     490               !(*(gw->edge_filter_map))[*this])
     491          *(static_cast<Edge*>(this))=
     492            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     493      }
     494      EdgeIt(const SubGraphWrapper<Graph, NodeFilterMap, EdgeFilterMap>& _gw,
     495             const Edge& e) :
     496        Edge(e), gw(&_gw) { }
     497      EdgeIt& operator++() {
     498        *(static_cast<Edge*>(this))=
     499          ++(typename Graph::EdgeIt(*(gw->graph), *this));
     500        while (*static_cast<Edge*>(this)!=INVALID &&
     501               !(*(gw->edge_filter_map))[*this])
     502          *(static_cast<Edge*>(this))=
     503            ++(typename Graph::EdgeIt(*(gw->graph), *this));
     504        return *this;
     505      }
     506    };
     507
     508    NodeIt& first(NodeIt& i) const {
     509      i=NodeIt(*this); return i;
     510    }
     511    OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
     512      i=OutEdgeIt(*this, p); return i;
     513    }
     514    InEdgeIt& first(InEdgeIt& i, const Node& p) const {
     515      i=InEdgeIt(*this, p); return i;
     516    }
     517    EdgeIt& first(EdgeIt& i) const {
     518      i=EdgeIt(*this); return i;
     519    }
     520   
     521    /// This function hides \c n in the graph, i.e. the iteration
     522    /// jumps over it. This is done by simply setting the value of \c n 
     523    /// to be false in the corresponding node-map.
     524    void hide(const Node& n) const { node_filter_map->set(n, false); }
     525
     526    /// This function hides \c e in the graph, i.e. the iteration
     527    /// jumps over it. This is done by simply setting the value of \c e 
     528    /// to be false in the corresponding edge-map.
     529    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
     530
     531    /// The value of \c n is set to be true in the node-map which stores
     532    /// hide information. If \c n was hidden previuosly, then it is shown
     533    /// again
     534     void unHide(const Node& n) const { node_filter_map->set(n, true); }
     535
     536    /// The value of \c e is set to be true in the edge-map which stores
     537    /// hide information. If \c e was hidden previuosly, then it is shown
     538    /// again
     539    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
     540
     541    /// Returns true if \c n is hidden.
     542    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
     543
     544    /// Returns true if \c n is hidden.
     545    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
     546
     547    /// \warning This is a linear time operation and works only if
     548    /// \c Graph::NodeIt is defined.
     549    int nodeNum() const {
     550      int i=0;
     551      for (NodeIt n(*this); n!=INVALID; ++n) ++i;
     552      return i;
     553    }
     554
     555    /// \warning This is a linear time operation and works only if
     556    /// \c Graph::EdgeIt is defined.
     557    int edgeNum() const {
     558      int i=0;
     559      for (EdgeIt e(*this); e!=INVALID; ++e) ++i;
     560      return i;
     561    }
     562
     563    //    KEEP_MAPS(Parent, SubGraphWrapper);
     564  };
     565
     566
     567  /*! \brief A wrapper for hiding nodes from a graph.
     568
     569  \warning Graph wrappers are in even more experimental state than the other
     570  parts of the lib. Use them at you own risk.
     571 
     572  A wrapper for hiding nodes from a graph.
     573  This wrapper specializes SubGraphWrapper in the way that only the node-set
     574  can be filtered. Note that this does not mean of considering induced
     575  subgraph, the edge-iterators consider the original edge-set.
     576  \author Marton Makai
     577  */
     578  template<typename Graph, typename NodeFilterMap>
     579  class NodeSubGraphWrapper :
     580    public SubGraphWrapper<Graph, NodeFilterMap,
     581                           ConstMap<typename Graph::Edge,bool> > {
     582  public:
     583    typedef SubGraphWrapper<Graph, NodeFilterMap,
     584                            ConstMap<typename Graph::Edge,bool> > Parent;
     585  protected:
     586    ConstMap<typename Graph::Edge, bool> const_true_map;
     587  public:
     588    NodeSubGraphWrapper(Graph& _graph, NodeFilterMap& _node_filter_map) :
     589      Parent(), const_true_map(true) {
     590      Parent::setGraph(_graph);
     591      Parent::setNodeFilterMap(_node_filter_map);
     592      Parent::setEdgeFilterMap(const_true_map);
     593    }
     594  };
     595
     596
     597  /*! \brief A wrapper for hiding edges from a graph.
     598
     599  \warning Graph wrappers are in even more experimental state than the other
     600  parts of the lib. Use them at you own risk.
     601 
     602  A wrapper for hiding edges from a graph.
     603  This wrapper specializes SubGraphWrapper in the way that only the edge-set
     604  can be filtered. The usefulness of this wrapper is demonstrated in the
     605  problem of searching a maximum number of edge-disjoint shortest paths
     606  between
     607  two nodes \c s and \c t. Shortest here means being shortest w.r.t.
     608  non-negative edge-lengths. Note that
     609  the comprehension of the presented solution
     610  need's some knowledge from elementary combinatorial optimization.
     611
     612  If a single shortest path is to be
    373613  searched between two nodes \c s and \c t, then this can be done easily by
    374614  applying the Dijkstra algorithm class. What happens, if a maximum number of
     
    377617  the potential function computed by Dijkstra. Moreover, any path containing
    378618  only such edges is a shortest one. Thus we have to compute a maximum number
    379   of edge-disjoint path between \c s and \c t in the graph which has edge-set
     619  of edge-disjoint paths between \c s and \c t in the graph which has edge-set
    380620  all the tight edges. The computation will be demonstrated on the following
    381621  graph, which is read from a dimacs file.
     
    478718   1, 0--2->2
    479719  \endcode
    480   \author Marton Makai
    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     }
    499    
    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     }
    626    
    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   };
    671 
    672 
    673   /*! \brief A wrapper for hiding edges from a graph.
    674 
    675   \warning Graph wrappers are in even more experimental state than the other
    676   parts of the lib. Use them at you own risk.
    677  
    678   A wrapper for hiding edges from a graph.
    679   This wrapper specializes SubGraphWrapper in the way that only the edge-set
    680   can be filtered.
     720
    681721  \author Marton Makai
    682722  */
  • src/test/graph_wrapper_test.cc

    r921 r933  
    5050template void checkCompileStaticGraph<SubGW>(SubGW &);
    5151
     52//Compile NodeSubGraphWrapper
     53typedef NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > NodeSubGW;
     54template void checkCompileStaticGraph<NodeSubGW>(NodeSubGW &);
     55
     56//Compile EdgeSubGraphWrapper
     57typedef EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > EdgeSubGW;
     58template void checkCompileStaticGraph<EdgeSubGW>(EdgeSubGW &);
     59
    5260//Compile UndirGraphWrapper
    5361/// \bug UndirGraphWrapper cannot pass the StaticGraph test
Note: See TracChangeset for help on using the changeset viewer.