lemon/concepts/graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 13 Dec 2009 22:19:08 +0100
changeset 804 4db8d5ccd26b
parent 734 bd72f8d20f33
child 877 141f9c0db4a3
permissions -rw-r--r--
Memory leak bugfix in BellmanFord (#51)
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@57
    19
///\ingroup graph_concepts
deba@57
    20
///\file
kpeter@734
    21
///\brief The concept of undirected graphs.
deba@57
    22
deba@529
    23
#ifndef LEMON_CONCEPTS_GRAPH_H
deba@529
    24
#define LEMON_CONCEPTS_GRAPH_H
deba@57
    25
deba@57
    26
#include <lemon/concepts/graph_components.h>
kpeter@734
    27
#include <lemon/concepts/maps.h>
kpeter@734
    28
#include <lemon/concept_check.h>
deba@220
    29
#include <lemon/core.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
    ///
kpeter@734
    36
    /// \brief Class describing the concept of undirected graphs.
deba@57
    37
    ///
kpeter@734
    38
    /// This class describes the common interface of all undirected
kpeter@734
    39
    /// graphs.
deba@57
    40
    ///
kpeter@734
    41
    /// Like all concept classes, it only provides an interface
kpeter@734
    42
    /// without any sensible implementation. So any general algorithm for
kpeter@734
    43
    /// undirected graphs should compile with this class, but it will not
deba@57
    44
    /// run properly, of course.
kpeter@734
    45
    /// An actual graph implementation like \ref ListGraph or
kpeter@734
    46
    /// \ref SmartGraph may have additional functionality.    
deba@57
    47
    ///
kpeter@734
    48
    /// The undirected graphs also fulfill the concept of \ref Digraph
kpeter@734
    49
    /// "directed graphs", since each edge can also be regarded as two
kpeter@734
    50
    /// oppositely directed arcs.
kpeter@734
    51
    /// Undirected graphs provide an Edge type for the undirected edges and
kpeter@734
    52
    /// an Arc type for the directed arcs. The Arc type is convertible to
kpeter@734
    53
    /// Edge or inherited from it, i.e. the corresponding edge can be
kpeter@734
    54
    /// obtained from an arc.
kpeter@734
    55
    /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt
kpeter@734
    56
    /// and ArcMap classes can be used for the arcs (just like in digraphs).
kpeter@734
    57
    /// Both InArcIt and OutArcIt iterates on the same edges but with
kpeter@734
    58
    /// opposite direction. IncEdgeIt also iterates on the same edges
kpeter@734
    59
    /// as OutArcIt and InArcIt, but it is not convertible to Arc,
kpeter@734
    60
    /// only to Edge.
deba@57
    61
    ///
kpeter@734
    62
    /// In LEMON, each undirected edge has an inherent orientation.
kpeter@734
    63
    /// Thus it can defined if an arc is forward or backward oriented in
kpeter@734
    64
    /// an undirected graph with respect to this default oriantation of
kpeter@734
    65
    /// the represented edge.
kpeter@734
    66
    /// With the direction() and direct() functions the direction
kpeter@734
    67
    /// of an arc can be obtained and set, respectively.
deba@57
    68
    ///
kpeter@734
    69
    /// Only nodes and edges can be added to or removed from an undirected
kpeter@734
    70
    /// graph and the corresponding arcs are added or removed automatically.
kpeter@734
    71
    ///
kpeter@734
    72
    /// \sa Digraph
deba@57
    73
    class Graph {
kpeter@734
    74
    private:
kpeter@734
    75
      /// Graphs are \e not copy constructible. Use DigraphCopy instead.
kpeter@734
    76
      Graph(const Graph&) {}
kpeter@734
    77
      /// \brief Assignment of a graph to another one is \e not allowed.
kpeter@734
    78
      /// Use DigraphCopy instead.
kpeter@734
    79
      void operator=(const Graph&) {}
kpeter@734
    80
deba@57
    81
    public:
kpeter@734
    82
      /// Default constructor.
kpeter@734
    83
      Graph() {}
kpeter@734
    84
kpeter@734
    85
      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
deba@57
    86
      ///
kpeter@734
    87
      /// Undirected graphs should be tagged with \c UndirectedTag.
kpeter@734
    88
      /// 
kpeter@734
    89
      /// This tag helps the \c enable_if technics to make compile time
alpar@209
    90
      /// specializations for undirected graphs.
deba@57
    91
      typedef True UndirectedTag;
deba@57
    92
kpeter@734
    93
      /// The node type of the graph
kpeter@734
    94
kpeter@734
    95
      /// This class identifies a node of the graph. It also serves
kpeter@734
    96
      /// as a base class of the node iterators,
kpeter@734
    97
      /// thus they convert to this type.
deba@57
    98
      class Node {
deba@57
    99
      public:
deba@57
   100
        /// Default constructor
deba@57
   101
kpeter@734
   102
        /// Default constructor.
kpeter@734
   103
        /// \warning It sets the object to an undefined value.
deba@57
   104
        Node() { }
deba@57
   105
        /// Copy constructor.
deba@57
   106
deba@57
   107
        /// Copy constructor.
deba@57
   108
        ///
deba@57
   109
        Node(const Node&) { }
deba@57
   110
kpeter@734
   111
        /// %Invalid constructor \& conversion.
deba@57
   112
kpeter@734
   113
        /// Initializes the object to be invalid.
deba@57
   114
        /// \sa Invalid for more details.
deba@57
   115
        Node(Invalid) { }
deba@57
   116
        /// Equality operator
deba@57
   117
kpeter@734
   118
        /// Equality operator.
kpeter@734
   119
        ///
deba@57
   120
        /// Two iterators are equal if and only if they point to the
kpeter@734
   121
        /// same object or both are \c INVALID.
deba@57
   122
        bool operator==(Node) const { return true; }
deba@57
   123
deba@57
   124
        /// Inequality operator
alpar@209
   125
kpeter@734
   126
        /// Inequality operator.
deba@57
   127
        bool operator!=(Node) const { return true; }
deba@57
   128
alpar@209
   129
        /// Artificial ordering operator.
alpar@209
   130
kpeter@734
   131
        /// Artificial ordering operator.
alpar@209
   132
        ///
kpeter@734
   133
        /// \note This operator only has to define some strict ordering of
alpar@209
   134
        /// the items; this order has nothing to do with the iteration
alpar@209
   135
        /// ordering of the items.
alpar@209
   136
        bool operator<(Node) const { return false; }
deba@57
   137
deba@57
   138
      };
alpar@209
   139
kpeter@734
   140
      /// Iterator class for the nodes.
deba@57
   141
kpeter@734
   142
      /// This iterator goes through each node of the graph.
kpeter@786
   143
      /// Its usage is quite simple, for example, you can count the number
kpeter@734
   144
      /// of nodes in a graph \c g of type \c %Graph like this:
deba@57
   145
      ///\code
deba@57
   146
      /// int count=0;
deba@57
   147
      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
deba@57
   148
      ///\endcode
deba@57
   149
      class NodeIt : public Node {
deba@57
   150
      public:
deba@57
   151
        /// Default constructor
deba@57
   152
kpeter@734
   153
        /// Default constructor.
kpeter@734
   154
        /// \warning It sets the iterator to an undefined value.
deba@57
   155
        NodeIt() { }
deba@57
   156
        /// Copy constructor.
alpar@209
   157
deba@57
   158
        /// Copy constructor.
deba@57
   159
        ///
deba@57
   160
        NodeIt(const NodeIt& n) : Node(n) { }
kpeter@734
   161
        /// %Invalid constructor \& conversion.
deba@57
   162
kpeter@734
   163
        /// Initializes the iterator to be invalid.
deba@57
   164
        /// \sa Invalid for more details.
deba@57
   165
        NodeIt(Invalid) { }
deba@57
   166
        /// Sets the iterator to the first node.
deba@57
   167
kpeter@734
   168
        /// Sets the iterator to the first node of the given digraph.
deba@57
   169
        ///
kpeter@734
   170
        explicit NodeIt(const Graph&) { }
kpeter@734
   171
        /// Sets the iterator to the given node.
deba@57
   172
kpeter@734
   173
        /// Sets the iterator to the given node of the given digraph.
kpeter@734
   174
        ///
deba@57
   175
        NodeIt(const Graph&, const Node&) { }
deba@57
   176
        /// Next node.
deba@57
   177
deba@57
   178
        /// Assign the iterator to the next node.
deba@57
   179
        ///
deba@57
   180
        NodeIt& operator++() { return *this; }
deba@57
   181
      };
alpar@209
   182
alpar@209
   183
kpeter@734
   184
      /// The edge type of the graph
deba@57
   185
kpeter@734
   186
      /// This class identifies an edge of the graph. It also serves
kpeter@734
   187
      /// as a base class of the edge iterators,
kpeter@734
   188
      /// thus they will convert to this type.
deba@57
   189
      class Edge {
deba@57
   190
      public:
deba@57
   191
        /// Default constructor
deba@57
   192
kpeter@734
   193
        /// Default constructor.
kpeter@734
   194
        /// \warning It sets the object to an undefined value.
deba@57
   195
        Edge() { }
deba@57
   196
        /// Copy constructor.
deba@57
   197
deba@57
   198
        /// Copy constructor.
deba@57
   199
        ///
deba@57
   200
        Edge(const Edge&) { }
kpeter@734
   201
        /// %Invalid constructor \& conversion.
deba@57
   202
kpeter@734
   203
        /// Initializes the object to be invalid.
kpeter@734
   204
        /// \sa Invalid for more details.
deba@57
   205
        Edge(Invalid) { }
deba@57
   206
        /// Equality operator
deba@57
   207
kpeter@734
   208
        /// Equality operator.
kpeter@734
   209
        ///
deba@57
   210
        /// Two iterators are equal if and only if they point to the
kpeter@734
   211
        /// same object or both are \c INVALID.
deba@57
   212
        bool operator==(Edge) const { return true; }
deba@57
   213
        /// Inequality operator
deba@57
   214
kpeter@734
   215
        /// Inequality operator.
deba@57
   216
        bool operator!=(Edge) const { return true; }
deba@57
   217
alpar@209
   218
        /// Artificial ordering operator.
alpar@209
   219
kpeter@734
   220
        /// Artificial ordering operator.
alpar@209
   221
        ///
kpeter@734
   222
        /// \note This operator only has to define some strict ordering of
kpeter@734
   223
        /// the edges; this order has nothing to do with the iteration
kpeter@734
   224
        /// ordering of the edges.
alpar@209
   225
        bool operator<(Edge) const { return false; }
deba@57
   226
      };
deba@57
   227
kpeter@734
   228
      /// Iterator class for the edges.
deba@57
   229
kpeter@734
   230
      /// This iterator goes through each edge of the graph.
kpeter@786
   231
      /// Its usage is quite simple, for example, you can count the number
kpeter@734
   232
      /// of edges in a graph \c g of type \c %Graph as follows:
deba@57
   233
      ///\code
deba@57
   234
      /// int count=0;
deba@57
   235
      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
deba@57
   236
      ///\endcode
deba@57
   237
      class EdgeIt : public Edge {
deba@57
   238
      public:
deba@57
   239
        /// Default constructor
deba@57
   240
kpeter@734
   241
        /// Default constructor.
kpeter@734
   242
        /// \warning It sets the iterator to an undefined value.
deba@57
   243
        EdgeIt() { }
deba@57
   244
        /// Copy constructor.
deba@57
   245
deba@57
   246
        /// Copy constructor.
deba@57
   247
        ///
deba@57
   248
        EdgeIt(const EdgeIt& e) : Edge(e) { }
kpeter@734
   249
        /// %Invalid constructor \& conversion.
deba@57
   250
kpeter@734
   251
        /// Initializes the iterator to be invalid.
kpeter@734
   252
        /// \sa Invalid for more details.
kpeter@734
   253
        EdgeIt(Invalid) { }
kpeter@734
   254
        /// Sets the iterator to the first edge.
kpeter@734
   255
kpeter@734
   256
        /// Sets the iterator to the first edge of the given graph.
deba@57
   257
        ///
kpeter@734
   258
        explicit EdgeIt(const Graph&) { }
kpeter@734
   259
        /// Sets the iterator to the given edge.
alpar@209
   260
kpeter@734
   261
        /// Sets the iterator to the given edge of the given graph.
kpeter@734
   262
        ///
alpar@209
   263
        EdgeIt(const Graph&, const Edge&) { }
deba@57
   264
        /// Next edge
alpar@209
   265
deba@57
   266
        /// Assign the iterator to the next edge.
kpeter@734
   267
        ///
deba@57
   268
        EdgeIt& operator++() { return *this; }
deba@57
   269
      };
deba@57
   270
kpeter@734
   271
      /// Iterator class for the incident edges of a node.
kpeter@734
   272
kpeter@734
   273
      /// This iterator goes trough the incident undirected edges
kpeter@734
   274
      /// of a certain node of a graph.
kpeter@786
   275
      /// Its usage is quite simple, for example, you can compute the
kpeter@734
   276
      /// degree (i.e. the number of incident edges) of a node \c n
kpeter@734
   277
      /// in a graph \c g of type \c %Graph as follows.
deba@57
   278
      ///
deba@57
   279
      ///\code
deba@57
   280
      /// int count=0;
deba@78
   281
      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
deba@57
   282
      ///\endcode
kpeter@734
   283
      ///
kpeter@734
   284
      /// \warning Loop edges will be iterated twice.
deba@78
   285
      class IncEdgeIt : public Edge {
deba@57
   286
      public:
deba@57
   287
        /// Default constructor
deba@57
   288
kpeter@734
   289
        /// Default constructor.
kpeter@734
   290
        /// \warning It sets the iterator to an undefined value.
deba@78
   291
        IncEdgeIt() { }
deba@57
   292
        /// Copy constructor.
deba@57
   293
deba@57
   294
        /// Copy constructor.
deba@57
   295
        ///
deba@78
   296
        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
kpeter@734
   297
        /// %Invalid constructor \& conversion.
deba@57
   298
kpeter@734
   299
        /// Initializes the iterator to be invalid.
kpeter@734
   300
        /// \sa Invalid for more details.
kpeter@734
   301
        IncEdgeIt(Invalid) { }
kpeter@734
   302
        /// Sets the iterator to the first incident edge.
kpeter@734
   303
kpeter@734
   304
        /// Sets the iterator to the first incident edge of the given node.
deba@57
   305
        ///
kpeter@734
   306
        IncEdgeIt(const Graph&, const Node&) { }
kpeter@734
   307
        /// Sets the iterator to the given edge.
alpar@209
   308
kpeter@734
   309
        /// Sets the iterator to the given edge of the given graph.
kpeter@734
   310
        ///
kpeter@734
   311
        IncEdgeIt(const Graph&, const Edge&) { }
kpeter@734
   312
        /// Next incident edge
deba@57
   313
kpeter@734
   314
        /// Assign the iterator to the next incident edge
alpar@209
   315
        /// of the corresponding node.
deba@78
   316
        IncEdgeIt& operator++() { return *this; }
deba@57
   317
      };
deba@57
   318
kpeter@734
   319
      /// The arc type of the graph
deba@57
   320
kpeter@734
   321
      /// This class identifies a directed arc of the graph. It also serves
kpeter@734
   322
      /// as a base class of the arc iterators,
kpeter@734
   323
      /// thus they will convert to this type.
kpeter@657
   324
      class Arc {
deba@57
   325
      public:
deba@57
   326
        /// Default constructor
deba@57
   327
kpeter@734
   328
        /// Default constructor.
kpeter@734
   329
        /// \warning It sets the object to an undefined value.
deba@57
   330
        Arc() { }
deba@57
   331
        /// Copy constructor.
deba@57
   332
deba@57
   333
        /// Copy constructor.
deba@57
   334
        ///
kpeter@657
   335
        Arc(const Arc&) { }
kpeter@734
   336
        /// %Invalid constructor \& conversion.
deba@57
   337
kpeter@734
   338
        /// Initializes the object to be invalid.
kpeter@734
   339
        /// \sa Invalid for more details.
deba@57
   340
        Arc(Invalid) { }
deba@57
   341
        /// Equality operator
deba@57
   342
kpeter@734
   343
        /// Equality operator.
kpeter@734
   344
        ///
deba@57
   345
        /// Two iterators are equal if and only if they point to the
kpeter@734
   346
        /// same object or both are \c INVALID.
deba@57
   347
        bool operator==(Arc) const { return true; }
deba@57
   348
        /// Inequality operator
deba@57
   349
kpeter@734
   350
        /// Inequality operator.
deba@57
   351
        bool operator!=(Arc) const { return true; }
deba@57
   352
alpar@209
   353
        /// Artificial ordering operator.
alpar@209
   354
kpeter@734
   355
        /// Artificial ordering operator.
alpar@209
   356
        ///
kpeter@734
   357
        /// \note This operator only has to define some strict ordering of
kpeter@734
   358
        /// the arcs; this order has nothing to do with the iteration
kpeter@734
   359
        /// ordering of the arcs.
alpar@209
   360
        bool operator<(Arc) const { return false; }
alpar@209
   361
kpeter@734
   362
        /// Converison to \c Edge
kpeter@734
   363
        
kpeter@734
   364
        /// Converison to \c Edge.
kpeter@734
   365
        ///
kpeter@657
   366
        operator Edge() const { return Edge(); }
alpar@209
   367
      };
deba@57
   368
kpeter@734
   369
      /// Iterator class for the arcs.
kpeter@734
   370
kpeter@734
   371
      /// This iterator goes through each directed arc of the graph.
kpeter@786
   372
      /// Its usage is quite simple, for example, you can count the number
kpeter@734
   373
      /// of arcs in a graph \c g of type \c %Graph as follows:
deba@57
   374
      ///\code
deba@57
   375
      /// int count=0;
kpeter@734
   376
      /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count;
deba@57
   377
      ///\endcode
deba@57
   378
      class ArcIt : public Arc {
deba@57
   379
      public:
deba@57
   380
        /// Default constructor
deba@57
   381
kpeter@734
   382
        /// Default constructor.
kpeter@734
   383
        /// \warning It sets the iterator to an undefined value.
deba@57
   384
        ArcIt() { }
deba@57
   385
        /// Copy constructor.
deba@57
   386
deba@57
   387
        /// Copy constructor.
deba@57
   388
        ///
deba@57
   389
        ArcIt(const ArcIt& e) : Arc(e) { }
kpeter@734
   390
        /// %Invalid constructor \& conversion.
deba@57
   391
kpeter@734
   392
        /// Initializes the iterator to be invalid.
kpeter@734
   393
        /// \sa Invalid for more details.
kpeter@734
   394
        ArcIt(Invalid) { }
kpeter@734
   395
        /// Sets the iterator to the first arc.
kpeter@734
   396
kpeter@734
   397
        /// Sets the iterator to the first arc of the given graph.
deba@57
   398
        ///
kpeter@734
   399
        explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
kpeter@734
   400
        /// Sets the iterator to the given arc.
alpar@209
   401
kpeter@734
   402
        /// Sets the iterator to the given arc of the given graph.
kpeter@734
   403
        ///
alpar@209
   404
        ArcIt(const Graph&, const Arc&) { }
kpeter@734
   405
        /// Next arc
alpar@209
   406
deba@57
   407
        /// Assign the iterator to the next arc.
kpeter@734
   408
        ///
deba@57
   409
        ArcIt& operator++() { return *this; }
deba@57
   410
      };
alpar@209
   411
kpeter@734
   412
      /// Iterator class for the outgoing arcs of a node.
deba@57
   413
kpeter@734
   414
      /// This iterator goes trough the \e outgoing directed arcs of a
kpeter@734
   415
      /// certain node of a graph.
kpeter@786
   416
      /// Its usage is quite simple, for example, you can count the number
deba@57
   417
      /// of outgoing arcs of a node \c n
kpeter@734
   418
      /// in a graph \c g of type \c %Graph as follows.
deba@57
   419
      ///\code
deba@57
   420
      /// int count=0;
kpeter@734
   421
      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
deba@57
   422
      ///\endcode
deba@57
   423
      class OutArcIt : public Arc {
deba@57
   424
      public:
deba@57
   425
        /// Default constructor
deba@57
   426
kpeter@734
   427
        /// Default constructor.
kpeter@734
   428
        /// \warning It sets the iterator to an undefined value.
deba@57
   429
        OutArcIt() { }
deba@57
   430
        /// Copy constructor.
deba@57
   431
deba@57
   432
        /// Copy constructor.
deba@57
   433
        ///
deba@57
   434
        OutArcIt(const OutArcIt& e) : Arc(e) { }
kpeter@734
   435
        /// %Invalid constructor \& conversion.
deba@57
   436
kpeter@734
   437
        /// Initializes the iterator to be invalid.
kpeter@734
   438
        /// \sa Invalid for more details.
kpeter@734
   439
        OutArcIt(Invalid) { }
kpeter@734
   440
        /// Sets the iterator to the first outgoing arc.
kpeter@734
   441
kpeter@734
   442
        /// Sets the iterator to the first outgoing arc of the given node.
deba@57
   443
        ///
deba@57
   444
        OutArcIt(const Graph& n, const Node& g) {
alpar@209
   445
          ignore_unused_variable_warning(n);
alpar@209
   446
          ignore_unused_variable_warning(g);
alpar@209
   447
        }
kpeter@734
   448
        /// Sets the iterator to the given arc.
deba@57
   449
kpeter@734
   450
        /// Sets the iterator to the given arc of the given graph.
kpeter@734
   451
        ///
deba@57
   452
        OutArcIt(const Graph&, const Arc&) { }
kpeter@734
   453
        /// Next outgoing arc
alpar@209
   454
alpar@209
   455
        /// Assign the iterator to the next
deba@57
   456
        /// outgoing arc of the corresponding node.
deba@57
   457
        OutArcIt& operator++() { return *this; }
deba@57
   458
      };
deba@57
   459
kpeter@734
   460
      /// Iterator class for the incoming arcs of a node.
deba@57
   461
kpeter@734
   462
      /// This iterator goes trough the \e incoming directed arcs of a
kpeter@734
   463
      /// certain node of a graph.
kpeter@786
   464
      /// Its usage is quite simple, for example, you can count the number
kpeter@734
   465
      /// of incoming arcs of a node \c n
kpeter@734
   466
      /// in a graph \c g of type \c %Graph as follows.
deba@57
   467
      ///\code
deba@57
   468
      /// int count=0;
kpeter@734
   469
      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
deba@57
   470
      ///\endcode
deba@57
   471
      class InArcIt : public Arc {
deba@57
   472
      public:
deba@57
   473
        /// Default constructor
deba@57
   474
kpeter@734
   475
        /// Default constructor.
kpeter@734
   476
        /// \warning It sets the iterator to an undefined value.
deba@57
   477
        InArcIt() { }
deba@57
   478
        /// Copy constructor.
deba@57
   479
deba@57
   480
        /// Copy constructor.
deba@57
   481
        ///
deba@57
   482
        InArcIt(const InArcIt& e) : Arc(e) { }
kpeter@734
   483
        /// %Invalid constructor \& conversion.
deba@57
   484
kpeter@734
   485
        /// Initializes the iterator to be invalid.
kpeter@734
   486
        /// \sa Invalid for more details.
kpeter@734
   487
        InArcIt(Invalid) { }
kpeter@734
   488
        /// Sets the iterator to the first incoming arc.
kpeter@734
   489
kpeter@734
   490
        /// Sets the iterator to the first incoming arc of the given node.
deba@57
   491
        ///
alpar@209
   492
        InArcIt(const Graph& g, const Node& n) {
alpar@209
   493
          ignore_unused_variable_warning(n);
alpar@209
   494
          ignore_unused_variable_warning(g);
alpar@209
   495
        }
kpeter@734
   496
        /// Sets the iterator to the given arc.
deba@57
   497
kpeter@734
   498
        /// Sets the iterator to the given arc of the given graph.
kpeter@734
   499
        ///
deba@57
   500
        InArcIt(const Graph&, const Arc&) { }
deba@57
   501
        /// Next incoming arc
deba@57
   502
kpeter@734
   503
        /// Assign the iterator to the next
kpeter@734
   504
        /// incoming arc of the corresponding node.
deba@57
   505
        InArcIt& operator++() { return *this; }
deba@57
   506
      };
deba@57
   507
kpeter@734
   508
      /// \brief Standard graph map type for the nodes.
alpar@209
   509
      ///
kpeter@734
   510
      /// Standard graph map type for the nodes.
kpeter@734
   511
      /// It conforms to the ReferenceMap concept.
alpar@209
   512
      template<class T>
kpeter@580
   513
      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
deba@57
   514
      {
deba@57
   515
      public:
deba@57
   516
kpeter@734
   517
        /// Constructor
kpeter@734
   518
        explicit NodeMap(const Graph&) { }
kpeter@734
   519
        /// Constructor with given initial value
deba@57
   520
        NodeMap(const Graph&, T) { }
deba@57
   521
kpeter@263
   522
      private:
deba@57
   523
        ///Copy constructor
kpeter@580
   524
        NodeMap(const NodeMap& nm) :
kpeter@580
   525
          ReferenceMap<Node, T, T&, const T&>(nm) { }
deba@57
   526
        ///Assignment operator
deba@57
   527
        template <typename CMap>
alpar@209
   528
        NodeMap& operator=(const CMap&) {
deba@57
   529
          checkConcept<ReadMap<Node, T>, CMap>();
alpar@209
   530
          return *this;
deba@57
   531
        }
deba@57
   532
      };
deba@57
   533
kpeter@734
   534
      /// \brief Standard graph map type for the arcs.
deba@57
   535
      ///
kpeter@734
   536
      /// Standard graph map type for the arcs.
kpeter@734
   537
      /// It conforms to the ReferenceMap concept.
alpar@209
   538
      template<class T>
kpeter@580
   539
      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
deba@57
   540
      {
deba@57
   541
      public:
deba@57
   542
kpeter@734
   543
        /// Constructor
kpeter@734
   544
        explicit ArcMap(const Graph&) { }
kpeter@734
   545
        /// Constructor with given initial value
deba@57
   546
        ArcMap(const Graph&, T) { }
kpeter@734
   547
kpeter@263
   548
      private:
deba@57
   549
        ///Copy constructor
kpeter@580
   550
        ArcMap(const ArcMap& em) :
kpeter@580
   551
          ReferenceMap<Arc, T, T&, const T&>(em) { }
deba@57
   552
        ///Assignment operator
deba@57
   553
        template <typename CMap>
alpar@209
   554
        ArcMap& operator=(const CMap&) {
deba@57
   555
          checkConcept<ReadMap<Arc, T>, CMap>();
alpar@209
   556
          return *this;
deba@57
   557
        }
deba@57
   558
      };
deba@57
   559
kpeter@734
   560
      /// \brief Standard graph map type for the edges.
kpeter@734
   561
      ///
kpeter@734
   562
      /// Standard graph map type for the edges.
kpeter@734
   563
      /// It conforms to the ReferenceMap concept.
alpar@209
   564
      template<class T>
kpeter@580
   565
      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
deba@57
   566
      {
deba@57
   567
      public:
deba@57
   568
kpeter@734
   569
        /// Constructor
kpeter@734
   570
        explicit EdgeMap(const Graph&) { }
kpeter@734
   571
        /// Constructor with given initial value
deba@57
   572
        EdgeMap(const Graph&, T) { }
kpeter@734
   573
kpeter@263
   574
      private:
deba@57
   575
        ///Copy constructor
kpeter@580
   576
        EdgeMap(const EdgeMap& em) :
kpeter@580
   577
          ReferenceMap<Edge, T, T&, const T&>(em) {}
deba@57
   578
        ///Assignment operator
deba@57
   579
        template <typename CMap>
alpar@209
   580
        EdgeMap& operator=(const CMap&) {
deba@57
   581
          checkConcept<ReadMap<Edge, T>, CMap>();
alpar@209
   582
          return *this;
deba@57
   583
        }
deba@57
   584
      };
deba@57
   585
kpeter@734
   586
      /// \brief The first node of the edge.
deba@57
   587
      ///
kpeter@734
   588
      /// Returns the first node of the given edge.
deba@57
   589
      ///
kpeter@786
   590
      /// Edges don't have source and target nodes, however, methods
kpeter@734
   591
      /// u() and v() are used to query the two end-nodes of an edge.
kpeter@734
   592
      /// The orientation of an edge that arises this way is called
kpeter@734
   593
      /// the inherent direction, it is used to define the default
kpeter@734
   594
      /// direction for the corresponding arcs.
kpeter@559
   595
      /// \sa v()
kpeter@559
   596
      /// \sa direction()
deba@57
   597
      Node u(Edge) const { return INVALID; }
deba@57
   598
kpeter@734
   599
      /// \brief The second node of the edge.
kpeter@559
   600
      ///
kpeter@734
   601
      /// Returns the second node of the given edge.
kpeter@559
   602
      ///
kpeter@786
   603
      /// Edges don't have source and target nodes, however, methods
kpeter@734
   604
      /// u() and v() are used to query the two end-nodes of an edge.
kpeter@734
   605
      /// The orientation of an edge that arises this way is called
kpeter@734
   606
      /// the inherent direction, it is used to define the default
kpeter@734
   607
      /// direction for the corresponding arcs.
kpeter@559
   608
      /// \sa u()
kpeter@559
   609
      /// \sa direction()
deba@57
   610
      Node v(Edge) const { return INVALID; }
deba@57
   611
kpeter@734
   612
      /// \brief The source node of the arc.
kpeter@734
   613
      ///
kpeter@734
   614
      /// Returns the source node of the given arc.
deba@57
   615
      Node source(Arc) const { return INVALID; }
deba@57
   616
kpeter@734
   617
      /// \brief The target node of the arc.
kpeter@734
   618
      ///
kpeter@734
   619
      /// Returns the target node of the given arc.
deba@57
   620
      Node target(Arc) const { return INVALID; }
deba@57
   621
kpeter@734
   622
      /// \brief The ID of the node.
kpeter@734
   623
      ///
kpeter@734
   624
      /// Returns the ID of the given node.
alpar@209
   625
      int id(Node) const { return -1; }
deba@61
   626
kpeter@734
   627
      /// \brief The ID of the edge.
kpeter@734
   628
      ///
kpeter@734
   629
      /// Returns the ID of the given edge.
alpar@209
   630
      int id(Edge) const { return -1; }
deba@61
   631
kpeter@734
   632
      /// \brief The ID of the arc.
kpeter@734
   633
      ///
kpeter@734
   634
      /// Returns the ID of the given arc.
alpar@209
   635
      int id(Arc) const { return -1; }
deba@61
   636
kpeter@734
   637
      /// \brief The node with the given ID.
deba@61
   638
      ///
kpeter@734
   639
      /// Returns the node with the given ID.
kpeter@734
   640
      /// \pre The argument should be a valid node ID in the graph.
alpar@209
   641
      Node nodeFromId(int) const { return INVALID; }
deba@61
   642
kpeter@734
   643
      /// \brief The edge with the given ID.
deba@61
   644
      ///
kpeter@734
   645
      /// Returns the edge with the given ID.
kpeter@734
   646
      /// \pre The argument should be a valid edge ID in the graph.
alpar@209
   647
      Edge edgeFromId(int) const { return INVALID; }
deba@61
   648
kpeter@734
   649
      /// \brief The arc with the given ID.
deba@61
   650
      ///
kpeter@734
   651
      /// Returns the arc with the given ID.
kpeter@734
   652
      /// \pre The argument should be a valid arc ID in the graph.
alpar@209
   653
      Arc arcFromId(int) const { return INVALID; }
deba@61
   654
kpeter@734
   655
      /// \brief An upper bound on the node IDs.
kpeter@734
   656
      ///
kpeter@734
   657
      /// Returns an upper bound on the node IDs.
alpar@209
   658
      int maxNodeId() const { return -1; }
deba@61
   659
kpeter@734
   660
      /// \brief An upper bound on the edge IDs.
kpeter@734
   661
      ///
kpeter@734
   662
      /// Returns an upper bound on the edge IDs.
alpar@209
   663
      int maxEdgeId() const { return -1; }
deba@61
   664
kpeter@734
   665
      /// \brief An upper bound on the arc IDs.
kpeter@734
   666
      ///
kpeter@734
   667
      /// Returns an upper bound on the arc IDs.
alpar@209
   668
      int maxArcId() const { return -1; }
deba@61
   669
kpeter@734
   670
      /// \brief The direction of the arc.
kpeter@734
   671
      ///
kpeter@734
   672
      /// Returns \c true if the direction of the given arc is the same as
kpeter@734
   673
      /// the inherent orientation of the represented edge.
kpeter@734
   674
      bool direction(Arc) const { return true; }
kpeter@734
   675
kpeter@734
   676
      /// \brief Direct the edge.
kpeter@734
   677
      ///
kpeter@734
   678
      /// Direct the given edge. The returned arc
kpeter@734
   679
      /// represents the given edge and its direction comes
kpeter@734
   680
      /// from the bool parameter. If it is \c true, then the direction
kpeter@734
   681
      /// of the arc is the same as the inherent orientation of the edge.
kpeter@734
   682
      Arc direct(Edge, bool) const {
kpeter@734
   683
        return INVALID;
kpeter@734
   684
      }
kpeter@734
   685
kpeter@734
   686
      /// \brief Direct the edge.
kpeter@734
   687
      ///
kpeter@734
   688
      /// Direct the given edge. The returned arc represents the given
kpeter@734
   689
      /// edge and its source node is the given node.
kpeter@734
   690
      Arc direct(Edge, Node) const {
kpeter@734
   691
        return INVALID;
kpeter@734
   692
      }
kpeter@734
   693
kpeter@734
   694
      /// \brief The oppositely directed arc.
kpeter@734
   695
      ///
kpeter@734
   696
      /// Returns the oppositely directed arc representing the same edge.
kpeter@734
   697
      Arc oppositeArc(Arc) const { return INVALID; }
kpeter@734
   698
kpeter@734
   699
      /// \brief The opposite node on the edge.
kpeter@734
   700
      ///
kpeter@734
   701
      /// Returns the opposite node on the given edge.
kpeter@734
   702
      Node oppositeNode(Node, Edge) const { return INVALID; }
kpeter@734
   703
deba@57
   704
      void first(Node&) const {}
deba@57
   705
      void next(Node&) const {}
deba@57
   706
deba@57
   707
      void first(Edge&) const {}
deba@57
   708
      void next(Edge&) const {}
deba@57
   709
deba@57
   710
      void first(Arc&) const {}
deba@57
   711
      void next(Arc&) const {}
deba@57
   712
deba@57
   713
      void firstOut(Arc&, Node) const {}
deba@57
   714
      void nextOut(Arc&) const {}
deba@57
   715
deba@57
   716
      void firstIn(Arc&, Node) const {}
deba@57
   717
      void nextIn(Arc&) const {}
deba@57
   718
deba@57
   719
      void firstInc(Edge &, bool &, const Node &) const {}
deba@57
   720
      void nextInc(Edge &, bool &) const {}
deba@57
   721
deba@61
   722
      // The second parameter is dummy.
deba@61
   723
      Node fromId(int, Node) const { return INVALID; }
deba@61
   724
      // The second parameter is dummy.
deba@61
   725
      Edge fromId(int, Edge) const { return INVALID; }
deba@61
   726
      // The second parameter is dummy.
deba@61
   727
      Arc fromId(int, Arc) const { return INVALID; }
deba@61
   728
deba@61
   729
      // Dummy parameter.
alpar@209
   730
      int maxId(Node) const { return -1; }
deba@61
   731
      // Dummy parameter.
alpar@209
   732
      int maxId(Edge) const { return -1; }
deba@61
   733
      // Dummy parameter.
alpar@209
   734
      int maxId(Arc) const { return -1; }
deba@61
   735
kpeter@734
   736
      /// \brief The base node of the iterator.
deba@57
   737
      ///
kpeter@734
   738
      /// Returns the base node of the given incident edge iterator.
kpeter@734
   739
      Node baseNode(IncEdgeIt) const { return INVALID; }
kpeter@734
   740
kpeter@734
   741
      /// \brief The running node of the iterator.
deba@57
   742
      ///
kpeter@734
   743
      /// Returns the running node of the given incident edge iterator.
kpeter@734
   744
      Node runningNode(IncEdgeIt) const { return INVALID; }
deba@57
   745
kpeter@734
   746
      /// \brief The base node of the iterator.
deba@57
   747
      ///
kpeter@734
   748
      /// Returns the base node of the given outgoing arc iterator
kpeter@734
   749
      /// (i.e. the source node of the corresponding arc).
kpeter@734
   750
      Node baseNode(OutArcIt) const { return INVALID; }
kpeter@734
   751
kpeter@734
   752
      /// \brief The running node of the iterator.
deba@57
   753
      ///
kpeter@734
   754
      /// Returns the running node of the given outgoing arc iterator
kpeter@734
   755
      /// (i.e. the target node of the corresponding arc).
kpeter@734
   756
      Node runningNode(OutArcIt) const { return INVALID; }
deba@57
   757
kpeter@734
   758
      /// \brief The base node of the iterator.
deba@57
   759
      ///
kpeter@734
   760
      /// Returns the base node of the given incomming arc iterator
kpeter@734
   761
      /// (i.e. the target node of the corresponding arc).
kpeter@734
   762
      Node baseNode(InArcIt) const { return INVALID; }
alpar@209
   763
kpeter@734
   764
      /// \brief The running node of the iterator.
deba@57
   765
      ///
kpeter@734
   766
      /// Returns the running node of the given incomming arc iterator
kpeter@734
   767
      /// (i.e. the source node of the corresponding arc).
kpeter@734
   768
      Node runningNode(InArcIt) const { return INVALID; }
deba@57
   769
deba@125
   770
      template <typename _Graph>
deba@57
   771
      struct Constraints {
alpar@209
   772
        void constraints() {
kpeter@580
   773
          checkConcept<BaseGraphComponent, _Graph>();
alpar@209
   774
          checkConcept<IterableGraphComponent<>, _Graph>();
alpar@209
   775
          checkConcept<IDableGraphComponent<>, _Graph>();
alpar@209
   776
          checkConcept<MappableGraphComponent<>, _Graph>();
alpar@209
   777
        }
deba@57
   778
      };
deba@57
   779
deba@57
   780
    };
deba@57
   781
deba@57
   782
  }
deba@57
   783
deba@57
   784
}
deba@57
   785
deba@57
   786
#endif