lemon/concepts/bpgraph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 08 Mar 2013 01:13:54 +0100
changeset 1046 387483bf0a56
parent 1027 8b2b9e61d8ce
child 1049 7bf489cf624e
permissions -rw-r--r--
Adjust image sizes in the documentation (#411)
deba@1018
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@1018
     2
 *
deba@1018
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@1018
     4
 *
deba@1018
     5
 * Copyright (C) 2003-2010
deba@1018
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1018
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1018
     8
 *
deba@1018
     9
 * Permission to use, modify and distribute this software is granted
deba@1018
    10
 * provided that this copyright notice appears in all copies. For
deba@1018
    11
 * precise terms see the accompanying LICENSE file.
deba@1018
    12
 *
deba@1018
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@1018
    14
 * express or implied, and with no claim as to its suitability for any
deba@1018
    15
 * purpose.
deba@1018
    16
 *
deba@1018
    17
 */
deba@1018
    18
deba@1018
    19
///\ingroup graph_concepts
deba@1018
    20
///\file
deba@1018
    21
///\brief The concept of undirected graphs.
deba@1018
    22
deba@1018
    23
#ifndef LEMON_CONCEPTS_BPGRAPH_H
deba@1018
    24
#define LEMON_CONCEPTS_BPGRAPH_H
deba@1018
    25
deba@1018
    26
#include <lemon/concepts/graph_components.h>
deba@1018
    27
#include <lemon/concepts/maps.h>
deba@1018
    28
#include <lemon/concept_check.h>
deba@1018
    29
#include <lemon/core.h>
deba@1018
    30
deba@1018
    31
namespace lemon {
deba@1018
    32
  namespace concepts {
deba@1018
    33
deba@1018
    34
    /// \ingroup graph_concepts
deba@1018
    35
    ///
deba@1018
    36
    /// \brief Class describing the concept of undirected bipartite graphs.
deba@1018
    37
    ///
deba@1018
    38
    /// This class describes the common interface of all undirected
deba@1018
    39
    /// bipartite graphs.
deba@1018
    40
    ///
deba@1018
    41
    /// Like all concept classes, it only provides an interface
deba@1018
    42
    /// without any sensible implementation. So any general algorithm for
deba@1018
    43
    /// undirected bipartite graphs should compile with this class,
deba@1018
    44
    /// but it will not run properly, of course.
deba@1018
    45
    /// An actual graph implementation like \ref ListBpGraph or
deba@1018
    46
    /// \ref SmartBpGraph may have additional functionality.
deba@1018
    47
    ///
deba@1018
    48
    /// The bipartite graphs also fulfill the concept of \ref Graph
deba@1018
    49
    /// "undirected graphs". Bipartite graphs provide a bipartition of
deba@1018
    50
    /// the node set, namely a red and blue set of the nodes. The
deba@1026
    51
    /// nodes can be iterated with the RedNodeIt and BlueNodeIt in the
deba@1026
    52
    /// two node sets. With RedNodeMap and BlueNodeMap values can be
deba@1026
    53
    /// assigned to the nodes in the two sets.
deba@1018
    54
    ///
deba@1018
    55
    /// The edges of the graph cannot connect two nodes of the same
deba@1018
    56
    /// set. The edges inherent orientation is from the red nodes to
deba@1018
    57
    /// the blue nodes.
deba@1018
    58
    ///
deba@1018
    59
    /// \sa Graph
deba@1018
    60
    class BpGraph {
deba@1018
    61
    private:
deba@1018
    62
      /// BpGraphs are \e not copy constructible. Use bpGraphCopy instead.
deba@1018
    63
      BpGraph(const BpGraph&) {}
deba@1018
    64
      /// \brief Assignment of a graph to another one is \e not allowed.
deba@1018
    65
      /// Use bpGraphCopy instead.
deba@1018
    66
      void operator=(const BpGraph&) {}
deba@1018
    67
deba@1018
    68
    public:
deba@1018
    69
      /// Default constructor.
deba@1018
    70
      BpGraph() {}
deba@1018
    71
deba@1018
    72
      /// \brief Undirected graphs should be tagged with \c UndirectedTag.
deba@1018
    73
      ///
deba@1018
    74
      /// Undirected graphs should be tagged with \c UndirectedTag.
deba@1018
    75
      ///
deba@1018
    76
      /// This tag helps the \c enable_if technics to make compile time
deba@1018
    77
      /// specializations for undirected graphs.
deba@1018
    78
      typedef True UndirectedTag;
deba@1018
    79
deba@1018
    80
      /// The node type of the graph
deba@1018
    81
deba@1018
    82
      /// This class identifies a node of the graph. It also serves
deba@1018
    83
      /// as a base class of the node iterators,
deba@1018
    84
      /// thus they convert to this type.
deba@1018
    85
      class Node {
deba@1018
    86
      public:
deba@1018
    87
        /// Default constructor
deba@1018
    88
deba@1018
    89
        /// Default constructor.
deba@1018
    90
        /// \warning It sets the object to an undefined value.
deba@1018
    91
        Node() { }
deba@1018
    92
        /// Copy constructor.
deba@1018
    93
deba@1018
    94
        /// Copy constructor.
deba@1018
    95
        ///
deba@1018
    96
        Node(const Node&) { }
deba@1018
    97
deba@1018
    98
        /// %Invalid constructor \& conversion.
deba@1018
    99
deba@1018
   100
        /// Initializes the object to be invalid.
deba@1018
   101
        /// \sa Invalid for more details.
deba@1018
   102
        Node(Invalid) { }
deba@1018
   103
        /// Equality operator
deba@1018
   104
deba@1018
   105
        /// Equality operator.
deba@1018
   106
        ///
deba@1018
   107
        /// Two iterators are equal if and only if they point to the
deba@1018
   108
        /// same object or both are \c INVALID.
deba@1018
   109
        bool operator==(Node) const { return true; }
deba@1018
   110
deba@1018
   111
        /// Inequality operator
deba@1018
   112
deba@1018
   113
        /// Inequality operator.
deba@1018
   114
        bool operator!=(Node) const { return true; }
deba@1018
   115
deba@1018
   116
        /// Artificial ordering operator.
deba@1018
   117
deba@1018
   118
        /// Artificial ordering operator.
deba@1018
   119
        ///
deba@1018
   120
        /// \note This operator only has to define some strict ordering of
deba@1018
   121
        /// the items; this order has nothing to do with the iteration
deba@1018
   122
        /// ordering of the items.
deba@1018
   123
        bool operator<(Node) const { return false; }
deba@1018
   124
deba@1018
   125
      };
deba@1018
   126
deba@1018
   127
      /// Class to represent red nodes.
deba@1018
   128
deba@1018
   129
      /// This class represents the red nodes of the graph. It does
deba@1018
   130
      /// not supposed to be used directly, because the nodes can be
deba@1018
   131
      /// represented as Node instances. This class can be used as
deba@1018
   132
      /// template parameter for special map classes.
deba@1018
   133
      class RedNode : public Node {
deba@1018
   134
      public:
deba@1018
   135
        /// Default constructor
deba@1018
   136
deba@1018
   137
        /// Default constructor.
deba@1018
   138
        /// \warning It sets the object to an undefined value.
deba@1018
   139
        RedNode() { }
deba@1018
   140
        /// Copy constructor.
deba@1018
   141
deba@1018
   142
        /// Copy constructor.
deba@1018
   143
        ///
deba@1018
   144
        RedNode(const RedNode&) : Node() { }
deba@1018
   145
deba@1018
   146
        /// %Invalid constructor \& conversion.
deba@1018
   147
deba@1018
   148
        /// Initializes the object to be invalid.
deba@1018
   149
        /// \sa Invalid for more details.
deba@1018
   150
        RedNode(Invalid) { }
deba@1018
   151
deba@1018
   152
      };
deba@1018
   153
deba@1018
   154
      /// Class to represent blue nodes.
deba@1018
   155
deba@1018
   156
      /// This class represents the blue nodes of the graph. It does
deba@1018
   157
      /// not supposed to be used directly, because the nodes can be
deba@1018
   158
      /// represented as Node instances. This class can be used as
deba@1018
   159
      /// template parameter for special map classes.
deba@1018
   160
      class BlueNode : public Node {
deba@1018
   161
      public:
deba@1018
   162
        /// Default constructor
deba@1018
   163
deba@1018
   164
        /// Default constructor.
deba@1018
   165
        /// \warning It sets the object to an undefined value.
deba@1018
   166
        BlueNode() { }
deba@1018
   167
        /// Copy constructor.
deba@1018
   168
deba@1018
   169
        /// Copy constructor.
deba@1018
   170
        ///
deba@1018
   171
        BlueNode(const BlueNode&) : Node() { }
deba@1018
   172
deba@1018
   173
        /// %Invalid constructor \& conversion.
deba@1018
   174
deba@1018
   175
        /// Initializes the object to be invalid.
deba@1018
   176
        /// \sa Invalid for more details.
deba@1018
   177
        BlueNode(Invalid) { }
deba@1018
   178
deba@1018
   179
      };
deba@1018
   180
deba@1018
   181
      /// Iterator class for the red nodes.
deba@1018
   182
deba@1018
   183
      /// This iterator goes through each red node of the graph.
deba@1018
   184
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   185
      /// of red nodes in a graph \c g of type \c %BpGraph like this:
deba@1018
   186
      ///\code
deba@1018
   187
      /// int count=0;
deba@1018
   188
      /// for (BpGraph::RedNodeIt n(g); n!=INVALID; ++n) ++count;
deba@1018
   189
      ///\endcode
deba@1026
   190
      class RedNodeIt : public RedNode {
deba@1018
   191
      public:
deba@1018
   192
        /// Default constructor
deba@1018
   193
deba@1018
   194
        /// Default constructor.
deba@1018
   195
        /// \warning It sets the iterator to an undefined value.
deba@1026
   196
        RedNodeIt() { }
deba@1018
   197
        /// Copy constructor.
deba@1018
   198
deba@1018
   199
        /// Copy constructor.
deba@1018
   200
        ///
deba@1026
   201
        RedNodeIt(const RedNodeIt& n) : RedNode(n) { }
deba@1018
   202
        /// %Invalid constructor \& conversion.
deba@1018
   203
deba@1018
   204
        /// Initializes the iterator to be invalid.
deba@1018
   205
        /// \sa Invalid for more details.
deba@1026
   206
        RedNodeIt(Invalid) { }
deba@1018
   207
        /// Sets the iterator to the first red node.
deba@1018
   208
deba@1018
   209
        /// Sets the iterator to the first red node of the given
deba@1018
   210
        /// digraph.
deba@1026
   211
        explicit RedNodeIt(const BpGraph&) { }
deba@1018
   212
        /// Sets the iterator to the given red node.
deba@1018
   213
deba@1018
   214
        /// Sets the iterator to the given red node of the given
deba@1018
   215
        /// digraph.
deba@1026
   216
        RedNodeIt(const BpGraph&, const RedNode&) { }
deba@1018
   217
        /// Next node.
deba@1018
   218
deba@1018
   219
        /// Assign the iterator to the next red node.
deba@1018
   220
        ///
deba@1026
   221
        RedNodeIt& operator++() { return *this; }
deba@1018
   222
      };
deba@1018
   223
deba@1018
   224
      /// Iterator class for the blue nodes.
deba@1018
   225
deba@1018
   226
      /// This iterator goes through each blue node of the graph.
deba@1018
   227
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   228
      /// of blue nodes in a graph \c g of type \c %BpGraph like this:
deba@1018
   229
      ///\code
deba@1018
   230
      /// int count=0;
deba@1018
   231
      /// for (BpGraph::BlueNodeIt n(g); n!=INVALID; ++n) ++count;
deba@1018
   232
      ///\endcode
deba@1026
   233
      class BlueNodeIt : public BlueNode {
deba@1018
   234
      public:
deba@1018
   235
        /// Default constructor
deba@1018
   236
deba@1018
   237
        /// Default constructor.
deba@1018
   238
        /// \warning It sets the iterator to an undefined value.
deba@1026
   239
        BlueNodeIt() { }
deba@1018
   240
        /// Copy constructor.
deba@1018
   241
deba@1018
   242
        /// Copy constructor.
deba@1018
   243
        ///
deba@1026
   244
        BlueNodeIt(const BlueNodeIt& n) : BlueNode(n) { }
deba@1018
   245
        /// %Invalid constructor \& conversion.
deba@1018
   246
deba@1018
   247
        /// Initializes the iterator to be invalid.
deba@1018
   248
        /// \sa Invalid for more details.
deba@1026
   249
        BlueNodeIt(Invalid) { }
deba@1018
   250
        /// Sets the iterator to the first blue node.
deba@1018
   251
deba@1018
   252
        /// Sets the iterator to the first blue node of the given
deba@1018
   253
        /// digraph.
deba@1026
   254
        explicit BlueNodeIt(const BpGraph&) { }
deba@1018
   255
        /// Sets the iterator to the given blue node.
deba@1018
   256
deba@1018
   257
        /// Sets the iterator to the given blue node of the given
deba@1018
   258
        /// digraph.
deba@1026
   259
        BlueNodeIt(const BpGraph&, const BlueNode&) { }
deba@1018
   260
        /// Next node.
deba@1018
   261
deba@1018
   262
        /// Assign the iterator to the next blue node.
deba@1018
   263
        ///
deba@1026
   264
        BlueNodeIt& operator++() { return *this; }
deba@1018
   265
      };
deba@1018
   266
deba@1018
   267
      /// Iterator class for the nodes.
deba@1018
   268
deba@1018
   269
      /// This iterator goes through each node of the graph.
deba@1018
   270
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   271
      /// of nodes in a graph \c g of type \c %BpGraph like this:
deba@1018
   272
      ///\code
deba@1018
   273
      /// int count=0;
deba@1018
   274
      /// for (BpGraph::NodeIt n(g); n!=INVALID; ++n) ++count;
deba@1018
   275
      ///\endcode
deba@1018
   276
      class NodeIt : public Node {
deba@1018
   277
      public:
deba@1018
   278
        /// Default constructor
deba@1018
   279
deba@1018
   280
        /// Default constructor.
deba@1018
   281
        /// \warning It sets the iterator to an undefined value.
deba@1018
   282
        NodeIt() { }
deba@1018
   283
        /// Copy constructor.
deba@1018
   284
deba@1018
   285
        /// Copy constructor.
deba@1018
   286
        ///
deba@1018
   287
        NodeIt(const NodeIt& n) : Node(n) { }
deba@1018
   288
        /// %Invalid constructor \& conversion.
deba@1018
   289
deba@1018
   290
        /// Initializes the iterator to be invalid.
deba@1018
   291
        /// \sa Invalid for more details.
deba@1018
   292
        NodeIt(Invalid) { }
deba@1018
   293
        /// Sets the iterator to the first node.
deba@1018
   294
deba@1018
   295
        /// Sets the iterator to the first node of the given digraph.
deba@1018
   296
        ///
deba@1018
   297
        explicit NodeIt(const BpGraph&) { }
deba@1018
   298
        /// Sets the iterator to the given node.
deba@1018
   299
deba@1018
   300
        /// Sets the iterator to the given node of the given digraph.
deba@1018
   301
        ///
deba@1018
   302
        NodeIt(const BpGraph&, const Node&) { }
deba@1018
   303
        /// Next node.
deba@1018
   304
deba@1018
   305
        /// Assign the iterator to the next node.
deba@1018
   306
        ///
deba@1018
   307
        NodeIt& operator++() { return *this; }
deba@1018
   308
      };
deba@1018
   309
deba@1018
   310
deba@1018
   311
      /// The edge type of the graph
deba@1018
   312
deba@1018
   313
      /// This class identifies an edge of the graph. It also serves
deba@1018
   314
      /// as a base class of the edge iterators,
deba@1018
   315
      /// thus they will convert to this type.
deba@1018
   316
      class Edge {
deba@1018
   317
      public:
deba@1018
   318
        /// Default constructor
deba@1018
   319
deba@1018
   320
        /// Default constructor.
deba@1018
   321
        /// \warning It sets the object to an undefined value.
deba@1018
   322
        Edge() { }
deba@1018
   323
        /// Copy constructor.
deba@1018
   324
deba@1018
   325
        /// Copy constructor.
deba@1018
   326
        ///
deba@1018
   327
        Edge(const Edge&) { }
deba@1018
   328
        /// %Invalid constructor \& conversion.
deba@1018
   329
deba@1018
   330
        /// Initializes the object to be invalid.
deba@1018
   331
        /// \sa Invalid for more details.
deba@1018
   332
        Edge(Invalid) { }
deba@1018
   333
        /// Equality operator
deba@1018
   334
deba@1018
   335
        /// Equality operator.
deba@1018
   336
        ///
deba@1018
   337
        /// Two iterators are equal if and only if they point to the
deba@1018
   338
        /// same object or both are \c INVALID.
deba@1018
   339
        bool operator==(Edge) const { return true; }
deba@1018
   340
        /// Inequality operator
deba@1018
   341
deba@1018
   342
        /// Inequality operator.
deba@1018
   343
        bool operator!=(Edge) const { return true; }
deba@1018
   344
deba@1018
   345
        /// Artificial ordering operator.
deba@1018
   346
deba@1018
   347
        /// Artificial ordering operator.
deba@1018
   348
        ///
deba@1018
   349
        /// \note This operator only has to define some strict ordering of
deba@1018
   350
        /// the edges; this order has nothing to do with the iteration
deba@1018
   351
        /// ordering of the edges.
deba@1018
   352
        bool operator<(Edge) const { return false; }
deba@1018
   353
      };
deba@1018
   354
deba@1018
   355
      /// Iterator class for the edges.
deba@1018
   356
deba@1018
   357
      /// This iterator goes through each edge of the graph.
deba@1018
   358
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   359
      /// of edges in a graph \c g of type \c %BpGraph as follows:
deba@1018
   360
      ///\code
deba@1018
   361
      /// int count=0;
deba@1018
   362
      /// for(BpGraph::EdgeIt e(g); e!=INVALID; ++e) ++count;
deba@1018
   363
      ///\endcode
deba@1018
   364
      class EdgeIt : public Edge {
deba@1018
   365
      public:
deba@1018
   366
        /// Default constructor
deba@1018
   367
deba@1018
   368
        /// Default constructor.
deba@1018
   369
        /// \warning It sets the iterator to an undefined value.
deba@1018
   370
        EdgeIt() { }
deba@1018
   371
        /// Copy constructor.
deba@1018
   372
deba@1018
   373
        /// Copy constructor.
deba@1018
   374
        ///
deba@1018
   375
        EdgeIt(const EdgeIt& e) : Edge(e) { }
deba@1018
   376
        /// %Invalid constructor \& conversion.
deba@1018
   377
deba@1018
   378
        /// Initializes the iterator to be invalid.
deba@1018
   379
        /// \sa Invalid for more details.
deba@1018
   380
        EdgeIt(Invalid) { }
deba@1018
   381
        /// Sets the iterator to the first edge.
deba@1018
   382
deba@1018
   383
        /// Sets the iterator to the first edge of the given graph.
deba@1018
   384
        ///
deba@1018
   385
        explicit EdgeIt(const BpGraph&) { }
deba@1018
   386
        /// Sets the iterator to the given edge.
deba@1018
   387
deba@1018
   388
        /// Sets the iterator to the given edge of the given graph.
deba@1018
   389
        ///
deba@1018
   390
        EdgeIt(const BpGraph&, const Edge&) { }
deba@1018
   391
        /// Next edge
deba@1018
   392
deba@1018
   393
        /// Assign the iterator to the next edge.
deba@1018
   394
        ///
deba@1018
   395
        EdgeIt& operator++() { return *this; }
deba@1018
   396
      };
deba@1018
   397
deba@1018
   398
      /// Iterator class for the incident edges of a node.
deba@1018
   399
deba@1018
   400
      /// This iterator goes trough the incident undirected edges
deba@1018
   401
      /// of a certain node of a graph.
deba@1018
   402
      /// Its usage is quite simple, for example, you can compute the
deba@1018
   403
      /// degree (i.e. the number of incident edges) of a node \c n
deba@1018
   404
      /// in a graph \c g of type \c %BpGraph as follows.
deba@1018
   405
      ///
deba@1018
   406
      ///\code
deba@1018
   407
      /// int count=0;
deba@1018
   408
      /// for(BpGraph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
deba@1018
   409
      ///\endcode
deba@1018
   410
      ///
deba@1018
   411
      /// \warning Loop edges will be iterated twice.
deba@1018
   412
      class IncEdgeIt : public Edge {
deba@1018
   413
      public:
deba@1018
   414
        /// Default constructor
deba@1018
   415
deba@1018
   416
        /// Default constructor.
deba@1018
   417
        /// \warning It sets the iterator to an undefined value.
deba@1018
   418
        IncEdgeIt() { }
deba@1018
   419
        /// Copy constructor.
deba@1018
   420
deba@1018
   421
        /// Copy constructor.
deba@1018
   422
        ///
deba@1018
   423
        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
deba@1018
   424
        /// %Invalid constructor \& conversion.
deba@1018
   425
deba@1018
   426
        /// Initializes the iterator to be invalid.
deba@1018
   427
        /// \sa Invalid for more details.
deba@1018
   428
        IncEdgeIt(Invalid) { }
deba@1018
   429
        /// Sets the iterator to the first incident edge.
deba@1018
   430
deba@1018
   431
        /// Sets the iterator to the first incident edge of the given node.
deba@1018
   432
        ///
deba@1018
   433
        IncEdgeIt(const BpGraph&, const Node&) { }
deba@1018
   434
        /// Sets the iterator to the given edge.
deba@1018
   435
deba@1018
   436
        /// Sets the iterator to the given edge of the given graph.
deba@1018
   437
        ///
deba@1018
   438
        IncEdgeIt(const BpGraph&, const Edge&) { }
deba@1018
   439
        /// Next incident edge
deba@1018
   440
deba@1018
   441
        /// Assign the iterator to the next incident edge
deba@1018
   442
        /// of the corresponding node.
deba@1018
   443
        IncEdgeIt& operator++() { return *this; }
deba@1018
   444
      };
deba@1018
   445
deba@1018
   446
      /// The arc type of the graph
deba@1018
   447
deba@1018
   448
      /// This class identifies a directed arc of the graph. It also serves
deba@1018
   449
      /// as a base class of the arc iterators,
deba@1018
   450
      /// thus they will convert to this type.
deba@1018
   451
      class Arc {
deba@1018
   452
      public:
deba@1018
   453
        /// Default constructor
deba@1018
   454
deba@1018
   455
        /// Default constructor.
deba@1018
   456
        /// \warning It sets the object to an undefined value.
deba@1018
   457
        Arc() { }
deba@1018
   458
        /// Copy constructor.
deba@1018
   459
deba@1018
   460
        /// Copy constructor.
deba@1018
   461
        ///
deba@1018
   462
        Arc(const Arc&) { }
deba@1018
   463
        /// %Invalid constructor \& conversion.
deba@1018
   464
deba@1018
   465
        /// Initializes the object to be invalid.
deba@1018
   466
        /// \sa Invalid for more details.
deba@1018
   467
        Arc(Invalid) { }
deba@1018
   468
        /// Equality operator
deba@1018
   469
deba@1018
   470
        /// Equality operator.
deba@1018
   471
        ///
deba@1018
   472
        /// Two iterators are equal if and only if they point to the
deba@1018
   473
        /// same object or both are \c INVALID.
deba@1018
   474
        bool operator==(Arc) const { return true; }
deba@1018
   475
        /// Inequality operator
deba@1018
   476
deba@1018
   477
        /// Inequality operator.
deba@1018
   478
        bool operator!=(Arc) const { return true; }
deba@1018
   479
deba@1018
   480
        /// Artificial ordering operator.
deba@1018
   481
deba@1018
   482
        /// Artificial ordering operator.
deba@1018
   483
        ///
deba@1018
   484
        /// \note This operator only has to define some strict ordering of
deba@1018
   485
        /// the arcs; this order has nothing to do with the iteration
deba@1018
   486
        /// ordering of the arcs.
deba@1018
   487
        bool operator<(Arc) const { return false; }
deba@1018
   488
deba@1018
   489
        /// Converison to \c Edge
deba@1018
   490
deba@1018
   491
        /// Converison to \c Edge.
deba@1018
   492
        ///
deba@1018
   493
        operator Edge() const { return Edge(); }
deba@1018
   494
      };
deba@1018
   495
deba@1018
   496
      /// Iterator class for the arcs.
deba@1018
   497
deba@1018
   498
      /// This iterator goes through each directed arc of the graph.
deba@1018
   499
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   500
      /// of arcs in a graph \c g of type \c %BpGraph as follows:
deba@1018
   501
      ///\code
deba@1018
   502
      /// int count=0;
deba@1018
   503
      /// for(BpGraph::ArcIt a(g); a!=INVALID; ++a) ++count;
deba@1018
   504
      ///\endcode
deba@1018
   505
      class ArcIt : public Arc {
deba@1018
   506
      public:
deba@1018
   507
        /// Default constructor
deba@1018
   508
deba@1018
   509
        /// Default constructor.
deba@1018
   510
        /// \warning It sets the iterator to an undefined value.
deba@1018
   511
        ArcIt() { }
deba@1018
   512
        /// Copy constructor.
deba@1018
   513
deba@1018
   514
        /// Copy constructor.
deba@1018
   515
        ///
deba@1018
   516
        ArcIt(const ArcIt& e) : Arc(e) { }
deba@1018
   517
        /// %Invalid constructor \& conversion.
deba@1018
   518
deba@1018
   519
        /// Initializes the iterator to be invalid.
deba@1018
   520
        /// \sa Invalid for more details.
deba@1018
   521
        ArcIt(Invalid) { }
deba@1018
   522
        /// Sets the iterator to the first arc.
deba@1018
   523
deba@1018
   524
        /// Sets the iterator to the first arc of the given graph.
deba@1018
   525
        ///
deba@1018
   526
        explicit ArcIt(const BpGraph &g) { ignore_unused_variable_warning(g); }
deba@1018
   527
        /// Sets the iterator to the given arc.
deba@1018
   528
deba@1018
   529
        /// Sets the iterator to the given arc of the given graph.
deba@1018
   530
        ///
deba@1018
   531
        ArcIt(const BpGraph&, const Arc&) { }
deba@1018
   532
        /// Next arc
deba@1018
   533
deba@1018
   534
        /// Assign the iterator to the next arc.
deba@1018
   535
        ///
deba@1018
   536
        ArcIt& operator++() { return *this; }
deba@1018
   537
      };
deba@1018
   538
deba@1018
   539
      /// Iterator class for the outgoing arcs of a node.
deba@1018
   540
deba@1018
   541
      /// This iterator goes trough the \e outgoing directed arcs of a
deba@1018
   542
      /// certain node of a graph.
deba@1018
   543
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   544
      /// of outgoing arcs of a node \c n
deba@1018
   545
      /// in a graph \c g of type \c %BpGraph as follows.
deba@1018
   546
      ///\code
deba@1018
   547
      /// int count=0;
deba@1018
   548
      /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count;
deba@1018
   549
      ///\endcode
deba@1018
   550
      class OutArcIt : public Arc {
deba@1018
   551
      public:
deba@1018
   552
        /// Default constructor
deba@1018
   553
deba@1018
   554
        /// Default constructor.
deba@1018
   555
        /// \warning It sets the iterator to an undefined value.
deba@1018
   556
        OutArcIt() { }
deba@1018
   557
        /// Copy constructor.
deba@1018
   558
deba@1018
   559
        /// Copy constructor.
deba@1018
   560
        ///
deba@1018
   561
        OutArcIt(const OutArcIt& e) : Arc(e) { }
deba@1018
   562
        /// %Invalid constructor \& conversion.
deba@1018
   563
deba@1018
   564
        /// Initializes the iterator to be invalid.
deba@1018
   565
        /// \sa Invalid for more details.
deba@1018
   566
        OutArcIt(Invalid) { }
deba@1018
   567
        /// Sets the iterator to the first outgoing arc.
deba@1018
   568
deba@1018
   569
        /// Sets the iterator to the first outgoing arc of the given node.
deba@1018
   570
        ///
deba@1018
   571
        OutArcIt(const BpGraph& n, const Node& g) {
deba@1018
   572
          ignore_unused_variable_warning(n);
deba@1018
   573
          ignore_unused_variable_warning(g);
deba@1018
   574
        }
deba@1018
   575
        /// Sets the iterator to the given arc.
deba@1018
   576
deba@1018
   577
        /// Sets the iterator to the given arc of the given graph.
deba@1018
   578
        ///
deba@1018
   579
        OutArcIt(const BpGraph&, const Arc&) { }
deba@1018
   580
        /// Next outgoing arc
deba@1018
   581
deba@1018
   582
        /// Assign the iterator to the next
deba@1018
   583
        /// outgoing arc of the corresponding node.
deba@1018
   584
        OutArcIt& operator++() { return *this; }
deba@1018
   585
      };
deba@1018
   586
deba@1018
   587
      /// Iterator class for the incoming arcs of a node.
deba@1018
   588
deba@1018
   589
      /// This iterator goes trough the \e incoming directed arcs of a
deba@1018
   590
      /// certain node of a graph.
deba@1018
   591
      /// Its usage is quite simple, for example, you can count the number
deba@1018
   592
      /// of incoming arcs of a node \c n
deba@1018
   593
      /// in a graph \c g of type \c %BpGraph as follows.
deba@1018
   594
      ///\code
deba@1018
   595
      /// int count=0;
deba@1018
   596
      /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count;
deba@1018
   597
      ///\endcode
deba@1018
   598
      class InArcIt : public Arc {
deba@1018
   599
      public:
deba@1018
   600
        /// Default constructor
deba@1018
   601
deba@1018
   602
        /// Default constructor.
deba@1018
   603
        /// \warning It sets the iterator to an undefined value.
deba@1018
   604
        InArcIt() { }
deba@1018
   605
        /// Copy constructor.
deba@1018
   606
deba@1018
   607
        /// Copy constructor.
deba@1018
   608
        ///
deba@1018
   609
        InArcIt(const InArcIt& e) : Arc(e) { }
deba@1018
   610
        /// %Invalid constructor \& conversion.
deba@1018
   611
deba@1018
   612
        /// Initializes the iterator to be invalid.
deba@1018
   613
        /// \sa Invalid for more details.
deba@1018
   614
        InArcIt(Invalid) { }
deba@1018
   615
        /// Sets the iterator to the first incoming arc.
deba@1018
   616
deba@1018
   617
        /// Sets the iterator to the first incoming arc of the given node.
deba@1018
   618
        ///
deba@1018
   619
        InArcIt(const BpGraph& g, const Node& n) {
deba@1018
   620
          ignore_unused_variable_warning(n);
deba@1018
   621
          ignore_unused_variable_warning(g);
deba@1018
   622
        }
deba@1018
   623
        /// Sets the iterator to the given arc.
deba@1018
   624
deba@1018
   625
        /// Sets the iterator to the given arc of the given graph.
deba@1018
   626
        ///
deba@1018
   627
        InArcIt(const BpGraph&, const Arc&) { }
deba@1018
   628
        /// Next incoming arc
deba@1018
   629
deba@1018
   630
        /// Assign the iterator to the next
deba@1018
   631
        /// incoming arc of the corresponding node.
deba@1018
   632
        InArcIt& operator++() { return *this; }
deba@1018
   633
      };
deba@1018
   634
deba@1018
   635
      /// \brief Standard graph map type for the nodes.
deba@1018
   636
      ///
deba@1018
   637
      /// Standard graph map type for the nodes.
deba@1018
   638
      /// It conforms to the ReferenceMap concept.
deba@1018
   639
      template<class T>
deba@1018
   640
      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
deba@1018
   641
      {
deba@1018
   642
      public:
deba@1018
   643
deba@1018
   644
        /// Constructor
deba@1018
   645
        explicit NodeMap(const BpGraph&) { }
deba@1018
   646
        /// Constructor with given initial value
deba@1018
   647
        NodeMap(const BpGraph&, T) { }
deba@1018
   648
deba@1018
   649
      private:
deba@1018
   650
        ///Copy constructor
deba@1018
   651
        NodeMap(const NodeMap& nm) :
deba@1018
   652
          ReferenceMap<Node, T, T&, const T&>(nm) { }
deba@1018
   653
        ///Assignment operator
deba@1018
   654
        template <typename CMap>
deba@1018
   655
        NodeMap& operator=(const CMap&) {
deba@1018
   656
          checkConcept<ReadMap<Node, T>, CMap>();
deba@1018
   657
          return *this;
deba@1018
   658
        }
deba@1018
   659
      };
deba@1018
   660
deba@1018
   661
      /// \brief Standard graph map type for the red nodes.
deba@1018
   662
      ///
deba@1018
   663
      /// Standard graph map type for the red nodes.
deba@1018
   664
      /// It conforms to the ReferenceMap concept.
deba@1018
   665
      template<class T>
deba@1026
   666
      class RedNodeMap : public ReferenceMap<Node, T, T&, const T&>
deba@1018
   667
      {
deba@1018
   668
      public:
deba@1018
   669
deba@1018
   670
        /// Constructor
deba@1026
   671
        explicit RedNodeMap(const BpGraph&) { }
deba@1018
   672
        /// Constructor with given initial value
deba@1026
   673
        RedNodeMap(const BpGraph&, T) { }
deba@1018
   674
deba@1018
   675
      private:
deba@1018
   676
        ///Copy constructor
deba@1026
   677
        RedNodeMap(const RedNodeMap& nm) :
deba@1018
   678
          ReferenceMap<Node, T, T&, const T&>(nm) { }
deba@1018
   679
        ///Assignment operator
deba@1018
   680
        template <typename CMap>
deba@1026
   681
        RedNodeMap& operator=(const CMap&) {
deba@1018
   682
          checkConcept<ReadMap<Node, T>, CMap>();
deba@1018
   683
          return *this;
deba@1018
   684
        }
deba@1018
   685
      };
deba@1018
   686
deba@1018
   687
      /// \brief Standard graph map type for the blue nodes.
deba@1018
   688
      ///
deba@1018
   689
      /// Standard graph map type for the blue nodes.
deba@1018
   690
      /// It conforms to the ReferenceMap concept.
deba@1018
   691
      template<class T>
deba@1026
   692
      class BlueNodeMap : public ReferenceMap<Node, T, T&, const T&>
deba@1018
   693
      {
deba@1018
   694
      public:
deba@1018
   695
deba@1018
   696
        /// Constructor
deba@1026
   697
        explicit BlueNodeMap(const BpGraph&) { }
deba@1018
   698
        /// Constructor with given initial value
deba@1026
   699
        BlueNodeMap(const BpGraph&, T) { }
deba@1018
   700
deba@1018
   701
      private:
deba@1018
   702
        ///Copy constructor
deba@1026
   703
        BlueNodeMap(const BlueNodeMap& nm) :
deba@1018
   704
          ReferenceMap<Node, T, T&, const T&>(nm) { }
deba@1018
   705
        ///Assignment operator
deba@1018
   706
        template <typename CMap>
deba@1026
   707
        BlueNodeMap& operator=(const CMap&) {
deba@1018
   708
          checkConcept<ReadMap<Node, T>, CMap>();
deba@1018
   709
          return *this;
deba@1018
   710
        }
deba@1018
   711
      };
deba@1018
   712
deba@1018
   713
      /// \brief Standard graph map type for the arcs.
deba@1018
   714
      ///
deba@1018
   715
      /// Standard graph map type for the arcs.
deba@1018
   716
      /// It conforms to the ReferenceMap concept.
deba@1018
   717
      template<class T>
deba@1018
   718
      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
deba@1018
   719
      {
deba@1018
   720
      public:
deba@1018
   721
deba@1018
   722
        /// Constructor
deba@1018
   723
        explicit ArcMap(const BpGraph&) { }
deba@1018
   724
        /// Constructor with given initial value
deba@1018
   725
        ArcMap(const BpGraph&, T) { }
deba@1018
   726
deba@1018
   727
      private:
deba@1018
   728
        ///Copy constructor
deba@1018
   729
        ArcMap(const ArcMap& em) :
deba@1018
   730
          ReferenceMap<Arc, T, T&, const T&>(em) { }
deba@1018
   731
        ///Assignment operator
deba@1018
   732
        template <typename CMap>
deba@1018
   733
        ArcMap& operator=(const CMap&) {
deba@1018
   734
          checkConcept<ReadMap<Arc, T>, CMap>();
deba@1018
   735
          return *this;
deba@1018
   736
        }
deba@1018
   737
      };
deba@1018
   738
deba@1018
   739
      /// \brief Standard graph map type for the edges.
deba@1018
   740
      ///
deba@1018
   741
      /// Standard graph map type for the edges.
deba@1018
   742
      /// It conforms to the ReferenceMap concept.
deba@1018
   743
      template<class T>
deba@1018
   744
      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
deba@1018
   745
      {
deba@1018
   746
      public:
deba@1018
   747
deba@1018
   748
        /// Constructor
deba@1018
   749
        explicit EdgeMap(const BpGraph&) { }
deba@1018
   750
        /// Constructor with given initial value
deba@1018
   751
        EdgeMap(const BpGraph&, T) { }
deba@1018
   752
deba@1018
   753
      private:
deba@1018
   754
        ///Copy constructor
deba@1018
   755
        EdgeMap(const EdgeMap& em) :
deba@1018
   756
          ReferenceMap<Edge, T, T&, const T&>(em) {}
deba@1018
   757
        ///Assignment operator
deba@1018
   758
        template <typename CMap>
deba@1018
   759
        EdgeMap& operator=(const CMap&) {
deba@1018
   760
          checkConcept<ReadMap<Edge, T>, CMap>();
deba@1018
   761
          return *this;
deba@1018
   762
        }
deba@1018
   763
      };
deba@1018
   764
deba@1018
   765
      /// \brief Gives back %true for red nodes.
deba@1018
   766
      ///
deba@1018
   767
      /// Gives back %true for red nodes.
deba@1018
   768
      bool red(const Node&) const { return true; }
deba@1018
   769
deba@1018
   770
      /// \brief Gives back %true for blue nodes.
deba@1018
   771
      ///
deba@1018
   772
      /// Gives back %true for blue nodes.
deba@1018
   773
      bool blue(const Node&) const { return true; }
deba@1018
   774
deba@1025
   775
      /// \brief Converts the node to red node object.
deba@1025
   776
      ///
deba@1028
   777
      /// This function converts unsafely the node to red node
deba@1025
   778
      /// object. It should be called only if the node is from the red
deba@1025
   779
      /// partition or INVALID.
deba@1025
   780
      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
deba@1025
   781
deba@1025
   782
      /// \brief Converts the node to blue node object.
deba@1025
   783
      ///
deba@1028
   784
      /// This function converts unsafely the node to blue node
deba@1025
   785
      /// object. It should be called only if the node is from the red
deba@1025
   786
      /// partition or INVALID.
deba@1025
   787
      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
deba@1025
   788
deba@1025
   789
      /// \brief Converts the node to red node object.
deba@1025
   790
      ///
deba@1028
   791
      /// This function converts safely the node to red node
deba@1025
   792
      /// object. If the node is not from the red partition, then it
deba@1025
   793
      /// returns INVALID.
deba@1025
   794
      RedNode asRedNode(const Node&) const { return RedNode(); }
deba@1025
   795
deba@1025
   796
      /// \brief Converts the node to blue node object.
deba@1025
   797
      ///
deba@1028
   798
      /// This function converts unsafely the node to blue node
deba@1025
   799
      /// object. If the node is not from the blue partition, then it
deba@1025
   800
      /// returns INVALID.
deba@1025
   801
      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
deba@1025
   802
deba@1018
   803
      /// \brief Gives back the red end node of the edge.
deba@1018
   804
      /// 
deba@1018
   805
      /// Gives back the red end node of the edge.
deba@1025
   806
      RedNode redNode(const Edge&) const { return RedNode(); }
deba@1018
   807
deba@1018
   808
      /// \brief Gives back the blue end node of the edge.
deba@1018
   809
      /// 
deba@1018
   810
      /// Gives back the blue end node of the edge.
deba@1025
   811
      BlueNode blueNode(const Edge&) const { return BlueNode(); }
deba@1018
   812
deba@1018
   813
      /// \brief The first node of the edge.
deba@1018
   814
      ///
deba@1018
   815
      /// It is a synonim for the \c redNode().
deba@1018
   816
      Node u(Edge) const { return INVALID; }
deba@1018
   817
deba@1018
   818
      /// \brief The second node of the edge.
deba@1018
   819
      ///
deba@1018
   820
      /// It is a synonim for the \c blueNode().
deba@1018
   821
      Node v(Edge) const { return INVALID; }
deba@1018
   822
deba@1018
   823
      /// \brief The source node of the arc.
deba@1018
   824
      ///
deba@1018
   825
      /// Returns the source node of the given arc.
deba@1018
   826
      Node source(Arc) const { return INVALID; }
deba@1018
   827
deba@1018
   828
      /// \brief The target node of the arc.
deba@1018
   829
      ///
deba@1018
   830
      /// Returns the target node of the given arc.
deba@1018
   831
      Node target(Arc) const { return INVALID; }
deba@1018
   832
deba@1018
   833
      /// \brief The ID of the node.
deba@1018
   834
      ///
deba@1018
   835
      /// Returns the ID of the given node.
deba@1018
   836
      int id(Node) const { return -1; }
deba@1018
   837
deba@1018
   838
      /// \brief The red ID of the node.
deba@1018
   839
      ///
deba@1018
   840
      /// Returns the red ID of the given node.
deba@1018
   841
      int id(RedNode) const { return -1; }
deba@1018
   842
deba@1018
   843
      /// \brief The blue ID of the node.
deba@1018
   844
      ///
deba@1018
   845
      /// Returns the blue ID of the given node.
deba@1018
   846
      int id(BlueNode) const { return -1; }
deba@1018
   847
deba@1018
   848
      /// \brief The ID of the edge.
deba@1018
   849
      ///
deba@1018
   850
      /// Returns the ID of the given edge.
deba@1018
   851
      int id(Edge) const { return -1; }
deba@1018
   852
deba@1018
   853
      /// \brief The ID of the arc.
deba@1018
   854
      ///
deba@1018
   855
      /// Returns the ID of the given arc.
deba@1018
   856
      int id(Arc) const { return -1; }
deba@1018
   857
deba@1018
   858
      /// \brief The node with the given ID.
deba@1018
   859
      ///
deba@1018
   860
      /// Returns the node with the given ID.
deba@1018
   861
      /// \pre The argument should be a valid node ID in the graph.
deba@1018
   862
      Node nodeFromId(int) const { return INVALID; }
deba@1018
   863
deba@1018
   864
      /// \brief The edge with the given ID.
deba@1018
   865
      ///
deba@1018
   866
      /// Returns the edge with the given ID.
deba@1018
   867
      /// \pre The argument should be a valid edge ID in the graph.
deba@1018
   868
      Edge edgeFromId(int) const { return INVALID; }
deba@1018
   869
deba@1018
   870
      /// \brief The arc with the given ID.
deba@1018
   871
      ///
deba@1018
   872
      /// Returns the arc with the given ID.
deba@1018
   873
      /// \pre The argument should be a valid arc ID in the graph.
deba@1018
   874
      Arc arcFromId(int) const { return INVALID; }
deba@1018
   875
deba@1018
   876
      /// \brief An upper bound on the node IDs.
deba@1018
   877
      ///
deba@1018
   878
      /// Returns an upper bound on the node IDs.
deba@1018
   879
      int maxNodeId() const { return -1; }
deba@1018
   880
deba@1018
   881
      /// \brief An upper bound on the red IDs.
deba@1018
   882
      ///
deba@1018
   883
      /// Returns an upper bound on the red IDs.
deba@1018
   884
      int maxRedId() const { return -1; }
deba@1018
   885
deba@1018
   886
      /// \brief An upper bound on the blue IDs.
deba@1018
   887
      ///
deba@1018
   888
      /// Returns an upper bound on the blue IDs.
deba@1018
   889
      int maxBlueId() const { return -1; }
deba@1018
   890
deba@1018
   891
      /// \brief An upper bound on the edge IDs.
deba@1018
   892
      ///
deba@1018
   893
      /// Returns an upper bound on the edge IDs.
deba@1018
   894
      int maxEdgeId() const { return -1; }
deba@1018
   895
deba@1018
   896
      /// \brief An upper bound on the arc IDs.
deba@1018
   897
      ///
deba@1018
   898
      /// Returns an upper bound on the arc IDs.
deba@1018
   899
      int maxArcId() const { return -1; }
deba@1018
   900
deba@1018
   901
      /// \brief The direction of the arc.
deba@1018
   902
      ///
deba@1018
   903
      /// Returns \c true if the given arc goes from a red node to a blue node.
deba@1018
   904
      bool direction(Arc) const { return true; }
deba@1018
   905
deba@1018
   906
      /// \brief Direct the edge.
deba@1018
   907
      ///
deba@1018
   908
      /// Direct the given edge. The returned arc
deba@1018
   909
      /// represents the given edge and its direction comes
deba@1018
   910
      /// from the bool parameter. If it is \c true, then the source of the node
deba@1018
   911
      /// will be a red node.
deba@1018
   912
      Arc direct(Edge, bool) const {
deba@1018
   913
        return INVALID;
deba@1018
   914
      }
deba@1018
   915
deba@1018
   916
      /// \brief Direct the edge.
deba@1018
   917
      ///
deba@1018
   918
      /// Direct the given edge. The returned arc represents the given
deba@1018
   919
      /// edge and its source node is the given node.
deba@1018
   920
      Arc direct(Edge, Node) const {
deba@1018
   921
        return INVALID;
deba@1018
   922
      }
deba@1018
   923
deba@1018
   924
      /// \brief The oppositely directed arc.
deba@1018
   925
      ///
deba@1018
   926
      /// Returns the oppositely directed arc representing the same edge.
deba@1018
   927
      Arc oppositeArc(Arc) const { return INVALID; }
deba@1018
   928
deba@1018
   929
      /// \brief The opposite node on the edge.
deba@1018
   930
      ///
deba@1018
   931
      /// Returns the opposite node on the given edge.
deba@1018
   932
      Node oppositeNode(Node, Edge) const { return INVALID; }
deba@1018
   933
deba@1018
   934
      void first(Node&) const {}
deba@1018
   935
      void next(Node&) const {}
deba@1018
   936
deba@1025
   937
      void firstRed(RedNode&) const {}
deba@1025
   938
      void nextRed(RedNode&) const {}
deba@1018
   939
deba@1025
   940
      void firstBlue(BlueNode&) const {}
deba@1025
   941
      void nextBlue(BlueNode&) const {}
deba@1018
   942
deba@1018
   943
      void first(Edge&) const {}
deba@1018
   944
      void next(Edge&) const {}
deba@1018
   945
deba@1018
   946
      void first(Arc&) const {}
deba@1018
   947
      void next(Arc&) const {}
deba@1018
   948
deba@1018
   949
      void firstOut(Arc&, Node) const {}
deba@1018
   950
      void nextOut(Arc&) const {}
deba@1018
   951
deba@1018
   952
      void firstIn(Arc&, Node) const {}
deba@1018
   953
      void nextIn(Arc&) const {}
deba@1018
   954
deba@1018
   955
      void firstInc(Edge &, bool &, const Node &) const {}
deba@1018
   956
      void nextInc(Edge &, bool &) const {}
deba@1018
   957
deba@1018
   958
      // The second parameter is dummy.
deba@1018
   959
      Node fromId(int, Node) const { return INVALID; }
deba@1018
   960
      // The second parameter is dummy.
deba@1018
   961
      Edge fromId(int, Edge) const { return INVALID; }
deba@1018
   962
      // The second parameter is dummy.
deba@1018
   963
      Arc fromId(int, Arc) const { return INVALID; }
deba@1018
   964
deba@1018
   965
      // Dummy parameter.
deba@1018
   966
      int maxId(Node) const { return -1; }
deba@1018
   967
      // Dummy parameter.
deba@1018
   968
      int maxId(RedNode) const { return -1; }
deba@1018
   969
      // Dummy parameter.
deba@1018
   970
      int maxId(BlueNode) const { return -1; }
deba@1018
   971
      // Dummy parameter.
deba@1018
   972
      int maxId(Edge) const { return -1; }
deba@1018
   973
      // Dummy parameter.
deba@1018
   974
      int maxId(Arc) const { return -1; }
deba@1018
   975
deba@1018
   976
      /// \brief The base node of the iterator.
deba@1018
   977
      ///
deba@1018
   978
      /// Returns the base node of the given incident edge iterator.
deba@1018
   979
      Node baseNode(IncEdgeIt) const { return INVALID; }
deba@1018
   980
deba@1018
   981
      /// \brief The running node of the iterator.
deba@1018
   982
      ///
deba@1018
   983
      /// Returns the running node of the given incident edge iterator.
deba@1018
   984
      Node runningNode(IncEdgeIt) const { return INVALID; }
deba@1018
   985
deba@1018
   986
      /// \brief The base node of the iterator.
deba@1018
   987
      ///
deba@1018
   988
      /// Returns the base node of the given outgoing arc iterator
deba@1018
   989
      /// (i.e. the source node of the corresponding arc).
deba@1018
   990
      Node baseNode(OutArcIt) const { return INVALID; }
deba@1018
   991
deba@1018
   992
      /// \brief The running node of the iterator.
deba@1018
   993
      ///
deba@1018
   994
      /// Returns the running node of the given outgoing arc iterator
deba@1018
   995
      /// (i.e. the target node of the corresponding arc).
deba@1018
   996
      Node runningNode(OutArcIt) const { return INVALID; }
deba@1018
   997
deba@1018
   998
      /// \brief The base node of the iterator.
deba@1018
   999
      ///
deba@1018
  1000
      /// Returns the base node of the given incomming arc iterator
deba@1018
  1001
      /// (i.e. the target node of the corresponding arc).
deba@1018
  1002
      Node baseNode(InArcIt) const { return INVALID; }
deba@1018
  1003
deba@1018
  1004
      /// \brief The running node of the iterator.
deba@1018
  1005
      ///
deba@1018
  1006
      /// Returns the running node of the given incomming arc iterator
deba@1018
  1007
      /// (i.e. the source node of the corresponding arc).
deba@1018
  1008
      Node runningNode(InArcIt) const { return INVALID; }
deba@1018
  1009
deba@1018
  1010
      template <typename _BpGraph>
deba@1018
  1011
      struct Constraints {
deba@1018
  1012
        void constraints() {
deba@1018
  1013
          checkConcept<BaseBpGraphComponent, _BpGraph>();
deba@1018
  1014
          checkConcept<IterableBpGraphComponent<>, _BpGraph>();
deba@1018
  1015
          checkConcept<IDableBpGraphComponent<>, _BpGraph>();
deba@1018
  1016
          checkConcept<MappableBpGraphComponent<>, _BpGraph>();
deba@1018
  1017
        }
deba@1018
  1018
      };
deba@1018
  1019
deba@1018
  1020
    };
deba@1018
  1021
deba@1018
  1022
  }
deba@1018
  1023
deba@1018
  1024
}
deba@1018
  1025
deba@1018
  1026
#endif