lemon/concepts/digraph.h
author Alpar Juttner <alpar@cs.elte.hu>
Fri, 29 Feb 2008 11:01:39 +0000
changeset 103 b68a7e348e00
parent 57 c1acf0018c0a
child 107 31a2e6d28f61
permissions -rw-r--r--
Port kruskal() and UnionFind from svn -r3468

The class type interface of Kruskal has not been ported yet
     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       /// \brief Returns the ID of the node.
   352       int id(Node) const { return -1; } 
   353 
   354       /// \brief Returns the ID of the arc.
   355       int id(Arc) const { return -1; } 
   356 
   357       /// \brief Returns the node with the given ID.
   358       ///
   359       /// \pre The argument should be a valid node ID in the graph.
   360       Node nodeFromId(int) const { return INVALID; } 
   361 
   362       /// \brief Returns the arc with the given ID.
   363       ///
   364       /// \pre The argument should be a valid arc ID in the graph.
   365       Arc arcFromId(int) const { return INVALID; } 
   366 
   367       /// \brief Returns an upper bound on the node IDs.
   368       int maxNodeId() const { return -1; } 
   369 
   370       /// \brief Returns an upper bound on the arc IDs.
   371       int maxArcId() const { return -1; } 
   372 
   373       void first(Node&) const {}
   374       void next(Node&) const {}
   375 
   376       void first(Arc&) const {}
   377       void next(Arc&) const {}
   378 
   379 
   380       void firstIn(Arc&, const Node&) const {}
   381       void nextIn(Arc&) const {}
   382 
   383       void firstOut(Arc&, const Node&) const {}
   384       void nextOut(Arc&) const {}
   385 
   386       // The second parameter is dummy.
   387       Node fromId(int, Node) const { return INVALID; }
   388       // The second parameter is dummy.
   389       Arc fromId(int, Arc) const { return INVALID; }
   390 
   391       // Dummy parameter.
   392       int maxId(Node) const { return -1; } 
   393       // Dummy parameter.
   394       int maxId(Arc) const { return -1; } 
   395 
   396       /// \brief The base node of the iterator.
   397       ///
   398       /// Gives back the base node of the iterator.
   399       /// It is always the target of the pointed arc.
   400       Node baseNode(const InArcIt&) const { return INVALID; }
   401 
   402       /// \brief The running node of the iterator.
   403       ///
   404       /// Gives back the running node of the iterator.
   405       /// It is always the source of the pointed arc.
   406       Node runningNode(const InArcIt&) const { return INVALID; }
   407 
   408       /// \brief The base node of the iterator.
   409       ///
   410       /// Gives back the base node of the iterator.
   411       /// It is always the source of the pointed arc.
   412       Node baseNode(const OutArcIt&) const { return INVALID; }
   413 
   414       /// \brief The running node of the iterator.
   415       ///
   416       /// Gives back the running node of the iterator.
   417       /// It is always the target of the pointed arc.
   418       Node runningNode(const OutArcIt&) const { return INVALID; }
   419 
   420       /// \brief The opposite node on the given arc.
   421       ///
   422       /// Gives back the opposite node on the given arc.
   423       Node oppositeNode(const Node&, const Arc&) const { return INVALID; }
   424 
   425       /// \brief Read write map of the nodes to type \c T.
   426       /// 
   427       /// ReadWrite map of the nodes to type \c T.
   428       /// \sa Reference
   429       template<class T> 
   430       class NodeMap : public ReadWriteMap< Node, T > {
   431       public:
   432 
   433         ///\e
   434         NodeMap(const Digraph&) { }
   435         ///\e
   436         NodeMap(const Digraph&, T) { }
   437 
   438         ///Copy constructor
   439         NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
   440         ///Assignment operator
   441         template <typename CMap>
   442         NodeMap& operator=(const CMap&) { 
   443           checkConcept<ReadMap<Node, T>, CMap>();
   444           return *this; 
   445         }
   446       };
   447 
   448       /// \brief Read write map of the arcs to type \c T.
   449       ///
   450       /// Reference map of the arcs to type \c T.
   451       /// \sa Reference
   452       template<class T> 
   453       class ArcMap : public ReadWriteMap<Arc,T> {
   454       public:
   455 
   456         ///\e
   457         ArcMap(const Digraph&) { }
   458         ///\e
   459         ArcMap(const Digraph&, T) { }
   460         ///Copy constructor
   461         ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
   462         ///Assignment operator
   463         template <typename CMap>
   464         ArcMap& operator=(const CMap&) { 
   465           checkConcept<ReadMap<Arc, T>, CMap>();
   466           return *this; 
   467         }
   468       };
   469 
   470       template <typename RDigraph>
   471       struct Constraints {
   472         void constraints() {
   473           checkConcept<IterableDigraphComponent<>, Digraph>();
   474 	  checkConcept<IDableDigraphComponent<>, Digraph>();
   475           checkConcept<MappableDigraphComponent<>, Digraph>();
   476         }
   477       };
   478 
   479     };
   480     
   481   } //namespace concepts  
   482 } //namespace lemon
   483 
   484 
   485 
   486 #endif // LEMON_CONCEPT_DIGRAPH_H