//     /// Skeleton class which describes an edge with direction in \ref

 //     /// UGraph "undirected graph".

     template <typename UGraph>

     class UGraphEdge : public UGraph::UEdge {

       typedef typename UGraph::UEdge UEdge;

       typedef typename UGraph::Node Node;

     public:

       /// \e

       UGraphEdge() {}

       /// \e

       UGraphEdge(const UGraphEdge& e) : UGraph::UEdge(e) {}

       /// \e

       UGraphEdge(Invalid) {}

       /// \brief Directed edge from undirected edge and a source node.

       ///

       /// Constructs a directed edge from undirected edge and a source node.

       ///

       /// \note You have to specify the graph for this constructor.

       UGraphEdge(const UGraph &g,

 		     UEdge u_edge, Node n) {

 	ignore_unused_variable_warning(u_edge);

 	ignore_unused_variable_warning(g);

 	ignore_unused_variable_warning(n);

       }

       /// \e

       UGraphEdge& operator=(UGraphEdge) { return *this; }

       /// \e

       bool operator==(UGraphEdge) const { return true; }

       /// \e

       bool operator!=(UGraphEdge) const { return false; }

       /// \e

       bool operator<(UGraphEdge) const { return false; }

       template <typename Edge>

       struct Constraints {

 	void constraints() {

 	  const_constraints();

 	}

 	void const_constraints() const {

 	  /// \bug This should be is_base_and_derived ...

 	  UEdge ue = e;

 	  ue = e;

 	  Edge e_with_source(graph,ue,n);

 	  ignore_unused_variable_warning(e_with_source);

 	}

 	Edge e;

 	UEdge ue;

 	UGraph graph;

 	Node n;

       };

     };

     struct BaseIterableUGraphConcept {

       template <typename Graph>

       struct Constraints {

 	typedef typename Graph::UEdge UEdge;

 	typedef typename Graph::Edge Edge;

 	typedef typename Graph::Node Node;

 	void constraints() {

 	  checkConcept<BaseIterableGraphComponent, Graph>();

 	  checkConcept<GraphItem<>, UEdge>();

 	  //checkConcept<UGraphEdge<Graph>, Edge>();

 	  graph.first(ue);

 	  graph.next(ue);

 	  const_constraints();

 	}

 	void const_constraints() {

 	  Node n;

 	  n = graph.target(ue);

 	  n = graph.source(ue);

 	  n = graph.oppositeNode(n0, ue);

 	  bool b;

 	  b = graph.direction(e);

 	  Edge e = graph.direct(UEdge(), true);

 	  e = graph.direct(UEdge(), n);

 	  ignore_unused_variable_warning(b);

 	}

 	Graph graph;

 	Edge e;

 	Node n0;

 	UEdge ue;

       };

     };

     struct IterableUGraphConcept {

       template <typename Graph>

       struct Constraints {

 	void constraints() {

 	  /// \todo we don't need the iterable component to be base iterable

 	  /// Don't we really???

 	  //checkConcept< BaseIterableUGraphConcept, Graph > ();

 	  checkConcept<IterableGraphComponent, Graph> ();

 	  typedef typename Graph::UEdge UEdge;

 	  typedef typename Graph::UEdgeIt UEdgeIt;

 	  typedef typename Graph::IncEdgeIt IncEdgeIt;

 	  checkConcept<GraphIterator<Graph, UEdge>, UEdgeIt>();

 	  checkConcept<GraphIncIterator<Graph, UEdge>, IncEdgeIt>();

 	}

       };

     };

     struct MappableUGraphConcept {

       template <typename Graph>

       struct Constraints {

 	struct Dummy {

 	  int value;

 	  Dummy() : value(0) {}

 	  Dummy(int _v) : value(_v) {}

 	};

 	void constraints() {

 	  checkConcept<MappableGraphComponent, Graph>();

 	  typedef typename Graph::template UEdgeMap<int> IntMap;

 	  checkConcept<GraphMap<Graph, typename Graph::UEdge, int>,

 	    IntMap >();

 	  typedef typename Graph::template UEdgeMap<bool> BoolMap;

 	  checkConcept<GraphMap<Graph, typename Graph::UEdge, bool>,

 	    BoolMap >();

 	  typedef typename Graph::template UEdgeMap<Dummy> DummyMap;

 	  checkConcept<GraphMap<Graph, typename Graph::UEdge, Dummy>,

 	    DummyMap >();

 	}

       };

     };

     struct ExtendableUGraphConcept {

       template <typename Graph>

       struct Constraints {

 	void constraints() {

 	  node_a = graph.addNode();

 	  uedge = graph.addEdge(node_a, node_b);

 	}

 	typename Graph::Node node_a, node_b;

 	typename Graph::UEdge uedge;

 	Graph graph;

       };

     };

     struct ErasableUGraphConcept {

       template <typename Graph>

       struct Constraints {

 	void constraints() {

 	  graph.erase(n);

 	  graph.erase(e);

 	}

 	Graph graph;

 	typename Graph::Node n;

 	typename Graph::UEdge e;

       };

     };

 //       /// \brief First node of the graph

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief Next node of the graph

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief First undirected edge of the graph

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief Next undirected edge of the graph

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief First directed edge of the graph

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief Next directed edge of the graph

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief First outgoing edge from a given node

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief Next outgoing edge to a node

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief First incoming edge to a given node

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

 //       /// \brief Next incoming edge to a node

 //       ///

 //       /// \note This method is part of so called \ref

 //       /// developpers_interface "Developpers' interface", so it shouldn't

 //       /// be used in an end-user program.

     /// \brief An empty non-static undirected graph class.

     ///    

     /// This class provides everything that \ref UGraph does.

     /// Additionally it enables building graphs from scratch.

     class ExtendableUGraph : public UGraph {

     public:

       /// \brief Add a new node to the graph.

       ///

       /// Add a new node to the graph.

       /// \return the new node.

       Node addNode();

       /// \brief Add a new undirected edge to the graph.

       ///

       /// Add a new undirected edge to the graph.

       /// \return the new edge.

       UEdge addEdge(const Node& from, const Node& to);

       /// \brief Resets the graph.

       ///

       /// This function deletes all undirected edges and nodes of the graph.

       /// It also frees the memory allocated to store them.

       void clear() { }

       template <typename Graph>

       struct Constraints {

 	void constraints() {

 	  checkConcept<BaseIterableUGraphConcept, Graph>();

 	  checkConcept<IterableUGraphConcept, Graph>();

 	  checkConcept<MappableUGraphConcept, Graph>();

 	  checkConcept<UGraph, Graph>();

 	  checkConcept<ExtendableUGraphConcept, Graph>();

 	  checkConcept<ClearableGraphComponent, Graph>();

 	}

       };

     };

     /// \brief An empty erasable undirected graph class.

     ///

     /// This class is an extension of \ref ExtendableUGraph. It makes it

     /// possible to erase undirected edges or nodes.

     class ErasableUGraph : public ExtendableUGraph {

     public:

       /// \brief Deletes a node.

       ///

       /// Deletes a node.

       ///

       void erase(Node) { }

       /// \brief Deletes an undirected edge.

       ///

       /// Deletes an undirected edge.

       ///

       void erase(UEdge) { }

       template <typename Graph>

       struct Constraints {

 	void constraints() {

 	  checkConcept<ExtendableUGraph, Graph>();

 	  checkConcept<ErasableUGraphConcept, Graph>();

 	}

       };

     };