lemon/concepts/digraph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 440 88ed40ad0d4f
child 580 2313edd0db0b
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
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@440
     5
 * Copyright (C) 2003-2009
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@529
    19
#ifndef LEMON_CONCEPTS_DIGRAPH_H
deba@529
    20
#define LEMON_CONCEPTS_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@529
   487
#endif