/// \brief An empty iterable base graph class.

     /// \brief An empty base bipartite undirected graph class.

     /// This class provides beside the core graph features

     /// This class provides the minimal set of features needed for an

     /// core iterable interface for the graph structure.

     /// bipartite undirected graph structure. All bipartite undirected

     /// Most of the base graphs should be conform to this concept.

     /// graph concepts have to be conform to this base graph. It just

     template <typename _Base = BaseGraphComponent>

     /// provides types for nodes, A-nodes, B-nodes, edges and

     class BaseIterableGraphComponent : public _Base {

     /// undirected edges and functions to get the source and the

     public:

     /// target of the edges and undirected edges, conversion from

     /// edges to undirected edges and function to get both direction

       typedef _Base Base; 

     /// of the undirected edges.

       typedef typename Base::Node Node;

     class BaseBpUGraphComponent : public BaseUGraphComponent {

       typedef typename Base::Edge Edge;

     public:

       typedef BaseUGraphComponent::Node Node;

       /// \brief Gives back the first node in the iterating order.

       typedef BaseUGraphComponent::Edge Edge;

       ///      

       typedef BaseUGraphComponent::UEdge UEdge;

       /// Gives back the first node in the iterating order.

       ///     

       /// \brief Helper class for A-nodes.

       void first(Node&) const {}

       ///

       /// This class is just a helper class for A-nodes, it is not

       /// \brief Gives back the next node in the iterating order.

       /// suggested to use it directly. It can be converted easily to

       ///

       /// node and vice versa. The usage of this class is limited

       /// Gives back the next node in the iterating order.

       /// to use just as template parameters for special map types. 

       ///     

       class ANode : public Node {

       void next(Node&) const {}

       public:

         typedef Node Parent;

       /// \brief Gives back the first edge in the iterating order.

       ///

         /// \brief Default constructor.

       /// Gives back the first edge in the iterating order.

         ///      

       ///     

         /// \warning The default constructor is not required to set

       void first(Edge&) const {}

         /// the item to some well-defined value. So you should consider it

         /// as uninitialized.

       /// \brief Gives back the next edge in the iterating order.

         ANode() {}

       ///

         /// \brief Copy constructor.

       /// Gives back the next edge in the iterating order.

         ///

       ///     

         /// Copy constructor.

       void next(Edge&) const {}

         ///

         ANode(const ANode &) : Parent() {}

         /// \brief Invalid constructor \& conversion.

       /// \brief Gives back the first of the edges point to the given

         ///

       /// node.

         /// This constructor initializes the item to be invalid.

       ///

         /// \sa Invalid for more details.

       /// Gives back the first of the edges point to the given node.

         ANode(Invalid) {}

       ///     

         /// \brief Converter from node to A-node.

       void firstIn(Edge&, const Node&) const {}

         ///

         /// Besides the core graph item functionality each node should

       /// \brief Gives back the next of the edges points to the given

         /// be convertible to the represented A-node if it is it possible. 

       /// node.

         ANode(const Node&) {}

       ///

         /// \brief Assign node to A-node.

       /// Gives back the next of the edges points to the given node.

         ///

       ///

         /// Besides the core graph item functionality each node should

       void nextIn(Edge&) const {}

         /// be convertible to the represented A-node if it is it possible. 

         ANode& operator=(const Node&) { return *this; }

       /// \brief Gives back the first of the edges start from the

       };

       /// given node.

       ///      

       /// \brief Helper class for B-nodes.

       /// Gives back the first of the edges start from the given node.

       ///

       ///     

       /// This class is just a helper class for B-nodes, it is not

       void firstOut(Edge&, const Node&) const {}

       /// suggested to use it directly. It can be converted easily to

       /// node and vice versa. The usage of this class is limited

       /// \brief Gives back the next of the edges start from the given

       /// to use just as template parameters for special map types. 

       /// node.

       class BNode : public Node {

       ///

       public:

       /// Gives back the next of the edges start from the given node.

         typedef Node Parent;

       ///     

       void nextOut(Edge&) const {}

         /// \brief Default constructor.

         ///      

         /// \warning The default constructor is not required to set

         /// the item to some well-defined value. So you should consider it

         /// as uninitialized.

         BNode() {}

         /// \brief Copy constructor.

         ///

         /// Copy constructor.

         ///

         BNode(const BNode &) : Parent() {}

         /// \brief Invalid constructor \& conversion.

         ///

         /// This constructor initializes the item to be invalid.

         /// \sa Invalid for more details.

         BNode(Invalid) {}

         /// \brief Converter from node to B-node.

         ///

         /// Besides the core graph item functionality each node should

         /// be convertible to the represented B-node if it is it possible. 

         BNode(const Node&) {}

         /// \brief Assign node to B-node.

         ///

         /// Besides the core graph item functionality each node should

         /// be convertible to the represented B-node if it is it possible. 

         BNode& operator=(const Node&) { return *this; }

       };

       /// \brief Gives back %true when the node is A-node.

       ///

       /// Gives back %true when the node is A-node.

       bool aNode(const Node&) const { return false; }

       /// \brief Gives back %true when the node is B-node.

       ///

       /// Gives back %true when the node is B-node.

       bool bNode(const Node&) const { return false; }

       /// \brief Gives back the A-node of the undirected edge.

       ///

       /// Gives back the A-node of the undirected edge.

       Node aNode(const UEdge&) const { return INVALID; }

       /// \brief Gives back the B-node of the undirected edge.

       ///

       /// Gives back the B-node of the undirected edge.

       Node bNode(const UEdge&) const { return INVALID; }

 	  checkConcept< BaseGraphComponent, _Graph >();

           checkConcept<BaseUGraphComponent, _Graph>();

 	  typename _Graph::Node node(INVALID);      

 	  checkConcept<GraphItem<'a'>, ANode>();

 	  typename _Graph::Edge edge(INVALID);

 	  checkConcept<GraphItem<'b'>, BNode>();

 	    graph.first(node);

 	    Node n;

 	    graph.next(node);

 	    UEdge ue(INVALID);

 	  }

             bool b;

 	  {

 	    n = graph.aNode(ue);

 	    graph.first(edge);

 	    n = graph.bNode(ue);

 	    graph.next(edge);

             b = graph.aNode(n);

 	  }

             b = graph.bNode(n);

 	  {

             ANode an;

 	    graph.firstIn(edge, node);

             an = n; n = an;

 	    graph.nextIn(edge);

             BNode bn;

 	  }

             bn = n; n = bn;            

 	  {

             ignore_unused_variable_warning(b);

 	    graph.firstOut(edge, node);

 	  }      

 	    graph.nextOut(edge);

 	}

 	  }

 	}

     };

     /// \brief An empty iterable base undirected graph class.

     ///  

     /// This class provides beside the core undirceted graph features

     /// core iterable interface for the undirected graph structure.

     /// Most of the base undirected graphs should be conform to this

     /// concept.

     template <typename _Base = BaseUGraphComponent>

     class BaseIterableUGraphComponent 

       : public BaseIterableGraphComponent<_Base> {

     public:

       typedef _Base Base; 

       typedef typename Base::UEdge UEdge;

       typedef typename Base::Node Node;

       using BaseIterableGraphComponent<_Base>::first;

       using BaseIterableGraphComponent<_Base>::next;

       /// \brief Gives back the first undirected edge in the iterating

       /// order.

       ///

       /// Gives back the first undirected edge in the iterating order.

       ///     

       void first(UEdge&) const {}

       /// \brief Gives back the next undirected edge in the iterating

       /// order.

       ///

       /// Gives back the next undirected edge in the iterating order.

       ///     

       void next(UEdge&) const {}

       /// \brief Gives back the first of the undirected edges from the

       /// given node.

       ///

       /// Gives back the first of the undirected edges from the given

       /// node. The bool parameter gives back that direction which

       /// gives a good direction of the uedge so the source of the

       /// directed edge is the given node.

       void firstInc(UEdge&, bool&, const Node&) const {}

       /// \brief Gives back the next of the undirected edges from the

       /// given node.

       ///

       /// Gives back the next of the undirected edges from the given

       /// node. The bool parameter should be used as the \c firstInc()

       /// use it.

       void nextInc(UEdge&, bool&) const {}

       template <typename _Graph>

       struct Constraints {

 	void constraints() {

 	  checkConcept<Base, _Graph >();

 	  checkConcept<BaseIterableGraphComponent<Base>, _Graph>();

 	  typename _Graph::Node node(INVALID);

 	  typename _Graph::UEdge uedge(INVALID);

           bool dir;

 	  {

 	    graph.first(uedge);

 	    graph.next(uedge);

 	  }

 	  {

 	    graph.firstInc(uedge, dir, node);

 	    graph.nextInc(uedge, dir);

 	  }

 	}

 	const _Graph& graph;

       };

 	  checkConcept< BaseGraphComponent, _Graph >();

 	  checkConcept<Base, _Graph >();

     /// \brief An empty extendable base graph class.

     /// \brief An empty idable base bipartite undirected graph class.

     ///

     /// This class provides beside the core graph features

     /// core graph extend interface for the graph structure.

     /// The most of the base graphs should be conform to this concept.

     template <typename _Base = BaseGraphComponent>

     class BaseExtendableGraphComponent : public _Base {

     public:

       typedef typename _Base::Node Node;

       typedef typename _Base::Edge Edge;

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

       ///

       /// Adds a new node to the graph.

       ///

       Node addNode() {

 	return INVALID;

       }

       /// \brief Adds a new edge connects the given two nodes.

       ///

       /// Adds a new edge connects the the given two nodes.

       Edge addEdge(const Node&, const Node&) {

 	return INVALID;

       }

       template <typename _Graph>

       struct Constraints {

 	void constraints() {

 	  typename _Graph::Node node_a, node_b;

 	  node_a = graph.addNode();

 	  node_b = graph.addNode();

 	  typename _Graph::Edge edge;

 	  edge = graph.addEdge(node_a, node_b);

 	}

 	_Graph& graph;

       };

     };

     /// \brief An empty extendable base undirected graph class.

     ///

     /// This class provides beside the core undirected graph features

     /// core undircted graph extend interface for the graph structure.

     /// The most of the base graphs should be conform to this concept.

     template <typename _Base = BaseUGraphComponent>

     class BaseExtendableUGraphComponent : public _Base {

     public:

       typedef typename _Base::Node Node;

       typedef typename _Base::UEdge UEdge;

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

       ///

       /// Adds a new node to the graph.

       ///

       Node addNode() {

 	return INVALID;

       }

       /// \brief Adds a new edge connects the given two nodes.

       ///

       /// Adds a new edge connects the the given two nodes.

       UEdge addEdge(const Node&, const Node&) {

 	return INVALID;

       }

       template <typename _Graph>

       struct Constraints {

 	void constraints() {

 	  typename _Graph::Node node_a, node_b;

 	  node_a = graph.addNode();

 	  node_b = graph.addNode();

 	  typename _Graph::UEdge uedge;

 	  uedge = graph.addUEdge(node_a, node_b);

 	}

 	_Graph& graph;

       };

     };

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

     /// This class provides beside the core graph features

     /// This class provides beside the core bipartite undirected graph

     /// core erase functions for the graph structure.

     /// features core id functions for the bipartite undirected graph

     /// The most of the base graphs should be conform to this concept.

     /// structure.  The most of the base undirected graphs should be

     template <typename _Base = BaseGraphComponent>

     /// conform to this concept.

     class BaseErasableGraphComponent : public _Base {

     template <typename _Base = BaseBpUGraphComponent>

     class IDableBpUGraphComponent : public IDableUGraphComponent<_Base> {

       typedef typename Base::Edge Edge;

       using IDableUGraphComponent<_Base>::id;

       /// \brief Erase a node from the graph.

       ///

       /// \brief Gives back an unique integer id for the ANode. 

       /// Erase a node from the graph. This function should not

       ///

       /// erase edges connecting to the Node.

       /// Gives back an unique integer id for the ANode. 

       void erase(const Node&) {}    

       ///

       int aNodeId(const Node&) const { return -1;}

       /// \brief Erase an edge from the graph.

       ///

       /// \brief Gives back the undirected edge by the unique id.

       /// Erase an edge from the graph.

       ///

       ///

       /// Gives back the undirected edge by the unique id.  If the

       void erase(const Edge&) {}

       /// graph does not contain edge with the given id then the

       /// result of the function is undetermined.

       Node nodeFromANodeId(int) const { return INVALID;}

       /// \brief Gives back an integer greater or equal to the maximum

       /// ANode id.

       ///

       /// Gives back an integer greater or equal to the maximum ANode

       /// id.

       int maxANodeId() const { return -1;}

       /// \brief Gives back an unique integer id for the BNode. 

       ///

       /// Gives back an unique integer id for the BNode. 

       ///

       int bNodeId(const Node&) const { return -1;}

       /// \brief Gives back the undirected edge by the unique id.

       ///

       /// Gives back the undirected edge by the unique id.  If the

       /// graph does not contain edge with the given id then the

       /// result of the function is undetermined.

       Node nodeFromBNodeId(int) const { return INVALID;}

       /// \brief Gives back an integer greater or equal to the maximum

       /// BNode id.

       ///

       /// Gives back an integer greater or equal to the maximum BNode

       /// id.

       int maxBNodeId() const { return -1;}

 	void constraints() {

 	  typename _Graph::Node node;

 	void constraints() {

 	  graph.erase(node);

 	  checkConcept<Base, _Graph >();

 	  typename _Graph::Edge edge;

 	  checkConcept<IDableGraphComponent<Base>, _Graph >();

 	  graph.erase(edge);

 	  typename _Graph::Node node(INVALID);

 	}

 	  int id;

           id = graph.aNodeId(node);

 	_Graph& graph;

           id = graph.bNodeId(node);

       };

           node = graph.nodeFromANodeId(id);

     };

           node = graph.nodeFromBNodeId(id);

           id = graph.maxANodeId();

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

           id = graph.maxBNodeId();

     ///  

 	}

     /// This class provides beside the core undirected graph features

     /// core erase functions for the undirceted graph structure.

 	const _Graph& graph;

     template <typename _Base = BaseUGraphComponent>

       };

     class BaseErasableUGraphComponent : public _Base {

     };

     public:

       typedef _Base Base;

       typedef typename Base::Node Node;

       typedef typename Base::UEdge UEdge;

       /// \brief Erase a node from the graph.

       ///

       /// Erase a node from the graph. This function should not

       /// erase edges connecting to the Node.

       void erase(const Node&) {}    

       /// \brief Erase an edge from the graph.

       ///

       /// Erase an edge from the graph.

       ///

       void erase(const UEdge&) {}

       template <typename _Graph>

       struct Constraints {

 	void constraints() {

 	  typename _Graph::Node node;

 	  graph.erase(node);

 	  typename _Graph::Edge edge;

 	  graph.erase(edge);

 	}

 	_Graph& graph;

       };

     };

     /// \brief An empty clearable base graph class.

     ///

     /// This class provides beside the core graph features

     /// core clear functions for the graph structure.

     /// The most of the base graphs should be conform to this concept.

     template <typename _Base = BaseGraphComponent>

     class BaseClearableGraphComponent : public _Base {

     public:

       /// \brief Erase all the nodes and edges from the graph.

       ///

       /// Erase all the nodes and edges from the graph.

       ///

       void clear() {}    

       template <typename _Graph>

       struct Constraints {

 	void constraints() {

 	  graph.clear();

 	}

 	_Graph graph;

       };

     };

     /// \brief An empty clearable base undirected graph class.

     ///

     /// This class provides beside the core undirected graph features

     /// core clear functions for the undirected graph structure.

     /// The most of the base graphs should be conform to this concept.

     template <typename _Base = BaseUGraphComponent>

     class BaseClearableUGraphComponent : public _Base {

     public:

       /// \brief Erase all the nodes and undirected edges from the graph.

       ///

       /// Erase all the nodes and undirected edges from the graph.

       ///

       void clear() {}    

       template <typename _Graph>

       struct Constraints {

 	void constraints() {

 	  graph.clear();

 	}

 	_Graph graph;

       };

     };

     /// This concept is part of the GraphConcept.

     /// This concept is part of the Graph concept.

       /// \brief The opposite node on the given edge.

       /// @}

       ///

       /// Gives back the opposite on the given edge.

       /// \todo It should not be here.

       Node oppositeNode(const Node&, const Edge&) const { return INVALID; }

 	  checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,

           {

 	    typename _Graph::EdgeIt >();

             typename _Graph::Node node(INVALID);      

 	  checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,

             typename _Graph::Edge edge(INVALID);

 	    typename _Graph::NodeIt >();

             {

 	  checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 

               graph.first(node);

             typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();

               graph.next(node);

 	  checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 

             }

             typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();

             {

               graph.first(edge);

           typename _Graph::Node n;

               graph.next(edge);

           typename _Graph::InEdgeIt ieit(INVALID);

             }

           typename _Graph::OutEdgeIt oeit(INVALID);

             {

           n = graph.baseNode(ieit);

               graph.firstIn(edge, node);

           n = graph.runningNode(ieit);

               graph.nextIn(edge);

           n = graph.baseNode(oeit);

             }

           n = graph.runningNode(oeit);

             {

           ignore_unused_variable_warning(n);

               graph.firstOut(edge, node);

               graph.nextOut(edge);

             }

           }           

           {

             checkConcept<GraphItemIt<_Graph, typename _Graph::Edge>,

               typename _Graph::EdgeIt >();

             checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,

               typename _Graph::NodeIt >();

             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 

               typename _Graph::Node, 'i'>, typename _Graph::InEdgeIt>();

             checkConcept<GraphIncIt<_Graph, typename _Graph::Edge, 

               typename _Graph::Node, 'o'>, typename _Graph::OutEdgeIt>();

             typename _Graph::Node n;

             typename _Graph::InEdgeIt ieit(INVALID);

             typename _Graph::OutEdgeIt oeit(INVALID);

             n = graph.baseNode(ieit);

             n = graph.runningNode(ieit);

             n = graph.baseNode(oeit);

             n = graph.runningNode(oeit);

             ignore_unused_variable_warning(n);

           }

     /// This concept is part of the GraphConcept.

     /// This concept is part of the UGraph concept.

 	  checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,

           {

 	    typename _Graph::UEdgeIt >();

             typename _Graph::Node node(INVALID);

 	  checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge, 

             typename _Graph::UEdge uedge(INVALID);

             typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();

             bool dir;

             {

           typename _Graph::Node n;

               graph.first(uedge);

           typename _Graph::IncEdgeIt ueit(INVALID);

               graph.next(uedge);

           n = graph.baseNode(ueit);

             }

           n = graph.runningNode(ueit);

             {

               graph.firstInc(uedge, dir, node);

               graph.nextInc(uedge, dir);

             }

           }	

           {

             checkConcept<GraphItemIt<_Graph, typename _Graph::UEdge>,

               typename _Graph::UEdgeIt >();

             checkConcept<GraphIncIt<_Graph, typename _Graph::UEdge, 

               typename _Graph::Node, 'u'>, typename _Graph::IncEdgeIt>();

             typename _Graph::Node n;

             typename _Graph::IncEdgeIt ueit(INVALID);

             n = graph.baseNode(ueit);

             n = graph.runningNode(ueit);

           }

         }

 	const _Graph& graph;

       };

     };

     /// \brief An empty iterable bipartite undirected graph class.

     ///

     /// This class provides beside the core graph features iterator

     /// based iterable interface for the bipartite undirected graph

     /// structure. This concept is part of the BpUGraph concept.

     template <typename _Base = BaseUGraphComponent>

     class IterableBpUGraphComponent : public IterableUGraphComponent<_Base> {

     public:

       typedef _Base Base;

       typedef typename Base::Node Node;

       typedef typename Base::UEdge UEdge;

       typedef IterableBpUGraphComponent Graph;

       /// \name Base iteration

       /// 

       /// This interface provides functions for iteration on graph items

       /// @{  

       using IterableUGraphComponent<_Base>::first;

       using IterableUGraphComponent<_Base>::next;

       /// \brief Gives back the first A-node in the iterating order.

       ///

       /// Gives back the first undirected A-node in the iterating

       /// order.

       ///     

       void firstANode(Node&) const {}

       /// \brief Gives back the next A-node in the iterating order.

       ///

       /// Gives back the next A-node in the iterating order.

       ///     

       void nextANode(Node&) const {}

       /// \brief Gives back the first B-node in the iterating order.

       ///

       /// Gives back the first undirected B-node in the iterating

       /// order.

       ///     

       void firstBNode(Node&) const {}

       /// \brief Gives back the next B-node in the iterating order.

       ///

       /// Gives back the next B-node in the iterating order.

       ///     

       void nextBNode(Node&) const {}

       /// \brief Gives back the first of the undirected edges start

       /// from the given A-node.

       ///      

       /// Gives back the first of the undirected edges start from the

       /// given A-node.

       void firstFromANode(UEdge&, const Node&) const {}

       /// \brief Gives back the next of the undirected edges start

       /// from the given A-node.

       ///      

       /// Gives back the next of the undirected edges start from the

       /// given A-node.

       void nextFromANode(UEdge&) const {}

       /// \brief Gives back the first of the undirected edges start

       /// from the given B-node.

       ///      

       /// Gives back the first of the undirected edges start from the

       /// given B-node.

       void firstFromBNode(UEdge&, const Node&) const {}

       /// \brief Gives back the next of the undirected edges start

       /// from the given B-node.

       ///      

       /// Gives back the next of the undirected edges start from the

       /// given B-node.

       void nextFromBNode(UEdge&) const {}

       /// @}

       /// \name Class based iteration

       /// 

       /// This interface provides functions for iteration on graph items

       ///

       /// @{

       /// \brief This iterator goes through each A-node.

       ///

       /// This iterator goes through each A-node.

       typedef GraphItemIt<Graph, Node> ANodeIt;

       /// \brief This iterator goes through each B-node.

       ///

       /// This iterator goes through each B-node.

       typedef GraphItemIt<Graph, Node> BNodeIt;

       /// @}

       template <typename _Graph> 

       struct Constraints {

 	void constraints() {

 	  checkConcept<IterableUGraphComponent<Base>, _Graph>();

           {

             typename _Graph::Node node(INVALID);

             typename _Graph::UEdge uedge(INVALID);

             graph.firstANode(node);

             graph.nextANode(node);

             graph.firstBNode(node);

             graph.nextBNode(node);

             graph.firstFromANode(uedge, node);

             graph.nextFromANode(uedge);

             graph.firstFromBNode(uedge, node);

             graph.nextFromBNode(uedge);

           }

           {

             checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,

               typename _Graph::ANodeIt >();

             checkConcept<GraphItemIt<_Graph, typename _Graph::Node>,

               typename _Graph::BNodeIt >();

           }

 	  checkConcept<Base, _Graph>();

 	  checkConcept<AlterableGraphComponent<Base>, _Graph>();

           checkConcept<AlterableGraphComponent, _Graph>();

     /// \brief An empty mappable base graph class.

     /// \brief An empty mappable base bipartite undirected graph class.