alpar@948: /* -*- C++ -*-
alpar@948:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@948:  *
alpar@948:  * Permission to use, modify and distribute this software is granted
alpar@948:  * provided that this copyright notice appears in all copies. For
alpar@948:  * precise terms see the accompanying LICENSE file.
alpar@948:  *
alpar@948:  * This software is provided "AS IS" with no warranty of any kind,
alpar@948:  * express or implied, and with no claim as to its suitability for any
alpar@948:  * purpose.
alpar@948:  *
alpar@948:  */
alpar@395: 
alpar@921: #ifndef LEMON_LIST_GRAPH_H
alpar@921: #define LEMON_LIST_GRAPH_H
alpar@395: 
alpar@948: ///\ingroup graphs
alpar@948: ///\file
deba@2116: ///\brief ListGraph, ListUGraph classes.
alpar@948: 
deba@2116: #include <lemon/bits/base_extender.h>
deba@1791: #include <lemon/bits/graph_extender.h>
deba@782: 
deba@2116: #include <lemon/error.h>
deba@2116: 
deba@1979: #include <vector>
alpar@1011: #include <list>
deba@782: 
alpar@921: namespace lemon {
alpar@395: 
klao@946:   class ListGraphBase {
alpar@406: 
alpar@949:   protected:
klao@946:     struct NodeT {
deba@1470:       int first_in, first_out;
alpar@397:       int prev, next;
alpar@395:     };
klao@946:  
klao@946:     struct EdgeT {
alpar@986:       int target, source;
alpar@397:       int prev_in, prev_out;
alpar@397:       int next_in, next_out;
alpar@395:     };
alpar@395: 
alpar@395:     std::vector<NodeT> nodes;
klao@946: 
alpar@397:     int first_node;
klao@946: 
alpar@397:     int first_free_node;
klao@946: 
alpar@395:     std::vector<EdgeT> edges;
klao@946: 
alpar@397:     int first_free_edge;
alpar@395:     
deba@782:   public:
alpar@395:     
klao@946:     typedef ListGraphBase Graph;
alpar@397:     
klao@946:     class Node {
marci@975:       friend class ListGraphBase;
klao@946:     protected:
alpar@395: 
klao@946:       int id;
deba@2031:       explicit Node(int pid) { id = pid;}
alpar@395: 
klao@946:     public:
klao@946:       Node() {}
klao@946:       Node (Invalid) { id = -1; }
klao@946:       bool operator==(const Node& node) const {return id == node.id;}
klao@946:       bool operator!=(const Node& node) const {return id != node.id;}
klao@946:       bool operator<(const Node& node) const {return id < node.id;}
klao@946:     };
deba@782: 
klao@946:     class Edge {
marci@975:       friend class ListGraphBase;
klao@946:     protected:
deba@782: 
klao@946:       int id;
deba@2031:       explicit Edge(int pid) { id = pid;}
alpar@395: 
klao@946:     public:
klao@946:       Edge() {}
klao@946:       Edge (Invalid) { id = -1; }
klao@946:       bool operator==(const Edge& edge) const {return id == edge.id;}
klao@946:       bool operator!=(const Edge& edge) const {return id != edge.id;}
klao@946:       bool operator<(const Edge& edge) const {return id < edge.id;}
klao@946:     };
klao@946: 
klao@946: 
klao@946: 
klao@946:     ListGraphBase()
deba@782:       : nodes(), first_node(-1),
deba@782: 	first_free_node(-1), edges(), first_free_edge(-1) {}
deba@782: 
alpar@395:     
alpar@813:     /// Maximum node ID.
alpar@813:     
alpar@813:     /// Maximum node ID.
alpar@813:     ///\sa id(Node)
deba@1791:     int maxNodeId() const { return nodes.size()-1; } 
klao@946: 
alpar@813:     /// Maximum edge ID.
alpar@813:     
alpar@813:     /// Maximum edge ID.
alpar@813:     ///\sa id(Edge)
deba@1791:     int maxEdgeId() const { return edges.size()-1; }
alpar@395: 
deba@2031:     Node source(Edge e) const { return Node(edges[e.id].source); }
deba@2031:     Node target(Edge e) const { return Node(edges[e.id].target); }
alpar@395: 
alpar@395: 
klao@946:     void first(Node& node) const { 
klao@946:       node.id = first_node;
klao@946:     }
klao@946: 
klao@946:     void next(Node& node) const {
klao@946:       node.id = nodes[node.id].next;
klao@946:     }
klao@946: 
klao@946: 
klao@946:     void first(Edge& e) const { 
klao@946:       int n;
klao@946:       for(n = first_node; 
klao@946: 	  n!=-1 && nodes[n].first_in == -1; 
klao@946: 	  n = nodes[n].next);
klao@946:       e.id = (n == -1) ? -1 : nodes[n].first_in;
klao@946:     }
klao@946: 
klao@946:     void next(Edge& edge) const {
klao@946:       if (edges[edge.id].next_in != -1) {
klao@946: 	edge.id = edges[edge.id].next_in;
klao@946:       } else {
klao@946: 	int n;
alpar@986: 	for(n = nodes[edges[edge.id].target].next;
klao@946: 	  n!=-1 && nodes[n].first_in == -1; 
klao@946: 	  n = nodes[n].next);
klao@946: 	edge.id = (n == -1) ? -1 : nodes[n].first_in;
klao@946:       }      
klao@946:     }
klao@946: 
klao@946:     void firstOut(Edge &e, const Node& v) const {
klao@946:       e.id = nodes[v.id].first_out;
klao@946:     }
klao@946:     void nextOut(Edge &e) const {
klao@946:       e.id=edges[e.id].next_out;
klao@946:     }
klao@946: 
klao@946:     void firstIn(Edge &e, const Node& v) const {
klao@946:       e.id = nodes[v.id].first_in;
klao@946:     }
klao@946:     void nextIn(Edge &e) const {
klao@946:       e.id=edges[e.id].next_in;
klao@946:     }
klao@946: 
alpar@813:     
klao@946:     static int id(Node v) { return v.id; }
klao@946:     static int id(Edge e) { return e.id; }
alpar@395: 
deba@1791:     static Node nodeFromId(int id) { return Node(id);}
deba@1791:     static Edge edgeFromId(int id) { return Edge(id);}
deba@1106: 
alpar@397:     /// Adds a new node to the graph.
alpar@397: 
alpar@2123:     /// Adds a new node to the graph.
alpar@2123:     ///
alpar@813:     /// \warning It adds the new node to the front of the list.
alpar@397:     /// (i.e. the lastly added node becomes the first.)
klao@946:     Node addNode() {     
alpar@397:       int n;
alpar@397:       
klao@946:       if(first_free_node==-1) {
klao@946: 	n = nodes.size();
klao@946: 	nodes.push_back(NodeT());
klao@946:       } else {
alpar@397: 	n = first_free_node;
alpar@397: 	first_free_node = nodes[n].next;
alpar@397:       }
alpar@397:       
alpar@397:       nodes[n].next = first_node;
alpar@397:       if(first_node != -1) nodes[first_node].prev = n;
alpar@397:       first_node = n;
alpar@397:       nodes[n].prev = -1;
alpar@397:       
alpar@397:       nodes[n].first_in = nodes[n].first_out = -1;
alpar@397:       
klao@946:       return Node(n);
alpar@395:     }
alpar@395:     
alpar@395:     Edge addEdge(Node u, Node v) {
klao@946:       int n;      
klao@946: 
klao@946:       if (first_free_edge == -1) {
klao@946: 	n = edges.size();
klao@946: 	edges.push_back(EdgeT());
klao@946:       } else {
alpar@397: 	n = first_free_edge;
alpar@397: 	first_free_edge = edges[n].next_in;
alpar@397:       }
alpar@397:       
alpar@986:       edges[n].source = u.id; 
alpar@986:       edges[n].target = v.id;
alpar@395: 
klao@946:       edges[n].next_out = nodes[u.id].first_out;
klao@946:       if(nodes[u.id].first_out != -1) {
klao@946: 	edges[nodes[u.id].first_out].prev_out = n;
klao@946:       }
klao@946:       
klao@946:       edges[n].next_in = nodes[v.id].first_in;
klao@946:       if(nodes[v.id].first_in != -1) {
klao@946: 	edges[nodes[v.id].first_in].prev_in = n;
klao@946:       }
klao@946:       
alpar@397:       edges[n].prev_in = edges[n].prev_out = -1;
alpar@397: 	
klao@946:       nodes[u.id].first_out = nodes[v.id].first_in = n;
alpar@397: 
klao@946:       return Edge(n);
alpar@395:     }
alpar@774:     
klao@946:     void erase(const Node& node) {
klao@946:       int n = node.id;
klao@946:       
klao@946:       if(nodes[n].next != -1) {
klao@946: 	nodes[nodes[n].next].prev = nodes[n].prev;
klao@946:       }
klao@946:       
klao@946:       if(nodes[n].prev != -1) {
klao@946: 	nodes[nodes[n].prev].next = nodes[n].next;
klao@946:       } else {
klao@946: 	first_node = nodes[n].next;
klao@946:       }
klao@946:       
klao@946:       nodes[n].next = first_free_node;
klao@946:       first_free_node = n;
alpar@395: 
alpar@774:     }
alpar@774:     
klao@946:     void erase(const Edge& edge) {
klao@946:       int n = edge.id;
alpar@397:       
klao@946:       if(edges[n].next_in!=-1) {
alpar@397: 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
klao@946:       }
klao@946: 
klao@946:       if(edges[n].prev_in!=-1) {
alpar@397: 	edges[edges[n].prev_in].next_in = edges[n].next_in;
klao@946:       } else {
alpar@986: 	nodes[edges[n].target].first_in = edges[n].next_in;
klao@946:       }
klao@946: 
alpar@397:       
klao@946:       if(edges[n].next_out!=-1) {
alpar@397: 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
klao@946:       } 
klao@946: 
klao@946:       if(edges[n].prev_out!=-1) {
alpar@397: 	edges[edges[n].prev_out].next_out = edges[n].next_out;
klao@946:       } else {
alpar@986: 	nodes[edges[n].source].first_out = edges[n].next_out;
klao@946:       }
alpar@397:       
alpar@397:       edges[n].next_in = first_free_edge;
alpar@695:       first_free_edge = n;      
alpar@397: 
alpar@397:     }
alpar@397: 
alpar@397:     void clear() {
deba@782:       edges.clear();
deba@782:       nodes.clear();
klao@946:       first_node = first_free_node = first_free_edge = -1;
deba@937:     }
deba@937: 
alpar@949:   protected:
deba@2111:     void changeTarget(Edge e, Node n) 
alpar@949:     {
alpar@949:       if(edges[e.id].next_in != -1)
alpar@949: 	edges[edges[e.id].next_in].prev_in = edges[e.id].prev_in;
alpar@949:       if(edges[e.id].prev_in != -1)
alpar@949: 	edges[edges[e.id].prev_in].next_in = edges[e.id].next_in;
alpar@986:       else nodes[edges[e.id].target].first_in = edges[e.id].next_in;
deba@1702:       if (nodes[n.id].first_in != -1) {
deba@1702: 	edges[nodes[n.id].first_in].prev_in = e.id;
deba@1702:       }
alpar@986:       edges[e.id].target = n.id;
alpar@949:       edges[e.id].prev_in = -1;
alpar@949:       edges[e.id].next_in = nodes[n.id].first_in;
alpar@949:       nodes[n.id].first_in = e.id;
alpar@949:     }
deba@2111:     void changeSource(Edge e, Node n) 
alpar@949:     {
alpar@949:       if(edges[e.id].next_out != -1)
alpar@949: 	edges[edges[e.id].next_out].prev_out = edges[e.id].prev_out;
alpar@949:       if(edges[e.id].prev_out != -1)
alpar@949: 	edges[edges[e.id].prev_out].next_out = edges[e.id].next_out;
alpar@986:       else nodes[edges[e.id].source].first_out = edges[e.id].next_out;
deba@1702:       if (nodes[n.id].first_out != -1) {
deba@1702: 	edges[nodes[n.id].first_out].prev_out = e.id;
deba@1702:       }
alpar@986:       edges[e.id].source = n.id;
alpar@949:       edges[e.id].prev_out = -1;
alpar@949:       edges[e.id].next_out = nodes[n.id].first_out;
alpar@949:       nodes[n.id].first_out = e.id;
alpar@949:     }
alpar@949: 
alpar@919:   };
deba@909: 
deba@1979:   typedef GraphExtender<ListGraphBase> ExtendedListGraphBase;
alpar@400: 
deba@2116:   /// \addtogroup graphs
deba@2116:   /// @{
alpar@400: 
alpar@948:   ///A list graph class.
alpar@400: 
alpar@2117:   ///This is a simple and fast graph implementation.
alpar@948:   ///
alpar@2117:   ///It conforms to the \ref concept::Graph "Graph concept" and it
deba@2111:   ///also provides several additional useful extra functionalities.
deba@2111:   ///The most of the member functions and nested classes are
deba@2111:   ///documented only in the concept class.
deba@2111:   ///\sa concept::Graph.
deba@782: 
deba@1999:   class ListGraph : public ExtendedListGraphBase {
alpar@2128:   private:
alpar@2128:     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128:     
alpar@2128:     ///ListGraph is \e not copy constructible. Use GraphCopy() instead.
alpar@2128:     ///
alpar@2128:     ListGraph(const ListGraph &) :ExtendedListGraphBase() {};
alpar@2132:     ///\brief Assignment of ListGraph to another one is \e not allowed.
alpar@2128:     ///Use GraphCopy() instead.
alpar@2128: 
alpar@2132:     ///Assignment of ListGraph to another one is \e not allowed.
alpar@2128:     ///Use GraphCopy() instead.
alpar@2128:     void operator=(const ListGraph &) {}
alpar@948:   public:
deba@1999: 
deba@1999:     typedef ExtendedListGraphBase Parent;
deba@1999: 
alpar@2128:     /// Constructor
alpar@2128:     
alpar@2128:     /// Constructor.
alpar@2128:     ///
alpar@2128:     ListGraph() {}
alpar@2128: 
deba@2111:     ///Add a new node to the graph.
deba@2111:     
deba@2111:     /// \return the new node.
deba@2111:     ///
deba@2111:     Node addNode() { return Parent::addNode(); }
deba@2111: 
deba@2111:     ///Add a new edge to the graph.
deba@2111:     
deba@2111:     ///Add a new edge to the graph with source node \c s
deba@2111:     ///and target node \c t.
deba@2111:     ///\return the new edge.
deba@2111:     Edge addEdge(const Node& s, const Node& t) { 
deba@2111:       return Parent::addEdge(s, t); 
deba@2111:     }
deba@2111: 
alpar@1546:     /// Changes the target of \c e to \c n
alpar@948: 
alpar@1546:     /// Changes the target of \c e to \c n
alpar@948:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s referencing
deba@2114:     ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
deba@2114:     ///invalidated.
alpar@2123:     ///\warning This functionality cannot be used together with the Snapshot
alpar@2123:     ///feature.
deba@1718:     void changeTarget(Edge e, Node n) { 
deba@2111:       Parent::changeTarget(e,n); 
deba@1718:     }
alpar@1546:     /// Changes the source of \c e to \c n
alpar@948: 
alpar@1546:     /// Changes the source of \c e to \c n
alpar@948:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2114:     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2114:     ///invalidated.
alpar@2123:     ///\warning This functionality cannot be used together with the Snapshot
alpar@2123:     ///feature.
deba@1718:     void changeSource(Edge e, Node n) { 
deba@2111:       Parent::changeSource(e,n);
deba@1718:     }
alpar@949: 
alpar@1010:     /// Invert the direction of an edge.
alpar@1010: 
deba@2160:     ///\note The <tt>EdgeIt</tt>s referencing the changed edge remain
deba@2114:     ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
deba@2114:     ///invalidated.
alpar@2123:     ///\warning This functionality cannot be used together with the Snapshot
alpar@2123:     ///feature.
alpar@1010:     void reverseEdge(Edge e) {
alpar@1010:       Node t=target(e);
deba@2111:       changeTarget(e,source(e));
deba@2111:       changeSource(e,t);
alpar@1010:     }
alpar@1010: 
deba@2111:     /// \brief Using this it is possible to avoid the superfluous memory
deba@2111:     /// allocation.
alpar@1010: 
deba@2107:     ///Using this it is possible to avoid the superfluous memory
deba@2107:     ///allocation: if you know that the graph you want to build will
alpar@2123:     ///contain at least 10 million nodes then it is worth reserving
deba@2107:     ///space for this amount before starting to build the graph.
deba@2107:     void reserveNode(int n) { nodes.reserve(n); };
deba@2107: 
deba@2111:     /// \brief Using this it is possible to avoid the superfluous memory
deba@2111:     /// allocation.
deba@2107: 
deba@2107:     ///Using this it is possible to avoid the superfluous memory
deba@2107:     ///allocation: see the \ref reserveNode function.
alpar@949:     void reserveEdge(int n) { edges.reserve(n); };
alpar@1010: 
deba@2107: 
alpar@1010:     ///Contract two nodes.
alpar@1010: 
alpar@1010:     ///This function contracts two nodes.
alpar@1010:     ///
alpar@1010:     ///Node \p b will be removed but instead of deleting
athos@2102:     ///incident edges, they will be joined to \p a.
alpar@1010:     ///The last parameter \p r controls whether to remove loops. \c true
alpar@1010:     ///means that loops will be removed.
alpar@1010:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s
alpar@1281:     ///referencing a moved edge remain
deba@2160:     ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s
alpar@1010:     ///may be invalidated.
alpar@2123:     ///\warning This functionality cannot be used together with the Snapshot
alpar@2123:     ///feature.
deba@1718:     void contract(Node a, Node b, bool r = true) 
alpar@1010:     {
alpar@1010:       for(OutEdgeIt e(*this,b);e!=INVALID;) {
alpar@1010: 	OutEdgeIt f=e;
alpar@1010: 	++f;
alpar@1010: 	if(r && target(e)==a) erase(e);
alpar@1546: 	else changeSource(e,a);
alpar@1010: 	e=f;
alpar@1010:       }
alpar@1010:       for(InEdgeIt e(*this,b);e!=INVALID;) {
alpar@1010: 	InEdgeIt f=e;
alpar@1010: 	++f;
alpar@1010: 	if(r && source(e)==a) erase(e);
alpar@1546: 	else changeTarget(e,a);
alpar@1010: 	e=f;
alpar@1010:       }
alpar@1010:       erase(b);
alpar@1010:     }
alpar@1011: 
alpar@1281:     ///Split a node.
alpar@1011: 
alpar@1284:     ///This function splits a node. First a new node is added to the graph,
alpar@1284:     ///then the source of each outgoing edge of \c n is moved to this new node.
alpar@1281:     ///If \c connect is \c true (this is the default value), then a new edge
alpar@1281:     ///from \c n to the newly created node is also added.
alpar@1281:     ///\return The newly created node.
alpar@1281:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s referencing a moved edge remain
deba@2160:     ///valid. However <tt>InEdgeIt</tt>s and <tt>OutEdgeIt</tt>s may
deba@2160:     ///be invalidated.  
deba@2160:     ///
deba@2160:     ///\warning This functionality cannot be used together with the
deba@2160:     ///Snapshot feature.  \todo It could be implemented in a bit
deba@2160:     ///faster way.
deba@2114:     Node split(Node n, bool connect = true) {
alpar@1281:       Node b = addNode();
alpar@1281:       for(OutEdgeIt e(*this,n);e!=INVALID;) {
alpar@1281:  	OutEdgeIt f=e;
alpar@1281: 	++f;
alpar@1546: 	changeSource(e,b);
alpar@1281: 	e=f;
alpar@1281:       }
deba@2114:       if (connect) addEdge(n,b);
alpar@1281:       return b;
alpar@1281:     }
alpar@1281:       
alpar@1812:     ///Split an edge.
alpar@1812: 
athos@2102:     ///This function splits an edge. First a new node \c b is added to
athos@2102:     ///the graph, then the original edge is re-targeted to \c
athos@2102:     ///b. Finally an edge from \c b to the original target is added.
athos@2102:     ///\return The newly created node.  
athos@2102:     ///\warning This functionality
athos@2102:     ///cannot be used together with the Snapshot feature.
deba@2114:     Node split(Edge e) {
alpar@1812:       Node b = addNode();
alpar@1812:       addEdge(b,target(e));
alpar@1812:       changeTarget(e,b);
alpar@1812:       return b;
alpar@1812:     }
alpar@1812:       
deba@2114:     /// \brief Class to make a snapshot of the graph and restore
deba@2114:     /// to it later.
alpar@1011:     ///
deba@2114:     /// Class to make a snapshot of the graph and to restore it
deba@2114:     /// later.
alpar@1011:     ///
deba@2114:     /// The newly added nodes and edges can be removed using the
deba@2114:     /// restore() function.
deba@2114:     ///
deba@2189:     /// \warning Edge and node deletions cannot be restored. This
deba@2189:     /// events invalidate the snapshot. 
deba@2114:     class Snapshot {
deba@1999:     protected:
deba@2114: 
deba@2114:       typedef Parent::NodeNotifier NodeNotifier;
deba@2114: 
deba@2114:       class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@2114:       public:
deba@2114: 
deba@2114:         NodeObserverProxy(Snapshot& _snapshot)
deba@2114:           : snapshot(_snapshot) {}
deba@2114: 
deba@2114:         using NodeNotifier::ObserverBase::attach;
deba@2114:         using NodeNotifier::ObserverBase::detach;
deba@2114:         using NodeNotifier::ObserverBase::attached;
deba@2114:         
deba@2114:       protected:
deba@2114:         
deba@2114:         virtual void add(const Node& node) {
deba@2114:           snapshot.addNode(node);
deba@2114:         }
deba@2114:         virtual void add(const std::vector<Node>& nodes) {
deba@2114:           for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@2114:             snapshot.addNode(nodes[i]);
deba@2114:           }
deba@2114:         }
deba@2114:         virtual void erase(const Node& node) {
deba@2114:           snapshot.eraseNode(node);
deba@2114:         }
deba@2114:         virtual void erase(const std::vector<Node>& nodes) {
deba@2114:           for (int i = 0; i < (int)nodes.size(); ++i) {
deba@2189:             snapshot.eraseNode(nodes[i]);
deba@2114:           }
deba@2114:         }
deba@2114:         virtual void build() {
deba@2114:           NodeNotifier* notifier = getNotifier();
deba@2114:           Node node;
deba@2114:           std::vector<Node> nodes;
deba@2114:           for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2114:             nodes.push_back(node);
deba@2114:           }
deba@2114:           for (int i = nodes.size() - 1; i >= 0; --i) {
deba@2114:             snapshot.addNode(nodes[i]);
deba@2114:           }
deba@2114:         }
deba@2114:         virtual void clear() {
deba@2114:           NodeNotifier* notifier = getNotifier();
deba@2114:           Node node;
deba@2114:           for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2189:             snapshot.eraseNode(node);
deba@2114:           }
deba@2114:         }
deba@2114: 
deba@2114:         Snapshot& snapshot;
deba@2114:       };
deba@2114: 
deba@2114:       class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
deba@2114:       public:
deba@2114: 
deba@2114:         EdgeObserverProxy(Snapshot& _snapshot)
deba@2114:           : snapshot(_snapshot) {}
deba@2114: 
deba@2114:         using EdgeNotifier::ObserverBase::attach;
deba@2114:         using EdgeNotifier::ObserverBase::detach;
deba@2114:         using EdgeNotifier::ObserverBase::attached;
deba@2114:         
deba@2114:       protected:
deba@2114: 
deba@2114:         virtual void add(const Edge& edge) {
deba@2114:           snapshot.addEdge(edge);
deba@2114:         }
deba@2114:         virtual void add(const std::vector<Edge>& edges) {
deba@2114:           for (int i = edges.size() - 1; i >= 0; ++i) {
deba@2114:             snapshot.addEdge(edges[i]);
deba@2114:           }
deba@2114:         }
deba@2114:         virtual void erase(const Edge& edge) {
deba@2114:           snapshot.eraseEdge(edge);
deba@2114:         }
deba@2114:         virtual void erase(const std::vector<Edge>& edges) {
deba@2114:           for (int i = 0; i < (int)edges.size(); ++i) {
deba@2189:             snapshot.eraseEdge(edges[i]);
deba@2114:           }
deba@2114:         }
deba@2114:         virtual void build() {
deba@2114:           EdgeNotifier* notifier = getNotifier();
deba@2114:           Edge edge;
deba@2114:           std::vector<Edge> edges;
deba@2114:           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2114:             edges.push_back(edge);
deba@2114:           }
deba@2114:           for (int i = edges.size() - 1; i >= 0; --i) {
deba@2114:             snapshot.addEdge(edges[i]);
deba@2114:           }
deba@2114:         }
deba@2114:         virtual void clear() {
deba@2114:           EdgeNotifier* notifier = getNotifier();
deba@2114:           Edge edge;
deba@2114:           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2189:             snapshot.eraseEdge(edge);
deba@2114:           }
deba@2114:         }
deba@2114: 
deba@2114:         Snapshot& snapshot;
deba@2114:       };
alpar@1011:       
deba@2114:       ListGraph *graph;
deba@2114: 
deba@2114:       NodeObserverProxy node_observer_proxy;
deba@2114:       EdgeObserverProxy edge_observer_proxy;
deba@2114: 
alpar@1011:       std::list<Node> added_nodes;
alpar@1011:       std::list<Edge> added_edges;
deba@2114: 
deba@2114: 
deba@2114:       void addNode(const Node& node) {
deba@2114:         added_nodes.push_front(node);        
alpar@1011:       }
deba@2189:       void eraseNode(const Node& node) {
deba@2114:         std::list<Node>::iterator it = 
deba@2114:           std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2114:         if (it == added_nodes.end()) {
deba@2114:           clear();
deba@2189:           edge_observer_proxy.detach();
deba@2189:           throw NodeNotifier::ImmediateDetach();
deba@2114:         } else {
deba@2114:           added_nodes.erase(it);
deba@2114:         }
alpar@1011:       }
alpar@1011: 
deba@2114:       void addEdge(const Edge& edge) {
deba@2114:         added_edges.push_front(edge);        
deba@2114:       }
deba@2189:       void eraseEdge(const Edge& edge) {
deba@2114:         std::list<Edge>::iterator it = 
deba@2114:           std::find(added_edges.begin(), added_edges.end(), edge);
deba@2114:         if (it == added_edges.end()) {
deba@2114:           clear();
deba@2189:           node_observer_proxy.detach(); 
deba@2189:           throw EdgeNotifier::ImmediateDetach();
deba@2114:         } else {
deba@2114:           added_edges.erase(it);
deba@2114:         }        
deba@2114:       }
alpar@1457: 
deba@2114:       void attach(ListGraph &_graph) {
deba@2114: 	graph = &_graph;
deba@2114: 	node_observer_proxy.attach(graph->getNotifier(Node()));
deba@2114:         edge_observer_proxy.attach(graph->getNotifier(Edge()));
alpar@1011:       }
alpar@1011:             
deba@2114:       void detach() {
deba@2114: 	node_observer_proxy.detach();
deba@2114: 	edge_observer_proxy.detach();
deba@2114:       }
deba@2114: 
deba@2189:       bool attached() const {
deba@2189:         return node_observer_proxy.attached();
deba@2189:       }
deba@2189: 
deba@2114:       void clear() {
deba@2114:         added_nodes.clear();
deba@2114:         added_edges.clear();        
alpar@1011:       }
deba@1774: 
alpar@1011:     public:
deba@2114: 
deba@2160:       /// \brief Default constructor.
deba@2114:       ///
deba@2114:       /// Default constructor.
deba@2114:       /// To actually make a snapshot you must call save().
deba@2114:       Snapshot() 
deba@2114:         : graph(0), node_observer_proxy(*this), 
deba@2114:           edge_observer_proxy(*this) {}
alpar@1011:       
deba@2114:       /// \brief Constructor that immediately makes a snapshot.
deba@2114:       ///      
deba@2114:       /// This constructor immediately makes a snapshot of the graph.
deba@2114:       /// \param _graph The graph we make a snapshot of.
deba@2114:       Snapshot(ListGraph &_graph) 
deba@2114:         : node_observer_proxy(*this), 
deba@2114:           edge_observer_proxy(*this) {
deba@2114: 	attach(_graph);
alpar@1011:       }
alpar@1011:       
deba@2114:       /// \brief Make a snapshot.
alpar@1011:       ///
deba@2114:       /// Make a snapshot of the graph.
deba@2114:       ///
deba@2114:       /// This function can be called more than once. In case of a repeated
deba@2114:       /// call, the previous snapshot gets lost.
deba@2114:       /// \param _graph The graph we make the snapshot of.
deba@2114:       void save(ListGraph &_graph) {
deba@2189:         if (attached()) {
deba@2189:           detach();
deba@2189:           clear();
deba@2189:         }
deba@2114:         attach(_graph);
alpar@1011:       }
alpar@1011:       
deba@2114:       /// \brief Undo the changes until the last snapshot.
deba@2114:       // 
alpar@2123:       /// Undo the changes until the last snapshot created by save().
alpar@1011:       void restore() {
deba@2114: 	detach();
deba@2189: 	for(std::list<Edge>::iterator it = added_edges.begin(); 
deba@2189:             it != added_edges.end(); ++it) {
deba@2189: 	  graph->erase(*it);
alpar@1011: 	}
deba@2189: 	for(std::list<Node>::iterator it = added_nodes.begin(); 
deba@2189:             it != added_nodes.end(); ++it) {
deba@2189: 	  graph->erase(*it);
alpar@1011: 	}
deba@2189:         clear();
alpar@1011:       }
deba@2114: 
deba@2114:       /// \brief Gives back true when the snapshot is valid.
deba@2114:       ///
deba@2114:       /// Gives back true when the snapshot is valid.
deba@2114:       bool valid() const {
deba@2189:         return attached();
deba@2114:       }
alpar@1011:     };
alpar@1011:     
alpar@949:   };
klao@1034: 
deba@2116:   ///@}
deba@2116: 
deba@2116:   /**************** Undirected List Graph ****************/
deba@2116: 
deba@2116:   typedef UGraphExtender<UndirGraphExtender<ListGraphBase> > 
deba@2116:   ExtendedListUGraphBase;
deba@2116: 
deba@2116:   /// \addtogroup graphs
deba@2116:   /// @{
deba@2116: 
deba@2116:   ///An undirected list graph class.
deba@2116: 
alpar@2117:   ///This is a simple and fast undirected graph implementation.
deba@2116:   ///
deba@2116:   ///It conforms to the
alpar@2117:   ///\ref concept::UGraph "UGraph concept".
deba@2116:   ///
deba@2116:   ///\sa concept::UGraph.
deba@2116:   ///
deba@2116:   class ListUGraph : public ExtendedListUGraphBase {
alpar@2128:   private:
alpar@2128:     ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128: 
alpar@2128:     ///ListUGraph is \e not copy constructible. Use UGraphCopy() instead.
alpar@2128:     ///
alpar@2128:     ListUGraph(const ListUGraph &) :ExtendedListUGraphBase()  {};
alpar@2132:     ///\brief Assignment of ListUGraph to another one is \e not allowed.
alpar@2128:     ///Use UGraphCopy() instead.
alpar@2128: 
alpar@2132:     ///Assignment of ListUGraph to another one is \e not allowed.
alpar@2128:     ///Use UGraphCopy() instead.
alpar@2128:     void operator=(const ListUGraph &) {}
deba@2116:   public:
alpar@2128:     /// Constructor
alpar@2128:     
alpar@2128:     /// Constructor.
alpar@2128:     ///
alpar@2128:     ListUGraph() {}
alpar@2128: 
deba@2116:     typedef ExtendedListUGraphBase Parent;
deba@2116:     /// \brief Add a new node to the graph.
deba@2116:     ///
deba@2116:     /// \return the new node.
deba@2116:     ///
deba@2116:     Node addNode() { return Parent::addNode(); }
deba@2116: 
deba@2116:     /// \brief Add a new edge to the graph.
deba@2116:     ///
deba@2116:     /// Add a new edge to the graph with source node \c s
deba@2116:     /// and target node \c t.
deba@2116:     /// \return the new undirected edge.
deba@2116:     UEdge addEdge(const Node& s, const Node& t) { 
deba@2116:       return Parent::addEdge(s, t); 
deba@2116:     }
deba@2160:     /// \brief Changes the source of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the source of \c e to \c n
deba@2160:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
deba@2160:     ///referencing the changed edge remain
deba@2160:     ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
deba@2160:     void changeSource(UEdge e, Node n) { 
deba@2160:       Parent::changeSource(e,n); 
deba@2160:     }    
deba@2116:     /// \brief Changes the target of \c e to \c n
deba@2116:     ///
deba@2116:     /// Changes the target of \c e to \c n
deba@2116:     ///
deba@2160:     /// \note The <tt>EdgeIt</tt>s referencing the changed edge remain
deba@2160:     /// valid. However the other iterators may be invalidated.
deba@2116:     void changeTarget(UEdge e, Node n) { 
deba@2116:       Parent::changeTarget(e,n); 
deba@2116:     }
deba@2160:     /// \brief Changes the source of \c e to \c n
deba@2116:     ///
deba@2160:     /// Changes the source of \c e to \c n. It changes the proper
deba@2160:     /// node of the represented undirected edge.
deba@2116:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
deba@2116:     ///referencing the changed edge remain
deba@2160:     ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
deba@2160:     void changeSource(Edge e, Node n) { 
deba@2160:       if (Parent::direction(e)) {
deba@2160:         Parent::changeSource(e,n);
deba@2160:       } else {
deba@2160:         Parent::changeTarget(e,n);
deba@2160:       } 
deba@2160:     }
deba@2160:     /// \brief Changes the target of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the target of \c e to \c n. It changes the proper
deba@2160:     /// node of the represented undirected edge.
deba@2160:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160:     ///referencing the changed edge remain
deba@2160:     ///valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160:     void changeTarget(Edge e, Node n) { 
deba@2160:       if (Parent::direction(e)) {
deba@2160:         Parent::changeTarget(e,n);
deba@2160:       } else {
deba@2160:         Parent::changeSource(e,n);
deba@2160:       } 
deba@2116:     }
deba@2116:     /// \brief Contract two nodes.
deba@2116:     ///
deba@2116:     /// This function contracts two nodes.
deba@2116:     ///
deba@2116:     /// Node \p b will be removed but instead of deleting
deba@2116:     /// its neighboring edges, they will be joined to \p a.
deba@2116:     /// The last parameter \p r controls whether to remove loops. \c true
deba@2116:     /// means that loops will be removed.
deba@2116:     ///
deba@2160:     /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
deba@2116:     /// valid.
deba@2116:     void contract(Node a, Node b, bool r = true) {
deba@2116:       for(IncEdgeIt e(*this, b); e!=INVALID;) {
deba@2116: 	IncEdgeIt f = e; ++f;
deba@2116: 	if (r && runningNode(e) == a) {
deba@2116: 	  erase(e);
deba@2116: 	} else if (source(e) == b) {
deba@2116: 	  changeSource(e, a);
deba@2116: 	} else {
deba@2116: 	  changeTarget(e, a);
deba@2116: 	}
deba@2116: 	e = f;
deba@2116:       }
deba@2116:       erase(b);
deba@2116:     }
deba@2189: 
deba@2189: 
deba@2189:     /// \brief Class to make a snapshot of the graph and restore
deba@2189:     /// to it later.
deba@2189:     ///
deba@2189:     /// Class to make a snapshot of the graph and to restore it
deba@2189:     /// later.
deba@2189:     ///
deba@2189:     /// The newly added nodes and undirected edges can be removed
deba@2189:     /// using the restore() function.
deba@2189:     ///
deba@2189:     /// \warning Edge and node deletions cannot be restored. This
deba@2189:     /// events invalidate the snapshot. 
deba@2189:     class Snapshot {
deba@2189:     protected:
deba@2189: 
deba@2189:       typedef Parent::NodeNotifier NodeNotifier;
deba@2189: 
deba@2189:       class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@2189:       public:
deba@2189: 
deba@2189:         NodeObserverProxy(Snapshot& _snapshot)
deba@2189:           : snapshot(_snapshot) {}
deba@2189: 
deba@2189:         using NodeNotifier::ObserverBase::attach;
deba@2189:         using NodeNotifier::ObserverBase::detach;
deba@2189:         using NodeNotifier::ObserverBase::attached;
deba@2189:         
deba@2189:       protected:
deba@2189:         
deba@2189:         virtual void add(const Node& node) {
deba@2189:           snapshot.addNode(node);
deba@2189:         }
deba@2189:         virtual void add(const std::vector<Node>& nodes) {
deba@2189:           for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@2189:             snapshot.addNode(nodes[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void erase(const Node& node) {
deba@2189:           snapshot.eraseNode(node);
deba@2189:         }
deba@2189:         virtual void erase(const std::vector<Node>& nodes) {
deba@2189:           for (int i = 0; i < (int)nodes.size(); ++i) {
deba@2189:             snapshot.eraseNode(nodes[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void build() {
deba@2189:           NodeNotifier* notifier = getNotifier();
deba@2189:           Node node;
deba@2189:           std::vector<Node> nodes;
deba@2189:           for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2189:             nodes.push_back(node);
deba@2189:           }
deba@2189:           for (int i = nodes.size() - 1; i >= 0; --i) {
deba@2189:             snapshot.addNode(nodes[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void clear() {
deba@2189:           NodeNotifier* notifier = getNotifier();
deba@2189:           Node node;
deba@2189:           for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2189:             snapshot.eraseNode(node);
deba@2189:           }
deba@2189:         }
deba@2189: 
deba@2189:         Snapshot& snapshot;
deba@2189:       };
deba@2189: 
deba@2189:       class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
deba@2189:       public:
deba@2189: 
deba@2189:         UEdgeObserverProxy(Snapshot& _snapshot)
deba@2189:           : snapshot(_snapshot) {}
deba@2189: 
deba@2189:         using UEdgeNotifier::ObserverBase::attach;
deba@2189:         using UEdgeNotifier::ObserverBase::detach;
deba@2189:         using UEdgeNotifier::ObserverBase::attached;
deba@2189:         
deba@2189:       protected:
deba@2189: 
deba@2189:         virtual void add(const UEdge& edge) {
deba@2189:           snapshot.addUEdge(edge);
deba@2189:         }
deba@2189:         virtual void add(const std::vector<UEdge>& edges) {
deba@2189:           for (int i = edges.size() - 1; i >= 0; ++i) {
deba@2189:             snapshot.addUEdge(edges[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void erase(const UEdge& edge) {
deba@2189:           snapshot.eraseUEdge(edge);
deba@2189:         }
deba@2189:         virtual void erase(const std::vector<UEdge>& edges) {
deba@2189:           for (int i = 0; i < (int)edges.size(); ++i) {
deba@2189:             snapshot.eraseUEdge(edges[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void build() {
deba@2189:           UEdgeNotifier* notifier = getNotifier();
deba@2189:           UEdge edge;
deba@2189:           std::vector<UEdge> edges;
deba@2189:           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2189:             edges.push_back(edge);
deba@2189:           }
deba@2189:           for (int i = edges.size() - 1; i >= 0; --i) {
deba@2189:             snapshot.addUEdge(edges[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void clear() {
deba@2189:           UEdgeNotifier* notifier = getNotifier();
deba@2189:           UEdge edge;
deba@2189:           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2189:             snapshot.eraseUEdge(edge);
deba@2189:           }
deba@2189:         }
deba@2189: 
deba@2189:         Snapshot& snapshot;
deba@2189:       };
deba@2189:       
deba@2189:       ListUGraph *graph;
deba@2189: 
deba@2189:       NodeObserverProxy node_observer_proxy;
deba@2189:       UEdgeObserverProxy edge_observer_proxy;
deba@2189: 
deba@2189:       std::list<Node> added_nodes;
deba@2189:       std::list<UEdge> added_edges;
deba@2189: 
deba@2189: 
deba@2189:       void addNode(const Node& node) {
deba@2189:         added_nodes.push_front(node);        
deba@2189:       }
deba@2189:       void eraseNode(const Node& node) {
deba@2189:         std::list<Node>::iterator it = 
deba@2189:           std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2189:         if (it == added_nodes.end()) {
deba@2189:           clear();
deba@2189:           edge_observer_proxy.detach();
deba@2189:           throw NodeNotifier::ImmediateDetach();
deba@2189:         } else {
deba@2189:           added_nodes.erase(it);
deba@2189:         }
deba@2189:       }
deba@2189: 
deba@2189:       void addUEdge(const UEdge& edge) {
deba@2189:         added_edges.push_front(edge);        
deba@2189:       }
deba@2189:       void eraseUEdge(const UEdge& edge) {
deba@2189:         std::list<UEdge>::iterator it = 
deba@2189:           std::find(added_edges.begin(), added_edges.end(), edge);
deba@2189:         if (it == added_edges.end()) {
deba@2189:           clear();
deba@2189:           node_observer_proxy.detach();
deba@2189:           throw UEdgeNotifier::ImmediateDetach();
deba@2189:         } else {
deba@2189:           added_edges.erase(it);
deba@2189:         }        
deba@2189:       }
deba@2189: 
deba@2189:       void attach(ListUGraph &_graph) {
deba@2189: 	graph = &_graph;
deba@2189: 	node_observer_proxy.attach(graph->getNotifier(Node()));
deba@2189:         edge_observer_proxy.attach(graph->getNotifier(UEdge()));
deba@2189:       }
deba@2189:             
deba@2189:       void detach() {
deba@2189: 	node_observer_proxy.detach();
deba@2189: 	edge_observer_proxy.detach();
deba@2189:       }
deba@2189: 
deba@2189:       bool attached() const {
deba@2189:         return node_observer_proxy.attached();
deba@2189:       }
deba@2189: 
deba@2189:       void clear() {
deba@2189:         added_nodes.clear();
deba@2189:         added_edges.clear();        
deba@2189:       }
deba@2189: 
deba@2189:     public:
deba@2189: 
deba@2189:       /// \brief Default constructor.
deba@2189:       ///
deba@2189:       /// Default constructor.
deba@2189:       /// To actually make a snapshot you must call save().
deba@2189:       Snapshot() 
deba@2189:         : graph(0), node_observer_proxy(*this), 
deba@2189:           edge_observer_proxy(*this) {}
deba@2189:       
deba@2189:       /// \brief Constructor that immediately makes a snapshot.
deba@2189:       ///      
deba@2189:       /// This constructor immediately makes a snapshot of the graph.
deba@2189:       /// \param _graph The graph we make a snapshot of.
deba@2189:       Snapshot(ListUGraph &_graph) 
deba@2189:         : node_observer_proxy(*this), 
deba@2189:           edge_observer_proxy(*this) {
deba@2189: 	attach(_graph);
deba@2189:       }
deba@2189:       
deba@2189:       /// \brief Make a snapshot.
deba@2189:       ///
deba@2189:       /// Make a snapshot of the graph.
deba@2189:       ///
deba@2189:       /// This function can be called more than once. In case of a repeated
deba@2189:       /// call, the previous snapshot gets lost.
deba@2189:       /// \param _graph The graph we make the snapshot of.
deba@2189:       void save(ListUGraph &_graph) {
deba@2189:         if (attached()) {
deba@2189:           detach();
deba@2189:           clear();
deba@2189:         }
deba@2189:         attach(_graph);
deba@2189:       }
deba@2189:       
deba@2189:       /// \brief Undo the changes until the last snapshot.
deba@2189:       // 
deba@2189:       /// Undo the changes until the last snapshot created by save().
deba@2189:       void restore() {
deba@2189: 	detach();
deba@2189: 	for(std::list<UEdge>::iterator it = added_edges.begin(); 
deba@2189:             it != added_edges.end(); ++it) {
deba@2189: 	  graph->erase(*it);
deba@2189: 	}
deba@2189: 	for(std::list<Node>::iterator it = added_nodes.begin(); 
deba@2189:             it != added_nodes.end(); ++it) {
deba@2189: 	  graph->erase(*it);
deba@2189: 	}
deba@2189:         clear();
deba@2189:       }
deba@2189: 
deba@2189:       /// \brief Gives back true when the snapshot is valid.
deba@2189:       ///
deba@2189:       /// Gives back true when the snapshot is valid.
deba@2189:       bool valid() const {
deba@2189:         return attached();
deba@2189:       }
deba@2189:     };
deba@2116:   };
deba@2116: 
deba@2116: 
deba@2116:   class ListBpUGraphBase {
deba@2116:   public:
deba@2116: 
deba@2116:     class NodeSetError : public LogicError {
deba@2160:     public:
alpar@2151:       virtual const char* what() const throw() { 
deba@2116: 	return "lemon::ListBpUGraph::NodeSetError";
deba@2116:       }
deba@2116:     };
deba@2116: 
deba@2116:   protected:
deba@2116: 
deba@2116:     struct NodeT {
deba@2116:       int first_edge, prev, next;
deba@2116:     };
deba@2116: 
deba@2116:     struct UEdgeT {
deba@2116:       int aNode, prev_out, next_out;
deba@2116:       int bNode, prev_in, next_in;
deba@2116:     };
deba@2116: 
deba@2116:     std::vector<NodeT> aNodes;
deba@2116:     std::vector<NodeT> bNodes;
deba@2116: 
deba@2116:     std::vector<UEdgeT> edges;
deba@2116: 
deba@2116:     int first_anode;
deba@2116:     int first_free_anode;
deba@2116: 
deba@2116:     int first_bnode;
deba@2116:     int first_free_bnode;
deba@2116: 
deba@2116:     int first_free_edge;
deba@2116: 
deba@2116:   public:
deba@2116:   
deba@2116:     class Node {
deba@2116:       friend class ListBpUGraphBase;
deba@2116:     protected:
deba@2116:       int id;
deba@2116: 
deba@2116:       explicit Node(int _id) : id(_id) {}
deba@2116:     public:
deba@2116:       Node() {}
deba@2116:       Node(Invalid) { id = -1; }
deba@2116:       bool operator==(const Node i) const {return id==i.id;}
deba@2116:       bool operator!=(const Node i) const {return id!=i.id;}
deba@2116:       bool operator<(const Node i) const {return id<i.id;}
deba@2116:     };
deba@2116: 
deba@2116:     class UEdge {
deba@2116:       friend class ListBpUGraphBase;
deba@2116:     protected:
deba@2116:       int id;
deba@2116: 
deba@2116:       explicit UEdge(int _id) { id = _id;}
deba@2116:     public:
deba@2116:       UEdge() {}
deba@2116:       UEdge (Invalid) { id = -1; }
deba@2116:       bool operator==(const UEdge i) const {return id==i.id;}
deba@2116:       bool operator!=(const UEdge i) const {return id!=i.id;}
deba@2116:       bool operator<(const UEdge i) const {return id<i.id;}
deba@2116:     };
deba@2116: 
deba@2116:     ListBpUGraphBase()
deba@2116:       : first_anode(-1), first_free_anode(-1),
deba@2116:         first_bnode(-1), first_free_bnode(-1),
deba@2116:         first_free_edge(-1) {}
deba@2116: 
deba@2116:     void firstANode(Node& node) const {
deba@2116:       node.id = first_anode != -1 ? (first_anode << 1) : -1;
deba@2116:     }
deba@2116:     void nextANode(Node& node) const {
deba@2116:       node.id = aNodes[node.id >> 1].next;
deba@2116:     }
deba@2116: 
deba@2116:     void firstBNode(Node& node) const {
deba@2116:       node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1;
deba@2116:     }
deba@2116:     void nextBNode(Node& node) const {
deba@2116:       node.id = bNodes[node.id >> 1].next;
deba@2116:     }
deba@2116: 
deba@2116:     void first(Node& node) const {
deba@2116:       if (first_anode != -1) {
deba@2116:         node.id = (first_anode << 1);
deba@2116:       } else if (first_bnode != -1) {
deba@2116:         node.id = (first_bnode << 1) + 1;
deba@2116:       } else {
deba@2116:         node.id = -1;
deba@2116:       }
deba@2116:     }
deba@2116:     void next(Node& node) const {
deba@2116:       if (aNode(node)) {
deba@2116:         node.id = aNodes[node.id >> 1].next;
deba@2116:         if (node.id == -1) {
deba@2116:           if (first_bnode != -1) {
deba@2116:             node.id = (first_bnode << 1) + 1;
deba@2116:           }
deba@2116:         }
deba@2116:       } else {
deba@2116:         node.id = bNodes[node.id >> 1].next;
deba@2116:       }
deba@2116:     }
deba@2116:   
deba@2116:     void first(UEdge& edge) const {
deba@2116:       int aNodeId = first_anode;
deba@2116:       while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
deba@2116:         aNodeId = aNodes[aNodeId].next != -1 ? 
deba@2116:           aNodes[aNodeId].next >> 1 : -1;
deba@2116:       }
deba@2116:       if (aNodeId != -1) {
deba@2116:         edge.id = aNodes[aNodeId].first_edge;
deba@2116:       } else {
deba@2116:         edge.id = -1;
deba@2116:       }
deba@2116:     }
deba@2116:     void next(UEdge& edge) const {
deba@2116:       int aNodeId = edges[edge.id].aNode >> 1;
deba@2116:       edge.id = edges[edge.id].next_out;
deba@2116:       if (edge.id == -1) {
deba@2116:         aNodeId = aNodes[aNodeId].next != -1 ? 
deba@2116:           aNodes[aNodeId].next >> 1 : -1;
deba@2116:         while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
deba@2116:           aNodeId = aNodes[aNodeId].next != -1 ? 
deba@2116:           aNodes[aNodeId].next >> 1 : -1;
deba@2116:         }
deba@2116:         if (aNodeId != -1) {
deba@2116:           edge.id = aNodes[aNodeId].first_edge;
deba@2116:         } else {
deba@2116:           edge.id = -1;
deba@2116:         }
deba@2116:       }
deba@2116:     }
deba@2116: 
deba@2116:     void firstFromANode(UEdge& edge, const Node& node) const {
deba@2116:       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
deba@2116:       edge.id = aNodes[node.id >> 1].first_edge;
deba@2116:     }
deba@2116:     void nextFromANode(UEdge& edge) const {
deba@2116:       edge.id = edges[edge.id].next_out;
deba@2116:     }
deba@2116: 
deba@2116:     void firstFromBNode(UEdge& edge, const Node& node) const {
deba@2116:       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
deba@2116:       edge.id = bNodes[node.id >> 1].first_edge;
deba@2116:     }
deba@2116:     void nextFromBNode(UEdge& edge) const {
deba@2116:       edge.id = edges[edge.id].next_in;
deba@2116:     }
deba@2116: 
deba@2116:     static int id(const Node& node) {
deba@2116:       return node.id;
deba@2116:     }
deba@2116:     static Node nodeFromId(int id) {
deba@2116:       return Node(id);
deba@2116:     }
deba@2116:     int maxNodeId() const {
deba@2116:       return aNodes.size() > bNodes.size() ?
deba@2116: 	aNodes.size() * 2 - 2 : bNodes.size() * 2 - 1;
deba@2116:     }
deba@2116:   
deba@2116:     static int id(const UEdge& edge) {
deba@2116:       return edge.id;
deba@2116:     }
deba@2116:     static UEdge uEdgeFromId(int id) {
deba@2116:       return UEdge(id);
deba@2116:     }
deba@2116:     int maxUEdgeId() const {
deba@2116:       return edges.size();
deba@2116:     }
deba@2116:   
deba@2116:     static int aNodeId(const Node& node) {
deba@2116:       return node.id >> 1;
deba@2116:     }
deba@2231:     static Node nodeFromANodeId(int id) {
deba@2116:       return Node(id << 1);
deba@2116:     }
deba@2116:     int maxANodeId() const {
deba@2116:       return aNodes.size();
deba@2116:     }
deba@2116: 
deba@2116:     static int bNodeId(const Node& node) {
deba@2116:       return node.id >> 1;
deba@2116:     }
deba@2231:     static Node nodeFromBNodeId(int id) {
deba@2116:       return Node((id << 1) + 1);
deba@2116:     }
deba@2116:     int maxBNodeId() const {
deba@2116:       return bNodes.size();
deba@2116:     }
deba@2116: 
deba@2116:     Node aNode(const UEdge& edge) const {
deba@2116:       return Node(edges[edge.id].aNode);
deba@2116:     }
deba@2116:     Node bNode(const UEdge& edge) const {
deba@2116:       return Node(edges[edge.id].bNode);
deba@2116:     }
deba@2116: 
deba@2116:     static bool aNode(const Node& node) {
deba@2116:       return (node.id & 1) == 0;
deba@2116:     }
deba@2116: 
deba@2116:     static bool bNode(const Node& node) {
deba@2116:       return (node.id & 1) == 1;
deba@2116:     }
deba@2116: 
deba@2116:     Node addANode() {
deba@2116:       int aNodeId;
deba@2116:       if (first_free_anode == -1) {
deba@2116:         aNodeId = aNodes.size();
deba@2116:         aNodes.push_back(NodeT());
deba@2116:       } else {
deba@2116:         aNodeId = first_free_anode;
deba@2116:         first_free_anode = aNodes[first_free_anode].next;
deba@2116:       }
deba@2116:       if (first_anode != -1) {
deba@2116:         aNodes[aNodeId].next = first_anode << 1;
deba@2116:         aNodes[first_anode].prev = aNodeId << 1;
deba@2116:       } else {
deba@2116:         aNodes[aNodeId].next = -1;
deba@2116:       }
deba@2116:       aNodes[aNodeId].prev = -1;
deba@2116:       first_anode = aNodeId;
deba@2116:       aNodes[aNodeId].first_edge = -1;
deba@2116:       return Node(aNodeId << 1);
deba@2116:     }
deba@2116: 
deba@2116:     Node addBNode() {
deba@2116:       int bNodeId;
deba@2116:       if (first_free_bnode == -1) {
deba@2116:         bNodeId = bNodes.size();
deba@2116:         bNodes.push_back(NodeT());
deba@2116:       } else {
deba@2116:         bNodeId = first_free_bnode;
deba@2116:         first_free_bnode = bNodes[first_free_bnode].next;
deba@2116:       }
deba@2116:       if (first_bnode != -1) {
deba@2116:         bNodes[bNodeId].next = (first_bnode << 1) + 1;
deba@2116:         bNodes[first_bnode].prev = (bNodeId << 1) + 1;
deba@2116:       } else {
deba@2116:         bNodes[bNodeId].next = -1;
deba@2116:       }
deba@2189:       bNodes[bNodeId].prev = -1;
deba@2116:       first_bnode = bNodeId;
deba@2116:       bNodes[bNodeId].first_edge = -1;
deba@2116:       return Node((bNodeId << 1) + 1);
deba@2116:     }
deba@2116: 
deba@2116:     UEdge addEdge(const Node& source, const Node& target) {
deba@2116:       LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
deba@2116:       int edgeId;
deba@2116:       if (first_free_edge != -1) {
deba@2116:         edgeId = first_free_edge;
deba@2116:         first_free_edge = edges[edgeId].next_out;
deba@2116:       } else {
deba@2116:         edgeId = edges.size();
deba@2116:         edges.push_back(UEdgeT());
deba@2116:       }
deba@2116:       if ((source.id & 1) == 0) {
deba@2116: 	edges[edgeId].aNode = source.id;
deba@2116: 	edges[edgeId].bNode = target.id;
deba@2116:       } else {
deba@2116: 	edges[edgeId].aNode = target.id;
deba@2116: 	edges[edgeId].bNode = source.id;
deba@2116:       }
deba@2116:       edges[edgeId].next_out = aNodes[edges[edgeId].aNode >> 1].first_edge;
deba@2116:       edges[edgeId].prev_out = -1;
deba@2116:       if (aNodes[edges[edgeId].aNode >> 1].first_edge != -1) {
deba@2116:         edges[aNodes[edges[edgeId].aNode >> 1].first_edge].prev_out = edgeId;
deba@2116:       }
deba@2116:       aNodes[edges[edgeId].aNode >> 1].first_edge = edgeId;
deba@2116:       edges[edgeId].next_in = bNodes[edges[edgeId].bNode >> 1].first_edge;
deba@2116:       edges[edgeId].prev_in = -1;
deba@2116:       if (bNodes[edges[edgeId].bNode >> 1].first_edge != -1) {
deba@2116:         edges[bNodes[edges[edgeId].bNode >> 1].first_edge].prev_in = edgeId;
deba@2116:       }
deba@2116:       bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
deba@2116:       return UEdge(edgeId);
deba@2116:     }
deba@2116: 
deba@2116:     void erase(const Node& node) {
deba@2116:       if (aNode(node)) {
deba@2116:         int aNodeId = node.id >> 1;
deba@2116:         if (aNodes[aNodeId].prev != -1) {
deba@2116:           aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
deba@2116:         } else {
deba@2189:           first_anode = 
deba@2189:             aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
deba@2116:         }
deba@2116:         if (aNodes[aNodeId].next != -1) {
deba@2116:           aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
deba@2116:         }
deba@2116:         aNodes[aNodeId].next = first_free_anode;
deba@2116:         first_free_anode = aNodeId;
deba@2116:       } else {
deba@2116:         int bNodeId = node.id >> 1;
deba@2116:         if (bNodes[bNodeId].prev != -1) {
deba@2116:           bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
deba@2116:         } else {
deba@2189:           first_bnode = 
deba@2189:             bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
deba@2116:         }
deba@2116:         if (bNodes[bNodeId].next != -1) {
deba@2116:           bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
deba@2116:         }
deba@2116:         bNodes[bNodeId].next = first_free_bnode;
deba@2116:         first_free_bnode = bNodeId;
deba@2116:       }
deba@2116:     }
deba@2116: 
deba@2116:     void erase(const UEdge& edge) {
deba@2116: 
deba@2116:       if (edges[edge.id].prev_out != -1) {
deba@2116:         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
deba@2116:       } else {
deba@2116:         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
deba@2116:       }
deba@2116:       if (edges[edge.id].next_out != -1) {
deba@2116:         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;
deba@2116:       }
deba@2116: 
deba@2116:       if (edges[edge.id].prev_in != -1) {
deba@2116:         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
deba@2116:       } else {
deba@2116:         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
deba@2116:       }
deba@2116:       if (edges[edge.id].next_in != -1) {
deba@2116:         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;
deba@2116:       }
deba@2116: 
deba@2116:       edges[edge.id].next_out = first_free_edge;
deba@2116:       first_free_edge = edge.id;
deba@2116:     }
alpar@2128:  
deba@2116:     void clear() {
deba@2116:       aNodes.clear();
deba@2116:       bNodes.clear();
deba@2116:       edges.clear();
deba@2116:       first_anode = -1;
deba@2116:       first_free_anode = -1;
deba@2116:       first_bnode = -1;
deba@2116:       first_free_bnode = -1;
deba@2116:       first_free_edge = -1;
deba@2116:     }
deba@2116: 
deba@2160:     void changeANode(const UEdge& edge, const Node& node) {
deba@2160:       LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
deba@2160:       if (edges[edge.id].prev_out != -1) {
deba@2160:         edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
deba@2160:       } else {
deba@2160:         aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out;
deba@2160:       }
deba@2160:       if (edges[edge.id].next_out != -1) {
deba@2160:         edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out;  
deba@2160:       }
deba@2160:       if (aNodes[node.id >> 1].first_edge != -1) {
deba@2160:         edges[aNodes[node.id >> 1].first_edge].prev_out = edge.id;
deba@2160:       }
deba@2160:       edges[edge.id].prev_out = -1;
deba@2160:       edges[edge.id].next_out = aNodes[node.id >> 1].first_edge;
deba@2160:       aNodes[node.id >> 1].first_edge = edge.id;
deba@2160:       edges[edge.id].aNode = node.id;
deba@2160:     } 
deba@2160: 
deba@2160:     void changeBNode(const UEdge& edge, const Node& node) {
deba@2160:       LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
deba@2160:       if (edges[edge.id].prev_in != -1) {
deba@2160:         edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in;
deba@2160:       } else {
deba@2160:         bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in;
deba@2160:       }
deba@2160:       if (edges[edge.id].next_in != -1) {
deba@2160:         edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in;  
deba@2160:       }
deba@2160:       if (bNodes[node.id >> 1].first_edge != -1) {
deba@2160:         edges[bNodes[node.id >> 1].first_edge].prev_in = edge.id;
deba@2160:       }
deba@2160:       edges[edge.id].prev_in = -1;
deba@2160:       edges[edge.id].next_in = bNodes[node.id >> 1].first_edge;
deba@2160:       bNodes[node.id >> 1].first_edge = edge.id;
deba@2160:       edges[edge.id].bNode = node.id;
deba@2160:     } 
deba@2160: 
deba@2116:   };
deba@2116: 
deba@2116: 
deba@2231:   typedef BpUGraphExtender<BidirBpUGraphExtender<ListBpUGraphBase> > 
deba@2231:   ExtendedListBpUGraphBase;
deba@2116: 
deba@2116:   /// \ingroup graphs
deba@2116:   ///
deba@2116:   /// \brief A smart bipartite undirected graph class.
deba@2116:   ///
deba@2116:   /// This is a bipartite undirected graph implementation.
alpar@2117:   /// It is conforms to the \ref concept::BpUGraph "BpUGraph concept".
deba@2116:   /// \sa concept::BpUGraph.
deba@2116:   ///
deba@2160:   class ListBpUGraph : public ExtendedListBpUGraphBase {
deba@2160:     /// \brief ListBpUGraph is \e not copy constructible.
deba@2160:     ///
deba@2160:     ///ListBpUGraph is \e not copy constructible.
deba@2160:     ListBpUGraph(const ListBpUGraph &) :ExtendedListBpUGraphBase()  {};
deba@2160:     /// \brief Assignment of ListBpUGraph to another one is \e not
deba@2160:     /// allowed.
deba@2160:     ///
deba@2160:     /// Assignment of ListBpUGraph to another one is \e not allowed.
deba@2160:     void operator=(const ListBpUGraph &) {}
deba@2160:   public:
deba@2160:     /// \brief Constructor
deba@2160:     ///    
deba@2160:     /// Constructor.
deba@2160:     ///
deba@2160:     ListBpUGraph() {}
deba@2160: 
deba@2160:     typedef ExtendedListBpUGraphBase Parent;
deba@2160:     /// \brief Add a new ANode to the graph.
deba@2160:     ///
deba@2160:     /// \return the new node.
deba@2160:     ///
deba@2160:     Node addANode() { return Parent::addANode(); }
deba@2160: 
deba@2160:     /// \brief Add a new BNode to the graph.
deba@2160:     ///
deba@2160:     /// \return the new node.
deba@2160:     ///
deba@2160:     Node addBNode() { return Parent::addBNode(); }
deba@2160: 
deba@2160:     /// \brief Add a new edge to the graph.
deba@2160:     ///
deba@2160:     /// Add a new edge to the graph with an ANode and a BNode.
deba@2160:     /// \return the new undirected edge.
deba@2160:     UEdge addEdge(const Node& s, const Node& t) { 
deba@2160:       return Parent::addEdge(s, t); 
deba@2160:     }
deba@2160: 
deba@2160:     /// \brief Changes the ANode of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the ANode of \c e to \c n
deba@2160:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2160:     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2160:     ///invalidated.
deba@2160:     void changeANode(UEdge e, Node n) { 
deba@2160:       Parent::changeANode(e,n); 
deba@2160:     }
deba@2160: 
deba@2160:     /// \brief Changes the BNode of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the BNode of \c e to \c n
deba@2160:     ///
deba@2160:     /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160:     /// referencing the changed edge remain
deba@2160:     /// valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160:     void changeBNode(UEdge e, Node n) { 
deba@2160:       Parent::changeBNode(e,n); 
deba@2160:     }
deba@2160: 
deba@2160:     /// \brief Changes the source(ANode) of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the source(ANode) of \c e to \c n
deba@2160:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s referencing
deba@2160:     ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
deba@2160:     ///invalidated.
deba@2160:     void changeSource(UEdge e, Node n) { 
deba@2160:       Parent::changeANode(e,n); 
deba@2160:     }
deba@2160: 
deba@2160:     /// \brief Changes the target(BNode) of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the target(BNode) of \c e to \c n
deba@2160:     ///
deba@2160:     /// \note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160:     /// referencing the changed edge remain
deba@2160:     /// valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160:     void changeTarget(UEdge e, Node n) { 
deba@2160:       Parent::changeBNode(e,n); 
deba@2160:     }
deba@2160: 
deba@2160:     /// \brief Changes the source of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the source of \c e to \c n. It changes the proper
deba@2160:     /// node of the represented undirected edge.
deba@2160:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>InEdgeIt</tt>s
deba@2160:     ///referencing the changed edge remain
deba@2160:     ///valid. However <tt>OutEdgeIt</tt>s are invalidated.
deba@2160:     void changeSource(Edge e, Node n) { 
deba@2160:       if (Parent::direction(e)) {
deba@2160:         Parent::changeANode(e,n);
deba@2160:       } else {
deba@2160:         Parent::changeBNode(e,n);
deba@2160:       } 
deba@2160:     }
deba@2160:     /// \brief Changes the target of \c e to \c n
deba@2160:     ///
deba@2160:     /// Changes the target of \c e to \c n. It changes the proper
deba@2160:     /// node of the represented undirected edge.
deba@2160:     ///
deba@2160:     ///\note The <tt>EdgeIt</tt>s and <tt>OutEdgeIt</tt>s
deba@2160:     ///referencing the changed edge remain
deba@2160:     ///valid. However <tt>InEdgeIt</tt>s are invalidated.
deba@2160:     void changeTarget(Edge e, Node n) { 
deba@2160:       if (Parent::direction(e)) {
deba@2160:         Parent::changeBNode(e,n);
deba@2160:       } else {
deba@2160:         Parent::changeANode(e,n);
deba@2160:       } 
deba@2160:     }
deba@2160:     /// \brief Contract two nodes.
deba@2160:     ///
deba@2160:     /// This function contracts two nodes.
deba@2160:     ///
deba@2160:     /// Node \p b will be removed but instead of deleting its
deba@2160:     /// neighboring edges, they will be joined to \p a.  The two nodes
deba@2160:     /// should be from the same nodeset, of course.
deba@2160:     ///
deba@2160:     /// \note The <tt>EdgeIt</tt>s referencing a moved edge remain
deba@2160:     /// valid.
deba@2160:     void contract(const Node& a, const Node& b) {
deba@2160:       LEMON_ASSERT(Parent::aNode(a) == Parent::aNode(b), NodeSetError());
deba@2160:       if (Parent::aNode(a)) {
deba@2160:         for (IncEdgeIt e(*this, b); e!=INVALID;) {
deba@2160:           IncEdgeIt f = e; ++f;
deba@2160:           changeSource(e, a);
deba@2160:           e = f;
deba@2160:         }
deba@2160:       } else {
deba@2160:         for (IncEdgeIt e(*this, b); e!=INVALID;) {
deba@2160:           IncEdgeIt f = e; ++f;
deba@2160:           changeTarget(e, a);
deba@2160:           e = f;
deba@2160:         }
deba@2160:       }
deba@2160:       erase(b);
deba@2160:     }
deba@2160: 
deba@2189:     /// \brief Class to make a snapshot of the graph and restore
deba@2189:     /// to it later.
deba@2189:     ///
deba@2189:     /// Class to make a snapshot of the graph and to restore it
deba@2189:     /// later.
deba@2189:     ///
deba@2189:     /// The newly added nodes and undirected edges can be removed
deba@2189:     /// using the restore() function.
deba@2189:     ///
deba@2189:     /// \warning Edge and node deletions cannot be restored. This
deba@2189:     /// events invalidate the snapshot. 
deba@2189:     class Snapshot {
deba@2189:     protected:
deba@2189: 
deba@2189:       typedef Parent::NodeNotifier NodeNotifier;
deba@2189: 
deba@2189:       class NodeObserverProxy : public NodeNotifier::ObserverBase {
deba@2189:       public:
deba@2189: 
deba@2189:         NodeObserverProxy(Snapshot& _snapshot)
deba@2189:           : snapshot(_snapshot) {}
deba@2189: 
deba@2189:         using NodeNotifier::ObserverBase::attach;
deba@2189:         using NodeNotifier::ObserverBase::detach;
deba@2189:         using NodeNotifier::ObserverBase::attached;
deba@2189:         
deba@2189:       protected:
deba@2189:         
deba@2189:         virtual void add(const Node& node) {
deba@2189:           snapshot.addNode(node);
deba@2189:         }
deba@2189:         virtual void add(const std::vector<Node>& nodes) {
deba@2189:           for (int i = nodes.size() - 1; i >= 0; ++i) {
deba@2189:             snapshot.addNode(nodes[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void erase(const Node& node) {
deba@2189:           snapshot.eraseNode(node);
deba@2189:         }
deba@2189:         virtual void erase(const std::vector<Node>& nodes) {
deba@2189:           for (int i = 0; i < (int)nodes.size(); ++i) {
deba@2189:             snapshot.eraseNode(nodes[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void build() {
deba@2189:           NodeNotifier* notifier = getNotifier();
deba@2189:           Node node;
deba@2189:           std::vector<Node> nodes;
deba@2189:           for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2189:             nodes.push_back(node);
deba@2189:           }
deba@2189:           for (int i = nodes.size() - 1; i >= 0; --i) {
deba@2189:             snapshot.addNode(nodes[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void clear() {
deba@2189:           NodeNotifier* notifier = getNotifier();
deba@2189:           Node node;
deba@2189:           for (notifier->first(node); node != INVALID; notifier->next(node)) {
deba@2189:             snapshot.eraseNode(node);
deba@2189:           }
deba@2189:         }
deba@2189: 
deba@2189:         Snapshot& snapshot;
deba@2189:       };
deba@2189: 
deba@2189:       class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
deba@2189:       public:
deba@2189: 
deba@2189:         UEdgeObserverProxy(Snapshot& _snapshot)
deba@2189:           : snapshot(_snapshot) {}
deba@2189: 
deba@2189:         using UEdgeNotifier::ObserverBase::attach;
deba@2189:         using UEdgeNotifier::ObserverBase::detach;
deba@2189:         using UEdgeNotifier::ObserverBase::attached;
deba@2189:         
deba@2189:       protected:
deba@2189: 
deba@2189:         virtual void add(const UEdge& edge) {
deba@2189:           snapshot.addUEdge(edge);
deba@2189:         }
deba@2189:         virtual void add(const std::vector<UEdge>& edges) {
deba@2189:           for (int i = edges.size() - 1; i >= 0; ++i) {
deba@2189:             snapshot.addUEdge(edges[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void erase(const UEdge& edge) {
deba@2189:           snapshot.eraseUEdge(edge);
deba@2189:         }
deba@2189:         virtual void erase(const std::vector<UEdge>& edges) {
deba@2189:           for (int i = 0; i < (int)edges.size(); ++i) {
deba@2189:             snapshot.eraseUEdge(edges[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void build() {
deba@2189:           UEdgeNotifier* notifier = getNotifier();
deba@2189:           UEdge edge;
deba@2189:           std::vector<UEdge> edges;
deba@2189:           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2189:             edges.push_back(edge);
deba@2189:           }
deba@2189:           for (int i = edges.size() - 1; i >= 0; --i) {
deba@2189:             snapshot.addUEdge(edges[i]);
deba@2189:           }
deba@2189:         }
deba@2189:         virtual void clear() {
deba@2189:           UEdgeNotifier* notifier = getNotifier();
deba@2189:           UEdge edge;
deba@2189:           for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
deba@2189:             snapshot.eraseUEdge(edge);
deba@2189:           }
deba@2189:         }
deba@2189: 
deba@2189:         Snapshot& snapshot;
deba@2189:       };
deba@2189:       
deba@2189:       ListBpUGraph *graph;
deba@2189: 
deba@2189:       NodeObserverProxy node_observer_proxy;
deba@2189:       UEdgeObserverProxy edge_observer_proxy;
deba@2189: 
deba@2189:       std::list<Node> added_nodes;
deba@2189:       std::list<UEdge> added_edges;
deba@2189: 
deba@2189: 
deba@2189:       void addNode(const Node& node) {
deba@2189:         added_nodes.push_front(node);        
deba@2189:       }
deba@2189:       void eraseNode(const Node& node) {
deba@2189:         std::list<Node>::iterator it = 
deba@2189:           std::find(added_nodes.begin(), added_nodes.end(), node);
deba@2189:         if (it == added_nodes.end()) {
deba@2189:           clear();
deba@2189:           edge_observer_proxy.detach();
deba@2189:           throw NodeNotifier::ImmediateDetach();
deba@2189:         } else {
deba@2189:           added_nodes.erase(it);
deba@2189:         }
deba@2189:       }
deba@2189: 
deba@2189:       void addUEdge(const UEdge& edge) {
deba@2189:         added_edges.push_front(edge);        
deba@2189:       }
deba@2189:       void eraseUEdge(const UEdge& edge) {
deba@2189:         std::list<UEdge>::iterator it = 
deba@2189:           std::find(added_edges.begin(), added_edges.end(), edge);
deba@2189:         if (it == added_edges.end()) {
deba@2189:           clear();
deba@2189:           node_observer_proxy.detach();
deba@2189:           throw UEdgeNotifier::ImmediateDetach();
deba@2189:         } else {
deba@2189:           added_edges.erase(it);
deba@2189:         }        
deba@2189:       }
deba@2189: 
deba@2189:       void attach(ListBpUGraph &_graph) {
deba@2189: 	graph = &_graph;
deba@2189: 	node_observer_proxy.attach(graph->getNotifier(Node()));
deba@2189:         edge_observer_proxy.attach(graph->getNotifier(UEdge()));
deba@2189:       }
deba@2189:             
deba@2189:       void detach() {
deba@2189: 	node_observer_proxy.detach();
deba@2189: 	edge_observer_proxy.detach();
deba@2189:       }
deba@2189: 
deba@2189:       bool attached() const {
deba@2189:         return node_observer_proxy.attached();
deba@2189:       }
deba@2189: 
deba@2189:       void clear() {
deba@2189:         added_nodes.clear();
deba@2189:         added_edges.clear();        
deba@2189:       }
deba@2189: 
deba@2189:     public:
deba@2189: 
deba@2189:       /// \brief Default constructor.
deba@2189:       ///
deba@2189:       /// Default constructor.
deba@2189:       /// To actually make a snapshot you must call save().
deba@2189:       Snapshot() 
deba@2189:         : graph(0), node_observer_proxy(*this), 
deba@2189:           edge_observer_proxy(*this) {}
deba@2189:       
deba@2189:       /// \brief Constructor that immediately makes a snapshot.
deba@2189:       ///      
deba@2189:       /// This constructor immediately makes a snapshot of the graph.
deba@2189:       /// \param _graph The graph we make a snapshot of.
deba@2189:       Snapshot(ListBpUGraph &_graph) 
deba@2189:         : node_observer_proxy(*this), 
deba@2189:           edge_observer_proxy(*this) {
deba@2189: 	attach(_graph);
deba@2189:       }
deba@2189:       
deba@2189:       /// \brief Make a snapshot.
deba@2189:       ///
deba@2189:       /// Make a snapshot of the graph.
deba@2189:       ///
deba@2189:       /// This function can be called more than once. In case of a repeated
deba@2189:       /// call, the previous snapshot gets lost.
deba@2189:       /// \param _graph The graph we make the snapshot of.
deba@2189:       void save(ListBpUGraph &_graph) {
deba@2189:         if (attached()) {
deba@2189:           detach();
deba@2189:           clear();
deba@2189:         }
deba@2189:         attach(_graph);
deba@2189:       }
deba@2189:       
deba@2189:       /// \brief Undo the changes until the last snapshot.
deba@2189:       // 
deba@2189:       /// Undo the changes until the last snapshot created by save().
deba@2189:       void restore() {
deba@2189: 	detach();
deba@2189: 	for(std::list<UEdge>::iterator it = added_edges.begin(); 
deba@2189:             it != added_edges.end(); ++it) {
deba@2189: 	  graph->erase(*it);
deba@2189: 	}
deba@2189: 	for(std::list<Node>::iterator it = added_nodes.begin(); 
deba@2189:             it != added_nodes.end(); ++it) {
deba@2189: 	  graph->erase(*it);
deba@2189: 	}
deba@2189:         clear();
deba@2189:       }
deba@2189: 
deba@2189:       /// \brief Gives back true when the snapshot is valid.
deba@2189:       ///
deba@2189:       /// Gives back true when the snapshot is valid.
deba@2189:       bool valid() const {
deba@2189:         return attached();
deba@2189:       }
deba@2189:     };
deba@2160:   };
deba@2116: 
deba@2116:   
deba@2116:   /// @}  
alpar@948: } //namespace lemon
klao@946:   
alpar@400: 
klao@946: #endif