COIN-OR::LEMON - Graph Library

Changeset 415:4b6112235fad in lemon-1.2 for lemon/digraph_adaptor.h


Ignore:
Timestamp:
11/30/08 19:00:30 (12 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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/digraph_adaptor.h

    r414 r415  
    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
Note: See TracChangeset for help on using the changeset viewer.