lemon/concepts/digraph.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 22 Jan 2008 10:59:14 +0000
changeset 59 4ab73d92f0fb
child 61 d718974f1290
permissions -rw-r--r--
Merge
     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