COIN-OR::LEMON - Graph Library

Changeset 431:4b6112235fad in lemon


Ignore:
Timestamp:
11/30/08 19:00:30 (15 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Improvements in graph adaptors (#67)

Remove DigraphAdaptor? and GraphAdaptor?
Remove docs of base classes
Move the member documentations to real adaptors
Minor improvements in documentation

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/digraph_adaptor.h

    r430 r431  
    2424///\brief Several digraph adaptors.
    2525///
    26 ///This file contains several useful digraph adaptor functions.
     26///This file contains several useful digraph adaptor classes.
    2727
    2828#include <lemon/core.h>
     
    3939namespace lemon {
    4040
    41   ///\brief Base type for the Digraph Adaptors
    42   ///
    43   ///Base type for the Digraph Adaptors
    44   ///
    45   ///This is the base type for most of LEMON digraph adaptors. This
    46   ///class implements a trivial digraph adaptor i.e. it only wraps the
    47   ///functions and types of the digraph. The purpose of this class is
    48   ///to make easier implementing digraph adaptors. E.g. if an adaptor
    49   ///is considered which differs from the wrapped digraph only in some
    50   ///of its functions or types, then it can be derived from
    51   ///DigraphAdaptor, and only the differences should be implemented.
    5241  template<typename _Digraph>
    5342  class DigraphAdaptorBase {
     
    167156  };
    168157
    169   ///\ingroup graph_adaptors
    170   ///
    171   ///\brief Trivial Digraph Adaptor
    172   ///
    173   /// This class is an adaptor which does not change the adapted
    174   /// digraph.  It can be used only to test the digraph adaptors.
    175   template <typename _Digraph>
    176   class DigraphAdaptor :
    177     public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > {
    178   public:
    179     typedef _Digraph Digraph;
    180     typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;
    181   protected:
    182     DigraphAdaptor() : Parent() { }
    183 
    184   public:
    185     explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }
    186   };
    187 
    188   /// \brief Just gives back a digraph adaptor
    189   ///
    190   /// Just gives back a digraph adaptor which
    191   /// should be provide original digraph
    192   template<typename Digraph>
    193   DigraphAdaptor<const Digraph>
    194   digraphAdaptor(const Digraph& digraph) {
    195     return DigraphAdaptor<const Digraph>(digraph);
    196   }
    197 
    198158
    199159  template <typename _Digraph>
     
    232192  /// If \c g is defined as
    233193  ///\code
    234   /// ListDigraph g;
     194  /// ListDigraph dg;
    235195  ///\endcode
    236196  /// then
    237197  ///\code
    238   /// RevDigraphAdaptor<ListDigraph> ga(g);
     198  /// RevDigraphAdaptor<ListDigraph> dga(dg);
    239199  ///\endcode
    240   /// implements the digraph obtained from \c g by
     200  /// implements the digraph obtained from \c dg by
    241201  /// reversing the orientation of its arcs.
    242202  ///
    243   /// A good example of using RevDigraphAdaptor is to decide that the
    244   /// directed graph is wheter strongly connected or not. If from one
    245   /// node each node is reachable and from each node is reachable this
    246   /// node then and just then the digraph is strongly
    247   /// connected. Instead of this condition we use a little bit
    248   /// different. From one node each node ahould be reachable in the
    249   /// digraph and in the reversed digraph. Now this condition can be
    250   /// checked with the Dfs algorithm class and the RevDigraphAdaptor
    251   /// algorithm class.
    252   ///
    253   /// And look at the code:
    254   ///
     203  /// A good example of using RevDigraphAdaptor is to decide whether
     204  /// the directed graph is strongly connected or not. The digraph is
     205  /// strongly connected iff each node is reachable from one node and
     206  /// this node is reachable from the others. Instead of this
     207  /// condition we use a slightly different, from one node each node
     208  /// is reachable both in the digraph and the reversed digraph. Now
     209  /// this condition can be checked with the Dfs algorithm and the
     210  /// RevDigraphAdaptor class.
     211  ///
     212  /// The implementation:
    255213  ///\code
    256214  /// bool stronglyConnected(const Digraph& digraph) {
     
    285243    RevDigraphAdaptor() { }
    286244  public:
     245
     246    /// \brief Constructor
     247    ///
     248    /// Creates a reverse graph adaptor for the given digraph
    287249    explicit RevDigraphAdaptor(Digraph& digraph) {
    288250      Parent::setDigraph(digraph);
     
    375337    }
    376338
    377     ///\e
    378 
    379     /// This function hides \c n in the digraph, i.e. the iteration
    380     /// jumps over it. This is done by simply setting the value of \c n 
    381     /// to be false in the corresponding node-map.
    382339    void hide(const Node& n) const { _node_filter->set(n, false); }
    383 
    384     ///\e
    385 
    386     /// This function hides \c a in the digraph, i.e. the iteration
    387     /// jumps over it. This is done by simply setting the value of \c a
    388     /// to be false in the corresponding arc-map.
    389340    void hide(const Arc& a) const { _arc_filter->set(a, false); }
    390341
    391     ///\e
    392 
    393     /// The value of \c n is set to be true in the node-map which stores
    394     /// hide information. If \c n was hidden previuosly, then it is shown
    395     /// again
    396      void unHide(const Node& n) const { _node_filter->set(n, true); }
    397 
    398     ///\e
    399 
    400     /// The value of \c a is set to be true in the arc-map which stores
    401     /// hide information. If \c a was hidden previuosly, then it is shown
    402     /// again
     342    void unHide(const Node& n) const { _node_filter->set(n, true); }
    403343    void unHide(const Arc& a) const { _arc_filter->set(a, true); }
    404344
    405     /// Returns true if \c n is hidden.
    406    
    407     ///\e
    408     ///
    409345    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
    410 
    411     /// Returns true if \c a is hidden.
    412    
    413     ///\e
    414     ///
    415346    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }
    416347
     
    549480    }
    550481
    551     ///\e
    552 
    553     /// This function hides \c n in the digraph, i.e. the iteration
    554     /// jumps over it. This is done by simply setting the value of \c n 
    555     /// to be false in the corresponding node-map.
    556482    void hide(const Node& n) const { _node_filter->set(n, false); }
    557 
    558     ///\e
    559 
    560     /// This function hides \c e in the digraph, i.e. the iteration
    561     /// jumps over it. This is done by simply setting the value of \c e 
    562     /// to be false in the corresponding arc-map.
    563483    void hide(const Arc& e) const { _arc_filter->set(e, false); }
    564484
    565     ///\e
    566 
    567     /// The value of \c n is set to be true in the node-map which stores
    568     /// hide information. If \c n was hidden previuosly, then it is shown
    569     /// again
    570      void unHide(const Node& n) const { _node_filter->set(n, true); }
    571 
    572     ///\e
    573 
    574     /// The value of \c e is set to be true in the arc-map which stores
    575     /// hide information. If \c e was hidden previuosly, then it is shown
    576     /// again
     485    void unHide(const Node& n) const { _node_filter->set(n, true); }
    577486    void unHide(const Arc& e) const { _arc_filter->set(e, true); }
    578487
    579     /// Returns true if \c n is hidden.
    580    
    581     ///\e
    582     ///
    583488    bool hidden(const Node& n) const { return !(*_node_filter)[n]; }
    584 
    585     /// Returns true if \c n is hidden.
    586    
    587     ///\e
    588     ///
    589489    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }
    590490
     
    662562  ///
    663563  /// SubDigraphAdaptor shows the digraph with filtered node-set and
    664   /// arc-set. If the \c checked parameter is true then it filters the arcset
    665   /// to do not get invalid arcs without source or target.
    666   /// Let \f$ G=(V, A) \f$ be a directed digraph
    667   /// and suppose that the digraph instance \c g of type ListDigraph
    668   /// implements \f$ G \f$.
    669   /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.
    670   /// on the node-set and arc-set.
    671   /// SubDigraphAdaptor<...>::NodeIt iterates
    672   /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and
    673   /// SubDigraphAdaptor<...>::ArcIt iterates
    674   /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly,
    675   /// SubDigraphAdaptor<...>::OutArcIt and
    676   /// SubDigraphAdaptor<...>::InArcIt iterates
    677   /// only on arcs leaving and entering a specific node which have true value.
     564  /// arc-set. If the \c checked parameter is true then it filters the arc-set
     565  /// respect to the source and target.
    678566  ///
    679   /// If the \c checked template parameter is false then we have to
    680   /// note that the node-iterator cares only the filter on the
    681   /// node-set, and the arc-iterator cares only the filter on the
    682   /// arc-set.  This way the arc-map should filter all arcs which's
    683   /// source or target is filtered by the node-filter.
     567  /// If the \c checked template parameter is false then the
     568  /// node-iterator cares only the filter on the node-set, and the
     569  /// arc-iterator cares only the filter on the arc-set.  Therefore
     570  /// the arc-map have to filter all arcs which's source or target is
     571  /// filtered by the node-filter.
    684572  ///\code
    685573  /// typedef ListDigraph Digraph;
     
    694582  /// BoolArcMap am(g, true);
    695583  /// am.set(a, false);
    696   /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;
    697   /// SubGA ga(g, nm, am);
    698   /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)
     584  /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubDGA;
     585  /// SubDGA ga(g, nm, am);
     586  /// for (SubDGA::NodeIt n(ga); n!=INVALID; ++n)
    699587  ///   std::cout << g.id(n) << std::endl;
    700   /// std::cout << ":-)" << std::endl;
    701   /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a)
     588  /// for (SubDGA::ArcIt a(ga); a!=INVALID; ++a)
    702589  ///   std::cout << g.id(a) << std::endl;
    703590  ///\endcode
     
    705592  ///\code
    706593  /// 1
    707   /// :-)
    708594  /// 1
    709595  ///\endcode
    710   /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to
     596  /// Note that \c n is of type \c SubDGA::NodeIt, but it can be converted to
    711597  /// \c Digraph::Node that is why \c g.id(n) can be applied.
    712598  ///
     
    729615    Parent;
    730616
     617    typedef typename Parent::Node Node;
     618    typedef typename Parent::Arc Arc;
     619
    731620  protected:
    732621    SubDigraphAdaptor() { }
    733622  public:
    734623
     624    /// \brief Constructor
     625    ///
     626    /// Creates a sub-digraph-adaptor for the given digraph with
     627    /// given node and arc map filters.
    735628    SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter,
    736629                      ArcFilterMap& arc_filter) {
     
    740633    }
    741634
     635    /// \brief Hides the node of the graph
     636    ///
     637    /// This function hides \c n in the digraph, i.e. the iteration
     638    /// jumps over it. This is done by simply setting the value of \c n 
     639    /// to be false in the corresponding node-map.
     640    void hide(const Node& n) const { Parent::hide(n); }
     641
     642    /// \brief Hides the arc of the graph
     643    ///
     644    /// This function hides \c a in the digraph, i.e. the iteration
     645    /// jumps over it. This is done by simply setting the value of \c a
     646    /// to be false in the corresponding arc-map.
     647    void hide(const Arc& a) const { Parent::hide(a); }
     648
     649    /// \brief Unhides the node of the graph
     650    ///
     651    /// The value of \c n is set to be true in the node-map which stores
     652    /// hide information. If \c n was hidden previuosly, then it is shown
     653    /// again
     654    void unHide(const Node& n) const { Parent::unHide(n); }
     655
     656    /// \brief Unhides the arc of the graph
     657    ///
     658    /// The value of \c a is set to be true in the arc-map which stores
     659    /// hide information. If \c a was hidden previuosly, then it is shown
     660    /// again
     661    void unHide(const Arc& a) const { Parent::unHide(a); }
     662
     663    /// \brief Returns true if \c n is hidden.
     664    ///
     665    /// Returns true if \c n is hidden.
     666    ///
     667    bool hidden(const Node& n) const { return Parent::hidden(n); }
     668
     669    /// \brief Returns true if \c a is hidden.
     670    ///
     671    /// Returns true if \c a is hidden.
     672    ///
     673    bool hidden(const Arc& a) const { return Parent::hidden(a); }
     674
    742675  };
    743676
    744   /// \brief Just gives back a sub digraph adaptor
    745   ///
    746   /// Just gives back a sub digraph adaptor
     677  /// \brief Just gives back a sub-digraph-adaptor
     678  ///
     679  /// Just gives back a sub-digraph-adaptor
    747680  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>
    748681  SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>
     
    775708    return SubDigraphAdaptor<const Digraph, const NodeFilterMap,
    776709      const ArcFilterMap>(digraph, nfm, afm);
     710
    777711  }
    778712
     
    803737    Parent;
    804738
     739    typedef typename Parent::Node Node;
     740
    805741  protected:
    806742    ConstMap<typename Digraph::Arc, bool> const_true_map;
     
    812748  public:
    813749
     750    /// \brief Constructor
     751    ///
     752    /// Creates a node-sub-digraph-adaptor for the given digraph with
     753    /// given node map filter.
    814754    NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) :
    815755      Parent(), const_true_map(true) {
     
    819759    }
    820760
     761    /// \brief Hides the node of the graph
     762    ///
     763    /// This function hides \c n in the digraph, i.e. the iteration
     764    /// jumps over it. This is done by simply setting the value of \c n 
     765    /// to be false in the corresponding node-map.
     766    void hide(const Node& n) const { Parent::hide(n); }
     767
     768    /// \brief Unhides the node of the graph
     769    ///
     770    /// The value of \c n is set to be true in the node-map which stores
     771    /// hide information. If \c n was hidden previuosly, then it is shown
     772    /// again
     773    void unHide(const Node& n) const { Parent::unHide(n); }
     774
     775    /// \brief Returns true if \c n is hidden.
     776    ///
     777    /// Returns true if \c n is hidden.
     778    ///
     779    bool hidden(const Node& n) const { return Parent::hidden(n); }
     780
    821781  };
    822782
    823783
    824   /// \brief Just gives back a \c NodeSubDigraphAdaptor
    825   ///
    826   /// Just gives back a \c NodeSubDigraphAdaptor
     784  /// \brief Just gives back a  node-sub-digraph adaptor
     785  ///
     786  /// Just gives back a node-sub-digraph adaptor
    827787  template<typename Digraph, typename NodeFilterMap>
    828788  NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>
     
    847807  ///in the problem of searching a maximum number of arc-disjoint
    848808  ///shortest paths between two nodes \c s and \c t. Shortest here
    849   ///means being shortest w.r.t.  non-negative arc-lengths. Note that
    850   ///the comprehension of the presented solution need's some
    851   ///elementary knowlarc from combinatorial optimization.
     809  ///means being shortest with respect to non-negative
     810  ///arc-lengths. Note that the comprehension of the presented
     811  ///solution need's some elementary knowledge from combinatorial
     812  ///optimization.
    852813  ///
    853814  ///If a single shortest path is to be searched between \c s and \c
     
    869830  ///
    870831  ///\dot
    871   ///didigraph lemon_dot_example {
     832  ///digraph lemon_dot_example {
    872833  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];
    873834  ///n0 [ label="0 (s)" ];
     
    975936    typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>,
    976937                              ArcFilterMap, false> Parent;
     938
     939    typedef typename Parent::Arc Arc;
     940
    977941  protected:
    978942    ConstMap<typename Digraph::Node, bool> const_true_map;
     
    984948  public:
    985949
     950    /// \brief Constructor
     951    ///
     952    /// Creates a arc-sub-digraph-adaptor for the given digraph with
     953    /// given arc map filter.
    986954    ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter)
    987955      : Parent(), const_true_map(true) {
     
    991959    }
    992960
     961    /// \brief Hides the arc of the graph
     962    ///
     963    /// This function hides \c a in the digraph, i.e. the iteration
     964    /// jumps over it. This is done by simply setting the value of \c a
     965    /// to be false in the corresponding arc-map.
     966    void hide(const Arc& a) const { Parent::hide(a); }
     967
     968    /// \brief Unhides the arc of the graph
     969    ///
     970    /// The value of \c a is set to be true in the arc-map which stores
     971    /// hide information. If \c a was hidden previuosly, then it is shown
     972    /// again
     973    void unHide(const Arc& a) const { Parent::unHide(a); }
     974
     975    /// \brief Returns true if \c a is hidden.
     976    ///
     977    /// Returns true if \c a is hidden.
     978    ///
     979    bool hidden(const Arc& a) const { return Parent::hidden(a); }
     980
    993981  };
    994982
    995   /// \brief Just gives back an arc sub digraph adaptor
    996   ///
    997   /// Just gives back an arc sub digraph adaptor
     983  /// \brief Just gives back an arc-sub-digraph adaptor
     984  ///
     985  /// Just gives back an arc-sub-digraph adaptor
    998986  template<typename Digraph, typename ArcFilterMap>
    999987  ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>
     
    13941382  ///\ingroup graph_adaptors
    13951383  ///
    1396   /// \brief An graph is made from a directed digraph by an adaptor
     1384  /// \brief A graph is made from a directed digraph by an adaptor
    13971385  ///
    13981386  /// This adaptor makes an undirected graph from a directed
    1399   /// digraph. All arc of the underlying will be showed in the adaptor
    1400   /// as an edge. Let's see an informal example about using
    1401   /// this adaptor:
     1387  /// graph. All arc of the underlying digraph will be showed in the
     1388  /// adaptor as an edge. Let's see an informal example about using
     1389  /// this adaptor.
    14021390  ///
    14031391  /// There is a network of the streets of a town. Of course there are
     
    18031791  };
    18041792
    1805   /// \brief Base class for split digraph adaptor
    1806   ///
    1807   /// Base class of split digraph adaptor. In most case you do not need to
    1808   /// use it directly but the documented member functions of this class can
    1809   /// be used with the SplitDigraphAdaptor class.
    1810   /// \sa SplitDigraphAdaptor
    18111793  template <typename _Digraph>
    18121794  class SplitDigraphAdaptorBase {
     
    20232005    }
    20242006
    2025     /// \brief Returns true when the node is in-node.
    2026     ///
    2027     /// Returns true when the node is in-node.
    20282007    static bool inNode(const Node& n) {
    20292008      return n._in;
    20302009    }
    20312010
    2032     /// \brief Returns true when the node is out-node.
    2033     ///
    2034     /// Returns true when the node is out-node.
    20352011    static bool outNode(const Node& n) {
    20362012      return !n._in;
    20372013    }
    20382014
    2039     /// \brief Returns true when the arc is arc in the original digraph.
    2040     ///
    2041     /// Returns true when the arc is arc in the original digraph.
    20422015    static bool origArc(const Arc& e) {
    20432016      return e._item.firstState();
    20442017    }
    20452018
    2046     /// \brief Returns true when the arc binds an in-node and an out-node.
    2047     ///
    2048     /// Returns true when the arc binds an in-node and an out-node.
    20492019    static bool bindArc(const Arc& e) {
    20502020      return e._item.secondState();
    20512021    }
    20522022
    2053     /// \brief Gives back the in-node created from the \c node.
    2054     ///
    2055     /// Gives back the in-node created from the \c node.
    20562023    static Node inNode(const DigraphNode& n) {
    20572024      return Node(n, true);
    20582025    }
    20592026
    2060     /// \brief Gives back the out-node created from the \c node.
    2061     ///
    2062     /// Gives back the out-node created from the \c node.
    20632027    static Node outNode(const DigraphNode& n) {
    20642028      return Node(n, false);
    20652029    }
    20662030
    2067     /// \brief Gives back the arc binds the two part of the node.
    2068     ///
    2069     /// Gives back the arc binds the two part of the node.
    20702031    static Arc arc(const DigraphNode& n) {
    20712032      return Arc(n);
    20722033    }
    20732034
    2074     /// \brief Gives back the arc of the original arc.
    2075     ///
    2076     /// Gives back the arc of the original arc.
    20772035    static Arc arc(const DigraphArc& e) {
    20782036      return Arc(e);
     
    22762234  /// bind arc in the adapted digraph.
    22772235  ///
    2278   /// By example a maximum flow algoritm can compute how many arc
     2236  /// For example a maximum flow algorithm can compute how many arc
    22792237  /// disjoint paths are in the digraph. But we would like to know how
    22802238  /// many node disjoint paths are in the digraph. First we have to
     
    23312289    typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;
    23322290
     2291    typedef typename Digraph::Node DigraphNode;
     2292    typedef typename Digraph::Arc DigraphArc;
     2293
    23332294    typedef typename Parent::Node Node;
    23342295    typedef typename Parent::Arc Arc;
     
    23392300    SplitDigraphAdaptor(Digraph& g) {
    23402301      Parent::setDigraph(g);
     2302    }
     2303
     2304    /// \brief Returns true when the node is in-node.
     2305    ///
     2306    /// Returns true when the node is in-node.
     2307    static bool inNode(const Node& n) {
     2308      return Parent::inNode(n);
     2309    }
     2310
     2311    /// \brief Returns true when the node is out-node.
     2312    ///
     2313    /// Returns true when the node is out-node.
     2314    static bool outNode(const Node& n) {
     2315      return Parent::outNode(n);
     2316    }
     2317
     2318    /// \brief Returns true when the arc is arc in the original digraph.
     2319    ///
     2320    /// Returns true when the arc is arc in the original digraph.
     2321    static bool origArc(const Arc& a) {
     2322      return Parent::origArc(a);
     2323    }
     2324
     2325    /// \brief Returns true when the arc binds an in-node and an out-node.
     2326    ///
     2327    /// Returns true when the arc binds an in-node and an out-node.
     2328    static bool bindArc(const Arc& a) {
     2329      return Parent::bindArc(a);
     2330    }
     2331
     2332    /// \brief Gives back the in-node created from the \c node.
     2333    ///
     2334    /// Gives back the in-node created from the \c node.
     2335    static Node inNode(const DigraphNode& n) {
     2336      return Parent::inNode(n);
     2337    }
     2338
     2339    /// \brief Gives back the out-node created from the \c node.
     2340    ///
     2341    /// Gives back the out-node created from the \c node.
     2342    static Node outNode(const DigraphNode& n) {
     2343      return Parent::outNode(n);
     2344    }
     2345
     2346    /// \brief Gives back the arc binds the two part of the node.
     2347    ///
     2348    /// Gives back the arc binds the two part of the node.
     2349    static Arc arc(const DigraphNode& n) {
     2350      return Parent::arc(n);
     2351    }
     2352
     2353    /// \brief Gives back the arc of the original arc.
     2354    ///
     2355    /// Gives back the arc of the original arc.
     2356    static Arc arc(const DigraphArc& a) {
     2357      return Parent::arc(a);
    23412358    }
    23422359
  • lemon/graph_adaptor.h

    r430 r431  
    3232namespace lemon {
    3333
    34   /// \brief Base type for the Graph Adaptors
    35   ///
    36   /// This is the base type for most of LEMON graph adaptors.
    37   /// This class implements a trivial graph adaptor i.e. it only wraps the
    38   /// functions and types of the graph. The purpose of this class is to
    39   /// make easier implementing graph adaptors. E.g. if an adaptor is
    40   /// considered which differs from the wrapped graph only in some of its
    41   /// functions or types, then it can be derived from GraphAdaptor, and only
    42   /// the differences should be implemented.
    4334  template<typename _Graph>
    4435  class GraphAdaptorBase {
     
    196187  };
    197188
    198   /// \ingroup graph_adaptors
    199   ///
    200   /// \brief Trivial graph adaptor
    201   ///
    202   /// This class is an adaptor which does not change the adapted undirected
    203   /// graph. It can be used only to test the graph adaptors.
    204   template <typename _Graph>
    205   class GraphAdaptor
    206     : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > {
    207   public:
    208     typedef _Graph Graph;
    209     typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;
    210   protected:
    211     GraphAdaptor() : Parent() {}
    212 
    213   public:
    214     explicit GraphAdaptor(Graph& graph) { setGraph(graph); }
    215   };
    216 
    217189  template <typename _Graph, typename NodeFilterMap,
    218190            typename EdgeFilterMap, bool checked = true>
     
    319291    }
    320292
    321     /// \brief Hide the given node in the graph.
    322     ///
    323     /// This function hides \c n in the graph, i.e. the iteration
    324     /// jumps over it. This is done by simply setting the value of \c n 
    325     /// to be false in the corresponding node-map.
    326293    void hide(const Node& n) const { _node_filter_map->set(n, false); }
    327 
    328     /// \brief Hide the given edge in the graph.
    329     ///
    330     /// This function hides \c e in the graph, i.e. the iteration
    331     /// jumps over it. This is done by simply setting the value of \c e 
    332     /// to be false in the corresponding edge-map.
    333294    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
    334295
    335     /// \brief Unhide the given node in the graph.
    336     ///
    337     /// The value of \c n is set to be true in the node-map which stores
    338     /// hide information. If \c n was hidden previuosly, then it is shown
    339     /// again
    340      void unHide(const Node& n) const { _node_filter_map->set(n, true); }
    341 
    342     /// \brief Hide the given edge in the graph.
    343     ///
    344     /// The value of \c e is set to be true in the edge-map which stores
    345     /// hide information. If \c e was hidden previuosly, then it is shown
    346     /// again
     296    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
    347297    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
    348298
    349     /// \brief Returns true if \c n is hidden.
    350     ///
    351     /// Returns true if \c n is hidden.
    352299    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
    353 
    354     /// \brief Returns true if \c e is hidden.
    355     ///
    356     /// Returns true if \c e is hidden.
    357300    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
    358301
     
    544487    }
    545488
    546     /// \brief Hide the given node in the graph.
    547     ///
    548     /// This function hides \c n in the graph, i.e. the iteration
    549     /// jumps over it. This is done by simply setting the value of \c n 
    550     /// to be false in the corresponding node-map.
    551489    void hide(const Node& n) const { _node_filter_map->set(n, false); }
    552 
    553     /// \brief Hide the given edge in the graph.
    554     ///
    555     /// This function hides \c e in the graph, i.e. the iteration
    556     /// jumps over it. This is done by simply setting the value of \c e 
    557     /// to be false in the corresponding edge-map.
    558490    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }
    559491
    560     /// \brief Unhide the given node in the graph.
    561     ///
    562     /// The value of \c n is set to be true in the node-map which stores
    563     /// hide information. If \c n was hidden previuosly, then it is shown
    564     /// again
    565      void unHide(const Node& n) const { _node_filter_map->set(n, true); }
    566 
    567     /// \brief Hide the given edge in the graph.
    568     ///
    569     /// The value of \c e is set to be true in the edge-map which stores
    570     /// hide information. If \c e was hidden previuosly, then it is shown
    571     /// again
     492    void unHide(const Node& n) const { _node_filter_map->set(n, true); }
    572493    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }
    573494
    574     /// \brief Returns true if \c n is hidden.
    575     ///
    576     /// Returns true if \c n is hidden.
    577495    bool hidden(const Node& n) const { return !(*_node_filter_map)[n]; }
    578 
    579     /// \brief Returns true if \c e is hidden.
    580     ///
    581     /// Returns true if \c e is hidden.
    582496    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }
    583497
     
    683597  /// \ingroup graph_adaptors
    684598  ///
    685   /// \brief A graph adaptor for hiding nodes and arcs from an
     599  /// \brief A graph adaptor for hiding nodes and edges from an
    686600  /// undirected graph.
    687601  ///
     
    705619    typedef GraphAdaptorExtender<
    706620      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;
     621
     622    typedef typename Parent::Node Node;
     623    typedef typename Parent::Edge Edge;
     624
    707625  protected:
    708626    SubGraphAdaptor() { }
    709627  public:
     628   
     629    /// \brief Constructor
     630    ///
     631    /// Creates a sub-graph-adaptor for the given graph with
     632    /// given node and edge map filters.
    710633    SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map,
    711634                    EdgeFilterMap& edge_filter_map) {
     
    714637      setEdgeFilterMap(edge_filter_map);
    715638    }
     639
     640    /// \brief Hides the node of the graph
     641    ///
     642    /// This function hides \c n in the digraph, i.e. the iteration
     643    /// jumps over it. This is done by simply setting the value of \c n 
     644    /// to be false in the corresponding node-map.
     645    void hide(const Node& n) const { Parent::hide(n); }
     646
     647    /// \brief Hides the edge of the graph
     648    ///
     649    /// This function hides \c e in the digraph, i.e. the iteration
     650    /// jumps over it. This is done by simply setting the value of \c e
     651    /// to be false in the corresponding edge-map.
     652    void hide(const Edge& e) const { Parent::hide(e); }
     653
     654    /// \brief Unhides the node of the graph
     655    ///
     656    /// The value of \c n is set to be true in the node-map which stores
     657    /// hide information. If \c n was hidden previuosly, then it is shown
     658    /// again
     659    void unHide(const Node& n) const { Parent::unHide(n); }
     660
     661    /// \brief Unhides the edge of the graph
     662    ///
     663    /// The value of \c e is set to be true in the edge-map which stores
     664    /// hide information. If \c e was hidden previuosly, then it is shown
     665    /// again
     666    void unHide(const Edge& e) const { Parent::unHide(e); }
     667
     668    /// \brief Returns true if \c n is hidden.
     669    ///
     670    /// Returns true if \c n is hidden.
     671    ///
     672    bool hidden(const Node& n) const { return Parent::hidden(n); }
     673
     674    /// \brief Returns true if \c e is hidden.
     675    ///
     676    /// Returns true if \c e is hidden.
     677    ///
     678    bool hidden(const Edge& e) const { return Parent::hidden(e); }
    716679  };
    717680
     681  /// \brief Just gives back a sub-graph adaptor
     682  ///
     683  /// Just gives back a sub-graph adaptor
    718684  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>
    719685  SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>
     
    766732    typedef SubGraphAdaptor<Graph, NodeFilterMap,
    767733                            ConstMap<typename Graph::Edge, bool> > Parent;
     734
     735    typedef typename Parent::Node Node;
    768736  protected:
    769737    ConstMap<typename Graph::Edge, bool> const_true_map;
     
    774742
    775743  public:
     744
     745    /// \brief Constructor
     746    ///
     747    /// Creates a node-sub-graph-adaptor for the given graph with
     748    /// given node map filters.
    776749    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) :
    777750      Parent(), const_true_map(true) {
     
    780753      Parent::setEdgeFilterMap(const_true_map);
    781754    }
     755
     756    /// \brief Hides the node of the graph
     757    ///
     758    /// This function hides \c n in the digraph, i.e. the iteration
     759    /// jumps over it. This is done by simply setting the value of \c n 
     760    /// to be false in the corresponding node-map.
     761    void hide(const Node& n) const { Parent::hide(n); }
     762
     763    /// \brief Unhides the node of the graph
     764    ///
     765    /// The value of \c n is set to be true in the node-map which stores
     766    /// hide information. If \c n was hidden previuosly, then it is shown
     767    /// again
     768    void unHide(const Node& n) const { Parent::unHide(n); }
     769
     770    /// \brief Returns true if \c n is hidden.
     771    ///
     772    /// Returns true if \c n is hidden.
     773    ///
     774    bool hidden(const Node& n) const { return Parent::hidden(n); }
     775
    782776  };
    783777
     778  /// \brief Just gives back a node-sub-graph adaptor
     779  ///
     780  /// Just gives back a node-sub-graph adaptor
    784781  template<typename Graph, typename NodeFilterMap>
    785782  NodeSubGraphAdaptor<const Graph, NodeFilterMap>
     
    814811    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,
    815812                            EdgeFilterMap, false> Parent;
     813    typedef typename Parent::Edge Edge;
    816814  protected:
    817815    ConstMap<typename Graph::Node, bool> const_true_map;
     
    823821  public:
    824822
     823    /// \brief Constructor
     824    ///
     825    /// Creates a edge-sub-graph-adaptor for the given graph with
     826    /// given node map filters.
    825827    EdgeSubGraphAdaptor(Graph& _graph, EdgeFilterMap& edge_filter_map) :
    826828      Parent(), const_true_map(true) {
     
    830832    }
    831833
     834    /// \brief Hides the edge of the graph
     835    ///
     836    /// This function hides \c e in the digraph, i.e. the iteration
     837    /// jumps over it. This is done by simply setting the value of \c e
     838    /// to be false in the corresponding edge-map.
     839    void hide(const Edge& e) const { Parent::hide(e); }
     840
     841    /// \brief Unhides the edge of the graph
     842    ///
     843    /// The value of \c e is set to be true in the edge-map which stores
     844    /// hide information. If \c e was hidden previuosly, then it is shown
     845    /// again
     846    void unHide(const Edge& e) const { Parent::unHide(e); }
     847
     848    /// \brief Returns true if \c e is hidden.
     849    ///
     850    /// Returns true if \c e is hidden.
     851    ///
     852    bool hidden(const Edge& e) const { return Parent::hidden(e); }
     853
    832854  };
    833855
     856  /// \brief Just gives back an edge-sub-graph adaptor
     857  ///
     858  /// Just gives back an edge-sub-graph adaptor
    834859  template<typename Graph, typename EdgeFilterMap>
    835860  EdgeSubGraphAdaptor<const Graph, EdgeFilterMap>
     
    844869  }
    845870
    846   /// \brief Base of direct graph adaptor
    847   ///
    848   /// Base class of the direct graph adaptor. All public member
    849   /// of this class can be used with the DirGraphAdaptor too.
    850   /// \sa DirGraphAdaptor
    851871  template <typename _Graph, typename _DirectionMap>
    852872  class DirGraphAdaptorBase {
     
    11041124    typedef DigraphAdaptorExtender<
    11051125      DirGraphAdaptorBase<_Graph, DirectionMap> > Parent;
     1126    typedef typename Parent::Arc Arc;
    11061127  protected:
    11071128    DirGraphAdaptor() { }
     
    11141135      setGraph(graph);
    11151136      setDirectionMap(direction);
     1137    }
     1138
     1139    /// \brief Reverse arc
     1140    ///
     1141    /// It reverse the given arc. It simply negate the direction in the map.
     1142    void reverseArc(const Arc& a) {
     1143      Parent::reverseArc(a);
    11161144    }
    11171145  };
  • test/graph_adaptor_test.cc

    r430 r431  
    3838using namespace lemon;
    3939
    40 void checkDigraphAdaptor() {
    41   checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();
    42 
    43   typedef ListDigraph Digraph;
    44   typedef DigraphAdaptor<Digraph> Adaptor;
    45 
    46   Digraph digraph;
    47   Adaptor adaptor(digraph);
    48 
    49   Digraph::Node n1 = digraph.addNode();
    50   Digraph::Node n2 = digraph.addNode();
    51   Digraph::Node n3 = digraph.addNode();
    52 
    53   Digraph::Arc a1 = digraph.addArc(n1, n2);
    54   Digraph::Arc a2 = digraph.addArc(n1, n3);
    55   Digraph::Arc a3 = digraph.addArc(n2, n3);
    56  
    57   checkGraphNodeList(adaptor, 3);
    58   checkGraphArcList(adaptor, 3);
    59   checkGraphConArcList(adaptor, 3);
    60 
    61   checkGraphOutArcList(adaptor, n1, 2);
    62   checkGraphOutArcList(adaptor, n2, 1);
    63   checkGraphOutArcList(adaptor, n3, 0);
    64 
    65   checkGraphInArcList(adaptor, n1, 0);
    66   checkGraphInArcList(adaptor, n2, 1);
    67   checkGraphInArcList(adaptor, n3, 2);
    68 
    69   checkNodeIds(adaptor);
    70   checkArcIds(adaptor);
    71 
    72   checkGraphNodeMap(adaptor);
    73   checkGraphArcMap(adaptor);
    74 }
    75 
    7640void checkRevDigraphAdaptor() {
    7741  checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
     
    586550}
    587551
    588 void checkGraphAdaptor() {
    589   checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();
    590 
    591   typedef ListGraph Graph;
    592   typedef GraphAdaptor<Graph> Adaptor;
    593 
    594   Graph graph;
    595   Adaptor adaptor(graph);
    596 
    597   Graph::Node n1 = graph.addNode();
    598   Graph::Node n2 = graph.addNode();
    599   Graph::Node n3 = graph.addNode();
    600   Graph::Node n4 = graph.addNode();
    601 
    602   Graph::Edge a1 = graph.addEdge(n1, n2);
    603   Graph::Edge a2 = graph.addEdge(n1, n3);
    604   Graph::Edge a3 = graph.addEdge(n2, n3);
    605   Graph::Edge a4 = graph.addEdge(n3, n4);
    606  
    607   checkGraphNodeList(adaptor, 4);
    608   checkGraphArcList(adaptor, 8);
    609   checkGraphEdgeList(adaptor, 4);
    610   checkGraphConArcList(adaptor, 8);
    611   checkGraphConEdgeList(adaptor, 4);
    612 
    613   checkGraphOutArcList(adaptor, n1, 2);
    614   checkGraphOutArcList(adaptor, n2, 2);
    615   checkGraphOutArcList(adaptor, n3, 3);
    616   checkGraphOutArcList(adaptor, n4, 1);
    617 
    618   checkGraphInArcList(adaptor, n1, 2);
    619   checkGraphInArcList(adaptor, n2, 2);
    620   checkGraphInArcList(adaptor, n3, 3);
    621   checkGraphInArcList(adaptor, n4, 1);
    622 
    623   checkGraphIncEdgeList(adaptor, n1, 2);
    624   checkGraphIncEdgeList(adaptor, n2, 2);
    625   checkGraphIncEdgeList(adaptor, n3, 3);
    626   checkGraphIncEdgeList(adaptor, n4, 1);
    627 
    628 
    629   checkNodeIds(adaptor);
    630   checkArcIds(adaptor);
    631   checkEdgeIds(adaptor);
    632 
    633   checkGraphNodeMap(adaptor);
    634   checkGraphArcMap(adaptor);
    635   checkGraphEdgeMap(adaptor);
    636 }
    637 
    638552void checkSubGraphAdaptor() {
    639553  checkConcept<concepts::Graph,
     
    1054968int main(int, const char **) {
    1055969
    1056   checkDigraphAdaptor();
    1057970  checkRevDigraphAdaptor();
    1058971  checkSubDigraphAdaptor();
     
    1063976  checkSplitDigraphAdaptor();
    1064977
    1065   checkGraphAdaptor();
    1066978  checkSubGraphAdaptor();
    1067979  checkNodeSubGraphAdaptor();
Note: See TracChangeset for help on using the changeset viewer.