///\brief ListDigraph, ListGraph classes.

 ///\brief ListDigraph and ListGraph classes.

   ///\ref ListDigraph is a simple and fast <em>directed graph</em>

   ///\ref ListDigraph is a versatile and fast directed graph

   ///implementation based on static linked lists that are stored in

   ///implementation based on linked lists that are stored in

   ///It conforms to the \ref concepts::Digraph "Digraph concept" and it

   ///This type fully conforms to the \ref concepts::Digraph "Digraph concept"

   ///also provides several useful additional functionalities.

   ///and it also provides several useful additional functionalities.

   ///Most of the member functions and nested classes are documented

   ///Most of its member functions and nested classes are documented

   ///\sa ListGraph

     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.

     /// Digraphs are \e not copy constructible. Use DigraphCopy instead.

     ///ListDigraph is \e not copy constructible. Use copyDigraph() instead.

     ///

     ///\brief Assignment of ListDigraph to another one is \e not allowed.

     /// \brief Assignment of a digraph to another one is \e not allowed.

     ///Use copyDigraph() instead.

     /// Use DigraphCopy instead.

     ///Assignment of ListDigraph to another one is \e not allowed.

     ///Use copyDigraph() instead.

     ///Add a new node to the digraph.

     ///This function adds a new node to the digraph.

     ///Add a new arc to the digraph with source node \c s

     ///This function adds a new arc to the digraph with source node \c s

     Arc addArc(const Node& s, const Node& t) {

     Arc addArc(Node s, Node t) {

     ///Erase a node from the digraph.

     ///This function erases the given node from the digraph.

     ///

     void erase(Node n) { Parent::erase(n); }

     void erase(const Node& n) { Parent::erase(n); }

     ///Erase an arc from the digraph.

     ///This function erases the given arc from the digraph.

     ///

     void erase(Arc a) { Parent::erase(a); }

     void erase(const Arc& a) { Parent::erase(a); }

     /// This function gives back true if the given node is valid,

     /// This function gives back \c true if the given node is valid,

     /// ie. it is a real node of the graph.

     /// i.e. it is a real node of the digraph.

     ///

     ///

     /// \warning A Node pointing to a removed item

     /// \warning A removed node could become valid again if new nodes are

     /// could become valid again later if new nodes are

     /// added to the digraph.

     /// added to the graph.

     /// This function gives back true if the given arc is valid,

     /// This function gives back \c true if the given arc is valid,

     /// ie. it is a real arc of the graph.

     /// i.e. it is a real arc of the digraph.

     ///

     ///

     /// \warning An Arc pointing to a removed item

     /// \warning A removed arc could become valid again if new arcs are

     /// could become valid again later if new nodes are

     /// added to the digraph.

     /// added to the graph.

     /// Change the target of \c a to \c n

     /// Change the target node of an arc

     /// Change the target of \c a to \c n

     /// This function changes the target node of the given arc \c a to \c n.

     ///

     ///

     ///\note The <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s referencing

     ///\note \c ArcIt and \c OutArcIt iterators referencing the changed

     ///the changed arc remain valid. However <tt>InArcIt</tt>s are

     ///arc remain valid, however \c InArcIt iterators are invalidated.

     ///invalidated.

     /// Change the source of \c a to \c n

     /// Change the source node of an arc

     /// Change the source of \c a to \c n

     /// This function changes the source node of the given arc \c a to \c n.

     ///

     ///

     ///\note The <tt>InArcIt</tt>s referencing the changed arc remain

     ///\note \c InArcIt iterators referencing the changed arc remain

     ///valid. However the <tt>ArcIt</tt>s and <tt>OutArcIt</tt>s are

     ///valid, however \c ArcIt and \c OutArcIt iterators are invalidated.

     ///invalidated.

     /// Invert the direction of an arc.

     /// Reverse the direction of an arc.

     ///\note The <tt>ArcIt</tt>s referencing the changed arc remain

     /// This function reverses the direction of the given arc.

     ///valid. However <tt>OutArcIt</tt>s and <tt>InArcIt</tt>s are

     ///\note \c ArcIt, \c OutArcIt and \c InArcIt iterators referencing

     ///invalidated.

     ///the changed arc are invalidated.

     void reverseArc(Arc e) {

     void reverseArc(Arc a) {

       Node t=target(e);

       Node t=target(a);

       changeTarget(e,source(e));

       changeTarget(a,source(a));

       changeSource(e,t);

       changeSource(a,t);

     }

     }

     /// Reserve memory for nodes.

     /// Using this function it is possible to avoid the superfluous memory

     /// allocation: if you know that the digraph you want to build will

     /// be very large (e.g. it will contain millions of nodes and/or arcs)

     /// then it is worth reserving space for this amount before starting

     /// to build the digraph.

     /// \sa reserveArc

     void reserveNode(int n) { nodes.reserve(n); };

     /// Reserve memory for arcs.

     /// Using this function it is possible to avoid the superfluous memory

     /// allocation: if you know that the digraph you want to build will

     /// be very large (e.g. it will contain millions of nodes and/or arcs)

     /// then it is worth reserving space for this amount before starting

     /// to build the digraph.

     /// \sa reserveNode

     void reserveArc(int m) { arcs.reserve(m); };

     ///This function contracts two nodes.

     ///This function contracts the given two nodes.

     ///Node \p b will be removed but instead of deleting

     ///Node \c v is removed, but instead of deleting its

     ///incident arcs, they will be joined to \p a.

     ///incident arcs, they are joined to node \c u.

     ///The last parameter \p r controls whether to remove loops. \c true

     ///If the last parameter \c r is \c true (this is the default value),

     ///means that loops will be removed.

     ///then the newly created loops are removed.

     ///

     ///

     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain

     ///\note The moved arcs are joined to node \c u using changeSource()

     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s

     ///or changeTarget(), thus \c ArcIt and \c OutArcIt iterators are

     ///may be invalidated.

     ///invalidated for the outgoing arcs of node \c v and \c InArcIt

     ///iterators are invalidated for the incomming arcs of \c v.

     ///Moreover all iterators referencing node \c v or the removed 

     ///loops are also invalidated. Other iterators remain valid.

     void contract(Node a, Node b, bool r = true)

     void contract(Node u, Node v, bool r = true)

       for(OutArcIt e(*this,b);e!=INVALID;) {

       for(OutArcIt e(*this,v);e!=INVALID;) {

         if(r && target(e)==a) erase(e);

         if(r && target(e)==u) erase(e);

         else changeSource(e,a);

         else changeSource(e,u);

       for(InArcIt e(*this,b);e!=INVALID;) {

       for(InArcIt e(*this,v);e!=INVALID;) {

         if(r && source(e)==a) erase(e);

         if(r && source(e)==u) erase(e);

         else changeTarget(e,a);

         else changeTarget(e,u);

       erase(b);

       erase(v);

     ///This function splits a node. First a new node is added to the digraph,

     ///This function splits the given node. First, a new node is added

     ///then the source of each outgoing arc of \c n is moved to this new node.

     ///to the digraph, then the source of each outgoing arc of node \c n

     ///If \c connect is \c true (this is the default value), then a new arc

     ///is moved to this new node.

     ///from \c n to the newly created node is also added.

     ///If the second parameter \c connect is \c true (this is the default

     ///value), then a new arc from node \c n to the newly created node

     ///is also added.

     ///\note The <tt>ArcIt</tt>s referencing a moved arc remain

     ///\note \c ArcIt and \c OutArcIt iterators referencing the outgoing

     ///valid. However <tt>InArcIt</tt>s and <tt>OutArcIt</tt>s may

     ///arcs of node \c n are invalidated. Other iterators remain valid.

     ///be invalidated.

     ///

     ///

     ///\warning This functionality cannot be used together with the

     ///\warning This functionality cannot be used in conjunction with the

     ///This function splits an arc. First a new node \c b is added to

     ///This function splits the given arc. First, a new node \c v is

     ///the digraph, then the original arc is re-targeted to \c

     ///added to the digraph, then the target node of the original arc

     ///b. Finally an arc from \c b to the original target is added.

     ///is set to \c v. Finally, an arc from \c v to the original target

     ///

     ///is added.

     Node split(Arc e) {

     Node split(Arc a) {

       Node b = addNode();

       Node v = addNode();

       addArc(b,target(e));

       addArc(v,target(a));

       changeTarget(e,b);

       changeTarget(a,v);

       return b;

       return v;

     }

     }

     ///Clear the digraph.

     ///This function erases all nodes and arcs from the digraph.

     ///

     void clear() {

       Parent::clear();

     }

     /// Reserve memory for nodes.

     /// Using this function, it is possible to avoid superfluous memory

     /// allocation: if you know that the digraph you want to build will

     /// be large (e.g. it will contain millions of nodes and/or arcs),

     /// then it is worth reserving space for this amount before starting

     /// to build the digraph.

     /// \sa reserveArc()

     void reserveNode(int n) { nodes.reserve(n); };

     /// Reserve memory for arcs.

     /// Using this function, it is possible to avoid superfluous memory

     /// allocation: if you know that the digraph you want to build will

     /// be large (e.g. it will contain millions of nodes and/or arcs),

     /// then it is worth reserving space for this amount before starting

     /// to build the digraph.

     /// \sa reserveNode()

     void reserveArc(int m) { arcs.reserve(m); };

     /// \warning Arc and node deletions and other modifications (e.g.

     /// \note After a state is restored, you cannot restore a later state, 

     /// contracting, splitting, reversing arcs or nodes) cannot be

     /// i.e. you cannot add the removed nodes and arcs again using

     /// another Snapshot instance.

     ///

     /// \warning Node and arc deletions and other modifications (e.g.

     /// reversing, contracting, splitting arcs or nodes) cannot be

       /// To actually make a snapshot you must call save().

       /// You have to call save() to actually make a snapshot.

       /// This constructor immediately makes a snapshot of the digraph.

       /// This constructor immediately makes a snapshot of the given digraph.

       /// \param _digraph The digraph we make a snapshot of.

       Snapshot(ListDigraph &gr)

       Snapshot(ListDigraph &_digraph)

         attach(_digraph);

         attach(gr);

       /// Make a snapshot of the digraph.

       /// This function makes a snapshot of the given digraph.

       ///

       /// It can be called more than once. In case of a repeated

       /// This function can be called more than once. In case of a repeated

       /// \param _digraph The digraph we make the snapshot of.

       void save(ListDigraph &gr) {

       void save(ListDigraph &_digraph) {

         attach(_digraph);

         attach(gr);

       //

       ///

       /// Undo the changes until the last snapshot created by save().

       /// This function undos the changes until the last snapshot

       /// created by save() or Snapshot(ListDigraph&).

       /// \brief Gives back true when the snapshot is valid.

       /// \brief Returns \c true if the snapshot is valid.

       /// Gives back true when the snapshot is valid.

       /// This function returns \c true if the snapshot is valid.

   ///\ref ListGraph is a simple and fast <em>undirected graph</em>

   ///\ref ListGraph is a versatile and fast undirected graph

   ///implementation based on static linked lists that are stored in

   ///implementation based on linked lists that are stored in

   ///It conforms to the \ref concepts::Graph "Graph concept" and it

   ///This type fully conforms to the \ref concepts::Graph "Graph concept"

   ///also provides several useful additional functionalities.

   ///and it also provides several useful additional functionalities.

   ///Most of the member functions and nested classes are documented

   ///Most of its member functions and nested classes are documented

   ///\sa ListDigraph

     ///ListGraph is \e not copy constructible. Use copyGraph() instead.

     /// Graphs are \e not copy constructible. Use GraphCopy instead.

     ///ListGraph is \e not copy constructible. Use copyGraph() instead.

     ///

     ///\brief Assignment of ListGraph to another one is \e not allowed.

     /// \brief Assignment of a graph to another one is \e not allowed.

     ///Use copyGraph() instead.

     /// Use GraphCopy instead.

     ///Assignment of ListGraph to another one is \e not allowed.

     ///Use copyGraph() instead.

     /// Add a new node to the graph.

     /// This function adds a new node to the graph.

     /// Add a new edge to the graph with source node \c s

     /// This function adds a new edge to the graph between nodes

     /// and target node \c t.

     /// \c u and \c v with inherent orientation from node \c u to

     /// node \c v.

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

     Edge addEdge(Node u, Node v) {

       return Parent::addEdge(s, t);

       return Parent::addEdge(u, v);

     }

     }

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

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

     ///

     ///

     /// Erase a node from the graph.

     /// This function erases the given node from the graph.

     ///

     void erase(Node n) { Parent::erase(n); }

     void erase(const Node& n) { Parent::erase(n); }

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

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

     ///

     ///

     /// This function erases the given edge from the graph.

     /// Erase an edge from the graph.

     void erase(Edge e) { Parent::erase(e); }

     ///

     void erase(const Edge& e) { Parent::erase(e); }

     /// This function gives back true if the given node is valid,

     /// This function gives back \c true if the given node is valid,

     /// ie. it is a real node of the graph.

     /// i.e. it is a real node of the graph.

     ///

     ///

     /// \warning A Node pointing to a removed item

     /// \warning A removed node could become valid again if new nodes are

     /// could become valid again later if new nodes are

     /// This function gives back true if the given arc is valid,

     /// This function gives back \c true if the given arc is valid,

     /// ie. it is a real arc of the graph.

     /// i.e. it is a real arc of the graph.

     ///

     ///

     /// \warning An Arc pointing to a removed item

     /// \warning A removed arc could become valid again if new edges are

     /// could become valid again later if new edges are

     /// Edge validity check

     /// \brief Change the first node of an edge.

     /// This function gives back true if the given edge is valid,

     ///

     /// ie. it is a real arc of the graph.

     /// This function changes the first node of the given edge \c e to \c n.

     ///

     ///

     /// \warning A Edge pointing to a removed item

     ///\note \c EdgeIt and \c ArcIt iterators referencing the

     /// could become valid again later if new edges are

     ///changed edge are invalidated and all other iterators whose

     /// added to the graph.

     ///base node is the changed node are also invalidated.

     bool valid(Edge e) const { return Parent::valid(e); }

     /// \brief Change the end \c u of \c e to \c n

     ///

     /// This function changes the end \c u of \c e to node \c n.

     ///

     ///\note The <tt>EdgeIt</tt>s and <tt>ArcIt</tt>s referencing the

     ///changed edge are invalidated and if the changed node is the

     ///base node of an iterator then this iterator is also

     ///invalidated.

     /// \brief Change the end \c v of \c e to \c n

     /// \brief Change the second node of an edge.

     ///

     ///

     /// This function changes the end \c v of \c e to \c n.

     /// This function changes the second node of the given edge \c e to \c n.

     ///

     ///

     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain

     ///\note \c EdgeIt iterators referencing the changed edge remain

     ///valid, however <tt>ArcIt</tt>s and if the changed node is the

     ///valid, however \c ArcIt iterators referencing the changed edge and

     ///base node of an iterator then this iterator is invalidated.

     ///all other iterators whose base node is the changed node are also

     ///invalidated.

     /// This function contracts two nodes.

     /// This function contracts the given two nodes.

     /// Node \p b will be removed but instead of deleting

     /// Node \c b is removed, but instead of deleting

     /// its neighboring arcs, they will be joined to \p a.

     /// its incident edges, they are joined to node \c a.

     /// The last parameter \p r controls whether to remove loops. \c true

     /// If the last parameter \c r is \c true (this is the default value),

     /// means that loops will be removed.

     /// then the newly created loops are removed.

     ///

     ///

     /// \note The <tt>ArcIt</tt>s referencing a moved arc remain

     /// \note The moved edges are joined to node \c a using changeU()

     /// valid.

     /// or changeV(), thus all edge and arc iterators whose base node is

     /// \c b are invalidated.

     /// Moreover all iterators referencing node \c b or the removed 

     /// loops are also invalidated. Other iterators remain valid.

     /// \warning Edge and node deletions and other modifications

     /// \note After a state is restored, you cannot restore a later state, 

     /// (e.g. changing nodes of edges, contracting nodes) cannot be

     /// i.e. you cannot add the removed nodes and edges again using

     /// restored. These events invalidate the snapshot.

     /// another Snapshot instance.

     ///

     /// \warning Node and edge deletions and other modifications

     /// (e.g. changing the end-nodes of edges or contracting nodes)

     /// cannot be restored. These events invalidate the snapshot.

     /// However the edges and nodes that were added to the graph after

     /// making the current snapshot can be removed without invalidating it.

       /// To actually make a snapshot you must call save().

       /// You have to call save() to actually make a snapshot.

       /// This constructor immediately makes a snapshot of the graph.

       /// This constructor immediately makes a snapshot of the given graph.

       /// \param _graph The graph we make a snapshot of.

       Snapshot(ListGraph &gr)

       Snapshot(ListGraph &_graph)

         attach(_graph);

         attach(gr);

       /// Make a snapshot of the graph.

       /// This function makes a snapshot of the given graph.

       ///

       /// It can be called more than once. In case of a repeated

       /// This function can be called more than once. In case of a repeated

       /// \param _graph The graph we make the snapshot of.

       void save(ListGraph &gr) {

       void save(ListGraph &_graph) {

         attach(_graph);

         attach(gr);

       //

       ///

       /// Undo the changes until the last snapshot created by save().

       /// This function undos the changes until the last snapshot

       /// created by save() or Snapshot(ListGraph&).

       /// \brief Gives back true when the snapshot is valid.

       /// \brief Returns \c true if the snapshot is valid.

       /// Gives back true when the snapshot is valid.

       /// This function returns \c true if the snapshot is valid.