lemon/concepts/digraph.h
changeset 59 4ab73d92f0fb
child 61 d718974f1290
equal deleted inserted replaced
-1:000000000000 0:f9807abb7643
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2007
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #ifndef LEMON_CONCEPT_DIGRAPH_H
       
    20 #define LEMON_CONCEPT_DIGRAPH_H
       
    21 
       
    22 ///\ingroup graph_concepts
       
    23 ///\file
       
    24 ///\brief The concept of directed graphs.
       
    25 
       
    26 #include <lemon/bits/invalid.h>
       
    27 #include <lemon/bits/utility.h>
       
    28 #include <lemon/concepts/maps.h>
       
    29 #include <lemon/concept_check.h>
       
    30 #include <lemon/concepts/graph_components.h>
       
    31 
       
    32 namespace lemon {
       
    33   namespace concepts {
       
    34 
       
    35     /// \ingroup graph_concepts
       
    36     ///
       
    37     /// \brief Class describing the concept of directed graphs.
       
    38     ///
       
    39     /// This class describes the \ref concept "concept" of the
       
    40     /// immutable directed digraphs.
       
    41     ///
       
    42     /// Note that actual digraph implementation like @ref ListDigraph or
       
    43     /// @ref SmartDigraph may have several additional functionality.
       
    44     ///
       
    45     /// \sa concept
       
    46     class Digraph {
       
    47     private:
       
    48       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
       
    49       
       
    50       ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
       
    51       ///
       
    52       Digraph(const Digraph &) {};
       
    53       ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
       
    54       ///\e not allowed. Use DigraphCopy() instead.
       
    55       
       
    56       ///Assignment of \ref Digraph "Digraph"s to another ones are
       
    57       ///\e not allowed.  Use DigraphCopy() instead.
       
    58 
       
    59       void operator=(const Digraph &) {}
       
    60     public:
       
    61       ///\e
       
    62 
       
    63       /// Defalult constructor.
       
    64 
       
    65       /// Defalult constructor.
       
    66       ///
       
    67       Digraph() { }
       
    68       /// Class for identifying a node of the digraph
       
    69 
       
    70       /// This class identifies a node of the digraph. It also serves
       
    71       /// as a base class of the node iterators,
       
    72       /// thus they will convert to this type.
       
    73       class Node {
       
    74       public:
       
    75         /// Default constructor
       
    76 
       
    77         /// @warning The default constructor sets the iterator
       
    78         /// to an undefined value.
       
    79         Node() { }
       
    80         /// Copy constructor.
       
    81 
       
    82         /// Copy constructor.
       
    83         ///
       
    84         Node(const Node&) { }
       
    85 
       
    86         /// Invalid constructor \& conversion.
       
    87 
       
    88         /// This constructor initializes the iterator to be invalid.
       
    89         /// \sa Invalid for more details.
       
    90         Node(Invalid) { }
       
    91         /// Equality operator
       
    92 
       
    93         /// Two iterators are equal if and only if they point to the
       
    94         /// same object or both are invalid.
       
    95         bool operator==(Node) const { return true; }
       
    96 
       
    97         /// Inequality operator
       
    98         
       
    99         /// \sa operator==(Node n)
       
   100         ///
       
   101         bool operator!=(Node) const { return true; }
       
   102 
       
   103 	/// Artificial ordering operator.
       
   104 	
       
   105 	/// To allow the use of digraph descriptors as key type in std::map or
       
   106 	/// similar associative container we require this.
       
   107 	///
       
   108 	/// \note This operator only have to define some strict ordering of
       
   109 	/// the items; this order has nothing to do with the iteration
       
   110 	/// ordering of the items.
       
   111 	bool operator<(Node) const { return false; }
       
   112 
       
   113       };
       
   114     
       
   115       /// This iterator goes through each node.
       
   116 
       
   117       /// This iterator goes through each node.
       
   118       /// Its usage is quite simple, for example you can count the number
       
   119       /// of nodes in digraph \c g of type \c Digraph like this:
       
   120       ///\code
       
   121       /// int count=0;
       
   122       /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
       
   123       ///\endcode
       
   124       class NodeIt : public Node {
       
   125       public:
       
   126         /// Default constructor
       
   127 
       
   128         /// @warning The default constructor sets the iterator
       
   129         /// to an undefined value.
       
   130         NodeIt() { }
       
   131         /// Copy constructor.
       
   132         
       
   133         /// Copy constructor.
       
   134         ///
       
   135         NodeIt(const NodeIt& n) : Node(n) { }
       
   136         /// Invalid constructor \& conversion.
       
   137 
       
   138         /// Initialize the iterator to be invalid.
       
   139         /// \sa Invalid for more details.
       
   140         NodeIt(Invalid) { }
       
   141         /// Sets the iterator to the first node.
       
   142 
       
   143         /// Sets the iterator to the first node of \c g.
       
   144         ///
       
   145         NodeIt(const Digraph&) { }
       
   146         /// Node -> NodeIt conversion.
       
   147 
       
   148         /// Sets the iterator to the node of \c the digraph pointed by 
       
   149 	/// the trivial iterator.
       
   150         /// This feature necessitates that each time we 
       
   151         /// iterate the arc-set, the iteration order is the same.
       
   152         NodeIt(const Digraph&, const Node&) { }
       
   153         /// Next node.
       
   154 
       
   155         /// Assign the iterator to the next node.
       
   156         ///
       
   157         NodeIt& operator++() { return *this; }
       
   158       };
       
   159     
       
   160     
       
   161       /// Class for identifying an arc of the digraph
       
   162 
       
   163       /// This class identifies an arc of the digraph. It also serves
       
   164       /// as a base class of the arc iterators,
       
   165       /// thus they will convert to this type.
       
   166       class Arc {
       
   167       public:
       
   168         /// Default constructor
       
   169 
       
   170         /// @warning The default constructor sets the iterator
       
   171         /// to an undefined value.
       
   172         Arc() { }
       
   173         /// Copy constructor.
       
   174 
       
   175         /// Copy constructor.
       
   176         ///
       
   177         Arc(const Arc&) { }
       
   178         /// Initialize the iterator to be invalid.
       
   179 
       
   180         /// Initialize the iterator to be invalid.
       
   181         ///
       
   182         Arc(Invalid) { }
       
   183         /// Equality operator
       
   184 
       
   185         /// Two iterators are equal if and only if they point to the
       
   186         /// same object or both are invalid.
       
   187         bool operator==(Arc) const { return true; }
       
   188         /// Inequality operator
       
   189 
       
   190         /// \sa operator==(Arc n)
       
   191         ///
       
   192         bool operator!=(Arc) const { return true; }
       
   193 
       
   194 	/// Artificial ordering operator.
       
   195 	
       
   196 	/// To allow the use of digraph descriptors as key type in std::map or
       
   197 	/// similar associative container we require this.
       
   198 	///
       
   199 	/// \note This operator only have to define some strict ordering of
       
   200 	/// the items; this order has nothing to do with the iteration
       
   201 	/// ordering of the items.
       
   202 	bool operator<(Arc) const { return false; }
       
   203       };
       
   204     
       
   205       /// This iterator goes trough the outgoing arcs of a node.
       
   206 
       
   207       /// This iterator goes trough the \e outgoing arcs of a certain node
       
   208       /// of a digraph.
       
   209       /// Its usage is quite simple, for example you can count the number
       
   210       /// of outgoing arcs of a node \c n
       
   211       /// in digraph \c g of type \c Digraph as follows.
       
   212       ///\code
       
   213       /// int count=0;
       
   214       /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
       
   215       ///\endcode
       
   216     
       
   217       class OutArcIt : public Arc {
       
   218       public:
       
   219         /// Default constructor
       
   220 
       
   221         /// @warning The default constructor sets the iterator
       
   222         /// to an undefined value.
       
   223         OutArcIt() { }
       
   224         /// Copy constructor.
       
   225 
       
   226         /// Copy constructor.
       
   227         ///
       
   228         OutArcIt(const OutArcIt& e) : Arc(e) { }
       
   229         /// Initialize the iterator to be invalid.
       
   230 
       
   231         /// Initialize the iterator to be invalid.
       
   232         ///
       
   233         OutArcIt(Invalid) { }
       
   234         /// This constructor sets the iterator to the first outgoing arc.
       
   235     
       
   236         /// This constructor sets the iterator to the first outgoing arc of
       
   237         /// the node.
       
   238         OutArcIt(const Digraph&, const Node&) { }
       
   239         /// Arc -> OutArcIt conversion
       
   240 
       
   241         /// Sets the iterator to the value of the trivial iterator.
       
   242 	/// This feature necessitates that each time we 
       
   243         /// iterate the arc-set, the iteration order is the same.
       
   244         OutArcIt(const Digraph&, const Arc&) { }
       
   245         ///Next outgoing arc
       
   246         
       
   247         /// Assign the iterator to the next 
       
   248         /// outgoing arc of the corresponding node.
       
   249         OutArcIt& operator++() { return *this; }
       
   250       };
       
   251 
       
   252       /// This iterator goes trough the incoming arcs of a node.
       
   253 
       
   254       /// This iterator goes trough the \e incoming arcs of a certain node
       
   255       /// of a digraph.
       
   256       /// Its usage is quite simple, for example you can count the number
       
   257       /// of outgoing arcs of a node \c n
       
   258       /// in digraph \c g of type \c Digraph as follows.
       
   259       ///\code
       
   260       /// int count=0;
       
   261       /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
       
   262       ///\endcode
       
   263 
       
   264       class InArcIt : public Arc {
       
   265       public:
       
   266         /// Default constructor
       
   267 
       
   268         /// @warning The default constructor sets the iterator
       
   269         /// to an undefined value.
       
   270         InArcIt() { }
       
   271         /// Copy constructor.
       
   272 
       
   273         /// Copy constructor.
       
   274         ///
       
   275         InArcIt(const InArcIt& e) : Arc(e) { }
       
   276         /// Initialize the iterator to be invalid.
       
   277 
       
   278         /// Initialize the iterator to be invalid.
       
   279         ///
       
   280         InArcIt(Invalid) { }
       
   281         /// This constructor sets the iterator to first incoming arc.
       
   282     
       
   283         /// This constructor set the iterator to the first incoming arc of
       
   284         /// the node.
       
   285         InArcIt(const Digraph&, const Node&) { }
       
   286         /// Arc -> InArcIt conversion
       
   287 
       
   288         /// Sets the iterator to the value of the trivial iterator \c e.
       
   289         /// This feature necessitates that each time we 
       
   290         /// iterate the arc-set, the iteration order is the same.
       
   291         InArcIt(const Digraph&, const Arc&) { }
       
   292         /// Next incoming arc
       
   293 
       
   294         /// Assign the iterator to the next inarc of the corresponding node.
       
   295         ///
       
   296         InArcIt& operator++() { return *this; }
       
   297       };
       
   298       /// This iterator goes through each arc.
       
   299 
       
   300       /// This iterator goes through each arc of a digraph.
       
   301       /// Its usage is quite simple, for example you can count the number
       
   302       /// of arcs in a digraph \c g of type \c Digraph as follows:
       
   303       ///\code
       
   304       /// int count=0;
       
   305       /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
       
   306       ///\endcode
       
   307       class ArcIt : public Arc {
       
   308       public:
       
   309         /// Default constructor
       
   310 
       
   311         /// @warning The default constructor sets the iterator
       
   312         /// to an undefined value.
       
   313         ArcIt() { }
       
   314         /// Copy constructor.
       
   315 
       
   316         /// Copy constructor.
       
   317         ///
       
   318         ArcIt(const ArcIt& e) : Arc(e) { }
       
   319         /// Initialize the iterator to be invalid.
       
   320 
       
   321         /// Initialize the iterator to be invalid.
       
   322         ///
       
   323         ArcIt(Invalid) { }
       
   324         /// This constructor sets the iterator to the first arc.
       
   325     
       
   326         /// This constructor sets the iterator to the first arc of \c g.
       
   327         ///@param g the digraph
       
   328         ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
       
   329         /// Arc -> ArcIt conversion
       
   330 
       
   331         /// Sets the iterator to the value of the trivial iterator \c e.
       
   332         /// This feature necessitates that each time we 
       
   333         /// iterate the arc-set, the iteration order is the same.
       
   334         ArcIt(const Digraph&, const Arc&) { } 
       
   335         ///Next arc
       
   336         
       
   337         /// Assign the iterator to the next arc.
       
   338         ArcIt& operator++() { return *this; }
       
   339       };
       
   340       ///Gives back the target node of an arc.
       
   341 
       
   342       ///Gives back the target node of an arc.
       
   343       ///
       
   344       Node target(Arc) const { return INVALID; }
       
   345       ///Gives back the source node of an arc.
       
   346 
       
   347       ///Gives back the source node of an arc.
       
   348       ///
       
   349       Node source(Arc) const { return INVALID; }
       
   350 
       
   351       void first(Node&) const {}
       
   352       void next(Node&) const {}
       
   353 
       
   354       void first(Arc&) const {}
       
   355       void next(Arc&) const {}
       
   356 
       
   357 
       
   358       void firstIn(Arc&, const Node&) const {}
       
   359       void nextIn(Arc&) const {}
       
   360 
       
   361       void firstOut(Arc&, const Node&) const {}
       
   362       void nextOut(Arc&) const {}
       
   363 
       
   364       /// \brief The base node of the iterator.
       
   365       ///
       
   366       /// Gives back the base node of the iterator.
       
   367       /// It is always the target of the pointed arc.
       
   368       Node baseNode(const InArcIt&) const { return INVALID; }
       
   369 
       
   370       /// \brief The running node of the iterator.
       
   371       ///
       
   372       /// Gives back the running node of the iterator.
       
   373       /// It is always the source of the pointed arc.
       
   374       Node runningNode(const InArcIt&) const { return INVALID; }
       
   375 
       
   376       /// \brief The base node of the iterator.
       
   377       ///
       
   378       /// Gives back the base node of the iterator.
       
   379       /// It is always the source of the pointed arc.
       
   380       Node baseNode(const OutArcIt&) const { return INVALID; }
       
   381 
       
   382       /// \brief The running node of the iterator.
       
   383       ///
       
   384       /// Gives back the running node of the iterator.
       
   385       /// It is always the target of the pointed arc.
       
   386       Node runningNode(const OutArcIt&) const { return INVALID; }
       
   387 
       
   388       /// \brief The opposite node on the given arc.
       
   389       ///
       
   390       /// Gives back the opposite node on the given arc.
       
   391       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
       
   392 
       
   393       /// \brief Read write map of the nodes to type \c T.
       
   394       /// 
       
   395       /// ReadWrite map of the nodes to type \c T.
       
   396       /// \sa Reference
       
   397       template<class T> 
       
   398       class NodeMap : public ReadWriteMap< Node, T > {
       
   399       public:
       
   400 
       
   401         ///\e
       
   402         NodeMap(const Digraph&) { }
       
   403         ///\e
       
   404         NodeMap(const Digraph&, T) { }
       
   405 
       
   406         ///Copy constructor
       
   407         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
       
   408         ///Assignment operator
       
   409         template <typename CMap>
       
   410         NodeMap& operator=(const CMap&) { 
       
   411           checkConcept<ReadMap<Node, T>, CMap>();
       
   412           return *this; 
       
   413         }
       
   414       };
       
   415 
       
   416       /// \brief Read write map of the arcs to type \c T.
       
   417       ///
       
   418       /// Reference map of the arcs to type \c T.
       
   419       /// \sa Reference
       
   420       template<class T> 
       
   421       class ArcMap : public ReadWriteMap<Arc,T> {
       
   422       public:
       
   423 
       
   424         ///\e
       
   425         ArcMap(const Digraph&) { }
       
   426         ///\e
       
   427         ArcMap(const Digraph&, T) { }
       
   428         ///Copy constructor
       
   429         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
       
   430         ///Assignment operator
       
   431         template <typename CMap>
       
   432         ArcMap& operator=(const CMap&) { 
       
   433           checkConcept<ReadMap<Arc, T>, CMap>();
       
   434           return *this; 
       
   435         }
       
   436       };
       
   437 
       
   438       template <typename RDigraph>
       
   439       struct Constraints {
       
   440         void constraints() {
       
   441           checkConcept<IterableDigraphComponent<>, Digraph>();
       
   442           checkConcept<MappableDigraphComponent<>, Digraph>();
       
   443         }
       
   444       };
       
   445 
       
   446     };
       
   447     
       
   448   } //namespace concepts  
       
   449 } //namespace lemon
       
   450 
       
   451 
       
   452 
       
   453 #endif // LEMON_CONCEPT_DIGRAPH_H