lemon/concepts/digraph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 13 Nov 2009 12:47:13 +0100
changeset 789 8ddb7deabab9
parent 580 2313edd0db0b
child 786 e20173729589
permissions -rw-r--r--
Map utility functions (#320)
     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-2009
     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_CONCEPTS_DIGRAPH_H
    20 #define LEMON_CONCEPTS_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 common interface of all directed
    39     /// graphs (digraphs).
    40     ///
    41     /// Like all concept classes, it only provides an interface
    42     /// without any sensible implementation. So any general algorithm for
    43     /// directed graphs should compile with this class, but it will not
    44     /// run properly, of course.
    45     /// An actual digraph implementation like \ref ListDigraph or
    46     /// \ref SmartDigraph may have additional functionality.
    47     ///
    48     /// \sa Graph
    49     class Digraph {
    50     private:
    51       /// Diraphs are \e not copy constructible. Use DigraphCopy instead.
    52       Digraph(const Digraph &) {}
    53       /// \brief Assignment of a digraph to another one is \e not allowed.
    54       /// Use DigraphCopy instead.
    55       void operator=(const Digraph &) {}
    56 
    57     public:
    58       /// Default constructor.
    59       Digraph() { }
    60 
    61       /// The node type of the digraph
    62 
    63       /// This class identifies a node of the digraph. It also serves
    64       /// as a base class of the node iterators,
    65       /// thus they convert to this type.
    66       class Node {
    67       public:
    68         /// Default constructor
    69 
    70         /// Default constructor.
    71         /// \warning It sets the object to an undefined value.
    72         Node() { }
    73         /// Copy constructor.
    74 
    75         /// Copy constructor.
    76         ///
    77         Node(const Node&) { }
    78 
    79         /// %Invalid constructor \& conversion.
    80 
    81         /// Initializes the object to be invalid.
    82         /// \sa Invalid for more details.
    83         Node(Invalid) { }
    84         /// Equality operator
    85 
    86         /// Equality operator.
    87         ///
    88         /// Two iterators are equal if and only if they point to the
    89         /// same object or both are \c INVALID.
    90         bool operator==(Node) const { return true; }
    91 
    92         /// Inequality operator
    93 
    94         /// Inequality operator.
    95         bool operator!=(Node) const { return true; }
    96 
    97         /// Artificial ordering operator.
    98 
    99         /// Artificial ordering operator.
   100         ///
   101         /// \note This operator only has to define some strict ordering of
   102         /// the nodes; this order has nothing to do with the iteration
   103         /// ordering of the nodes.
   104         bool operator<(Node) const { return false; }
   105       };
   106 
   107       /// Iterator class for the nodes.
   108 
   109       /// This iterator goes through each node of the digraph.
   110       /// Its usage is quite simple, for example you can count the number
   111       /// of nodes in a digraph \c g of type \c %Digraph like this:
   112       ///\code
   113       /// int count=0;
   114       /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
   115       ///\endcode
   116       class NodeIt : public Node {
   117       public:
   118         /// Default constructor
   119 
   120         /// Default constructor.
   121         /// \warning It sets the iterator to an undefined value.
   122         NodeIt() { }
   123         /// Copy constructor.
   124 
   125         /// Copy constructor.
   126         ///
   127         NodeIt(const NodeIt& n) : Node(n) { }
   128         /// %Invalid constructor \& conversion.
   129 
   130         /// Initializes the iterator to be invalid.
   131         /// \sa Invalid for more details.
   132         NodeIt(Invalid) { }
   133         /// Sets the iterator to the first node.
   134 
   135         /// Sets the iterator to the first node of the given digraph.
   136         ///
   137         explicit NodeIt(const Digraph&) { }
   138         /// Sets the iterator to the given node.
   139 
   140         /// Sets the iterator to the given node of the given digraph.
   141         ///
   142         NodeIt(const Digraph&, const Node&) { }
   143         /// Next node.
   144 
   145         /// Assign the iterator to the next node.
   146         ///
   147         NodeIt& operator++() { return *this; }
   148       };
   149 
   150 
   151       /// The arc type of the digraph
   152 
   153       /// This class identifies an arc of the digraph. It also serves
   154       /// as a base class of the arc iterators,
   155       /// thus they will convert to this type.
   156       class Arc {
   157       public:
   158         /// Default constructor
   159 
   160         /// Default constructor.
   161         /// \warning It sets the object to an undefined value.
   162         Arc() { }
   163         /// Copy constructor.
   164 
   165         /// Copy constructor.
   166         ///
   167         Arc(const Arc&) { }
   168         /// %Invalid constructor \& conversion.
   169 
   170         /// Initializes the object to be invalid.
   171         /// \sa Invalid for more details.
   172         Arc(Invalid) { }
   173         /// Equality operator
   174 
   175         /// Equality operator.
   176         ///
   177         /// Two iterators are equal if and only if they point to the
   178         /// same object or both are \c INVALID.
   179         bool operator==(Arc) const { return true; }
   180         /// Inequality operator
   181 
   182         /// Inequality operator.
   183         bool operator!=(Arc) const { return true; }
   184 
   185         /// Artificial ordering operator.
   186 
   187         /// Artificial ordering operator.
   188         ///
   189         /// \note This operator only has to define some strict ordering of
   190         /// the arcs; this order has nothing to do with the iteration
   191         /// ordering of the arcs.
   192         bool operator<(Arc) const { return false; }
   193       };
   194 
   195       /// Iterator class for the outgoing arcs of a node.
   196 
   197       /// This iterator goes trough the \e outgoing arcs of a certain node
   198       /// of a digraph.
   199       /// Its usage is quite simple, for example you can count the number
   200       /// of outgoing arcs of a node \c n
   201       /// in a digraph \c g of type \c %Digraph as follows.
   202       ///\code
   203       /// int count=0;
   204       /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
   205       ///\endcode
   206       class OutArcIt : public Arc {
   207       public:
   208         /// Default constructor
   209 
   210         /// Default constructor.
   211         /// \warning It sets the iterator to an undefined value.
   212         OutArcIt() { }
   213         /// Copy constructor.
   214 
   215         /// Copy constructor.
   216         ///
   217         OutArcIt(const OutArcIt& e) : Arc(e) { }
   218         /// %Invalid constructor \& conversion.
   219 
   220         /// Initializes the iterator to be invalid.
   221         /// \sa Invalid for more details.
   222         OutArcIt(Invalid) { }
   223         /// Sets the iterator to the first outgoing arc.
   224 
   225         /// Sets the iterator to the first outgoing arc of the given node.
   226         ///
   227         OutArcIt(const Digraph&, const Node&) { }
   228         /// Sets the iterator to the given arc.
   229 
   230         /// Sets the iterator to the given arc of the given digraph.
   231         ///
   232         OutArcIt(const Digraph&, const Arc&) { }
   233         /// Next outgoing arc
   234 
   235         /// Assign the iterator to the next
   236         /// outgoing arc of the corresponding node.
   237         OutArcIt& operator++() { return *this; }
   238       };
   239 
   240       /// Iterator class for the incoming arcs of a node.
   241 
   242       /// This iterator goes trough the \e incoming arcs of a certain node
   243       /// of a digraph.
   244       /// Its usage is quite simple, for example you can count the number
   245       /// of incoming arcs of a node \c n
   246       /// in a digraph \c g of type \c %Digraph as follows.
   247       ///\code
   248       /// int count=0;
   249       /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
   250       ///\endcode
   251       class InArcIt : public Arc {
   252       public:
   253         /// Default constructor
   254 
   255         /// Default constructor.
   256         /// \warning It sets the iterator to an undefined value.
   257         InArcIt() { }
   258         /// Copy constructor.
   259 
   260         /// Copy constructor.
   261         ///
   262         InArcIt(const InArcIt& e) : Arc(e) { }
   263         /// %Invalid constructor \& conversion.
   264 
   265         /// Initializes the iterator to be invalid.
   266         /// \sa Invalid for more details.
   267         InArcIt(Invalid) { }
   268         /// Sets the iterator to the first incoming arc.
   269 
   270         /// Sets the iterator to the first incoming arc of the given node.
   271         ///
   272         InArcIt(const Digraph&, const Node&) { }
   273         /// Sets the iterator to the given arc.
   274 
   275         /// Sets the iterator to the given arc of the given digraph.
   276         ///
   277         InArcIt(const Digraph&, const Arc&) { }
   278         /// Next incoming arc
   279 
   280         /// Assign the iterator to the next
   281         /// incoming arc of the corresponding node.
   282         InArcIt& operator++() { return *this; }
   283       };
   284 
   285       /// Iterator class for the arcs.
   286 
   287       /// This iterator goes through each arc of the digraph.
   288       /// Its usage is quite simple, for example you can count the number
   289       /// of arcs in a digraph \c g of type \c %Digraph as follows:
   290       ///\code
   291       /// int count=0;
   292       /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count;
   293       ///\endcode
   294       class ArcIt : public Arc {
   295       public:
   296         /// Default constructor
   297 
   298         /// Default constructor.
   299         /// \warning It sets the iterator to an undefined value.
   300         ArcIt() { }
   301         /// Copy constructor.
   302 
   303         /// Copy constructor.
   304         ///
   305         ArcIt(const ArcIt& e) : Arc(e) { }
   306         /// %Invalid constructor \& conversion.
   307 
   308         /// Initializes the iterator to be invalid.
   309         /// \sa Invalid for more details.
   310         ArcIt(Invalid) { }
   311         /// Sets the iterator to the first arc.
   312 
   313         /// Sets the iterator to the first arc of the given digraph.
   314         ///
   315         explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
   316         /// Sets the iterator to the given arc.
   317 
   318         /// Sets the iterator to the given arc of the given digraph.
   319         ///
   320         ArcIt(const Digraph&, const Arc&) { }
   321         /// Next arc
   322 
   323         /// Assign the iterator to the next arc.
   324         ///
   325         ArcIt& operator++() { return *this; }
   326       };
   327 
   328       /// \brief The source node of the arc.
   329       ///
   330       /// Returns the source node of the given arc.
   331       Node source(Arc) const { return INVALID; }
   332 
   333       /// \brief The target node of the arc.
   334       ///
   335       /// Returns the target node of the given arc.
   336       Node target(Arc) const { return INVALID; }
   337 
   338       /// \brief The ID of the node.
   339       ///
   340       /// Returns the ID of the given node.
   341       int id(Node) const { return -1; }
   342 
   343       /// \brief The ID of the arc.
   344       ///
   345       /// Returns the ID of the given arc.
   346       int id(Arc) const { return -1; }
   347 
   348       /// \brief The node with the given ID.
   349       ///
   350       /// Returns the node with the given ID.
   351       /// \pre The argument should be a valid node ID in the digraph.
   352       Node nodeFromId(int) const { return INVALID; }
   353 
   354       /// \brief The arc with the given ID.
   355       ///
   356       /// Returns the arc with the given ID.
   357       /// \pre The argument should be a valid arc ID in the digraph.
   358       Arc arcFromId(int) const { return INVALID; }
   359 
   360       /// \brief An upper bound on the node IDs.
   361       ///
   362       /// Returns an upper bound on the node IDs.
   363       int maxNodeId() const { return -1; }
   364 
   365       /// \brief An upper bound on the arc IDs.
   366       ///
   367       /// Returns an upper bound on the arc IDs.
   368       int maxArcId() const { return -1; }
   369 
   370       void first(Node&) const {}
   371       void next(Node&) const {}
   372 
   373       void first(Arc&) const {}
   374       void next(Arc&) const {}
   375 
   376 
   377       void firstIn(Arc&, const Node&) const {}
   378       void nextIn(Arc&) const {}
   379 
   380       void firstOut(Arc&, const Node&) const {}
   381       void nextOut(Arc&) const {}
   382 
   383       // The second parameter is dummy.
   384       Node fromId(int, Node) const { return INVALID; }
   385       // The second parameter is dummy.
   386       Arc fromId(int, Arc) const { return INVALID; }
   387 
   388       // Dummy parameter.
   389       int maxId(Node) const { return -1; }
   390       // Dummy parameter.
   391       int maxId(Arc) const { return -1; }
   392 
   393       /// \brief The opposite node on the arc.
   394       ///
   395       /// Returns the opposite node on the given arc.
   396       Node oppositeNode(Node, Arc) const { return INVALID; }
   397 
   398       /// \brief The base node of the iterator.
   399       ///
   400       /// Returns the base node of the given outgoing arc iterator
   401       /// (i.e. the source node of the corresponding arc).
   402       Node baseNode(OutArcIt) const { return INVALID; }
   403 
   404       /// \brief The running node of the iterator.
   405       ///
   406       /// Returns the running node of the given outgoing arc iterator
   407       /// (i.e. the target node of the corresponding arc).
   408       Node runningNode(OutArcIt) const { return INVALID; }
   409 
   410       /// \brief The base node of the iterator.
   411       ///
   412       /// Returns the base node of the given incomming arc iterator
   413       /// (i.e. the target node of the corresponding arc).
   414       Node baseNode(InArcIt) const { return INVALID; }
   415 
   416       /// \brief The running node of the iterator.
   417       ///
   418       /// Returns the running node of the given incomming arc iterator
   419       /// (i.e. the source node of the corresponding arc).
   420       Node runningNode(InArcIt) const { return INVALID; }
   421 
   422       /// \brief Standard graph map type for the nodes.
   423       ///
   424       /// Standard graph map type for the nodes.
   425       /// It conforms to the ReferenceMap concept.
   426       template<class T>
   427       class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
   428       public:
   429 
   430         /// Constructor
   431         explicit NodeMap(const Digraph&) { }
   432         /// Constructor with given initial value
   433         NodeMap(const Digraph&, T) { }
   434 
   435       private:
   436         ///Copy constructor
   437         NodeMap(const NodeMap& nm) : 
   438           ReferenceMap<Node, T, T&, const T&>(nm) { }
   439         ///Assignment operator
   440         template <typename CMap>
   441         NodeMap& operator=(const CMap&) {
   442           checkConcept<ReadMap<Node, T>, CMap>();
   443           return *this;
   444         }
   445       };
   446 
   447       /// \brief Standard graph map type for the arcs.
   448       ///
   449       /// Standard graph map type for the arcs.
   450       /// It conforms to the ReferenceMap concept.
   451       template<class T>
   452       class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
   453       public:
   454 
   455         /// Constructor
   456         explicit ArcMap(const Digraph&) { }
   457         /// Constructor with given initial value
   458         ArcMap(const Digraph&, T) { }
   459 
   460       private:
   461         ///Copy constructor
   462         ArcMap(const ArcMap& em) :
   463           ReferenceMap<Arc, T, T&, const T&>(em) { }
   464         ///Assignment operator
   465         template <typename CMap>
   466         ArcMap& operator=(const CMap&) {
   467           checkConcept<ReadMap<Arc, T>, CMap>();
   468           return *this;
   469         }
   470       };
   471 
   472       template <typename _Digraph>
   473       struct Constraints {
   474         void constraints() {
   475           checkConcept<BaseDigraphComponent, _Digraph>();
   476           checkConcept<IterableDigraphComponent<>, _Digraph>();
   477           checkConcept<IDableDigraphComponent<>, _Digraph>();
   478           checkConcept<MappableDigraphComponent<>, _Digraph>();
   479         }
   480       };
   481 
   482     };
   483 
   484   } //namespace concepts
   485 } //namespace lemon
   486 
   487 
   488 
   489 #endif