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