lemon/concept/ugraph.h
author alpar
Mon, 30 Jan 2006 09:37:41 +0000
changeset 1930 92b70deed0c5
parent 1909 2d806130e700
child 1946 17eb3eaad9f8
permissions -rw-r--r--
Solve bug #23: Floating versus Integer Coordinates

- BoundingBox values rounds to integer
- The generated .eps rescales if the bounding box were too small otherwise.
klao@962
     1
/* -*- C++ -*-
klao@962
     2
 *
klao@1909
     3
 * lemon/concept/ugraph_component.h - Part of LEMON, a generic
klao@962
     4
 * C++ optimization library
klao@962
     5
 *
alpar@1875
     6
 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi
alpar@1359
     7
 * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
klao@962
     8
 * EGRES).
klao@962
     9
 *
klao@962
    10
 * Permission to use, modify and distribute this software is granted
klao@962
    11
 * provided that this copyright notice appears in all copies. For
klao@962
    12
 * precise terms see the accompanying LICENSE file.
klao@962
    13
 *
klao@962
    14
 * This software is provided "AS IS" with no warranty of any kind,
klao@962
    15
 * express or implied, and with no claim as to its suitability for any
klao@962
    16
 * purpose.
klao@962
    17
 *
klao@962
    18
 */
klao@962
    19
klao@1030
    20
///\ingroup graph_concepts
klao@962
    21
///\file
klao@962
    22
///\brief Undirected graphs and components of.
klao@962
    23
klao@962
    24
deba@1910
    25
#ifndef LEMON_CONCEPT_UGRAPH_H
deba@1910
    26
#define LEMON_CONCEPT_UGRAPH_H
klao@962
    27
klao@962
    28
#include <lemon/concept/graph_component.h>
alpar@1620
    29
#include <lemon/concept/graph.h>
alpar@1448
    30
#include <lemon/utility.h>
klao@962
    31
klao@962
    32
