lemon/concepts/graph_components.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 11 Jan 2012 22:58:05 +0100
changeset 1196 4441b066368c
parent 1195 8b2b9e61d8ce
child 1217 7bf489cf624e
permissions -rw-r--r--
Doc fix in BpGraphs (#69)
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@956
     5
 * Copyright (C) 2003-2010
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@833
    21
///\brief The concepts of graph components.
deba@57
    22
deba@576
    23
#ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H
deba@576
    24
#define LEMON_CONCEPTS_GRAPH_COMPONENTS_H
deba@57
    25
deba@220
    26
#include <lemon/core.h>
deba@57
    27
#include <lemon/concepts/maps.h>
deba@57
    28
deba@57
    29
#include <lemon/bits/alteration_notifier.h>
deba@57
    30
deba@57
    31
namespace lemon {
deba@57
    32
  namespace concepts {
deba@57
    33
kpeter@626
    34
    /// \brief Concept class for \c Node, \c Arc and \c Edge types.
deba@57
    35
    ///
kpeter@626
    36
    /// This class describes the concept of \c Node, \c Arc and \c Edge
kpeter@626
    37
    /// subtypes of digraph and graph types.
deba@57
    38
    ///
deba@57
    39
    /// \note This class is a template class so that we can use it to
kpeter@626
    40
    /// create graph skeleton classes. The reason for this is that \c Node
alpar@956
    41
    /// and \c Arc (or \c Edge) types should \e not derive from the same
kpeter@626
    42
    /// base class. For \c Node you should instantiate it with character
kpeter@626
    43
    /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'.
deba@57
    44
#ifndef DOXYGEN
kpeter@606
    45
    template <char sel = '0'>
deba@57
    46
#endif
deba@57
    47
    class GraphItem {
deba@57
    48
    public:
deba@57
    49
      /// \brief Default constructor.
alpar@209
    50
      ///
kpeter@626
    51
      /// Default constructor.
deba@57
    52
      /// \warning The default constructor is not required to set
deba@57
    53
      /// the item to some well-defined value. So you should consider it
deba@57
    54
      /// as uninitialized.
deba@57
    55
      GraphItem() {}
kpeter@626
    56
deba@57
    57
      /// \brief Copy constructor.
deba@57
    58
      ///
deba@57
    59
      /// Copy constructor.
kpeter@626
    60
      GraphItem(const GraphItem &) {}
kpeter@626
    61
kpeter@626
    62
      /// \brief Constructor for conversion from \c INVALID.
deba@57
    63
      ///
kpeter@626
    64
      /// Constructor for conversion from \c INVALID.
kpeter@626
    65
      /// It initializes the item to be invalid.
deba@57
    66
      /// \sa Invalid for more details.
deba@57
    67
      GraphItem(Invalid) {}
kpeter@626
    68
kpeter@626
    69
      /// \brief Assignment operator.
deba@57
    70
      ///
kpeter@626
    71
      /// Assignment operator for the item.
kpeter@626
    72
      GraphItem& operator=(const GraphItem&) { return *this; }
kpeter@626
    73
alpar@713
    74
      /// \brief Assignment operator for INVALID.
alpar@713
    75
      ///
alpar@713
    76
      /// This operator makes the item invalid.
alpar@713
    77
      GraphItem& operator=(Invalid) { return *this; }
alpar@713
    78
deba@57
    79
      /// \brief Equality operator.
deba@57
    80
      ///
kpeter@626
    81
      /// Equality operator.
kpeter@626
    82
      bool operator==(const GraphItem&) const { return false; }
kpeter@626
    83
deba@57
    84
      /// \brief Inequality operator.
deba@57
    85
      ///
kpeter@626
    86
      /// Inequality operator.
kpeter@626
    87
      bool operator!=(const GraphItem&) const { return false; }
kpeter@626
    88
kpeter@626
    89
      /// \brief Ordering operator.
deba@57
    90
      ///
kpeter@626
    91
      /// This operator defines an ordering of the items.
alpar@956
    92
      /// It makes possible to use graph item types as key types in
kpeter@626
    93
      /// associative containers (e.g. \c std::map).
deba@57
    94
      ///
kpeter@781
    95
      /// \note This operator only has to define some strict ordering of
deba@57
    96
      /// the items; this order has nothing to do with the iteration
deba@57
    97
      /// ordering of the items.
kpeter@626
    98
      bool operator<(const GraphItem&) const { return false; }
deba@57
    99
deba@57
   100
      template<typename _GraphItem>
deba@57
   101
      struct Constraints {
alpar@209
   102
        void constraints() {
alpar@209
   103
          _GraphItem i1;
alpar@713
   104
          i1=INVALID;
alpar@209
   105
          _GraphItem i2 = i1;
alpar@209
   106
          _GraphItem i3 = INVALID;
deba@57
   107
alpar@209
   108
          i1 = i2 = i3;
alpar@209
   109
alpar@209
   110
          bool b;
alpar@1171
   111
          ignore_unused_variable_warning(b);
alpar@1171
   112
alpar@209
   113
          b = (ia == ib) && (ia != ib);
alpar@209
   114
          b = (ia == INVALID) && (ib != INVALID);
deba@57
   115
          b = (ia < ib);
alpar@209
   116
        }
deba@57
   117
alpar@209
   118
        const _GraphItem &ia;
alpar@209
   119
        const _GraphItem &ib;
alpar@1125
   120
        Constraints() {}
deba@57
   121
      };
deba@57
   122
    };
deba@57
   123
kpeter@626
   124
    /// \brief Base skeleton class for directed graphs.
alpar@209
   125
    ///
kpeter@626
   126
    /// This class describes the base interface of directed graph types.
kpeter@626
   127
    /// All digraph %concepts have to conform to this class.
alpar@956
   128
    /// It just provides types for nodes and arcs and functions
kpeter@626
   129
    /// to get the source and the target nodes of arcs.
deba@57
   130
    class BaseDigraphComponent {
deba@57
   131
    public:
deba@57
   132
deba@57
   133
      typedef BaseDigraphComponent Digraph;
alpar@209
   134
deba@57
   135
      /// \brief Node class of the digraph.
deba@57
   136
      ///
kpeter@626
   137
      /// This class represents the nodes of the digraph.
deba@57
   138
      typedef GraphItem<'n'> Node;
deba@57
   139
deba@57
   140
      /// \brief Arc class of the digraph.
deba@57
   141
      ///
kpeter@626
   142
      /// This class represents the arcs of the digraph.
kpeter@626
   143
      typedef GraphItem<'a'> Arc;
kpeter@626
   144
kpeter@626
   145
      /// \brief Return the source node of an arc.
deba@57
   146
      ///
kpeter@626
   147
      /// This function returns the source node of an arc.
kpeter@626
   148
      Node source(const Arc&) const { return INVALID; }
deba@57
   149
kpeter@626
   150
      /// \brief Return the target node of an arc.
deba@57
   151
      ///
kpeter@626
   152
      /// This function returns the target node of an arc.
kpeter@626
   153
      Node target(const Arc&) const { return INVALID; }
kpeter@626
   154
kpeter@626
   155
      /// \brief Return the opposite node on the given arc.
deba@57
   156
      ///
kpeter@626
   157
      /// This function returns the opposite node on the given arc.
deba@57
   158
      Node oppositeNode(const Node&, const Arc&) const {
deba@57
   159
        return INVALID;
deba@57
   160
      }
deba@57
   161
deba@57
   162
      template <typename _Digraph>
deba@57
   163
      struct Constraints {
alpar@209
   164
        typedef typename _Digraph::Node Node;
alpar@209
   165
        typedef typename _Digraph::Arc Arc;
alpar@209
   166
alpar@209
   167
        void constraints() {
alpar@209
   168
          checkConcept<GraphItem<'n'>, Node>();
alpar@209
   169
          checkConcept<GraphItem<'a'>, Arc>();
alpar@209
   170
          {
alpar@209
   171
            Node n;
alpar@209
   172
            Arc e(INVALID);
alpar@209
   173
            n = digraph.source(e);
alpar@209
   174
            n = digraph.target(e);
deba@57
   175
            n = digraph.oppositeNode(n, e);
alpar@209
   176
          }
alpar@209
   177
        }
alpar@209
   178
alpar@209
   179
        const _Digraph& digraph;
alpar@1125
   180
        Constraints() {}
deba@57
   181
      };
deba@57
   182
    };
deba@57
   183
kpeter@626
   184
    /// \brief Base skeleton class for undirected graphs.
alpar@209
   185
    ///
kpeter@626
   186
    /// This class describes the base interface of undirected graph types.
kpeter@626
   187
    /// All graph %concepts have to conform to this class.
kpeter@626
   188
    /// It extends the interface of \ref BaseDigraphComponent with an
kpeter@626
   189
    /// \c Edge type and functions to get the end nodes of edges,
kpeter@626
   190
    /// to convert from arcs to edges and to get both direction of edges.
deba@57
   191
    class BaseGraphComponent : public BaseDigraphComponent {
deba@57
   192
    public:
kpeter@664
   193
kpeter@664
   194
      typedef BaseGraphComponent Graph;
kpeter@664
   195
deba@57
   196
      typedef BaseDigraphComponent::Node Node;
deba@57
   197
      typedef BaseDigraphComponent::Arc Arc;
kpeter@626
   198
kpeter@626
   199
      /// \brief Undirected edge class of the graph.
deba@57
   200
      ///
kpeter@626
   201
      /// This class represents the undirected edges of the graph.
kpeter@626
   202
      /// Undirected graphs can be used as directed graphs, each edge is
kpeter@626
   203
      /// represented by two opposite directed arcs.
kpeter@626
   204
      class Edge : public GraphItem<'e'> {
kpeter@626
   205
        typedef GraphItem<'e'> Parent;
kpeter@626
   206
kpeter@664
   207
      public:
deba@57
   208
        /// \brief Default constructor.
alpar@209
   209
        ///
kpeter@626
   210
        /// Default constructor.
deba@57
   211
        /// \warning The default constructor is not required to set
deba@57
   212
        /// the item to some well-defined value. So you should consider it
deba@57
   213
        /// as uninitialized.
deba@57
   214
        Edge() {}
kpeter@626
   215
deba@57
   216
        /// \brief Copy constructor.
deba@57
   217
        ///
deba@57
   218
        /// Copy constructor.
kpeter@626
   219
        Edge(const Edge &) : Parent() {}
kpeter@626
   220
kpeter@626
   221
        /// \brief Constructor for conversion from \c INVALID.
deba@57
   222
        ///
kpeter@626
   223
        /// Constructor for conversion from \c INVALID.
kpeter@626
   224
        /// It initializes the item to be invalid.
deba@57
   225
        /// \sa Invalid for more details.
deba@57
   226
        Edge(Invalid) {}
kpeter@626
   227
kpeter@626
   228
        /// \brief Constructor for conversion from an arc.
deba@57
   229
        ///
kpeter@626
   230
        /// Constructor for conversion from an arc.
deba@57
   231
        /// Besides the core graph item functionality each arc should
alpar@209
   232
        /// be convertible to the represented edge.
deba@57
   233
        Edge(const Arc&) {}
alpar@713
   234
     };
deba@57
   235
kpeter@626
   236
      /// \brief Return one end node of an edge.
kpeter@626
   237
      ///
kpeter@626
   238
      /// This function returns one end node of an edge.
kpeter@626
   239
      Node u(const Edge&) const { return INVALID; }
kpeter@626
   240
kpeter@626
   241
      /// \brief Return the other end node of an edge.
kpeter@626
   242
      ///
kpeter@626
   243
      /// This function returns the other end node of an edge.
kpeter@626
   244
      Node v(const Edge&) const { return INVALID; }
kpeter@626
   245
kpeter@626
   246
      /// \brief Return a directed arc related to an edge.
kpeter@626
   247
      ///
kpeter@626
   248
      /// This function returns a directed arc from its direction and the
kpeter@626
   249
      /// represented edge.
kpeter@626
   250
      Arc direct(const Edge&, bool) const { return INVALID; }
kpeter@626
   251
kpeter@626
   252
      /// \brief Return a directed arc related to an edge.
kpeter@626
   253
      ///
kpeter@626
   254
      /// This function returns a directed arc from its source node and the
kpeter@626
   255
      /// represented edge.
kpeter@626
   256
      Arc direct(const Edge&, const Node&) const { return INVALID; }
kpeter@626
   257
kpeter@626
   258
      /// \brief Return the direction of the arc.
deba@57
   259
      ///
deba@57
   260
      /// Returns the direction of the arc. Each arc represents an
deba@57
   261
      /// edge with a direction. It gives back the
deba@57
   262
      /// direction.
deba@57
   263
      bool direction(const Arc&) const { return true; }
deba@57
   264
kpeter@626
   265
      /// \brief Return the opposite arc.
deba@57
   266
      ///
kpeter@626
   267
      /// This function returns the opposite arc, i.e. the arc representing
kpeter@626
   268
      /// the same edge and has opposite direction.
kpeter@626
   269
      Arc oppositeArc(const Arc&) const { return INVALID; }
alpar@209
   270
deba@57
   271
      template <typename _Graph>
deba@57
   272
      struct Constraints {
alpar@209
   273
        typedef typename _Graph::Node Node;
alpar@209
   274
        typedef typename _Graph::Arc Arc;
alpar@209
   275
        typedef typename _Graph::Edge Edge;
alpar@209
   276
alpar@209
   277
        void constraints() {
deba@57
   278
          checkConcept<BaseDigraphComponent, _Graph>();
kpeter@626
   279
          checkConcept<GraphItem<'e'>, Edge>();
alpar@209
   280
          {
alpar@209
   281
            Node n;
alpar@209
   282
            Edge ue(INVALID);
deba@57
   283
            Arc e;
alpar@209
   284
            n = graph.u(ue);
alpar@209
   285
            n = graph.v(ue);
deba@57
   286
            e = graph.direct(ue, true);
kpeter@626
   287
            e = graph.direct(ue, false);
deba@57
   288
            e = graph.direct(ue, n);
deba@57
   289
            e = graph.oppositeArc(e);
deba@57
   290
            ue = e;
deba@57
   291
            bool d = graph.direction(e);
deba@57
   292
            ignore_unused_variable_warning(d);
alpar@209
   293
          }
alpar@209
   294
        }
alpar@209
   295
alpar@209
   296
        const _Graph& graph;
alpar@1125
   297
      Constraints() {}
deba@57
   298
      };
deba@57
   299
deba@57
   300
    };
deba@57
   301
deba@1186
   302
    /// \brief Base skeleton class for undirected bipartite graphs.
deba@1186
   303
    ///
deba@1186
   304
    /// This class describes the base interface of undirected
deba@1186
   305
    /// bipartite graph types.  All bipartite graph %concepts have to
deba@1186
   306
    /// conform to this class.  It extends the interface of \ref
deba@1186
   307
    /// BaseGraphComponent with an \c Edge type and functions to get
deba@1186
   308
    /// the end nodes of edges, to convert from arcs to edges and to
deba@1186
   309
    /// get both direction of edges.
deba@1186
   310
    class BaseBpGraphComponent : public BaseGraphComponent {
deba@1186
   311
    public:
deba@1186
   312
deba@1186
   313
      typedef BaseBpGraphComponent BpGraph;
deba@1186
   314
deba@1186
   315
      typedef BaseDigraphComponent::Node Node;
deba@1186
   316
      typedef BaseDigraphComponent::Arc Arc;
deba@1186
   317
deba@1186
   318
      /// \brief Class to represent red nodes.
deba@1186
   319
      ///
deba@1193
   320
      /// This class represents the red nodes of the graph. The red
deba@1196
   321
      /// nodes can also be used as normal nodes.
deba@1186
   322
      class RedNode : public Node {
deba@1186
   323
        typedef Node Parent;
deba@1186
   324
deba@1186
   325
      public:
deba@1186
   326
        /// \brief Default constructor.
deba@1186
   327
        ///
deba@1186
   328
        /// Default constructor.
deba@1186
   329
        /// \warning The default constructor is not required to set
deba@1186
   330
        /// the item to some well-defined value. So you should consider it
deba@1186
   331
        /// as uninitialized.
deba@1186
   332
        RedNode() {}
deba@1186
   333
deba@1186
   334
        /// \brief Copy constructor.
deba@1186
   335
        ///
deba@1186
   336
        /// Copy constructor.
deba@1186
   337
        RedNode(const RedNode &) : Parent() {}
deba@1186
   338
deba@1186
   339
        /// \brief Constructor for conversion from \c INVALID.
deba@1186
   340
        ///
deba@1186
   341
        /// Constructor for conversion from \c INVALID.
deba@1186
   342
        /// It initializes the item to be invalid.
deba@1186
   343
        /// \sa Invalid for more details.
deba@1186
   344
        RedNode(Invalid) {}
deba@1186
   345
      };
deba@1186
   346
deba@1186
   347
      /// \brief Class to represent blue nodes.
deba@1186
   348
      ///
deba@1193
   349
      /// This class represents the blue nodes of the graph. The blue
deba@1196
   350
      /// nodes can also be used as normal nodes.
deba@1186
   351
      class BlueNode : public Node {
deba@1186
   352
        typedef Node Parent;
deba@1186
   353
deba@1186
   354
      public:
deba@1186
   355
        /// \brief Default constructor.
deba@1186
   356
        ///
deba@1186
   357
        /// Default constructor.
deba@1186
   358
        /// \warning The default constructor is not required to set
deba@1186
   359
        /// the item to some well-defined value. So you should consider it
deba@1186
   360
        /// as uninitialized.
deba@1186
   361
        BlueNode() {}
deba@1186
   362
deba@1186
   363
        /// \brief Copy constructor.
deba@1186
   364
        ///
deba@1186
   365
        /// Copy constructor.
deba@1186
   366
        BlueNode(const BlueNode &) : Parent() {}
deba@1186
   367
deba@1186
   368
        /// \brief Constructor for conversion from \c INVALID.
deba@1186
   369
        ///
deba@1186
   370
        /// Constructor for conversion from \c INVALID.
deba@1186
   371
        /// It initializes the item to be invalid.
deba@1186
   372
        /// \sa Invalid for more details.
deba@1186
   373
        BlueNode(Invalid) {}
deba@1186
   374
deba@1186
   375
        /// \brief Constructor for conversion from a node.
deba@1186
   376
        ///
deba@1186
   377
        /// Constructor for conversion from a node. The conversion can
deba@1186
   378
        /// be invalid, since the Node can be member of the red
deba@1186
   379
        /// set.
deba@1186
   380
        BlueNode(const Node&) {}
deba@1186
   381
      };
deba@1186
   382
deba@1186
   383
      /// \brief Gives back %true for red nodes.
deba@1186
   384
      ///
deba@1186
   385
      /// Gives back %true for red nodes.
deba@1186
   386
      bool red(const Node&) const { return true; }
deba@1186
   387
deba@1186
   388
      /// \brief Gives back %true for blue nodes.
deba@1186
   389
      ///
deba@1186
   390
      /// Gives back %true for blue nodes.
deba@1186
   391
      bool blue(const Node&) const { return true; }
deba@1186
   392
deba@1186
   393
      /// \brief Gives back the red end node of the edge.
deba@1186
   394
      /// 
deba@1186
   395
      /// Gives back the red end node of the edge.
deba@1193
   396
      RedNode redNode(const Edge&) const { return RedNode(); }
deba@1186
   397
deba@1186
   398
      /// \brief Gives back the blue end node of the edge.
deba@1186
   399
      /// 
deba@1186
   400
      /// Gives back the blue end node of the edge.
deba@1193
   401
      BlueNode blueNode(const Edge&) const { return BlueNode(); }
deba@1193
   402
deba@1193
   403
      /// \brief Converts the node to red node object.
deba@1193
   404
      ///
deba@1196
   405
      /// This function converts unsafely the node to red node
deba@1193
   406
      /// object. It should be called only if the node is from the red
deba@1193
   407
      /// partition or INVALID.
deba@1193
   408
      RedNode asRedNodeUnsafe(const Node&) const { return RedNode(); }
deba@1193
   409
deba@1193
   410
      /// \brief Converts the node to blue node object.
deba@1193
   411
      ///
deba@1196
   412
      /// This function converts unsafely the node to blue node
deba@1193
   413
      /// object. It should be called only if the node is from the red
deba@1193
   414
      /// partition or INVALID.
deba@1193
   415
      BlueNode asBlueNodeUnsafe(const Node&) const { return BlueNode(); }
deba@1193
   416
deba@1193
   417
      /// \brief Converts the node to red node object.
deba@1193
   418
      ///
deba@1196
   419
      /// This function converts safely the node to red node
deba@1193
   420
      /// object. If the node is not from the red partition, then it
deba@1193
   421
      /// returns INVALID.
deba@1193
   422
      RedNode asRedNode(const Node&) const { return RedNode(); }
deba@1193
   423
deba@1193
   424
      /// \brief Converts the node to blue node object.
deba@1193
   425
      ///
deba@1196
   426
      /// This function converts unsafely the node to blue node
deba@1193
   427
      /// object. If the node is not from the blue partition, then it
deba@1193
   428
      /// returns INVALID.
deba@1193
   429
      BlueNode asBlueNode(const Node&) const { return BlueNode(); }
deba@1193
   430
deba@1186
   431
      template <typename _BpGraph>
deba@1186
   432
      struct Constraints {
deba@1186
   433
        typedef typename _BpGraph::Node Node;
deba@1186
   434
        typedef typename _BpGraph::RedNode RedNode;
deba@1186
   435
        typedef typename _BpGraph::BlueNode BlueNode;
deba@1186
   436
        typedef typename _BpGraph::Arc Arc;
deba@1186
   437
        typedef typename _BpGraph::Edge Edge;
deba@1186
   438
deba@1186
   439
        void constraints() {
deba@1186
   440
          checkConcept<BaseGraphComponent, _BpGraph>();
deba@1186
   441
          checkConcept<GraphItem<'n'>, RedNode>();
deba@1186
   442
          checkConcept<GraphItem<'n'>, BlueNode>();
deba@1186
   443
          {
deba@1186
   444
            Node n;
deba@1193
   445
            RedNode rn;
deba@1193
   446
            BlueNode bn;
deba@1193
   447
            Node rnan = rn;
deba@1193
   448
            Node bnan = bn;
deba@1186
   449
            Edge e;
deba@1186
   450
            bool b;
deba@1193
   451
            b = bpgraph.red(rnan);
deba@1193
   452
            b = bpgraph.blue(bnan);
deba@1193
   453
            rn = bpgraph.redNode(e);
deba@1193
   454
            bn = bpgraph.blueNode(e);
deba@1193
   455
            rn = bpgraph.asRedNodeUnsafe(rnan);
deba@1193
   456
            bn = bpgraph.asBlueNodeUnsafe(bnan);
deba@1193
   457
            rn = bpgraph.asRedNode(rnan);
deba@1193
   458
            bn = bpgraph.asBlueNode(bnan);
deba@1195
   459
            ignore_unused_variable_warning(b);
deba@1186
   460
          }
deba@1186
   461
        }
deba@1186
   462
deba@1186
   463
        const _BpGraph& bpgraph;
deba@1186
   464
      };
deba@1186
   465
deba@1186
   466
    };
deba@1186
   467
kpeter@626
   468
    /// \brief Skeleton class for \e idable directed graphs.
alpar@209
   469
    ///
kpeter@626
   470
    /// This class describes the interface of \e idable directed graphs.
kpeter@626
   471
    /// It extends \ref BaseDigraphComponent with the core ID functions.
kpeter@626
   472
    /// The ids of the items must be unique and immutable.
kpeter@626
   473
    /// This concept is part of the Digraph concept.
kpeter@606
   474
    template <typename BAS = BaseDigraphComponent>
kpeter@606
   475
    class IDableDigraphComponent : public BAS {
deba@57
   476
    public:
deba@57
   477
kpeter@606
   478
      typedef BAS Base;
deba@57
   479
      typedef typename Base::Node Node;
deba@57
   480
      typedef typename Base::Arc Arc;
deba@57
   481
kpeter@626
   482
      /// \brief Return a unique integer id for the given node.
deba@57
   483
      ///
kpeter@626
   484
      /// This function returns a unique integer id for the given node.
kpeter@626
   485
      int id(const Node&) const { return -1; }
kpeter@626
   486
kpeter@626
   487
      /// \brief Return the node by its unique id.
deba@57
   488
      ///
kpeter@626
   489
      /// This function returns the node by its unique id.
kpeter@626
   490
      /// If the digraph does not contain a node with the given id,
kpeter@626
   491
      /// then the result of the function is undefined.
kpeter@626
   492
      Node nodeFromId(int) const { return INVALID; }
deba@57
   493
kpeter@626
   494
      /// \brief Return a unique integer id for the given arc.
deba@57
   495
      ///
kpeter@626
   496
      /// This function returns a unique integer id for the given arc.
kpeter@626
   497
      int id(const Arc&) const { return -1; }
deba@57
   498
kpeter@626
   499
      /// \brief Return the arc by its unique id.
deba@57
   500
      ///
kpeter@626
   501
      /// This function returns the arc by its unique id.
kpeter@626
   502
      /// If the digraph does not contain an arc with the given id,
kpeter@626
   503
      /// then the result of the function is undefined.
kpeter@626
   504
      Arc arcFromId(int) const { return INVALID; }
kpeter@626
   505
kpeter@626
   506
      /// \brief Return an integer greater or equal to the maximum
kpeter@626
   507
      /// node id.
deba@57
   508
      ///
kpeter@626
   509
      /// This function returns an integer greater or equal to the
kpeter@626
   510
      /// maximum node id.
kpeter@626
   511
      int maxNodeId() const { return -1; }
deba@57
   512
kpeter@626
   513
      /// \brief Return an integer greater or equal to the maximum
kpeter@626
   514
      /// arc id.
deba@57
   515
      ///
kpeter@626
   516
      /// This function returns an integer greater or equal to the
kpeter@626
   517
      /// maximum arc id.
kpeter@626
   518
      int maxArcId() const { return -1; }
deba@57
   519
deba@57
   520
      template <typename _Digraph>
deba@57
   521
      struct Constraints {
deba@57
   522
alpar@209
   523
        void constraints() {
alpar@209
   524
          checkConcept<Base, _Digraph >();
alpar@209
   525
          typename _Digraph::Node node;
alpar@713
   526
          node=INVALID;
alpar@209
   527
          int nid = digraph.id(node);
alpar@209
   528
          nid = digraph.id(node);
alpar@209
   529
          node = digraph.nodeFromId(nid);
alpar@209
   530
          typename _Digraph::Arc arc;
alpar@713
   531
          arc=INVALID;
alpar@209
   532
          int eid = digraph.id(arc);
alpar@209
   533
          eid = digraph.id(arc);
alpar@209
   534
          arc = digraph.arcFromId(eid);
deba@57
   535
alpar@209
   536
          nid = digraph.maxNodeId();
alpar@209
   537
          ignore_unused_variable_warning(nid);
alpar@209
   538
          eid = digraph.maxArcId();
alpar@209
   539
          ignore_unused_variable_warning(eid);
alpar@209
   540
        }
deba@57
   541
alpar@209
   542
        const _Digraph& digraph;
alpar@1125
   543
        Constraints() {}
deba@57
   544
      };
deba@57
   545
    };
deba@57
   546
kpeter@626
   547
    /// \brief Skeleton class for \e idable undirected graphs.
alpar@209
   548
    ///
kpeter@626
   549
    /// This class describes the interface of \e idable undirected
kpeter@626
   550
    /// graphs. It extends \ref IDableDigraphComponent with the core ID
kpeter@626
   551
    /// functions of undirected graphs.
kpeter@626
   552
    /// The ids of the items must be unique and immutable.
kpeter@626
   553
    /// This concept is part of the Graph concept.
kpeter@606
   554
    template <typename BAS = BaseGraphComponent>
kpeter@606
   555
    class IDableGraphComponent : public IDableDigraphComponent<BAS> {
deba@57
   556
    public:
deba@57
   557
kpeter@606
   558
      typedef BAS Base;
deba@57
   559
      typedef typename Base::Edge Edge;
deba@57
   560
kpeter@606
   561
      using IDableDigraphComponent<Base>::id;
deba@57
   562
kpeter@626
   563
      /// \brief Return a unique integer id for the given edge.
deba@57
   564
      ///
kpeter@626
   565
      /// This function returns a unique integer id for the given edge.
kpeter@626
   566
      int id(const Edge&) const { return -1; }
kpeter@626
   567
kpeter@626
   568
      /// \brief Return the edge by its unique id.
deba@57
   569
      ///
kpeter@626
   570
      /// This function returns the edge by its unique id.
kpeter@626
   571
      /// If the graph does not contain an edge with the given id,
kpeter@626
   572
      /// then the result of the function is undefined.
kpeter@626
   573
      Edge edgeFromId(int) const { return INVALID; }
deba@57
   574
kpeter@626
   575
      /// \brief Return an integer greater or equal to the maximum
kpeter@626
   576
      /// edge id.
deba@57
   577
      ///
kpeter@626
   578
      /// This function returns an integer greater or equal to the
kpeter@626
   579
      /// maximum edge id.
kpeter@626
   580
      int maxEdgeId() const { return -1; }
deba@57
   581
deba@57
   582
      template <typename _Graph>
deba@57
   583
      struct Constraints {
deba@57
   584
alpar@209
   585
        void constraints() {
alpar@209
   586
          checkConcept<IDableDigraphComponent<Base>, _Graph >();
alpar@209
   587
          typename _Graph::Edge edge;
alpar@209
   588
          int ueid = graph.id(edge);
alpar@209
   589
          ueid = graph.id(edge);
alpar@209
   590
          edge = graph.edgeFromId(ueid);
alpar@209
   591
          ueid = graph.maxEdgeId();
alpar@209
   592
          ignore_unused_variable_warning(ueid);
alpar@209
   593
        }
deba@57
   594
alpar@209
   595
        const _Graph& graph;
alpar@1125
   596
        Constraints() {}
deba@57
   597
      };
deba@57
   598
    };
deba@57
   599
deba@1186
   600
    /// \brief Skeleton class for \e idable undirected bipartite graphs.
deba@1186
   601
    ///
deba@1186
   602
    /// This class describes the interface of \e idable undirected
deba@1186
   603
    /// bipartite graphs. It extends \ref IDableGraphComponent with
deba@1186
   604
    /// the core ID functions of undirected bipartite graphs. Beside
deba@1186
   605
    /// the regular node ids, this class also provides ids within the
deba@1186
   606
    /// the red and blue sets of the nodes. This concept is part of
deba@1186
   607
    /// the BpGraph concept.
deba@1186
   608
    template <typename BAS = BaseBpGraphComponent>
deba@1186
   609
    class IDableBpGraphComponent : public IDableGraphComponent<BAS> {
deba@1186
   610
    public:
deba@1186
   611
deba@1186
   612
      typedef BAS Base;
deba@1186
   613
      typedef IDableGraphComponent<BAS> Parent;
deba@1186
   614
      typedef typename Base::Node Node;
deba@1186
   615
      typedef typename Base::RedNode RedNode;
deba@1186
   616
      typedef typename Base::BlueNode BlueNode;
deba@1186
   617
deba@1186
   618
      using Parent::id;
deba@1186
   619
deba@1186
   620
      /// \brief Return a unique integer id for the given node in the red set.
deba@1186
   621
      ///
deba@1186
   622
      /// Return a unique integer id for the given node in the red set.
deba@1186
   623
      int id(const RedNode&) const { return -1; }
deba@1186
   624
deba@1186
   625
      /// \brief Return a unique integer id for the given node in the blue set.
deba@1186
   626
      ///
deba@1186
   627
      /// Return a unique integer id for the given node in the blue set.
deba@1186
   628
      int id(const BlueNode&) const { return -1; }
deba@1186
   629
deba@1186
   630
      /// \brief Return an integer greater or equal to the maximum
deba@1186
   631
      /// node id in the red set.
deba@1186
   632
      ///
deba@1186
   633
      /// Return an integer greater or equal to the maximum
deba@1186
   634
      /// node id in the red set.
deba@1186
   635
      int maxRedId() const { return -1; }
deba@1186
   636
deba@1186
   637
      /// \brief Return an integer greater or equal to the maximum
deba@1186
   638
      /// node id in the blue set.
deba@1186
   639
      ///
deba@1186
   640
      /// Return an integer greater or equal to the maximum
deba@1186
   641
      /// node id in the blue set.
deba@1186
   642
      int maxBlueId() const { return -1; }
deba@1186
   643
deba@1186
   644
      template <typename _BpGraph>
deba@1186
   645
      struct Constraints {
deba@1186
   646
deba@1186
   647
        void constraints() {
deba@1186
   648
          checkConcept<IDableGraphComponent<Base>, _BpGraph>();
deba@1186
   649
          typename _BpGraph::Node node;
deba@1186
   650
          typename _BpGraph::RedNode red;
deba@1186
   651
          typename _BpGraph::BlueNode blue;
deba@1193
   652
          int rid = bpgraph.id(red);
deba@1193
   653
          int bid = bpgraph.id(blue);
deba@1186
   654
          rid = bpgraph.maxRedId();
deba@1186
   655
          bid = bpgraph.maxBlueId();
deba@1186
   656
          ignore_unused_variable_warning(rid);
deba@1186
   657
          ignore_unused_variable_warning(bid);
deba@1186
   658
        }
deba@1186
   659
deba@1186
   660
        const _BpGraph& bpgraph;
deba@1186
   661
      };
deba@1186
   662
    };
deba@1186
   663
kpeter@626
   664
    /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types.
deba@57
   665
    ///
alpar@956
   666
    /// This class describes the concept of \c NodeIt, \c ArcIt and
kpeter@626
   667
    /// \c EdgeIt subtypes of digraph and graph types.
kpeter@606
   668
    template <typename GR, typename Item>
kpeter@606
   669
    class GraphItemIt : public Item {
deba@57
   670
    public:
deba@57
   671
      /// \brief Default constructor.
deba@57
   672
      ///
kpeter@626
   673
      /// Default constructor.
kpeter@626
   674
      /// \warning The default constructor is not required to set
kpeter@626
   675
      /// the iterator to some well-defined value. So you should consider it
kpeter@626
   676
      /// as uninitialized.
deba@57
   677
      GraphItemIt() {}
kpeter@626
   678
deba@57
   679
      /// \brief Copy constructor.
deba@57
   680
      ///
deba@57
   681
      /// Copy constructor.
kpeter@626
   682
      GraphItemIt(const GraphItemIt& it) : Item(it) {}
kpeter@626
   683
kpeter@626
   684
      /// \brief Constructor that sets the iterator to the first item.
deba@57
   685
      ///
kpeter@626
   686
      /// Constructor that sets the iterator to the first item.
kpeter@626
   687
      explicit GraphItemIt(const GR&) {}
kpeter@626
   688
kpeter@626
   689
      /// \brief Constructor for conversion from \c INVALID.
deba@57
   690
      ///
kpeter@626
   691
      /// Constructor for conversion from \c INVALID.
kpeter@626
   692
      /// It initializes the iterator to be invalid.
deba@57
   693
      /// \sa Invalid for more details.
deba@57
   694
      GraphItemIt(Invalid) {}
kpeter@626
   695
kpeter@626
   696
      /// \brief Assignment operator.
deba@57
   697
      ///
kpeter@626
   698
      /// Assignment operator for the iterator.
kpeter@626
   699
      GraphItemIt& operator=(const GraphItemIt&) { return *this; }
kpeter@626
   700
kpeter@626
   701
      /// \brief Increment the iterator.
deba@57
   702
      ///
kpeter@626
   703
      /// This operator increments the iterator, i.e. assigns it to the
kpeter@626
   704
      /// next item.
deba@57
   705
      GraphItemIt& operator++() { return *this; }
alpar@956
   706
deba@57
   707
      /// \brief Equality operator
alpar@209
   708
      ///
kpeter@626
   709
      /// Equality operator.
deba@57
   710
      /// Two iterators are equal if and only if they point to the
deba@57
   711
      /// same object or both are invalid.
deba@57
   712
      bool operator==(const GraphItemIt&) const { return true;}
kpeter@626
   713
deba@57
   714
      /// \brief Inequality operator
alpar@209
   715
      ///
kpeter@626
   716
      /// Inequality operator.
kpeter@626
   717
      /// Two iterators are equal if and only if they point to the
kpeter@626
   718
      /// same object or both are invalid.
deba@57
   719
      bool operator!=(const GraphItemIt&) const { return true;}
alpar@209
   720
deba@57
   721
      template<typename _GraphItemIt>
deba@57
   722
      struct Constraints {
alpar@209
   723
        void constraints() {
kpeter@626
   724
          checkConcept<GraphItem<>, _GraphItemIt>();
alpar@209
   725
          _GraphItemIt it1(g);
alpar@209
   726
          _GraphItemIt it2;
kpeter@626
   727
          _GraphItemIt it3 = it1;
kpeter@626
   728
          _GraphItemIt it4 = INVALID;
alpar@1157
   729
          ignore_unused_variable_warning(it3);
alpar@1157
   730
          ignore_unused_variable_warning(it4);
deba@57
   731
alpar@209
   732
          it2 = ++it1;
alpar@209
   733
          ++it2 = it1;
alpar@209
   734
          ++(++it1);
deba@57
   735
kpeter@606
   736
          Item bi = it1;
alpar@209
   737
          bi = it2;
alpar@209
   738
        }
kpeter@626
   739
        const GR& g;
alpar@1125
   740
        Constraints() {}
deba@57
   741
      };
deba@57
   742
    };
deba@57
   743
alpar@956
   744
    /// \brief Concept class for \c InArcIt, \c OutArcIt and
kpeter@626
   745
    /// \c IncEdgeIt types.
deba@57
   746
    ///
alpar@956
   747
    /// This class describes the concept of \c InArcIt, \c OutArcIt
kpeter@626
   748
    /// and \c IncEdgeIt subtypes of digraph and graph types.
kpeter@626
   749
    ///
kpeter@626
   750
    /// \note Since these iterator classes do not inherit from the same
kpeter@626
   751
    /// base class, there is an additional template parameter (selector)
alpar@956
   752
    /// \c sel. For \c InArcIt you should instantiate it with character
kpeter@626
   753
    /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'.
kpeter@606
   754
    template <typename GR,
kpeter@606
   755
              typename Item = typename GR::Arc,
kpeter@606
   756
              typename Base = typename GR::Node,
kpeter@606
   757
              char sel = '0'>
kpeter@606
   758
    class GraphIncIt : public Item {
deba@57
   759
    public:
deba@57
   760
      /// \brief Default constructor.
deba@57
   761
      ///
kpeter@626
   762
      /// Default constructor.
kpeter@626
   763
      /// \warning The default constructor is not required to set
kpeter@626
   764
      /// the iterator to some well-defined value. So you should consider it
kpeter@626
   765
      /// as uninitialized.
deba@57
   766
      GraphIncIt() {}
kpeter@626
   767
deba@57
   768
      /// \brief Copy constructor.
deba@57
   769
      ///
deba@57
   770
      /// Copy constructor.
kpeter@626
   771
      GraphIncIt(const GraphIncIt& it) : Item(it) {}
kpeter@626
   772
alpar@956
   773
      /// \brief Constructor that sets the iterator to the first
kpeter@626
   774
      /// incoming or outgoing arc.
deba@57
   775
      ///
alpar@956
   776
      /// Constructor that sets the iterator to the first arc
kpeter@626
   777
      /// incoming to or outgoing from the given node.
kpeter@626
   778
      explicit GraphIncIt(const GR&, const Base&) {}
kpeter@626
   779
kpeter@626
   780
      /// \brief Constructor for conversion from \c INVALID.
deba@57
   781
      ///
kpeter@626
   782
      /// Constructor for conversion from \c INVALID.
kpeter@626
   783
      /// It initializes the iterator to be invalid.
deba@57
   784
      /// \sa Invalid for more details.
deba@57
   785
      GraphIncIt(Invalid) {}
kpeter@626
   786
kpeter@626
   787
      /// \brief Assignment operator.
deba@57
   788
      ///
kpeter@626
   789
      /// Assignment operator for the iterator.
kpeter@626
   790
      GraphIncIt& operator=(const GraphIncIt&) { return *this; }
kpeter@626
   791
kpeter@626
   792
      /// \brief Increment the iterator.
deba@57
   793
      ///
kpeter@626
   794
      /// This operator increments the iterator, i.e. assigns it to the
kpeter@626
   795
      /// next arc incoming to or outgoing from the given node.
deba@57
   796
      GraphIncIt& operator++() { return *this; }
deba@57
   797
deba@57
   798
      /// \brief Equality operator
deba@57
   799
      ///
kpeter@626
   800
      /// Equality operator.
deba@57
   801
      /// Two iterators are equal if and only if they point to the
deba@57
   802
      /// same object or both are invalid.
deba@57
   803
      bool operator==(const GraphIncIt&) const { return true;}
deba@57
   804
deba@57
   805
      /// \brief Inequality operator
deba@57
   806
      ///
kpeter@626
   807
      /// Inequality operator.
kpeter@626
   808
      /// Two iterators are equal if and only if they point to the
kpeter@626
   809
      /// same object or both are invalid.
deba@57
   810
      bool operator!=(const GraphIncIt&) const { return true;}
deba@57
   811
deba@57
   812
      template <typename _GraphIncIt>
deba@57
   813
      struct Constraints {
alpar@209
   814
        void constraints() {
kpeter@606
   815
          checkConcept<GraphItem<sel>, _GraphIncIt>();
alpar@209
   816
          _GraphIncIt it1(graph, node);
alpar@209
   817
          _GraphIncIt it2;
kpeter@626
   818
          _GraphIncIt it3 = it1;
kpeter@626
   819
          _GraphIncIt it4 = INVALID;
alpar@1157
   820
          ignore_unused_variable_warning(it3);
alpar@1157
   821
          ignore_unused_variable_warning(it4);
deba@57
   822
alpar@209
   823
          it2 = ++it1;
alpar@209
   824
          ++it2 = it1;
alpar@209
   825
          ++(++it1);
kpeter@606
   826
          Item e = it1;
alpar@209
   827
          e = it2;
alpar@209
   828
        }
kpeter@626
   829
        const Base& node;
kpeter@626
   830
        const GR& graph;
alpar@1125
   831
        Constraints() {}
deba@57
   832
      };
deba@57
   833
    };
deba@57
   834
kpeter@626
   835
    /// \brief Skeleton class for iterable directed graphs.
deba@57
   836
    ///
kpeter@626
   837
    /// This class describes the interface of iterable directed
kpeter@626
   838
    /// graphs. It extends \ref BaseDigraphComponent with the core
kpeter@626
   839
    /// iterable interface.
deba@57
   840
    /// This concept is part of the Digraph concept.
kpeter@606
   841
    template <typename BAS = BaseDigraphComponent>
kpeter@606
   842
    class IterableDigraphComponent : public BAS {
deba@57
   843
deba@57
   844
    public:
alpar@209
   845
kpeter@606
   846
      typedef BAS Base;
deba@57
   847
      typedef typename Base::Node Node;
deba@57
   848
      typedef typename Base::Arc Arc;
deba@57
   849
deba@57
   850
      typedef IterableDigraphComponent Digraph;
deba@57
   851
kpeter@631
   852
      /// \name Base Iteration
alpar@209
   853
      ///
kpeter@626
   854
      /// This interface provides functions for iteration on digraph items.
deba@57
   855
      ///
alpar@209
   856
      /// @{
deba@57
   857
kpeter@626
   858
      /// \brief Return the first node.
alpar@209
   859
      ///
kpeter@626
   860
      /// This function gives back the first node in the iteration order.
deba@57
   861
      void first(Node&) const {}
deba@57
   862
kpeter@626
   863
      /// \brief Return the next node.
deba@57
   864
      ///
kpeter@626
   865
      /// This function gives back the next node in the iteration order.
deba@57
   866
      void next(Node&) const {}
deba@57
   867
kpeter@626
   868
      /// \brief Return the first arc.
deba@57
   869
      ///
kpeter@626
   870
      /// This function gives back the first arc in the iteration order.
deba@57
   871
      void first(Arc&) const {}
deba@57
   872
kpeter@626
   873
      /// \brief Return the next arc.
deba@57
   874
      ///
kpeter@626
   875
      /// This function gives back the next arc in the iteration order.
deba@57
   876
      void next(Arc&) const {}
deba@57
   877
kpeter@626
   878
      /// \brief Return the first arc incomming to the given node.
deba@57
   879
      ///
kpeter@626
   880
      /// This function gives back the first arc incomming to the
kpeter@626
   881
      /// given node.
deba@57
   882
      void firstIn(Arc&, const Node&) const {}
deba@57
   883
kpeter@626
   884
      /// \brief Return the next arc incomming to the given node.
deba@57
   885
      ///
kpeter@626
   886
      /// This function gives back the next arc incomming to the
kpeter@626
   887
      /// given node.
deba@57
   888
      void nextIn(Arc&) const {}
deba@57
   889
kpeter@626
   890
      /// \brief Return the first arc outgoing form the given node.
kpeter@626
   891
      ///
kpeter@626
   892
      /// This function gives back the first arc outgoing form the
deba@57
   893
      /// given node.
deba@57
   894
      void firstOut(Arc&, const Node&) const {}
deba@57
   895
kpeter@626
   896
      /// \brief Return the next arc outgoing form the given node.
deba@57
   897
      ///
kpeter@626
   898
      /// This function gives back the next arc outgoing form the
kpeter@626
   899
      /// given node.
deba@57
   900
      void nextOut(Arc&) const {}
deba@57
   901
deba@57
   902
      /// @}
deba@57
   903
kpeter@631
   904
      /// \name Class Based Iteration
alpar@209
   905
      ///
kpeter@626
   906
      /// This interface provides iterator classes for digraph items.
deba@57
   907
      ///
deba@57
   908
      /// @{
deba@57
   909
deba@57
   910
      /// \brief This iterator goes through each node.
deba@57
   911
      ///
deba@57
   912
      /// This iterator goes through each node.
deba@57
   913
      ///
deba@57
   914
      typedef GraphItemIt<Digraph, Node> NodeIt;
deba@57
   915
kpeter@626
   916
      /// \brief This iterator goes through each arc.
deba@57
   917
      ///
kpeter@626
   918
      /// This iterator goes through each arc.
deba@57
   919
      ///
deba@57
   920
      typedef GraphItemIt<Digraph, Arc> ArcIt;
deba@57
   921
deba@57
   922
      /// \brief This iterator goes trough the incoming arcs of a node.
deba@57
   923
      ///
kpeter@626
   924
      /// This iterator goes trough the \e incoming arcs of a certain node
deba@57
   925
      /// of a digraph.
deba@57
   926
      typedef GraphIncIt<Digraph, Arc, Node, 'i'> InArcIt;
deba@57
   927
deba@57
   928
      /// \brief This iterator goes trough the outgoing arcs of a node.
deba@57
   929
      ///
deba@57
   930
      /// This iterator goes trough the \e outgoing arcs of a certain node
deba@57
   931
      /// of a digraph.
deba@57
   932
      typedef GraphIncIt<Digraph, Arc, Node, 'o'> OutArcIt;
deba@57
   933
deba@57
   934
      /// \brief The base node of the iterator.
deba@57
   935
      ///
kpeter@626
   936
      /// This function gives back the base node of the iterator.
kpeter@626
   937
      /// It is always the target node of the pointed arc.
deba@57
   938
      Node baseNode(const InArcIt&) const { return INVALID; }
deba@57
   939
deba@57
   940
      /// \brief The running node of the iterator.
deba@57
   941
      ///
kpeter@626
   942
      /// This function gives back the running node of the iterator.
kpeter@626
   943
      /// It is always the source node of the pointed arc.
deba@57
   944
      Node runningNode(const InArcIt&) const { return INVALID; }
deba@57
   945
deba@57
   946
      /// \brief The base node of the iterator.
deba@57
   947
      ///
kpeter@626
   948
      /// This function gives back the base node of the iterator.
kpeter@626
   949
      /// It is always the source node of the pointed arc.
deba@57
   950
      Node baseNode(const OutArcIt&) const { return INVALID; }
deba@57
   951
deba@57
   952
      /// \brief The running node of the iterator.
deba@57
   953
      ///
kpeter@626
   954
      /// This function gives back the running node of the iterator.
kpeter@626
   955
      /// It is always the target node of the pointed arc.
deba@57
   956
      Node runningNode(const OutArcIt&) const { return INVALID; }
deba@57
   957
deba@57
   958
      /// @}
deba@57
   959
alpar@209
   960
      template <typename _Digraph>
deba@57
   961
      struct Constraints {
alpar@209
   962
        void constraints() {
alpar@209
   963
          checkConcept<Base, _Digraph>();
deba@57
   964
deba@57
   965
          {
alpar@209
   966
            typename _Digraph::Node node(INVALID);
deba@57
   967
            typename _Digraph::Arc arc(INVALID);
deba@57
   968
            {
deba@57
   969
              digraph.first(node);
deba@57
   970
              digraph.next(node);
deba@57
   971
            }
deba@57
   972
            {
deba@57
   973
              digraph.first(arc);
deba@57
   974
              digraph.next(arc);
deba@57
   975
            }
deba@57
   976
            {
deba@57
   977
              digraph.firstIn(arc, node);
deba@57
   978
              digraph.nextIn(arc);
deba@57
   979
            }
deba@57
   980
            {
deba@57
   981
              digraph.firstOut(arc, node);
deba@57
   982
              digraph.nextOut(arc);
deba@57
   983
            }
alpar@209
   984
          }
deba@57
   985
deba@57
   986
          {
deba@57
   987
            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Arc>,
deba@57
   988
              typename _Digraph::ArcIt >();
deba@57
   989
            checkConcept<GraphItemIt<_Digraph, typename _Digraph::Node>,
deba@57
   990
              typename _Digraph::NodeIt >();
alpar@209
   991
            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
deba@57
   992
              typename _Digraph::Node, 'i'>, typename _Digraph::InArcIt>();
alpar@209
   993
            checkConcept<GraphIncIt<_Digraph, typename _Digraph::Arc,
deba@57
   994
              typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>();
deba@57
   995
deba@57
   996
            typename _Digraph::Node n;
kpeter@626
   997
            const typename _Digraph::InArcIt iait(INVALID);
kpeter@626
   998
            const typename _Digraph::OutArcIt oait(INVALID);
kpeter@626
   999
            n = digraph.baseNode(iait);
kpeter@626
  1000
            n = digraph.runningNode(iait);
kpeter@626
  1001
            n = digraph.baseNode(oait);
kpeter@626
  1002
            n = digraph.runningNode(oait);
deba@57
  1003
            ignore_unused_variable_warning(n);
deba@57
  1004
          }
deba@57
  1005
        }
alpar@209
  1006
alpar@209
  1007
        const _Digraph& digraph;
alpar@1125
  1008
        Constraints() {}
deba@57
  1009
      };
deba@57
  1010
    };
deba@57
  1011
kpeter@626
  1012
    /// \brief Skeleton class for iterable undirected graphs.
deba@57
  1013
    ///
kpeter@626
  1014
    /// This class describes the interface of iterable undirected
kpeter@626
  1015
    /// graphs. It extends \ref IterableDigraphComponent with the core
kpeter@626
  1016
    /// iterable interface of undirected graphs.
deba@57
  1017
    /// This concept is part of the Graph concept.
kpeter@606
  1018
    template <typename BAS = BaseGraphComponent>
kpeter@606
  1019
    class IterableGraphComponent : public IterableDigraphComponent<BAS> {
deba@57
  1020
    public:
deba@57
  1021
kpeter@606
  1022
      typedef BAS Base;
deba@57
  1023
      typedef typename Base::Node Node;
deba@57
  1024
      typedef typename Base::Arc Arc;
deba@57
  1025
      typedef typename Base::Edge Edge;
deba@57
  1026
alpar@209
  1027
deba@57
  1028
      typedef IterableGraphComponent Graph;
deba@57
  1029
kpeter@631
  1030
      /// \name Base Iteration
alpar@209
  1031
      ///
kpeter@626
  1032
      /// This interface provides functions for iteration on edges.
kpeter@626
  1033
      ///
alpar@209
  1034
      /// @{
deba@57
  1035
kpeter@606
  1036
      using IterableDigraphComponent<Base>::first;
kpeter@606
  1037
      using IterableDigraphComponent<Base>::next;
deba@57
  1038
kpeter@626
  1039
      /// \brief Return the first edge.
deba@57
  1040
      ///
kpeter@626
  1041
      /// This function gives back the first edge in the iteration order.
deba@57
  1042
      void first(Edge&) const {}
deba@57
  1043
kpeter@626
  1044
      /// \brief Return the next edge.
deba@57
  1045
      ///
kpeter@626
  1046
      /// This function gives back the next edge in the iteration order.
deba@57
  1047
      void next(Edge&) const {}
deba@57
  1048
kpeter@626
  1049
      /// \brief Return the first edge incident to the given node.
kpeter@626
  1050
      ///
alpar@956
  1051
      /// This function gives back the first edge incident to the given
kpeter@626
  1052
      /// node. The bool parameter gives back the direction for which the
alpar@956
  1053
      /// source node of the directed arc representing the edge is the
deba@57
  1054
      /// given node.
deba@57
  1055
      void firstInc(Edge&, bool&, const Node&) const {}
deba@57
  1056
deba@57
  1057
      /// \brief Gives back the next of the edges from the
deba@57
  1058
      /// given node.
deba@57
  1059
      ///
alpar@956
  1060
      /// This function gives back the next edge incident to the given
kpeter@626
  1061
      /// node. The bool parameter should be used as \c firstInc() use it.
deba@57
  1062
      void nextInc(Edge&, bool&) const {}
deba@57
  1063
kpeter@606
  1064
      using IterableDigraphComponent<Base>::baseNode;
kpeter@606
  1065
      using IterableDigraphComponent<Base>::runningNode;
deba@57
  1066
deba@57
  1067
      /// @}
deba@57
  1068
kpeter@631
  1069
      /// \name Class Based Iteration
alpar@209
  1070
      ///
kpeter@626
  1071
      /// This interface provides iterator classes for edges.
deba@57
  1072
      ///
deba@57
  1073
      /// @{
deba@57
  1074
kpeter@626
  1075
      /// \brief This iterator goes through each edge.
deba@57
  1076
      ///
kpeter@626
  1077
      /// This iterator goes through each edge.
deba@57
  1078
      typedef GraphItemIt<Graph, Edge> EdgeIt;
kpeter@626
  1079
kpeter@626
  1080
      /// \brief This iterator goes trough the incident edges of a
deba@57
  1081
      /// node.
deba@57
  1082
      ///
kpeter@626
  1083
      /// This iterator goes trough the incident edges of a certain
deba@57
  1084
      /// node of a graph.
kpeter@626
  1085
      typedef GraphIncIt<Graph, Edge, Node, 'e'> IncEdgeIt;
kpeter@626
  1086
deba@57
  1087
      /// \brief The base node of the iterator.
deba@57
  1088
      ///
kpeter@626
  1089
      /// This function gives back the base node of the iterator.
deba@78
  1090
      Node baseNode(const IncEdgeIt&) const { return INVALID; }
deba@57
  1091
deba@57
  1092
      /// \brief The running node of the iterator.
deba@57
  1093
      ///
kpeter@626
  1094
      /// This function gives back the running node of the iterator.
deba@78
  1095
      Node runningNode(const IncEdgeIt&) const { return INVALID; }
deba@57
  1096
deba@57
  1097
      /// @}
deba@57
  1098
alpar@209
  1099
      template <typename _Graph>
deba@57
  1100
      struct Constraints {
alpar@209
  1101
        void constraints() {
alpar@209
  1102
          checkConcept<IterableDigraphComponent<Base>, _Graph>();
deba@57
  1103
deba@57
  1104
          {
deba@57
  1105
            typename _Graph::Node node(INVALID);
deba@57
  1106
            typename _Graph::Edge edge(INVALID);
deba@57
  1107
            bool dir;
deba@57
  1108
            {
deba@57
  1109
              graph.first(edge);
deba@57
  1110
              graph.next(edge);
deba@57
  1111
            }
deba@57
  1112
            {
deba@57
  1113
              graph.firstInc(edge, dir, node);
deba@57
  1114
              graph.nextInc(edge, dir);
deba@57
  1115
            }
alpar@209
  1116
alpar@209
  1117
          }
alpar@209
  1118
deba@57
  1119
          {
deba@57
  1120
            checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,
deba@57
  1121
              typename _Graph::EdgeIt >();
alpar@209
  1122
            checkConcept<GraphIncIt<_Graph, typename _Graph::Edge,
kpeter@626
  1123
              typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>();
alpar@209
  1124
deba@57
  1125
            typename _Graph::Node n;
kpeter@626
  1126
            const typename _Graph::IncEdgeIt ieit(INVALID);
kpeter@626
  1127
            n = graph.baseNode(ieit);
kpeter@626
  1128
            n = graph.runningNode(ieit);
deba@57
  1129
          }
deba@57
  1130
        }
alpar@209
  1131
alpar@209
  1132
        const _Graph& graph;
alpar@1125
  1133
        Constraints() {}
deba@57
  1134
      };
deba@57
  1135
    };
deba@57
  1136
deba@1186
  1137
    /// \brief Skeleton class for iterable undirected bipartite graphs.
deba@1186
  1138
    ///
deba@1186
  1139
    /// This class describes the interface of iterable undirected
deba@1186
  1140
    /// bipartite graphs. It extends \ref IterableGraphComponent with
deba@1186
  1141
    /// the core iterable interface of undirected bipartite graphs.
deba@1186
  1142
    /// This concept is part of the BpGraph concept.
deba@1186
  1143
    template <typename BAS = BaseBpGraphComponent>
deba@1186
  1144
    class IterableBpGraphComponent : public IterableGraphComponent<BAS> {
deba@1186
  1145
    public:
deba@1186
  1146
deba@1186
  1147
      typedef BAS Base;
deba@1186
  1148
      typedef typename Base::Node Node;
deba@1193
  1149
      typedef typename Base::RedNode RedNode;
deba@1193
  1150
      typedef typename Base::BlueNode BlueNode;
deba@1186
  1151
      typedef typename Base::Arc Arc;
deba@1186
  1152
      typedef typename Base::Edge Edge;
deba@1193
  1153
      
deba@1193
  1154
      typedef IterableBpGraphComponent BpGraph;
deba@1186
  1155
deba@1193
  1156
      using IterableGraphComponent<BAS>::first;
deba@1193
  1157
      using IterableGraphComponent<BAS>::next;
deba@1186
  1158
deba@1186
  1159
      /// \name Base Iteration
deba@1186
  1160
      ///
deba@1186
  1161
      /// This interface provides functions for iteration on red and blue nodes.
deba@1186
  1162
      ///
deba@1186
  1163
      /// @{
deba@1186
  1164
deba@1186
  1165
      /// \brief Return the first red node.
deba@1186
  1166
      ///
deba@1186
  1167
      /// This function gives back the first red node in the iteration order.
deba@1193
  1168
      void first(RedNode&) const {}
deba@1186
  1169
deba@1186
  1170
      /// \brief Return the next red node.
deba@1186
  1171
      ///
deba@1186
  1172
      /// This function gives back the next red node in the iteration order.
deba@1193
  1173
      void next(RedNode&) const {}
deba@1186
  1174
deba@1186
  1175
      /// \brief Return the first blue node.
deba@1186
  1176
      ///
deba@1186
  1177
      /// This function gives back the first blue node in the iteration order.
deba@1193
  1178
      void first(BlueNode&) const {}
deba@1186
  1179
deba@1186
  1180
      /// \brief Return the next blue node.
deba@1186
  1181
      ///
deba@1186
  1182
      /// This function gives back the next blue node in the iteration order.
deba@1193
  1183
      void next(BlueNode&) const {}
deba@1186
  1184
deba@1186
  1185
deba@1186
  1186
      /// @}
deba@1186
  1187
deba@1186
  1188
      /// \name Class Based Iteration
deba@1186
  1189
      ///
deba@1186
  1190
      /// This interface provides iterator classes for red and blue nodes.
deba@1186
  1191
      ///
deba@1186
  1192
      /// @{
deba@1186
  1193
deba@1186
  1194
      /// \brief This iterator goes through each red node.
deba@1186
  1195
      ///
deba@1186
  1196
      /// This iterator goes through each red node.
deba@1194
  1197
      typedef GraphItemIt<BpGraph, RedNode> RedNodeIt;
deba@1186
  1198
deba@1186
  1199
      /// \brief This iterator goes through each blue node.
deba@1186
  1200
      ///
deba@1186
  1201
      /// This iterator goes through each blue node.
deba@1194
  1202
      typedef GraphItemIt<BpGraph, BlueNode> BlueNodeIt;
deba@1186
  1203
deba@1186
  1204
      /// @}
deba@1186
  1205
deba@1186
  1206
      template <typename _BpGraph>
deba@1186
  1207
      struct Constraints {
deba@1186
  1208
        void constraints() {
deba@1186
  1209
          checkConcept<IterableGraphComponent<Base>, _BpGraph>();
deba@1186
  1210
deba@1193
  1211
          typename _BpGraph::RedNode rn(INVALID);
deba@1193
  1212
          bpgraph.first(rn);
deba@1193
  1213
          bpgraph.next(rn); 
deba@1193
  1214
          typename _BpGraph::BlueNode bn(INVALID);
deba@1193
  1215
          bpgraph.first(bn);
deba@1193
  1216
          bpgraph.next(bn);
deba@1186
  1217
deba@1193
  1218
          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::RedNode>,
deba@1194
  1219
            typename _BpGraph::RedNodeIt>();
deba@1193
  1220
          checkConcept<GraphItemIt<_BpGraph, typename _BpGraph::BlueNode>,
deba@1194
  1221
            typename _BpGraph::BlueNodeIt>();
deba@1186
  1222
        }
deba@1186
  1223
deba@1186
  1224
        const _BpGraph& bpgraph;
deba@1186
  1225
      };
deba@1186
  1226
    };
deba@1186
  1227
kpeter@626
  1228
    /// \brief Skeleton class for alterable directed graphs.
alpar@209
  1229
    ///
kpeter@626
  1230
    /// This class describes the interface of alterable directed
kpeter@626
  1231
    /// graphs. It extends \ref BaseDigraphComponent with the alteration
kpeter@626
  1232
    /// notifier interface. It implements
deba@57
  1233
    /// an observer-notifier pattern for each digraph item. More
deba@57
  1234
    /// obsevers can be registered into the notifier and whenever an
kpeter@626
  1235
    /// alteration occured in the digraph all the observers will be
deba@57
  1236
    /// notified about it.
kpeter@606
  1237
    template <typename BAS = BaseDigraphComponent>
kpeter@606
  1238
    class AlterableDigraphComponent : public BAS {
deba@57
  1239
    public:
deba@57
  1240
kpeter@606
  1241
      typedef BAS Base;
deba@57
  1242
      typedef typename Base::Node Node;
deba@57
  1243
      typedef typename Base::Arc Arc;
deba@57
  1244
deba@57
  1245
kpeter@626
  1246
      /// Node alteration notifier class.
alpar@209
  1247
      typedef AlterationNotifier<AlterableDigraphComponent, Node>
deba@57
  1248
      NodeNotifier;
kpeter@626
  1249
      /// Arc alteration notifier class.
alpar@209
  1250
      typedef AlterationNotifier<AlterableDigraphComponent, Arc>
deba@57
  1251
      ArcNotifier;
alpar@209
  1252
deba@1186
  1253
      mutable NodeNotifier node_notifier;
deba@1186
  1254
      mutable ArcNotifier arc_notifier;
deba@1186
  1255
kpeter@626
  1256
      /// \brief Return the node alteration notifier.
deba@57
  1257
      ///
kpeter@626
  1258
      /// This function gives back the node alteration notifier.
deba@57
  1259
      NodeNotifier& notifier(Node) const {
deba@1186
  1260
        return node_notifier;
deba@57
  1261
      }
alpar@209
  1262
kpeter@626
  1263
      /// \brief Return the arc alteration notifier.
deba@57
  1264
      ///
kpeter@626
  1265
      /// This function gives back the arc alteration notifier.
deba@57
  1266
      ArcNotifier& notifier(Arc) const {
deba@1186
  1267
        return arc_notifier;
deba@57
  1268
      }
deba@57
  1269
alpar@209
  1270
      template <typename _Digraph>
deba@57
  1271
      struct Constraints {
alpar@209
  1272
        void constraints() {
alpar@209
  1273
          checkConcept<Base, _Digraph>();
alpar@209
  1274
          typename _Digraph::NodeNotifier& nn
deba@57
  1275
            = digraph.notifier(typename _Digraph::Node());
deba@57
  1276
alpar@209
  1277
          typename _Digraph::ArcNotifier& en
deba@57
  1278
            = digraph.notifier(typename _Digraph::Arc());
alpar@209
  1279
deba@57
  1280
          ignore_unused_variable_warning(nn);
deba@57
  1281
          ignore_unused_variable_warning(en);
alpar@209
  1282
        }
alpar@209
  1283
alpar@209
  1284
        const _Digraph& digraph;
alpar@1125
  1285
        Constraints() {}
deba@57
  1286
      };
deba@57
  1287
    };
deba@57
  1288
kpeter@626
  1289
    /// \brief Skeleton class for alterable undirected graphs.
alpar@209
  1290
    ///
kpeter@626
  1291
    /// This class describes the interface of alterable undirected
kpeter@626
  1292
    /// graphs. It extends \ref AlterableDigraphComponent with the alteration
kpeter@626
  1293
    /// notifier interface of undirected graphs. It implements
kpeter@626
  1294
    /// an observer-notifier pattern for the edges. More
deba@57
  1295
    /// obsevers can be registered into the notifier and whenever an
kpeter@626
  1296
    /// alteration occured in the graph all the observers will be
deba@57
  1297
    /// notified about it.
kpeter@606
  1298
    template <typename BAS = BaseGraphComponent>
kpeter@606
  1299
    class AlterableGraphComponent : public AlterableDigraphComponent<BAS> {
deba@57
  1300
    public:
deba@57
  1301
kpeter@606
  1302
      typedef BAS Base;
deba@1186
  1303
      typedef AlterableDigraphComponent<Base> Parent;
deba@57
  1304
      typedef typename Base::Edge Edge;
deba@57
  1305
deba@57
  1306
kpeter@626
  1307
      /// Edge alteration notifier class.
alpar@209
  1308
      typedef AlterationNotifier<AlterableGraphComponent, Edge>
deba@57
  1309
      EdgeNotifier;
alpar@209
  1310
deba@1186
  1311
      mutable EdgeNotifier edge_notifier;
deba@1186
  1312
deba@1186
  1313
      using Parent::notifier;
deba@1186
  1314
kpeter@626
  1315
      /// \brief Return the edge alteration notifier.
deba@57
  1316
      ///
kpeter@626
  1317
      /// This function gives back the edge alteration notifier.
deba@57
  1318
      EdgeNotifier& notifier(Edge) const {
deba@1186
  1319
        return edge_notifier;
deba@57
  1320
      }
deba@57
  1321
alpar@209
  1322
      template <typename _Graph>
deba@57
  1323
      struct Constraints {
alpar@209
  1324
        void constraints() {
kpeter@626
  1325
          checkConcept<AlterableDigraphComponent<Base>, _Graph>();
alpar@209
  1326
          typename _Graph::EdgeNotifier& uen
deba@57
  1327
            = graph.notifier(typename _Graph::Edge());
deba@57
  1328
          ignore_unused_variable_warning(uen);
alpar@209
  1329
        }
alpar@209
  1330
alpar@209
  1331
        const _Graph& graph;
alpar@1125
  1332
        Constraints() {}
deba@57
  1333
      };
deba@57
  1334
    };
deba@57
  1335
deba@1186
  1336
    /// \brief Skeleton class for alterable undirected bipartite graphs.
deba@1186
  1337
    ///
deba@1186
  1338
    /// This class describes the interface of alterable undirected
deba@1186
  1339
    /// bipartite graphs. It extends \ref AlterableGraphComponent with
deba@1186
  1340
    /// the alteration notifier interface of bipartite graphs. It
deba@1186
  1341
    /// implements an observer-notifier pattern for the red and blue
deba@1186
  1342
    /// nodes. More obsevers can be registered into the notifier and
deba@1186
  1343
    /// whenever an alteration occured in the graph all the observers
deba@1186
  1344
    /// will be notified about it.
deba@1186
  1345
    template <typename BAS = BaseBpGraphComponent>
deba@1186
  1346
    class AlterableBpGraphComponent : public AlterableGraphComponent<BAS> {
deba@1186
  1347
    public:
deba@1186
  1348
deba@1186
  1349
      typedef BAS Base;
deba@1186
  1350
      typedef AlterableGraphComponent<Base> Parent;
deba@1186
  1351
      typedef typename Base::RedNode RedNode;
deba@1186
  1352
      typedef typename Base::BlueNode BlueNode;
deba@1186
  1353
deba@1186
  1354
deba@1186
  1355
      /// Red node alteration notifier class.
deba@1186
  1356
      typedef AlterationNotifier<AlterableBpGraphComponent, RedNode>
deba@1186
  1357
      RedNodeNotifier;
deba@1186
  1358
deba@1186
  1359
      /// Blue node alteration notifier class.
deba@1186
  1360
      typedef AlterationNotifier<AlterableBpGraphComponent, BlueNode>
deba@1186
  1361
      BlueNodeNotifier;
deba@1186
  1362
deba@1186
  1363
      mutable RedNodeNotifier red_node_notifier;
deba@1186
  1364
      mutable BlueNodeNotifier blue_node_notifier;
deba@1186
  1365
deba@1186
  1366
      using Parent::notifier;
deba@1186
  1367
deba@1186
  1368
      /// \brief Return the red node alteration notifier.
deba@1186
  1369
      ///
deba@1186
  1370
      /// This function gives back the red node alteration notifier.
deba@1186
  1371
      RedNodeNotifier& notifier(RedNode) const {
deba@1186
  1372
        return red_node_notifier;
deba@1186
  1373
      }
deba@1186
  1374
deba@1186
  1375
      /// \brief Return the blue node alteration notifier.
deba@1186
  1376
      ///
deba@1186
  1377
      /// This function gives back the blue node alteration notifier.
deba@1186
  1378
      BlueNodeNotifier& notifier(BlueNode) const {
deba@1186
  1379
        return blue_node_notifier;
deba@1186
  1380
      }
deba@1186
  1381
deba@1186
  1382
      template <typename _BpGraph>
deba@1186
  1383
      struct Constraints {
deba@1186
  1384
        void constraints() {
deba@1186
  1385
          checkConcept<AlterableGraphComponent<Base>, _BpGraph>();
deba@1186
  1386
          typename _BpGraph::RedNodeNotifier& rnn
deba@1186
  1387
            = bpgraph.notifier(typename _BpGraph::RedNode());
deba@1186
  1388
          typename _BpGraph::BlueNodeNotifier& bnn
deba@1186
  1389
            = bpgraph.notifier(typename _BpGraph::BlueNode());
deba@1186
  1390
          ignore_unused_variable_warning(rnn);
deba@1186
  1391
          ignore_unused_variable_warning(bnn);
deba@1186
  1392
        }
deba@1186
  1393
deba@1186
  1394
        const _BpGraph& bpgraph;
deba@1186
  1395
      };
deba@1186
  1396
    };
deba@1186
  1397
kpeter@626
  1398
    /// \brief Concept class for standard graph maps.
alpar@209
  1399
    ///
kpeter@626
  1400
    /// This class describes the concept of standard graph maps, i.e.
alpar@956
  1401
    /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and
kpeter@626
  1402
    /// graph types, which can be used for associating data to graph items.
kpeter@627
  1403
    /// The standard graph maps must conform to the ReferenceMap concept.
kpeter@606
  1404
    template <typename GR, typename K, typename V>
kpeter@627
  1405
    class GraphMap : public ReferenceMap<K, V, V&, const V&> {
kpeter@664
  1406
      typedef ReferenceMap<K, V, V&, const V&> Parent;
kpeter@664
  1407
deba@57
  1408
    public:
deba@57
  1409
deba@57
  1410
      /// The key type of the map.
kpeter@606
  1411
      typedef K Key;
deba@57
  1412
      /// The value type of the map.
kpeter@606
  1413
      typedef V Value;
kpeter@627
  1414
      /// The reference type of the map.
kpeter@627
  1415
      typedef Value& Reference;
kpeter@627
  1416
      /// The const reference type of the map.
kpeter@627
  1417
      typedef const Value& ConstReference;
kpeter@627
  1418
kpeter@627
  1419
      // The reference map tag.
kpeter@627
  1420
      typedef True ReferenceMapTag;
deba@57
  1421
deba@57
  1422
      /// \brief Construct a new map.
deba@57
  1423
      ///
deba@57
  1424
      /// Construct a new map for the graph.
kpeter@664
  1425
      explicit GraphMap(const GR&) {}
deba@57
  1426
      /// \brief Construct a new map with default value.
deba@57
  1427
      ///
kpeter@626
  1428
      /// Construct a new map for the graph and initalize the values.
kpeter@664
  1429
      GraphMap(const GR&, const Value&) {}
kpeter@263
  1430
kpeter@263
  1431
    private:
deba@57
  1432
      /// \brief Copy constructor.
deba@57
  1433
      ///
deba@57
  1434
      /// Copy Constructor.
deba@57
  1435
      GraphMap(const GraphMap&) : Parent() {}
alpar@209
  1436
kpeter@626
  1437
      /// \brief Assignment operator.
deba@57
  1438
      ///
kpeter@626
  1439
      /// Assignment operator. It does not mofify the underlying graph,
deba@57
  1440
      /// it just iterates on the current item set and set the  map
alpar@209
  1441
      /// with the value returned by the assigned map.
deba@57
  1442
      template <typename CMap>
alpar@209
  1443
      GraphMap& operator=(const CMap&) {
deba@57
  1444
        checkConcept<ReadMap<Key, Value>, CMap>();
deba@57
  1445
        return *this;
deba@57
  1446
      }
deba@57
  1447
kpeter@263
  1448
    public:
deba@57
  1449
      template<typename _Map>
deba@57
  1450
      struct Constraints {
alpar@209
  1451
        void constraints() {
kpeter@627
  1452
          checkConcept
kpeter@627
  1453
            <ReferenceMap<Key, Value, Value&, const Value&>, _Map>();
kpeter@626
  1454
          _Map m1(g);
kpeter@626
  1455
          _Map m2(g,t);
alpar@956
  1456
kpeter@626
  1457
          // Copy constructor
kpeter@626
  1458
          // _Map m3(m);
alpar@209
  1459
kpeter@626
  1460
          // Assignment operator
kpeter@263
  1461
          // ReadMap<Key, Value> cmap;
kpeter@626
  1462
          // m3 = cmap;
deba@57
  1463
kpeter@626
  1464
          ignore_unused_variable_warning(m1);
kpeter@626
  1465
          ignore_unused_variable_warning(m2);
kpeter@626
  1466
          // ignore_unused_variable_warning(m3);
alpar@209
  1467
        }
deba@57
  1468
kpeter@626
  1469
        const _Map &m;
kpeter@664
  1470
        const GR &g;
alpar@209
  1471
        const typename GraphMap::Value &t;
alpar@1125
  1472
        Constraints() {}
deba@57
  1473
      };
deba@57
  1474
deba@57
  1475
    };
deba@57
  1476
kpeter@626
  1477
    /// \brief Skeleton class for mappable directed graphs.
deba@57
  1478
    ///
kpeter@626
  1479
    /// This class describes the interface of mappable directed graphs.
alpar@956
  1480
    /// It extends \ref BaseDigraphComponent with the standard digraph
kpeter@626
  1481
    /// map classes, namely \c NodeMap and \c ArcMap.
deba@57
  1482
    /// This concept is part of the Digraph concept.
kpeter@606
  1483
    template <typename BAS = BaseDigraphComponent>
kpeter@606
  1484
    class MappableDigraphComponent : public BAS  {
deba@57
  1485
    public:
deba@57
  1486
kpeter@606
  1487
      typedef BAS Base;
deba@57
  1488
      typedef typename Base::Node Node;
deba@57
  1489
      typedef typename Base::Arc Arc;
deba@57
  1490
deba@57
  1491
      typedef MappableDigraphComponent Digraph;
deba@57
  1492
kpeter@626
  1493
      /// \brief Standard graph map for the nodes.
deba@57
  1494
      ///
kpeter@626
  1495
      /// Standard graph map for the nodes.
kpeter@627
  1496
      /// It conforms to the ReferenceMap concept.
kpeter@606
  1497
      template <typename V>
kpeter@626
  1498
      class NodeMap : public GraphMap<MappableDigraphComponent, Node, V> {
kpeter@606
  1499
        typedef GraphMap<MappableDigraphComponent, Node, V> Parent;
deba@57
  1500
kpeter@664
  1501
      public:
alpar@209
  1502
        /// \brief Construct a new map.
alpar@209
  1503
        ///
alpar@209
  1504
        /// Construct a new map for the digraph.
alpar@209
  1505
        explicit NodeMap(const MappableDigraphComponent& digraph)
deba@57
  1506
          : Parent(digraph) {}
deba@57
  1507
alpar@209
  1508
        /// \brief Construct a new map with default value.
alpar@209
  1509
        ///
kpeter@626
  1510
        /// Construct a new map for the digraph and initalize the values.
kpeter@606
  1511
        NodeMap(const MappableDigraphComponent& digraph, const V& value)
deba@57
  1512
          : Parent(digraph, value) {}
deba@57
  1513
kpeter@263
  1514
      private:
alpar@209
  1515
        /// \brief Copy constructor.
alpar@209
  1516
        ///
alpar@209
  1517
        /// Copy Constructor.
alpar@209
  1518
        NodeMap(const NodeMap& nm) : Parent(nm) {}
deba@57
  1519
kpeter@626
  1520
        /// \brief Assignment operator.
alpar@209
  1521
        ///
kpeter@626
  1522
        /// Assignment operator.
deba@57
  1523
        template <typename CMap>
alpar@209
  1524
        NodeMap& operator=(const CMap&) {
kpeter@606
  1525
          checkConcept<ReadMap<Node, V>, CMap>();
deba@57
  1526
          return *this;
deba@57
  1527
        }
deba@57
  1528
deba@57
  1529
      };
deba@57
  1530
kpeter@626
  1531
      /// \brief Standard graph map for the arcs.
deba@57
  1532
      ///
kpeter@626
  1533
      /// Standard graph map for the arcs.
kpeter@627
  1534
      /// It conforms to the ReferenceMap concept.
kpeter@606
  1535
      template <typename V>
kpeter@626
  1536
      class ArcMap : public GraphMap<MappableDigraphComponent, Arc, V> {
kpeter@606
  1537
        typedef GraphMap<MappableDigraphComponent, Arc, V> Parent;
deba@57
  1538
kpeter@664
  1539
      public:
alpar@209
  1540
        /// \brief Construct a new map.
alpar@209
  1541
        ///
alpar@209
  1542
        /// Construct a new map for the digraph.
alpar@209
  1543
        explicit ArcMap(const MappableDigraphComponent& digraph)
deba@57
  1544
          : Parent(digraph) {}
deba@57
  1545
alpar@209
  1546
        /// \brief Construct a new map with default value.
alpar@209
  1547
        ///
kpeter@626
  1548
        /// Construct a new map for the digraph and initalize the values.
kpeter@606
  1549
        ArcMap(const MappableDigraphComponent& digraph, const V& value)
deba@57
  1550
          : Parent(digraph, value) {}
deba@57
  1551
kpeter@263
  1552
      private:
alpar@209
  1553
        /// \brief Copy constructor.
alpar@209
  1554
        ///
alpar@209
  1555
        /// Copy Constructor.
alpar@209
  1556
        ArcMap(const ArcMap& nm) : Parent(nm) {}
deba@57
  1557
kpeter@626
  1558
        /// \brief Assignment operator.
alpar@209
  1559
        ///
kpeter@626
  1560
        /// Assignment operator.
deba@57
  1561
        template <typename CMap>
alpar@209
  1562
        ArcMap& operator=(const CMap&) {
kpeter@606
  1563
          checkConcept<ReadMap<Arc, V>, CMap>();
deba@57
  1564
          return *this;
deba@57
  1565
        }
deba@57
  1566
deba@57
  1567
      };
deba@57
  1568
deba@57
  1569
deba@57
  1570
      template <typename _Digraph>
deba@57
  1571
      struct Constraints {
deba@57
  1572
alpar@209
  1573
        struct Dummy {
alpar@209
  1574
          int value;
alpar@209
  1575
          Dummy() : value(0) {}
alpar@209
  1576
          Dummy(int _v) : value(_v) {}
alpar@209
  1577
        };
deba@57
  1578
alpar@209
  1579
        void constraints() {
alpar@209
  1580
          checkConcept<Base, _Digraph>();
alpar@209
  1581
          { // int map test
alpar@209
  1582
            typedef typename _Digraph::template NodeMap<int> IntNodeMap;
alpar@209
  1583
            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, int>,
alpar@209
  1584
              IntNodeMap >();
alpar@209
  1585
          } { // bool map test
alpar@209
  1586
            typedef typename _Digraph::template NodeMap<bool> BoolNodeMap;
alpar@209
  1587
            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, bool>,
alpar@209
  1588
              BoolNodeMap >();
alpar@209
  1589
          } { // Dummy map test
alpar@209
  1590
            typedef typename _Digraph::template NodeMap<Dummy> DummyNodeMap;
alpar@209
  1591
            checkConcept<GraphMap<_Digraph, typename _Digraph::Node, Dummy>,
alpar@209
  1592
              DummyNodeMap >();
alpar@209
  1593
          }
deba@57
  1594
alpar@209
  1595
          { // int map test
alpar@209
  1596
            typedef typename _Digraph::template ArcMap<int> IntArcMap;
alpar@209
  1597
            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, int>,
alpar@209
  1598
              IntArcMap >();
alpar@209
  1599
          } { // bool map test
alpar@209
  1600
            typedef typename _Digraph::template ArcMap<bool> BoolArcMap;
alpar@209
  1601
            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, bool>,
alpar@209
  1602
              BoolArcMap >();
alpar@209
  1603
          } { // Dummy map test
alpar@209
  1604
            typedef typename _Digraph::template ArcMap<Dummy> DummyArcMap;
alpar@209
  1605
            checkConcept<GraphMap<_Digraph, typename _Digraph::Arc, Dummy>,
alpar@209
  1606
              DummyArcMap >();
alpar@209
  1607
          }
alpar@209
  1608
        }
deba@57
  1609
kpeter@626
  1610
        const _Digraph& digraph;
alpar@1125
  1611
        Constraints() {}
deba@57
  1612
      };
deba@57
  1613
    };
deba@57
  1614
kpeter@626
  1615
    /// \brief Skeleton class for mappable undirected graphs.
deba@57
  1616
    ///
kpeter@626
  1617
    /// This class describes the interface of mappable undirected graphs.
alpar@956
  1618
    /// It extends \ref MappableDigraphComponent with the standard graph
kpeter@626
  1619
    /// map class for edges (\c EdgeMap).
deba@57
  1620
    /// This concept is part of the Graph concept.
kpeter@606
  1621
    template <typename BAS = BaseGraphComponent>
kpeter@606
  1622
    class MappableGraphComponent : public MappableDigraphComponent<BAS>  {
deba@57
  1623
    public:
deba@57
  1624
kpeter@606
  1625
      typedef BAS Base;
deba@57
  1626
      typedef typename Base::Edge Edge;
deba@57
  1627
deba@57
  1628
      typedef MappableGraphComponent Graph;
deba@57
  1629
kpeter@626
  1630
      /// \brief Standard graph map for the edges.
deba@57
  1631
      ///
kpeter@626
  1632
      /// Standard graph map for the edges.
kpeter@627
  1633
      /// It conforms to the ReferenceMap concept.
kpeter@606
  1634
      template <typename V>
kpeter@626
  1635
      class EdgeMap : public GraphMap<MappableGraphComponent, Edge, V> {
kpeter@606
  1636
        typedef GraphMap<MappableGraphComponent, Edge, V> Parent;
deba@57
  1637
kpeter@664
  1638
      public:
alpar@209
  1639
        /// \brief Construct a new map.
alpar@209
  1640
        ///
alpar@209
  1641
        /// Construct a new map for the graph.
alpar@209
  1642
        explicit EdgeMap(const MappableGraphComponent& graph)
deba@57
  1643
          : Parent(graph) {}
deba@57
  1644
alpar@209
  1645
        /// \brief Construct a new map with default value.
alpar@209
  1646
        ///
kpeter@626
  1647
        /// Construct a new map for the graph and initalize the values.
kpeter@606
  1648
        EdgeMap(const MappableGraphComponent& graph, const V& value)
deba@57
  1649
          : Parent(graph, value) {}
deba@57
  1650
kpeter@263
  1651
      private:
alpar@209
  1652
        /// \brief Copy constructor.
alpar@209
  1653
        ///
alpar@209
  1654
        /// Copy Constructor.
alpar@209
  1655
        EdgeMap(const EdgeMap& nm) : Parent(nm) {}
deba@57
  1656
kpeter@626
  1657
        /// \brief Assignment operator.
alpar@209
  1658
        ///
kpeter@626
  1659
        /// Assignment operator.
deba@57
  1660
        template <typename CMap>
alpar@209
  1661
        EdgeMap& operator=(const CMap&) {
kpeter@606
  1662
          checkConcept<ReadMap<Edge, V>, CMap>();
deba@57
  1663
          return *this;
deba@57
  1664
        }
deba@57
  1665
deba@57
  1666
      };
deba@57
  1667
deba@57
  1668
deba@57
  1669
      template <typename _Graph>
deba@57
  1670
      struct Constraints {
deba@57
  1671
alpar@209
  1672
        struct Dummy {
alpar@209
  1673
          int value;
alpar@209
  1674
          Dummy() : value(0) {}
alpar@209
  1675
          Dummy(int _v) : value(_v) {}
alpar@209
  1676
        };
deba@57
  1677
alpar@209
  1678
        void constraints() {
kpeter@626
  1679
          checkConcept<MappableDigraphComponent<Base>, _Graph>();
deba@57
  1680
alpar@209
  1681
          { // int map test
alpar@209
  1682
            typedef typename _Graph::template EdgeMap<int> IntEdgeMap;
alpar@209
  1683
            checkConcept<GraphMap<_Graph, typename _Graph::Edge, int>,
alpar@209
  1684
              IntEdgeMap >();
alpar@209
  1685
          } { // bool map test
alpar@209
  1686
            typedef typename _Graph::template EdgeMap<bool> BoolEdgeMap;
alpar@209
  1687
            checkConcept<GraphMap<_Graph, typename _Graph::Edge, bool>,
alpar@209
  1688
              BoolEdgeMap >();
alpar@209
  1689
          } { // Dummy map test
alpar@209
  1690
            typedef typename _Graph::template EdgeMap<Dummy> DummyEdgeMap;
alpar@209
  1691
            checkConcept<GraphMap<_Graph, typename _Graph::Edge, Dummy>,
alpar@209
  1692
              DummyEdgeMap >();
alpar@209
  1693
          }
alpar@209
  1694
        }
deba@57
  1695
kpeter@626
  1696
        const _Graph& graph;
alpar@1125
  1697
        Constraints() {}
deba@57
  1698
      };
deba@57
  1699
    };
deba@57
  1700
deba@1186
  1701
    /// \brief Skeleton class for mappable undirected bipartite graphs.
deba@1186
  1702
    ///
deba@1186
  1703
    /// This class describes the interface of mappable undirected
deba@1186
  1704
    /// bipartite graphs.  It extends \ref MappableGraphComponent with
deba@1186
  1705
    /// the standard graph map class for red and blue nodes (\c
deba@1194
  1706
    /// RedNodeMap and BlueNodeMap). This concept is part of the
deba@1194
  1707
    /// BpGraph concept.
deba@1186
  1708
    template <typename BAS = BaseBpGraphComponent>
deba@1186
  1709
    class MappableBpGraphComponent : public MappableGraphComponent<BAS>  {
deba@1186
  1710
    public:
deba@1186
  1711
deba@1186
  1712
      typedef BAS Base;
deba@1186
  1713
      typedef typename Base::Node Node;
deba@1186
  1714
deba@1186
  1715
      typedef MappableBpGraphComponent BpGraph;
deba@1186
  1716
deba@1186
  1717
      /// \brief Standard graph map for the red nodes.
deba@1186
  1718
      ///
deba@1186
  1719
      /// Standard graph map for the red nodes.
deba@1186
  1720
      /// It conforms to the ReferenceMap concept.
deba@1186
  1721
      template <typename V>
deba@1194
  1722
      class RedNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
deba@1186
  1723
        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
deba@1186
  1724
deba@1186
  1725
      public:
deba@1186
  1726
        /// \brief Construct a new map.
deba@1186
  1727
        ///
deba@1186
  1728
        /// Construct a new map for the graph.
deba@1194
  1729
        explicit RedNodeMap(const MappableBpGraphComponent& graph)
deba@1186
  1730
          : Parent(graph) {}
deba@1186
  1731
deba@1186
  1732
        /// \brief Construct a new map with default value.
deba@1186
  1733
        ///
deba@1186
  1734
        /// Construct a new map for the graph and initalize the values.
deba@1194
  1735
        RedNodeMap(const MappableBpGraphComponent& graph, const V& value)
deba@1186
  1736
          : Parent(graph, value) {}
deba@1186
  1737
deba@1186
  1738
      private:
deba@1186
  1739
        /// \brief Copy constructor.
deba@1186
  1740
        ///
deba@1186
  1741
        /// Copy Constructor.
deba@1194
  1742
        RedNodeMap(const RedNodeMap& nm) : Parent(nm) {}
deba@1186
  1743
deba@1186
  1744
        /// \brief Assignment operator.
deba@1186
  1745
        ///
deba@1186
  1746
        /// Assignment operator.
deba@1186
  1747
        template <typename CMap>
deba@1194
  1748
        RedNodeMap& operator=(const CMap&) {
deba@1186
  1749
          checkConcept<ReadMap<Node, V>, CMap>();
deba@1186
  1750
          return *this;
deba@1186
  1751
        }
deba@1186
  1752
deba@1186
  1753
      };
deba@1186
  1754
deba@1186
  1755
      /// \brief Standard graph map for the blue nodes.
deba@1186
  1756
      ///
deba@1186
  1757
      /// Standard graph map for the blue nodes.
deba@1186
  1758
      /// It conforms to the ReferenceMap concept.
deba@1186
  1759
      template <typename V>
deba@1194
  1760
      class BlueNodeMap : public GraphMap<MappableBpGraphComponent, Node, V> {
deba@1186
  1761
        typedef GraphMap<MappableBpGraphComponent, Node, V> Parent;
deba@1186
  1762
deba@1186
  1763
      public:
deba@1186
  1764
        /// \brief Construct a new map.
deba@1186
  1765
        ///
deba@1186
  1766
        /// Construct a new map for the graph.
deba@1194
  1767
        explicit BlueNodeMap(const MappableBpGraphComponent& graph)
deba@1186
  1768
          : Parent(graph) {}
deba@1186
  1769
deba@1186
  1770
        /// \brief Construct a new map with default value.
deba@1186
  1771
        ///
deba@1186
  1772
        /// Construct a new map for the graph and initalize the values.
deba@1194
  1773
        BlueNodeMap(const MappableBpGraphComponent& graph, const V& value)
deba@1186
  1774
          : Parent(graph, value) {}
deba@1186
  1775
deba@1186
  1776
      private:
deba@1186
  1777
        /// \brief Copy constructor.
deba@1186
  1778
        ///
deba@1186
  1779
        /// Copy Constructor.
deba@1194
  1780
        BlueNodeMap(const BlueNodeMap& nm) : Parent(nm) {}
deba@1186
  1781
deba@1186
  1782
        /// \brief Assignment operator.
deba@1186
  1783
        ///
deba@1186
  1784
        /// Assignment operator.
deba@1186
  1785
        template <typename CMap>
deba@1194
  1786
        BlueNodeMap& operator=(const CMap&) {
deba@1186
  1787
          checkConcept<ReadMap<Node, V>, CMap>();
deba@1186
  1788
          return *this;
deba@1186
  1789
        }
deba@1186
  1790
deba@1186
  1791
      };
deba@1186
  1792
deba@1186
  1793
deba@1186
  1794
      template <typename _BpGraph>
deba@1186
  1795
      struct Constraints {
deba@1186
  1796
deba@1186
  1797
        struct Dummy {
deba@1186
  1798
          int value;
deba@1186
  1799
          Dummy() : value(0) {}
deba@1186
  1800
          Dummy(int _v) : value(_v) {}
deba@1186
  1801
        };
deba@1186
  1802
deba@1186
  1803
        void constraints() {
deba@1186
  1804
          checkConcept<MappableGraphComponent<Base>, _BpGraph>();
deba@1186
  1805
deba@1186
  1806
          { // int map test
deba@1194
  1807
            typedef typename _BpGraph::template RedNodeMap<int>
deba@1194
  1808
              IntRedNodeMap;
deba@1193
  1809
            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, int>,
deba@1194
  1810
              IntRedNodeMap >();
deba@1186
  1811
          } { // bool map test
deba@1194
  1812
            typedef typename _BpGraph::template RedNodeMap<bool>
deba@1194
  1813
              BoolRedNodeMap;
deba@1193
  1814
            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, bool>,
deba@1194
  1815
              BoolRedNodeMap >();
deba@1186
  1816
          } { // Dummy map test
deba@1194
  1817
            typedef typename _BpGraph::template RedNodeMap<Dummy>
deba@1194
  1818
              DummyRedNodeMap;
deba@1193
  1819
            checkConcept<GraphMap<_BpGraph, typename _BpGraph::RedNode, Dummy>,
deba@1194
  1820
              DummyRedNodeMap >();
deba@1186
  1821
          }
deba@1186
  1822
deba@1186
  1823
          { // int map test
deba@1194
  1824
            typedef typename _BpGraph::template BlueNodeMap<int>
deba@1194
  1825
              IntBlueNodeMap;
deba@1193
  1826
            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, int>,
deba@1194
  1827
              IntBlueNodeMap >();
deba@1186
  1828
          } { // bool map test
deba@1194
  1829
            typedef typename _BpGraph::template BlueNodeMap<bool>
deba@1194
  1830
              BoolBlueNodeMap;
deba@1193
  1831
            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, bool>,
deba@1194
  1832
              BoolBlueNodeMap >();
deba@1186
  1833
          } { // Dummy map test
deba@1194
  1834
            typedef typename _BpGraph::template BlueNodeMap<Dummy>
deba@1194
  1835
              DummyBlueNodeMap;
deba@1193
  1836
            checkConcept<GraphMap<_BpGraph, typename _BpGraph::BlueNode, Dummy>,
deba@1194
  1837
              DummyBlueNodeMap >();
deba@1186
  1838
          }
deba@1186
  1839
        }
deba@1186
  1840
deba@1186
  1841
        const _BpGraph& bpgraph;
deba@1186
  1842
      };
deba@1186
  1843
    };
deba@1186
  1844
kpeter@626
  1845
    /// \brief Skeleton class for extendable directed graphs.
deba@57
  1846
    ///
kpeter@626
  1847
    /// This class describes the interface of extendable directed graphs.
alpar@956
  1848
    /// It extends \ref BaseDigraphComponent with functions for adding
kpeter@626
  1849
    /// nodes and arcs to the digraph.
kpeter@626
  1850
    /// This concept requires \ref AlterableDigraphComponent.
kpeter@606
  1851
    template <typename BAS = BaseDigraphComponent>
kpeter@606
  1852
    class ExtendableDigraphComponent : public BAS {
deba@57
  1853
    public:
kpeter@606
  1854
      typedef BAS Base;
deba@57
  1855
kpeter@606
  1856
      typedef typename Base::Node Node;
kpeter@606
  1857
      typedef typename Base::Arc Arc;
deba@57
  1858
kpeter@626
  1859
      /// \brief Add a new node to the digraph.
deba@57
  1860
      ///
kpeter@626
  1861
      /// This function adds a new node to the digraph.
deba@57
  1862
      Node addNode() {
alpar@209
  1863
        return INVALID;
deba@57
  1864
      }
alpar@209
  1865
kpeter@626
  1866
      /// \brief Add a new arc connecting the given two nodes.
deba@57
  1867
      ///
kpeter@626
  1868
      /// This function adds a new arc connecting the given two nodes
kpeter@626
  1869
      /// of the digraph.
deba@57
  1870
      Arc addArc(const Node&, const Node&) {
alpar@209
  1871
        return INVALID;
deba@57
  1872
      }
deba@57
  1873
deba@57
  1874
      template <typename _Digraph>
deba@57
  1875
      struct Constraints {
alpar@209
  1876
        void constraints() {
deba@57
  1877
          checkConcept<Base, _Digraph>();
alpar@209
  1878
          typename _Digraph::Node node_a, node_b;
alpar@209
  1879
          node_a = digraph.addNode();
alpar@209
  1880
          node_b = digraph.addNode();
alpar@209
  1881
          typename _Digraph::Arc arc;
alpar@209
  1882
          arc = digraph.addArc(node_a, node_b);
alpar@209
  1883
        }
deba@57
  1884
alpar@209
  1885
        _Digraph& digraph;
alpar@1125
  1886
        Constraints() {}
deba@57
  1887
      };
deba@57
  1888
    };
deba@57
  1889
kpeter@626
  1890
    /// \brief Skeleton class for extendable undirected graphs.
deba@57
  1891
    ///
kpeter@626
  1892
    /// This class describes the interface of extendable undirected graphs.
alpar@956
  1893
    /// It extends \ref BaseGraphComponent with functions for adding
kpeter@626
  1894
    /// nodes and edges to the graph.
kpeter@626
  1895
    /// This concept requires \ref AlterableGraphComponent.
kpeter@606
  1896
    template <typename BAS = BaseGraphComponent>
kpeter@606
  1897
    class ExtendableGraphComponent : public BAS {
deba@57
  1898
    public:
deba@57
  1899
kpeter@606
  1900
      typedef BAS Base;
kpeter@606
  1901
      typedef typename Base::Node Node;
kpeter@606
  1902
      typedef typename Base::Edge Edge;
deba@57
  1903
kpeter@626
  1904
      /// \brief Add a new node to the digraph.
deba@57
  1905
      ///
kpeter@626
  1906
      /// This function adds a new node to the digraph.
deba@57
  1907
      Node addNode() {
alpar@209
  1908
        return INVALID;
deba@57
  1909
      }
alpar@209
  1910
kpeter@626
  1911
      /// \brief Add a new edge connecting the given two nodes.
deba@57
  1912
      ///
kpeter@626
  1913
      /// This function adds a new edge connecting the given two nodes
kpeter@626
  1914
      /// of the graph.
kpeter@626
  1915
      Edge addEdge(const Node&, const Node&) {
alpar@209
  1916
        return INVALID;
deba@57
  1917
      }
deba@57
  1918
deba@57
  1919
      template <typename _Graph>
deba@57
  1920
      struct Constraints {
alpar@209
  1921
        void constraints() {
alpar@209
  1922
          checkConcept<Base, _Graph>();
alpar@209
  1923
          typename _Graph::Node node_a, node_b;
alpar@209
  1924
          node_a = graph.addNode();
alpar@209
  1925
          node_b = graph.addNode();
alpar@209
  1926
          typename _Graph::Edge edge;
alpar@209
  1927
          edge = graph.addEdge(node_a, node_b);
alpar@209
  1928
        }
deba@57
  1929
alpar@209
  1930
        _Graph& graph;
alpar@1125
  1931
        Constraints() {}
deba@57
  1932
      };
deba@57
  1933
    };
deba@57
  1934
deba@1186
  1935
    /// \brief Skeleton class for extendable undirected bipartite graphs.
deba@1186
  1936
    ///
deba@1186
  1937
    /// This class describes the interface of extendable undirected
deba@1186
  1938
    /// bipartite graphs. It extends \ref BaseGraphComponent with
deba@1186
  1939
    /// functions for adding nodes and edges to the graph. This
deba@1186
  1940
    /// concept requires \ref AlterableBpGraphComponent.
deba@1186
  1941
    template <typename BAS = BaseBpGraphComponent>
deba@1186
  1942
    class ExtendableBpGraphComponent : public BAS {
deba@1186
  1943
    public:
deba@1186
  1944
deba@1186
  1945
      typedef BAS Base;
deba@1186
  1946
      typedef typename Base::Node Node;
deba@1193
  1947
      typedef typename Base::RedNode RedNode;
deba@1193
  1948
      typedef typename Base::BlueNode BlueNode;
deba@1186
  1949
      typedef typename Base::Edge Edge;
deba@1186
  1950
deba@1186
  1951
      /// \brief Add a new red node to the digraph.
deba@1186
  1952
      ///
deba@1186
  1953
      /// This function adds a red new node to the digraph.
deba@1193
  1954
      RedNode addRedNode() {
deba@1186
  1955
        return INVALID;
deba@1186
  1956
      }
deba@1186
  1957
deba@1186
  1958
      /// \brief Add a new blue node to the digraph.
deba@1186
  1959
      ///
deba@1186
  1960
      /// This function adds a blue new node to the digraph.
deba@1193
  1961
      BlueNode addBlueNode() {
deba@1186
  1962
        return INVALID;
deba@1186
  1963
      }
deba@1186
  1964
deba@1186
  1965
      /// \brief Add a new edge connecting the given two nodes.
deba@1186
  1966
      ///
deba@1186
  1967
      /// This function adds a new edge connecting the given two nodes
deba@1186
  1968
      /// of the graph. The first node has to be a red node, and the
deba@1186
  1969
      /// second one a blue node.
deba@1193
  1970
      Edge addEdge(const RedNode&, const BlueNode&) {
deba@1193
  1971
        return INVALID;
deba@1193
  1972
      }
deba@1193
  1973
      Edge addEdge(const BlueNode&, const RedNode&) {
deba@1186
  1974
        return INVALID;
deba@1186
  1975
      }
deba@1186
  1976
deba@1186
  1977
      template <typename _BpGraph>
deba@1186
  1978
      struct Constraints {
deba@1186
  1979
        void constraints() {
deba@1186
  1980
          checkConcept<Base, _BpGraph>();
deba@1193
  1981
          typename _BpGraph::RedNode red_node;
deba@1193
  1982
          typename _BpGraph::BlueNode blue_node;
deba@1186
  1983
          red_node = bpgraph.addRedNode();
deba@1186
  1984
          blue_node = bpgraph.addBlueNode();
deba@1186
  1985
          typename _BpGraph::Edge edge;
deba@1186
  1986
          edge = bpgraph.addEdge(red_node, blue_node);
deba@1193
  1987
          edge = bpgraph.addEdge(blue_node, red_node);
deba@1186
  1988
        }
deba@1186
  1989
deba@1186
  1990
        _BpGraph& bpgraph;
deba@1186
  1991
      };
deba@1186
  1992
    };
deba@1186
  1993
kpeter@626
  1994
    /// \brief Skeleton class for erasable directed graphs.
alpar@209
  1995
    ///
kpeter@626
  1996
    /// This class describes the interface of erasable directed graphs.
alpar@956
  1997
    /// It extends \ref BaseDigraphComponent with functions for removing
kpeter@626
  1998
    /// nodes and arcs from the digraph.
kpeter@626
  1999
    /// This concept requires \ref AlterableDigraphComponent.
kpeter@606
  2000
    template <typename BAS = BaseDigraphComponent>
kpeter@606
  2001
    class ErasableDigraphComponent : public BAS {
deba@57
  2002
    public:
deba@57
  2003
kpeter@606
  2004
      typedef BAS Base;
deba@57
  2005
      typedef typename Base::Node Node;
deba@57
  2006
      typedef typename Base::Arc Arc;
deba@57
  2007
deba@57
  2008
      /// \brief Erase a node from the digraph.
deba@57
  2009
      ///
alpar@956
  2010
      /// This function erases the given node from the digraph and all arcs
kpeter@626
  2011
      /// connected to the node.
alpar@209
  2012
      void erase(const Node&) {}
deba@57
  2013
deba@57
  2014
      /// \brief Erase an arc from the digraph.
deba@57
  2015
      ///
kpeter@626
  2016
      /// This function erases the given arc from the digraph.
deba@57
  2017
      void erase(const Arc&) {}
deba@57
  2018
deba@57
  2019
      template <typename _Digraph>
deba@57
  2020
      struct Constraints {
alpar@209
  2021
        void constraints() {
deba@57
  2022
          checkConcept<Base, _Digraph>();
kpeter@626
  2023
          const typename _Digraph::Node node(INVALID);
alpar@209
  2024
          digraph.erase(node);
kpeter@626
  2025
          const typename _Digraph::Arc arc(INVALID);
alpar@209
  2026
          digraph.erase(arc);
alpar@209
  2027
        }
deba@57
  2028
alpar@209
  2029
        _Digraph& digraph;
alpar@1125
  2030
        Constraints() {}
deba@57
  2031
      };
deba@57
  2032
    };
deba@57
  2033
kpeter@626
  2034
    /// \brief Skeleton class for erasable undirected graphs.
alpar@209
  2035
    ///
kpeter@626
  2036
    /// This class describes the interface of erasable undirected graphs.
alpar@956
  2037
    /// It extends \ref BaseGraphComponent with functions for removing
kpeter@626
  2038
    /// nodes and edges from the graph.
kpeter@626
  2039
    /// This concept requires \ref AlterableGraphComponent.
kpeter@606
  2040
    template <typename BAS = BaseGraphComponent>
kpeter@606
  2041
    class ErasableGraphComponent : public BAS {
deba@57
  2042
    public:
deba@57
  2043
kpeter@606
  2044
      typedef BAS Base;
deba@57
  2045
      typedef typename Base::Node Node;
deba@57
  2046
      typedef typename Base::Edge Edge;
deba@57
  2047
deba@57
  2048
      /// \brief Erase a node from the graph.
deba@57
  2049
      ///
kpeter@626
  2050
      /// This function erases the given node from the graph and all edges
kpeter@626
  2051
      /// connected to the node.
alpar@209
  2052
      void erase(const Node&) {}
deba@57
  2053
kpeter@626
  2054
      /// \brief Erase an edge from the digraph.
deba@57
  2055
      ///
kpeter@626
  2056
      /// This function erases the given edge from the digraph.
deba@57
  2057
      void erase(const Edge&) {}
deba@57
  2058
deba@57
  2059
      template <typename _Graph>
deba@57
  2060
      struct Constraints {
alpar@209
  2061
        void constraints() {
deba@57
  2062
          checkConcept<Base, _Graph>();
kpeter@626
  2063
          const typename _Graph::Node node(INVALID);
alpar@209
  2064
          graph.erase(node);
kpeter@626
  2065
          const typename _Graph::Edge edge(INVALID);
alpar@209
  2066
          graph.erase(edge);
alpar@209
  2067
        }
deba@57
  2068
alpar@209
  2069
        _Graph& graph;
alpar@1125
  2070
        Constraints() {}
deba@57
  2071
      };
deba@57
  2072
    };
deba@57
  2073
deba@1186
  2074
    /// \brief Skeleton class for erasable undirected graphs.
deba@1186
  2075
    ///
deba@1186
  2076
    /// This class describes the interface of erasable undirected
deba@1186
  2077
    /// bipartite graphs. It extends \ref BaseBpGraphComponent with
deba@1186
  2078
    /// functions for removing nodes and edges from the graph. This
deba@1186
  2079
    /// concept requires \ref AlterableBpGraphComponent.
deba@1186
  2080
    template <typename BAS = BaseBpGraphComponent>
deba@1186
  2081
    class ErasableBpGraphComponent : public ErasableGraphComponent<BAS> {};
deba@1186
  2082
kpeter@626
  2083
    /// \brief Skeleton class for clearable directed graphs.
deba@57
  2084
    ///
kpeter@626
  2085
    /// This class describes the interface of clearable directed graphs.
kpeter@626
  2086
    /// It extends \ref BaseDigraphComponent with a function for clearing
kpeter@626
  2087
    /// the digraph.
kpeter@626
  2088
    /// This concept requires \ref AlterableDigraphComponent.
kpeter@606
  2089
    template <typename BAS = BaseDigraphComponent>
kpeter@606
  2090
    class ClearableDigraphComponent : public BAS {
deba@57
  2091
    public:
deba@57
  2092
kpeter@606
  2093
      typedef BAS Base;
deba@57
  2094
deba@57
  2095
      /// \brief Erase all nodes and arcs from the digraph.
deba@57
  2096
      ///
kpeter@626
  2097
      /// This function erases all nodes and arcs from the digraph.
alpar@209
  2098
      void clear() {}
deba@57
  2099
deba@57
  2100
      template <typename _Digraph>
deba@57
  2101
      struct Constraints {
alpar@209
  2102
        void constraints() {
deba@57
  2103
          checkConcept<Base, _Digraph>();
alpar@209
  2104
          digraph.clear();
alpar@209
  2105
        }
deba@57
  2106
kpeter@626
  2107
        _Digraph& digraph;
alpar@1125
  2108
        Constraints() {}
deba@57
  2109
      };
deba@57
  2110
    };
deba@57
  2111
kpeter@626
  2112
    /// \brief Skeleton class for clearable undirected graphs.
deba@57
  2113
    ///
kpeter@626
  2114
    /// This class describes the interface of clearable undirected graphs.
kpeter@626
  2115
    /// It extends \ref BaseGraphComponent with a function for clearing
kpeter@626
  2116
    /// the graph.
kpeter@626
  2117
    /// This concept requires \ref AlterableGraphComponent.
kpeter@606
  2118
    template <typename BAS = BaseGraphComponent>
deba@1186
  2119
    class ClearableGraphComponent : public ClearableDigraphComponent<BAS> {};
deba@57
  2120
deba@1186
  2121
    /// \brief Skeleton class for clearable undirected biparite graphs.
deba@1186
  2122
    ///
deba@1186
  2123
    /// This class describes the interface of clearable undirected
deba@1186
  2124
    /// bipartite graphs. It extends \ref BaseBpGraphComponent with a
deba@1186
  2125
    /// function for clearing the graph.  This concept requires \ref
deba@1186
  2126
    /// AlterableBpGraphComponent.
deba@1186
  2127
    template <typename BAS = BaseBpGraphComponent>
deba@1186
  2128
    class ClearableBpGraphComponent : public ClearableGraphComponent<BAS> {};
deba@57
  2129
deba@57
  2130
  }
deba@57
  2131
deba@57
  2132
}
deba@57
  2133
deba@57
  2134
#endif