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