namespace lemon {
klao@962
    33
  namespace concept {
klao@962
    34
alpar@1630
    35
//     /// Skeleton class which describes an edge with direction in \ref
klao@1909
    36
//     /// UGraph "undirected graph".
klao@1909
    37
    template <typename UGraph>
klao@1909
    38
    class UGraphEdge : public UGraph::UEdge {
klao@1909
    39
      typedef typename UGraph::UEdge UEdge;
klao@1909
    40
      typedef typename UGraph::Node Node;
klao@1030
    41
    public:
klao@1030
    42
klao@1030
    43
      /// \e
klao@1909
    44
      UGraphEdge() {}
klao@1030
    45
klao@1030
    46
      /// \e
klao@1909
    47
      UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}
klao@1030
    48
klao@1030
    49
      /// \e
klao@1909
    50
      UGraphEdge(Invalid) {}
klao@1030
    51
klao@1158
    52
      /// \brief Directed edge from undirected edge and a source node.
klao@1030
    53
      ///
klao@1158
    54
      /// Constructs a directed edge from undirected edge and a source node.
klao@1158
    55
      ///
klao@1158
    56
      /// \note You have to specify the graph for this constructor.
klao@1909
    57
      UGraphEdge(const UGraph &g,
klao@1909
    58
		     UEdge u_edge, Node n) {
klao@1909
    59
	ignore_unused_variable_warning(u_edge);
klao@1158
    60
	ignore_unused_variable_warning(g);
klao@1158
    61
	ignore_unused_variable_warning(n);
klao@1030
    62
      }
klao@1030
    63
klao@1030
    64
      /// \e
klao@1909
    65
      UGraphEdge& operator=(UGraphEdge) { return *this; }
klao@1030
    66
klao@1030
    67
      /// \e
klao@1909
    68
      bool operator==(UGraphEdge) const { return true; }
klao@1030
    69
      /// \e
klao@1909
    70
      bool operator!=(UGraphEdge) const { return false; }
klao@1030
    71
klao@1030
    72
      /// \e
klao@1909
    73
      bool operator<(UGraphEdge) const { return false; }
klao@1030
    74
klao@1030
    75
      template <typename Edge>
klao@1030
    76
      struct Constraints {
klao@1030
    77
	void constraints() {
klao@1158
    78
	  const_constraints();
klao@1158
    79
	}
klao@1158
    80
	void const_constraints() const {
klao@1030
    81
	  /// \bug This should be is_base_and_derived ...
klao@1909
    82
	  UEdge ue = e;
klao@1030
    83
	  ue = e;
klao@1030
    84
klao@1158
    85
	  Edge e_with_source(graph,ue,n);
klao@1158
    86
	  ignore_unused_variable_warning(e_with_source);
klao@1030
    87
	}
klao@1030
    88
	Edge e;
klao@1909
    89
	UEdge ue;
klao@1909
    90
	UGraph graph;
klao@1158
    91
	Node n;
klao@1030
    92
      };
klao@1030
    93
    };
klao@1030
    94
    
klao@962
    95
klao@1909
    96
    struct BaseIterableUGraphConcept {
deba@989
    97
klao@1022
    98
      template <typename Graph>
klao@1022
    99
      struct Constraints {
klao@962
   100
klao@1909
   101
	typedef typename Graph::UEdge UEdge;
klao@1022
   102
	typedef typename Graph::Edge Edge;
klao@1022
   103
	typedef typename Graph::Node Node;
klao@962
   104
klao@1022
   105
	void constraints() {
klao@1022
   106
	  checkConcept<BaseIterableGraphComponent, Graph>();
klao@1909
   107
	  checkConcept<GraphItem<>, UEdge>();
klao@1909
   108
	  //checkConcept<UGraphEdge<Graph>, Edge>();
klao@962
   109
klao@1030
   110
	  graph.first(ue);
klao@1030
   111
	  graph.next(ue);
klao@1022
   112
klao@1030
   113
	  const_constraints();
klao@1030
   114
	}
klao@1030
   115
	void const_constraints() {
klao@1022
   116
	  Node n;
klao@1022
   117
	  n = graph.target(ue);
klao@1022
   118
	  n = graph.source(ue);
klao@1030
   119
	  n = graph.oppositeNode(n0, ue);
klao@1022
   120
klao@1030
   121
	  bool b;
deba@1627
   122
	  b = graph.direction(e);
klao@1909
   123
	  Edge e = graph.direct(UEdge(), true);
klao@1909
   124
	  e = graph.direct(UEdge(), n);
deba@1627
   125
 
klao@1030
   126
	  ignore_unused_variable_warning(b);
klao@1022
   127
	}
klao@1030
   128
klao@1030
   129
	Graph graph;
klao@1022
   130
	Edge e;
klao@1030
   131
	Node n0;
klao@1909
   132
	UEdge ue;
klao@1022
   133
      };
klao@1022
   134
klao@962
   135
    };
klao@962
   136
klao@1022
   137
klao@1909
   138
    struct IterableUGraphConcept {
klao@962
   139
klao@1022
   140
      template <typename Graph>
klao@1022
   141
      struct Constraints {
klao@1022
   142
	void constraints() {
klao@1022
   143
	  /// \todo we don't need the iterable component to be base iterable
klao@1022
   144
	  /// Don't we really???
klao@1909
   145
	  //checkConcept< BaseIterableUGraphConcept, Graph > ();
klao@962
   146
klao@1022
   147
	  checkConcept<IterableGraphComponent, Graph> ();
klao@1021
   148
klao@1909
   149
	  typedef typename Graph::UEdge UEdge;
klao@1909
   150
	  typedef typename Graph::UEdgeIt UEdgeIt;
klao@1030
   151
	  typedef typename Graph::IncEdgeIt IncEdgeIt;
klao@1022
   152
klao@1909
   153
	  checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();
klao@1909
   154
	  checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();
klao@1022
   155
	}
klao@1022
   156
      };
klao@1022
   157
klao@1022
   158
    };
klao@1022
   159
klao@1909
   160
    struct MappableUGraphConcept {
klao@1022
   161
klao@1022
   162
      template <typename Graph>
klao@1022
   163
      struct Constraints {
klao@1022
   164
klao@1022
   165
	struct Dummy {
klao@1022
   166
	  int value;
klao@1022
   167
	  Dummy() : value(0) {}
klao@1022
   168
	  Dummy(int _v) : value(_v) {}
klao@1022
   169
	};
klao@1022
   170
klao@1022
   171
	void constraints() {
klao@1022
   172
	  checkConcept<MappableGraphComponent, Graph>();
klao@1022
   173
klao@1909
   174
	  typedef typename Graph::template UEdgeMap<int> IntMap;
klao@1909
   175
	  checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,
klao@1022
   176
	    IntMap >();
klao@1022
   177
klao@1909
   178
	  typedef typename Graph::template UEdgeMap<bool> BoolMap;
klao@1909
   179
	  checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,
klao@1022
   180
	    BoolMap >();
klao@1022
   181
klao@1909
   182
	  typedef typename Graph::template UEdgeMap<Dummy> DummyMap;
klao@1909
   183
	  checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,
klao@1022
   184
	    DummyMap >();
klao@1022
   185
	}
klao@1022
   186
      };
klao@1022
   187
klao@1022
   188
    };
klao@1022
   189
klao@1909
   190
    struct ExtendableUGraphConcept {
klao@1022
   191
klao@1022
   192
      template <typename Graph>
klao@1022
   193
      struct Constraints {
klao@1022
   194
	void constraints() {
klao@1022
   195
	  node_a = graph.addNode();
klao@1022
   196
	  uedge = graph.addEdge(node_a, node_b);
klao@1022
   197
	}
klao@1022
   198
	typename Graph::Node node_a, node_b;
klao@1909
   199
	typename Graph::UEdge uedge;
klao@1022
   200
	Graph graph;
klao@1022
   201
      };
klao@1022
   202
klao@1022
   203
    };
klao@1022
   204
klao@1909
   205
    struct ErasableUGraphConcept {
klao@1022
   206
klao@1022
   207
      template <typename Graph>
klao@1022
   208
      struct Constraints {
klao@1022
   209
	void constraints() {
klao@1022
   210
	  graph.erase(n);
klao@1022
   211
	  graph.erase(e);
klao@1022
   212
	}
klao@1022
   213
	Graph graph;
klao@1022
   214
	typename Graph::Node n;
klao@1909
   215
	typename Graph::UEdge e;
klao@1022
   216
      };
klao@1022
   217
klao@1022
   218
    };
klao@1022
   219
alpar@1620
   220
    /// \addtogroup graph_concepts
alpar@1620
   221
    /// @{
alpar@1620
   222
alpar@1620
   223
klao@1030
   224
    /// Class describing the concept of Undirected Graphs.
klao@1030
   225
klao@1030
   226
    /// This class describes the common interface of all Undirected
klao@1030
   227
    /// Graphs.
klao@1030
   228
    ///
klao@1030
   229
    /// As all concept describing classes it provides only interface
klao@1030
   230
    /// without any sensible implementation. So any algorithm for
klao@1030
   231
    /// undirected graph should compile with this class, but it will not
klao@1030
   232
    /// run properly, of couse.
klao@1030
   233
    ///
klao@1030
   234
    /// In LEMON undirected graphs also fulfill the concept of directed
alpar@1631
   235
    /// graphs (\ref lemon::concept::StaticGraph "Graph Concept"). For
klao@1909
   236
    /// explanation of this and more see also the page \ref ugraphs,
klao@1030
   237
    /// a tutorial about undirected graphs.
deba@1627
   238
    ///
deba@1627
   239
    /// You can assume that all undirected graph can be handled
deba@1627
   240
    /// as a static directed graph. This way it is fully conform
deba@1627
   241
    /// to the StaticGraph concept.
klao@1030
   242
klao@1909
   243
    class UGraph {
klao@1022
   244
    public:
alpar@1448
   245
      ///\e
alpar@1448
   246
alpar@1448
   247
      ///\todo undocumented
alpar@1448
   248
      ///
klao@1909
   249
      typedef True UTag;
klao@1022
   250
deba@1669
   251
      /// \brief The base type of node iterators, 
deba@1627
   252
      /// or in other words, the trivial node iterator.
deba@1669
   253
      ///
deba@1627
   254
      /// This is the base type of each node iterator,
deba@1627
   255
      /// thus each kind of node iterator converts to this.
deba@1627
   256
      /// More precisely each kind of node iterator should be inherited 
deba@1627
   257
      /// from the trivial node iterator.
deba@1627
   258
      class Node {
deba@1627
   259
      public:
deba@1627
   260
        /// Default constructor
deba@1627
   261
deba@1627
   262
        /// @warning The default constructor sets the iterator
deba@1627
   263
        /// to an undefined value.
deba@1627
   264
        Node() { }
deba@1627
   265
        /// Copy constructor.
deba@1627
   266
deba@1627
   267
        /// Copy constructor.
deba@1627
   268
        ///
deba@1627
   269
        Node(const Node&) { }
deba@1627
   270
deba@1627
   271
        /// Invalid constructor \& conversion.
deba@1627
   272
deba@1627
   273
        /// This constructor initializes the iterator to be invalid.
deba@1627
   274
        /// \sa Invalid for more details.
deba@1627
   275
        Node(Invalid) { }
deba@1627
   276
        /// Equality operator
deba@1627
   277
deba@1627
   278
        /// Two iterators are equal if and only if they point to the
deba@1627
   279
        /// same object or both are invalid.
deba@1627
   280
        bool operator==(Node) const { return true; }
deba@1627
   281
deba@1627
   282
        /// Inequality operator
deba@1627
   283
        
deba@1627
   284
        /// \sa operator==(Node n)
deba@1627
   285
        ///
deba@1627
   286
        bool operator!=(Node) const { return true; }
deba@1627
   287
deba@1627
   288
	/// Artificial ordering operator.
deba@1627
   289
	
deba@1627
   290
	/// To allow the use of graph descriptors as key type in std::map or
deba@1627
   291
	/// similar associative container we require this.
deba@1627
   292
	///
deba@1627
   293
	/// \note This operator only have to define some strict ordering of
deba@1627
   294
	/// the items; this order has nothing to do with the iteration
deba@1627
   295
	/// ordering of the items.
deba@1627
   296
	///
deba@1627
   297
	/// \bug This is a technical requirement. Do we really need this?
deba@1627
   298
	bool operator<(Node) const { return false; }
deba@1627
   299
deba@1627
   300
      };
deba@1627
   301
    
deba@1627
   302
      /// This iterator goes through each node.
deba@1627
   303
deba@1627
   304
      /// This iterator goes through each node.
deba@1627
   305
      /// Its usage is quite simple, for example you can count the number
deba@1627
   306
      /// of nodes in graph \c g of type \c Graph like this:
deba@1627
   307
      /// \code
deba@1627
   308
      /// int count=0;
deba@1627
   309
      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
deba@1627
   310
      /// \endcode
deba@1627
   311
      class NodeIt : public Node {
deba@1627
   312
      public:
deba@1627
   313
        /// Default constructor
deba@1627
   314
deba@1627
   315
        /// @warning The default constructor sets the iterator
deba@1627
   316
        /// to an undefined value.
deba@1627
   317
        NodeIt() { }
deba@1627
   318
        /// Copy constructor.
deba@1627
   319
        
deba@1627
   320
        /// Copy constructor.
deba@1627
   321
        ///
deba@1627
   322
        NodeIt(const NodeIt& n) : Node(n) { }
deba@1627
   323
        /// Invalid constructor \& conversion.
deba@1627
   324
deba@1627
   325
        /// Initialize the iterator to be invalid.
deba@1627
   326
        /// \sa Invalid for more details.
deba@1627
   327
        NodeIt(Invalid) { }
deba@1627
   328
        /// Sets the iterator to the first node.
deba@1627
   329
deba@1627
   330
        /// Sets the iterator to the first node of \c g.
deba@1627
   331
        ///
klao@1909
   332
        NodeIt(const UGraph&) { }
deba@1627
   333
        /// Node -> NodeIt conversion.
deba@1627
   334
deba@1627
   335
        /// Sets the iterator to the node of \c the graph pointed by 
deba@1627
   336
	/// the trivial iterator.
deba@1627
   337
        /// This feature necessitates that each time we 
deba@1627
   338
        /// iterate the edge-set, the iteration order is the same.
klao@1909
   339
        NodeIt(const UGraph&, const Node&) { }
deba@1627
   340
        /// Next node.
deba@1627
   341
deba@1627
   342
        /// Assign the iterator to the next node.
deba@1627
   343
        ///
deba@1627
   344
        NodeIt& operator++() { return *this; }
deba@1627
   345
      };
deba@1627
   346
    
deba@1627
   347
    
alpar@1620
   348
      /// The base type of the undirected edge iterators.
deba@1627
   349
alpar@1620
   350
      /// The base type of the undirected edge iterators.
alpar@1620
   351
      ///
klao@1909
   352
      class UEdge {
alpar@1620
   353
      public:
alpar@1620
   354
        /// Default constructor
klao@1030
   355
alpar@1620
   356
        /// @warning The default constructor sets the iterator
alpar@1620
   357
        /// to an undefined value.
klao@1909
   358
        UEdge() { }
alpar@1620
   359
        /// Copy constructor.
klao@1030
   360
alpar@1620
   361
        /// Copy constructor.
alpar@1620
   362
        ///
klao@1909
   363
        UEdge(const UEdge&) { }
alpar@1620
   364
        /// Initialize the iterator to be invalid.
klao@1030
   365
alpar@1620
   366
        /// Initialize the iterator to be invalid.
alpar@1620
   367
        ///
klao@1909
   368
        UEdge(Invalid) { }
alpar@1620
   369
        /// Equality operator
klao@1030
   370
alpar@1620
   371
        /// Two iterators are equal if and only if they point to the
alpar@1620
   372
        /// same object or both are invalid.
klao@1909
   373
        bool operator==(UEdge) const { return true; }
alpar@1620
   374
        /// Inequality operator
klao@1030
   375
klao@1909
   376
        /// \sa operator==(UEdge n)
alpar@1620
   377
        ///
klao@1909
   378
        bool operator!=(UEdge) const { return true; }
klao@1030
   379
deba@1627
   380
	/// Artificial ordering operator.
deba@1627
   381
	
deba@1627
   382
	/// To allow the use of graph descriptors as key type in std::map or
deba@1627
   383
	/// similar associative container we require this.
deba@1627
   384
	///
deba@1627
   385
	/// \note This operator only have to define some strict ordering of
deba@1627
   386
	/// the items; this order has nothing to do with the iteration
deba@1627
   387
	/// ordering of the items.
deba@1627
   388
	///
deba@1627
   389
	/// \bug This is a technical requirement. Do we really need this?
klao@1909
   390
	bool operator<(UEdge) const { return false; }
deba@1627
   391
      };
klao@1030
   392
alpar@1620
   393
      /// This iterator goes through each undirected edge.
klao@1030
   394
alpar@1620
   395
      /// This iterator goes through each undirected edge of a graph.
alpar@1620
   396
      /// Its usage is quite simple, for example you can count the number
deba@1627
   397
      /// of undirected edges in a graph \c g of type \c Graph as follows:
alpar@1620
   398
      /// \code
alpar@1620
   399
      /// int count=0;
klao@1909
   400
      /// for(Graph::UEdgeIt e(g); e!=INVALID; ++e) ++count;
alpar@1620
   401
      /// \endcode
klao@1909
   402
      class UEdgeIt : public UEdge {
alpar@1620
   403
      public:
alpar@1620
   404
        /// Default constructor
deba@1627
   405
alpar@1620
   406
        /// @warning The default constructor sets the iterator
alpar@1620
   407
        /// to an undefined value.
klao@1909
   408
        UEdgeIt() { }
alpar@1620
   409
        /// Copy constructor.
deba@1627
   410
alpar@1620
   411
        /// Copy constructor.
alpar@1620
   412
        ///
klao@1909
   413
        UEdgeIt(const UEdgeIt& e) : UEdge(e) { }
alpar@1620
   414
        /// Initialize the iterator to be invalid.
klao@1030
   415
alpar@1620
   416
        /// Initialize the iterator to be invalid.
alpar@1620
   417
        ///
klao@1909
   418
        UEdgeIt(Invalid) { }
deba@1627
   419
        /// This constructor sets the iterator to the first undirected edge.
alpar@1620
   420
    
deba@1627
   421
        /// This constructor sets the iterator to the first undirected edge.
klao@1909
   422
        UEdgeIt(const UGraph&) { }
klao@1909
   423
        /// UEdge -> UEdgeIt conversion
klao@1030
   424
deba@1627
   425
        /// Sets the iterator to the value of the trivial iterator.
deba@1627
   426
        /// This feature necessitates that each time we
deba@1627
   427
        /// iterate the undirected edge-set, the iteration order is the 
deba@1627
   428
	/// same.
klao@1909
   429
        UEdgeIt(const UGraph&, const UEdge&) { } 
deba@1627
   430
        /// Next undirected edge
alpar@1620
   431
        
deba@1627
   432
        /// Assign the iterator to the next undirected edge.
klao@1909
   433
        UEdgeIt& operator++() { return *this; }
alpar@1620
   434
      };
klao@1030
   435
deba@1627
   436
      /// \brief This iterator goes trough the incident undirected 
deba@1627
   437
      /// edges of a node.
deba@1627
   438
      ///
alpar@1620
   439
      /// This iterator goes trough the incident undirected edges
alpar@1620
   440
      /// of a certain node
alpar@1620
   441
      /// of a graph.
alpar@1620
   442
      /// Its usage is quite simple, for example you can compute the
alpar@1620
   443
      /// degree (i.e. count the number
alpar@1620
   444
      /// of incident edges of a node \c n
alpar@1620
   445
      /// in graph \c g of type \c Graph as follows.
alpar@1620
   446
      /// \code
alpar@1620
   447
      /// int count=0;
alpar@1620
   448
      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
alpar@1620
   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:
deba@1627
   535
      /// \code
deba@1627
   536
      /// int count=0;
deba@1627
   537
      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
deba@1627
   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.
deba@1627
   580
      /// \code
deba@1627
   581
      /// int count=0;
deba@1627
   582
      /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
deba@1627
   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.
deba@1627
   632
      /// \code
deba@1627
   633
      /// int count=0;
deba@1627
   634
      /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
deba@1627
   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@1627
   868
      /// \brief Base node of the iterator
klao@1158
   869
      ///
klao@1158
   870
      /// Returns the base node (the source in this case) of the iterator
klao@1158
   871
      Node baseNode(OutEdgeIt e) const {
klao@1158
   872
	return source(e);
klao@1158
   873
      }
deba@1627
   874
      /// \brief Running node of the iterator
klao@1158
   875
      ///
klao@1158
   876
      /// Returns the running node (the target in this case) of the
klao@1158
   877
      /// iterator
klao@1158
   878
      Node runningNode(OutEdgeIt e) const {
klao@1158
   879
	return target(e);
klao@1158
   880
      }
klao@1158
   881
deba@1627
   882
      /// \brief Base node of the iterator
klao@1158
   883
      ///
klao@1158
   884
      /// Returns the base node (the target in this case) of the iterator
klao@1158
   885
      Node baseNode(InEdgeIt e) const {
klao@1158
   886
	return target(e);
klao@1158
   887
      }
deba@1627
   888
      /// \brief Running node of the iterator
klao@1158
   889
      ///
klao@1158
   890
      /// Returns the running node (the source in this case) of the
klao@1158
   891
      /// iterator
klao@1158
   892
      Node runningNode(InEdgeIt e) const {
klao@1158
   893
	return source(e);
klao@1158
   894
      }
klao@1158
   895
deba@1627
   896
      /// \brief Base node of the iterator
klao@1158
   897
      ///
klao@1158
   898
      /// Returns the base node of the iterator
alpar@1367
   899
      Node baseNode(IncEdgeIt) const {
klao@1158
   900
	return INVALID;
klao@1158
   901
      }
deba@1627
   902
      
deba@1627
   903
      /// \brief Running node of the iterator
klao@1158
   904
      ///
klao@1158
   905
      /// Returns the running node of the iterator
alpar@1367
   906
      Node runningNode(IncEdgeIt) const {
klao@1158
   907
	return INVALID;
klao@1158
   908
      }
klao@1158
   909
klao@1022
   910
      template <typename Graph>
klao@1022
   911
      struct Constraints {
klao@1022
   912
	void constraints() {
klao@1909
   913
	  checkConcept<BaseIterableUGraphConcept, Graph>();
klao@1909
   914
	  checkConcept<IterableUGraphConcept, Graph>();
klao@1909
   915
	  checkConcept<MappableUGraphConcept, Graph>();
klao@1022
   916
	}
klao@1022
   917
      };
klao@1022
   918
klao@1022
   919
    };
klao@1022
   920
deba@1627
   921
    /// \brief An empty non-static undirected graph class.
deba@1627
   922
    ///    
klao@1909
   923
    /// This class provides everything that \ref UGraph does.
deba@1627
   924
    /// Additionally it enables building graphs from scratch.
klao@1909
   925
    class ExtendableUGraph : public UGraph {
klao@1022
   926
    public:
deba@1627
   927
      
deba@1627
   928
      /// \brief Add a new node to the graph.
deba@1627
   929
      ///
deba@1627
   930
      /// Add a new node to the graph.
deba@1627
   931
      /// \return the new node.
deba@1627
   932
      Node addNode();
deba@1627
   933
deba@1627
   934
      /// \brief Add a new undirected edge to the graph.
deba@1627
   935
      ///
deba@1627
   936
      /// Add a new undirected edge to the graph.
deba@1627
   937
      /// \return the new edge.
klao@1909
   938
      UEdge addEdge(const Node& from, const Node& to);
deba@1627
   939
deba@1627
   940
      /// \brief Resets the graph.
deba@1627
   941
      ///
deba@1627
   942
      /// This function deletes all undirected edges and nodes of the graph.
deba@1627
   943
      /// It also frees the memory allocated to store them.
deba@1627
   944
      void clear() { }
klao@1022
   945
klao@1022
   946
      template <typename Graph>
klao@1022
   947
      struct Constraints {
klao@1022
   948
	void constraints() {
klao@1909
   949
	  checkConcept<BaseIterableUGraphConcept, Graph>();
klao@1909
   950
	  checkConcept<IterableUGraphConcept, Graph>();
klao@1909
   951
	  checkConcept<MappableUGraphConcept, Graph>();
klao@1022
   952
klao@1909
   953
	  checkConcept<UGraph, Graph>();
klao@1909
   954
	  checkConcept<ExtendableUGraphConcept, Graph>();
klao@1022
   955
	  checkConcept<ClearableGraphComponent, Graph>();
klao@1022
   956
	}
klao@1022
   957
      };
klao@1022
   958
klao@1022
   959
    };
klao@1022
   960
deba@1627
   961
    /// \brief An empty erasable undirected graph class.
deba@1627
   962
    ///
klao@1909
   963
    /// This class is an extension of \ref ExtendableUGraph. It makes it
deba@1627
   964
    /// possible to erase undirected edges or nodes.
klao@1909
   965
    class ErasableUGraph : public ExtendableUGraph {
klao@1022
   966
    public:
klao@1022
   967
deba@1627
   968
      /// \brief Deletes a node.
deba@1627
   969
      ///
deba@1627
   970
      /// Deletes a node.
deba@1627
   971
      ///
deba@1627
   972
      void erase(Node) { }
deba@1627
   973
      /// \brief Deletes an undirected edge.
deba@1627
   974
      ///
deba@1627
   975
      /// Deletes an undirected edge.
deba@1627
   976
      ///
klao@1909
   977
      void erase(UEdge) { }
deba@1627
   978
klao@1022
   979
      template <typename Graph>
klao@1022
   980
      struct Constraints {
klao@1022
   981
	void constraints() {
klao@1909
   982
	  checkConcept<ExtendableUGraph, Graph>();
klao@1909
   983
	  checkConcept<ErasableUGraphConcept, Graph>();
klao@1022
   984
	}
klao@1022
   985
      };
klao@1022
   986
klao@962
   987
    };
klao@962
   988
klao@1030
   989
    /// @}
klao@1030
   990
klao@962
   991
  }
klao@962
   992
klao@962
   993
}
klao@962
   994
klao@962
   995
#endif