lemon/concepts/digraph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 09 Jan 2009 12:54:27 +0100
changeset 451 fbd6e04acf44
parent 220 a5d8c039f218
child 440 88ed40ad0d4f
permissions -rw-r--r--
Various doc improvements for graph adaptors (#67)

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