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