deba@1842: /* -*- C++ -*-
deba@1842:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1842:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1842:  *
deba@1842:  * Permission to use, modify and distribute this software is granted
deba@1842:  * provided that this copyright notice appears in all copies. For
deba@1842:  * precise terms see the accompanying LICENSE file.
deba@1842:  *
deba@1842:  * This software is provided "AS IS" with no warranty of any kind,
deba@1842:  * express or implied, and with no claim as to its suitability for any
deba@1842:  * purpose.
deba@1842:  *
deba@1842:  */
deba@1842: 
deba@1842: #ifndef LEMON_EDGE_SET_H
deba@1842: #define LEMON_EDGE_SET_H
deba@1842: 
deba@1979: 
deba@1990: #include <lemon/bits/default_map.h>
deba@1979: #include <lemon/bits/edge_set_extender.h>
deba@1962: 
deba@2224: /// \ingroup semi_adaptors
deba@1842: /// \file
deba@1842: /// \brief EdgeSet classes.
deba@1842: ///
deba@1842: /// Graphs which use another graph's node-set as own. 
deba@1842: 
deba@1842: namespace lemon {
deba@1842: 
deba@1842:   template <typename _Graph>
deba@1842:   class ListEdgeSetBase {
deba@1842:   public:
deba@1842: 
deba@1842:     typedef _Graph Graph;
deba@1842:     typedef typename Graph::Node Node;
deba@1842:     typedef typename Graph::NodeIt NodeIt;
deba@1842: 
deba@1842:   protected:
deba@1842: 
deba@1842:     struct NodeT {
deba@1842:       int first_out, first_in;
deba@1842:       NodeT() : first_out(-1), first_in(-1) {}
deba@1842:     };
deba@1842: 
deba@1990:     typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
deba@1842: 
deba@1842:     NodesImplBase* nodes;
deba@1842: 
deba@1842:     struct EdgeT {
deba@1842:       Node source, target;
deba@1842:       int next_out, next_in;
deba@1842:       int prev_out, prev_in;
deba@1842:       EdgeT() : prev_out(-1), prev_in(-1) {}
deba@1842:     };
deba@1842: 
deba@1842:     std::vector<EdgeT> edges;
deba@1842: 
deba@1842:     int first_edge;
deba@1842:     int first_free_edge;
deba@1842: 
deba@1842:     const Graph* graph;
deba@1842: 
deba@1842:     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@1842:       graph = &_graph;
deba@1842:       nodes = &_nodes;
deba@1842:     }
deba@1842:     
deba@1842:   public:
deba@1842: 
deba@1842:     class Edge {
deba@1842:       friend class ListEdgeSetBase<Graph>;
deba@1842:     protected:
deba@1842:       Edge(int _id) : id(_id) {}
deba@1842:       int id;
deba@1842:     public:
deba@1842:       Edge() {}
deba@1842:       Edge(Invalid) : id(-1) {}
deba@1842:       bool operator==(const Edge& edge) const { return id == edge.id; }
deba@1842:       bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@1842:       bool operator<(const Edge& edge) const { return id < edge.id; }
deba@1842:     };
deba@1842: 
deba@1842:     ListEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} 
deba@1842: 
deba@2386:     Edge addEdge(const Node& u, const Node& v) {
deba@1842:       int n;
deba@1842:       if (first_free_edge == -1) {
deba@1842: 	n = edges.size();
deba@1842: 	edges.push_back(EdgeT());
deba@1842:       } else {
deba@1842: 	n = first_free_edge;
deba@1842: 	first_free_edge = edges[first_free_edge].next_in;
deba@1842:       }
deba@2386:       edges[n].next_in = (*nodes)[v].first_in;
deba@2386:       if ((*nodes)[v].first_in != -1) {
deba@2386:         edges[(*nodes)[v].first_in].prev_in = n;
deba@1962:       }
deba@2386:       (*nodes)[v].first_in = n;
deba@2386:       edges[n].next_out = (*nodes)[u].first_out;
deba@2386:       if ((*nodes)[u].first_out != -1) {
deba@2386:         edges[(*nodes)[u].first_out].prev_out = n;
deba@1962:       }
deba@2386:       (*nodes)[u].first_out = n;
deba@2386:       edges[n].source = u;
deba@2386:       edges[n].target = v;
deba@1842:       return Edge(n);
deba@1842:     }
deba@1842: 
deba@1842:     void erase(const Edge& edge) {
deba@1842:       int n = edge.id;
deba@1842:       if (edges[n].prev_in != -1) {
deba@1842: 	edges[edges[n].prev_in].next_in = edges[n].next_in;
deba@1842:       } else {
deba@1842: 	(*nodes)[edges[n].target].first_in = edges[n].next_in;
deba@1842:       }
deba@1842:       if (edges[n].next_in != -1) {
deba@1842: 	edges[edges[n].next_in].prev_in = edges[n].prev_in;
deba@1842:       }
deba@1842: 
deba@1842:       if (edges[n].prev_out != -1) {
deba@1842: 	edges[edges[n].prev_out].next_out = edges[n].next_out;
deba@1842:       } else {
deba@1842: 	(*nodes)[edges[n].source].first_out = edges[n].next_out;
deba@1842:       }
deba@1842:       if (edges[n].next_out != -1) {
deba@1842: 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
deba@1842:       }
deba@1842:            
deba@1842:     }
deba@1842: 
deba@1842:     void clear() {
deba@1962:       Node node;
deba@1962:       for (first(node); node != INVALID; next(node)) {
deba@1962:         (*nodes)[node].first_in = -1;
deba@1962:         (*nodes)[node].first_out = -1;
deba@1962:       }
deba@1842:       edges.clear();
deba@1842:       first_edge = -1;
deba@1842:       first_free_edge = -1;
deba@1842:     }
deba@1842: 
deba@1842:     void first(Node& node) const {
deba@1842:       graph->first(node);
deba@1842:     }
deba@1842: 
deba@1842:     void next(Node& node) const {
deba@1842:       graph->next(node);
deba@1842:     }
deba@1842: 
deba@1842:     void first(Edge& edge) const {
deba@1842:       Node node;
deba@1842:       for (first(node); node != INVALID && (*nodes)[node].first_in == -1; 
deba@1842: 	   next(node));
deba@1842:       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1842:     }
deba@1842: 
deba@1842:     void next(Edge& edge) const {
deba@1842:       if (edges[edge.id].next_in != -1) {
deba@1842: 	edge.id = edges[edge.id].next_in;
deba@1842:       } else {
deba@1842: 	Node node = edges[edge.id].target;
deba@1842: 	for (next(node); node != INVALID && (*nodes)[node].first_in == -1; 
deba@1842: 	     next(node));
deba@1842: 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
deba@1842:       }      
deba@1842:     }
deba@1842: 
deba@1842:     void firstOut(Edge& edge, const Node& node) const {
deba@1842:       edge.id = (*nodes)[node].first_out;    
deba@1842:     }
deba@1842:     
deba@1842:     void nextOut(Edge& edge) const {
deba@1842:       edge.id = edges[edge.id].next_out;        
deba@1842:     }
deba@1842: 
deba@1842:     void firstIn(Edge& edge, const Node& node) const {
deba@1842:       edge.id = (*nodes)[node].first_in;          
deba@1842:     }
deba@1842: 
deba@1842:     void nextIn(Edge& edge) const {
deba@1842:       edge.id = edges[edge.id].next_in;    
deba@1842:     }
deba@1842: 
deba@1842:     int id(const Node& node) const { return graph->id(node); }
deba@1842:     int id(const Edge& edge) const { return edge.id; }
deba@1842: 
deba@2386:     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
deba@2386:     Edge edgeFromId(int ix) const { return Edge(ix); }
deba@1842: 
deba@1962:     int maxNodeId() const { return graph->maxNodeId(); };
deba@1842:     int maxEdgeId() const { return edges.size() - 1; }
deba@1842: 
deba@1842:     Node source(const Edge& edge) const { return edges[edge.id].source;}
deba@1842:     Node target(const Edge& edge) const { return edges[edge.id].target;}
deba@1842: 
deba@1990:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1990: 
deba@2384:     NodeNotifier& notifier(Node) const {
deba@2384:       return graph->notifier(Node());
deba@1990:     } 
deba@1990: 
deba@1842:     template <typename _Value>
deba@1842:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@1842:     public:
deba@2031: 
deba@1842:       typedef typename _Graph::template NodeMap<_Value> Parent;
deba@2031: 
deba@1842:       explicit NodeMap(const ListEdgeSetBase<Graph>& edgeset) 
deba@2031: 	: Parent(*edgeset.graph) {}
deba@2031: 
deba@1842:       NodeMap(const ListEdgeSetBase<Graph>& edgeset, const _Value& value)
deba@2031: 	: Parent(*edgeset.graph, value) {}
deba@2031: 
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031:         return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@1842:     };
deba@1842: 
deba@1842:   };
deba@1842: 
deba@1866:   /// \ingroup semi_adaptors
deba@1842:   ///
deba@1842:   /// \brief Graph using a node set of another graph and an
deba@1842:   /// own edge set.
deba@1842:   ///
deba@1842:   /// This structure can be used to establish another graph over a node set
deba@1842:   /// of an existing one. The node iterator will go through the nodes of the
deba@1842:   /// original graph.
deba@1842:   ///
deba@1842:   /// \param _Graph The type of the graph which shares its node set with 
alpar@2260:   /// this class. Its interface must conform to the \ref concepts::Graph
deba@2111:   /// "Graph" concept.
deba@1842:   ///
deba@1842:   template <typename _Graph>
deba@1979:   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
deba@1842: 
deba@1842:   public:
deba@1842: 
deba@1979:     typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
deba@1842:     
deba@1842:     typedef typename Parent::Node Node;
deba@1842:     typedef typename Parent::Edge Edge;
deba@1842:     
deba@1842:     typedef _Graph Graph;
deba@1842: 
deba@1842: 
deba@1842:     typedef typename Parent::NodesImplBase NodesImplBase;
deba@1842: 
deba@1842:     void eraseNode(const Node& node) {
deba@1842:       Edge edge;
deba@1842:       Parent::firstOut(edge, node);
deba@1842:       while (edge != INVALID ) {
deba@1842: 	erase(edge);
deba@1842: 	Parent::firstOut(edge, node);
deba@1842:       } 
deba@1842: 
deba@1842:       Parent::firstIn(edge, node);
deba@1842:       while (edge != INVALID ) {
deba@1842: 	erase(edge);
deba@1842: 	Parent::firstIn(edge, node);
deba@1842:       }
deba@1842:     }
deba@1842:     
deba@1842:     void clearNodes() {
deba@1842:       Parent::clear();
deba@1842:     }
deba@1842: 
deba@1842:     class NodesImpl : public NodesImplBase {
deba@1842:     public:
deba@1842:       typedef NodesImplBase Parent;
deba@1842:       
deba@1842:       NodesImpl(const Graph& graph, ListEdgeSet& edgeset) 
deba@1842: 	: Parent(graph), _edgeset(edgeset) {}
deba@1962: 
deba@1962:       virtual ~NodesImpl() {}
deba@1842:       
deba@1842:     protected:
deba@1842: 
deba@1842:       virtual void erase(const Node& node) {
deba@1842: 	_edgeset.eraseNode(node);
deba@1842: 	Parent::erase(node);
deba@1842:       }
deba@1962:       virtual void erase(const std::vector<Node>& nodes) {
deba@2386:         for (int i = 0; i < int(nodes.size()); ++i) {
deba@1962:           _edgeset.eraseNode(nodes[i]);
deba@1962:         }
deba@1962: 	Parent::erase(nodes);
deba@1962:       }
deba@1842:       virtual void clear() {
deba@1842: 	_edgeset.clearNodes();
deba@1842: 	Parent::clear();
deba@1842:       }
deba@1842: 
deba@1842:     private:
deba@1842:       ListEdgeSet& _edgeset;
deba@1842:     };
deba@1842: 
deba@1842:     NodesImpl nodes;
deba@1842:     
deba@1842:   public:
deba@1842: 
deba@1842:     /// \brief Constructor of the adaptor.
deba@1842:     /// 
deba@1842:     /// Constructor of the adaptor.
deba@1842:     ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@1842:       Parent::initalize(graph, nodes);
deba@1842:     }
deba@1842:     
deba@1842:   };
deba@1842: 
deba@2498:   template <typename _Graph>
deba@2498:   class ListUEdgeSetBase {
deba@2498:   public:
deba@2498: 
deba@2498:     typedef _Graph Graph;
deba@2498:     typedef typename Graph::Node Node;
deba@2498:     typedef typename Graph::NodeIt NodeIt;
deba@2498: 
deba@2498:   protected:
deba@2498: 
deba@2498:     struct NodeT {
deba@2498:       int first_out;
deba@2498:       NodeT() : first_out(-1) {}
deba@2498:     };
deba@2498: 
deba@2498:     typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
deba@2498: 
deba@2498:     NodesImplBase* nodes;
deba@2498: 
deba@2498:     struct EdgeT {
deba@2498:       Node target;
deba@2498:       int prev_out, next_out;
deba@2498:       EdgeT() : prev_out(-1), next_out(-1) {}
deba@2498:     };
deba@2498: 
deba@2498:     std::vector<EdgeT> edges;
deba@2498: 
deba@2498:     int first_edge;
deba@2498:     int first_free_edge;
deba@2498: 
deba@2498:     const Graph* graph;
deba@2498: 
deba@2498:     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@2498:       graph = &_graph;
deba@2498:       nodes = &_nodes;
deba@2498:     }
deba@2498:     
deba@2498:   public:
deba@2498: 
deba@2498:     class UEdge {
deba@2498:       friend class ListUEdgeSetBase;
deba@2498:     protected:
deba@2498: 
deba@2498:       int id;
deba@2498:       explicit UEdge(int _id) { id = _id;}
deba@2498: 
deba@2498:     public:
deba@2498:       UEdge() {}
deba@2498:       UEdge (Invalid) { id = -1; }
deba@2498:       bool operator==(const UEdge& edge) const {return id == edge.id;}
deba@2498:       bool operator!=(const UEdge& edge) const {return id != edge.id;}
deba@2498:       bool operator<(const UEdge& edge) const {return id < edge.id;}
deba@2498:     };
deba@2498: 
deba@2498:     class Edge {
deba@2498:       friend class ListUEdgeSetBase;
deba@2498:     protected:
deba@2498:       Edge(int _id) : id(_id) {}
deba@2498:       int id;
deba@2498:     public:
deba@2498:       operator UEdge() const { return uEdgeFromId(id / 2); }
deba@2498: 
deba@2498:       Edge() {}
deba@2498:       Edge(Invalid) : id(-1) {}
deba@2498:       bool operator==(const Edge& edge) const { return id == edge.id; }
deba@2498:       bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@2498:       bool operator<(const Edge& edge) const { return id < edge.id; }
deba@2498:     };
deba@2498: 
deba@2498:     ListUEdgeSetBase() : first_edge(-1), first_free_edge(-1) {} 
deba@2498: 
deba@2498:     UEdge addEdge(const Node& u, const Node& v) {
deba@2498:       int n;
deba@2498: 
deba@2498:       if (first_free_edge == -1) {
deba@2498: 	n = edges.size();
deba@2498: 	edges.push_back(EdgeT());
deba@2498: 	edges.push_back(EdgeT());
deba@2498:       } else {
deba@2498: 	n = first_free_edge;
deba@2498: 	first_free_edge = edges[n].next_out;
deba@2498:       }
deba@2498:       
deba@2498:       edges[n].target = u;
deba@2498:       edges[n | 1].target = v;
deba@2498: 
deba@2498:       edges[n].next_out = (*nodes)[v].first_out;
deba@2498:       if ((*nodes)[v].first_out != -1) {
deba@2498: 	edges[(*nodes)[v].first_out].prev_out = n;
deba@2498:       }
deba@2498:       (*nodes)[v].first_out = n;
deba@2498:       edges[n].prev_out = -1;
deba@2498:       
deba@2498:       if ((*nodes)[u].first_out != -1) {
deba@2498: 	edges[(*nodes)[u].first_out].prev_out = (n | 1);
deba@2498:       }
deba@2498:       edges[n | 1].next_out = (*nodes)[u].first_out;
deba@2498:       (*nodes)[u].first_out = (n | 1);
deba@2498:       edges[n | 1].prev_out = -1;
deba@2498: 
deba@2498:       return UEdge(n / 2);
deba@2498:     }
deba@2498: 
deba@2498:     void erase(const UEdge& edge) {
deba@2498:       int n = edge.id * 2;
deba@2498:       
deba@2498:       if (edges[n].next_out != -1) {
deba@2498: 	edges[edges[n].next_out].prev_out = edges[n].prev_out;
deba@2498:       } 
deba@2498: 
deba@2498:       if (edges[n].prev_out != -1) {
deba@2498: 	edges[edges[n].prev_out].next_out = edges[n].next_out;
deba@2498:       } else {
deba@2498: 	(*nodes)[edges[n | 1].target].first_out = edges[n].next_out;
deba@2498:       }
deba@2498: 
deba@2498:       if (edges[n | 1].next_out != -1) {
deba@2498: 	edges[edges[n | 1].next_out].prev_out = edges[n | 1].prev_out;
deba@2498:       } 
deba@2498: 
deba@2498:       if (edges[n | 1].prev_out != -1) {
deba@2498: 	edges[edges[n | 1].prev_out].next_out = edges[n | 1].next_out;
deba@2498:       } else {
deba@2498: 	(*nodes)[edges[n].target].first_out = edges[n | 1].next_out;
deba@2498:       }
deba@2498:       
deba@2498:       edges[n].next_out = first_free_edge;
deba@2498:       first_free_edge = n;      
deba@2498:            
deba@2498:     }
deba@2498: 
deba@2498:     void clear() {
deba@2498:       Node node;
deba@2498:       for (first(node); node != INVALID; next(node)) {
deba@2498:         (*nodes)[node].first_out = -1;
deba@2498:       }
deba@2498:       edges.clear();
deba@2498:       first_edge = -1;
deba@2498:       first_free_edge = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void first(Node& node) const {
deba@2498:       graph->first(node);
deba@2498:     }
deba@2498: 
deba@2498:     void next(Node& node) const {
deba@2498:       graph->next(node);
deba@2498:     }
deba@2498: 
deba@2498:     void first(Edge& edge) const {
deba@2498:       Node node;
deba@2498:       first(node);
deba@2498:       while (node != INVALID && (*nodes)[node].first_out == -1) {
deba@2498:         next(node);
deba@2498:       }
deba@2498:       edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
deba@2498:     }
deba@2498: 
deba@2498:     void next(Edge& edge) const {
deba@2498:       if (edges[edge.id].next_out != -1) {
deba@2498: 	edge.id = edges[edge.id].next_out;
deba@2498:       } else {
deba@2498: 	Node node = edges[edge.id ^ 1].target;
deba@2498: 	next(node);
deba@2498:         while(node != INVALID && (*nodes)[node].first_out == -1) {
deba@2498:           next(node);
deba@2498:         }
deba@2498: 	edge.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
deba@2498:       }      
deba@2498:     }
deba@2498: 
deba@2498:     void first(UEdge& uedge) const {
deba@2498:       Node node;
deba@2498:       first(node);
deba@2498:       while (node != INVALID) {
deba@2498:         uedge.id = (*nodes)[node].first_out;
deba@2498:         while ((uedge.id & 1) != 1) {
deba@2498:           uedge.id = edges[uedge.id].next_out;
deba@2498:         }
deba@2498:         if (uedge.id != -1) {
deba@2498:           uedge.id /= 2;
deba@2498:           return;
deba@2498:         } 
deba@2498:         next(node);
deba@2498:       }
deba@2498:       uedge.id = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void next(UEdge& uedge) const {
deba@2498:       Node node = edges[uedge.id * 2].target;
deba@2498:       uedge.id = edges[(uedge.id * 2) | 1].next_out;
deba@2498:       while ((uedge.id & 1) != 1) {
deba@2498:         uedge.id = edges[uedge.id].next_out;
deba@2498:       }
deba@2498:       if (uedge.id != -1) {
deba@2498:         uedge.id /= 2;
deba@2498:         return;
deba@2498:       } 
deba@2498:       next(node);
deba@2498:       while (node != INVALID) {
deba@2498:         uedge.id = (*nodes)[node].first_out;
deba@2498:         while ((uedge.id & 1) != 1) {
deba@2498:           uedge.id = edges[uedge.id].next_out;
deba@2498:         }
deba@2498:         if (uedge.id != -1) {
deba@2498:           uedge.id /= 2;
deba@2498:           return;
deba@2498:         } 
deba@2498: 	next(node);
deba@2498:       }
deba@2498:       uedge.id = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void firstOut(Edge& edge, const Node& node) const {
deba@2498:       edge.id = (*nodes)[node].first_out;
deba@2498:     }
deba@2498:     
deba@2498:     void nextOut(Edge& edge) const {
deba@2498:       edge.id = edges[edge.id].next_out;        
deba@2498:     }
deba@2498: 
deba@2498:     void firstIn(Edge& edge, const Node& node) const {
deba@2498:       edge.id = (((*nodes)[node].first_out) ^ 1);
deba@2498:       if (edge.id == -2) edge.id = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void nextIn(Edge& edge) const {
deba@2498:       edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
deba@2498:       if (edge.id == -2) edge.id = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void firstInc(UEdge &edge, bool& dir, const Node& node) const {
deba@2498:       int de = (*nodes)[node].first_out;
deba@2498:       if (de != -1 ) {
deba@2498:         edge.id = de / 2;
deba@2498:         dir = ((de & 1) == 1);
deba@2498:       } else {
deba@2498:         edge.id = -1;
deba@2498:         dir = true;
deba@2498:       }
deba@2498:     }
deba@2498:     void nextInc(UEdge &edge, bool& dir) const {
deba@2498:       int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
deba@2498:       if (de != -1 ) {
deba@2498:         edge.id = de / 2;
deba@2498:         dir = ((de & 1) == 1);
deba@2498:       } else {
deba@2498:         edge.id = -1;
deba@2498:         dir = true;
deba@2498:       }
deba@2498:     }
deba@2498: 
deba@2498:     static bool direction(Edge edge) {
deba@2498:       return (edge.id & 1) == 1;
deba@2498:     }
deba@2498: 
deba@2498:     static Edge direct(UEdge uedge, bool dir) {
deba@2498:       return Edge(uedge.id * 2 + (dir ? 1 : 0));
deba@2498:     }
deba@2498: 
deba@2498:     int id(const Node& node) const { return graph->id(node); }
deba@2498:     static int id(Edge e) { return e.id; }
deba@2498:     static int id(UEdge e) { return e.id; }
deba@2498: 
deba@2498:     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
deba@2498:     static Edge edgeFromId(int id) { return Edge(id);}
deba@2498:     static UEdge uEdgeFromId(int id) { return UEdge(id);}
deba@2498: 
deba@2498:     int maxNodeId() const { return graph->maxNodeId(); };
deba@2498:     int maxUEdgeId() const { return edges.size() / 2 - 1; }
deba@2498:     int maxEdgeId() const { return edges.size()-1; }
deba@2498: 
deba@2498:     Node source(Edge e) const { return edges[e.id ^ 1].target; }
deba@2498:     Node target(Edge e) const { return edges[e.id].target; }
deba@2498: 
deba@2498:     Node source(UEdge e) const { return edges[2 * e.id].target; }
deba@2498:     Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
deba@2498: 
deba@2498:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@2498: 
deba@2498:     NodeNotifier& notifier(Node) const {
deba@2498:       return graph->notifier(Node());
deba@2498:     } 
deba@2498: 
deba@2498:     template <typename _Value>
deba@2498:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@2498:     public:
deba@2498: 
deba@2498:       typedef typename _Graph::template NodeMap<_Value> Parent;
deba@2498: 
deba@2498:       explicit NodeMap(const ListUEdgeSetBase<Graph>& edgeset) 
deba@2498: 	: Parent(*edgeset.graph) {}
deba@2498: 
deba@2498:       NodeMap(const ListUEdgeSetBase<Graph>& edgeset, const _Value& value)
deba@2498: 	: Parent(*edgeset.graph, value) {}
deba@2498: 
deba@2498:       NodeMap& operator=(const NodeMap& cmap) {
deba@2498:         return operator=<NodeMap>(cmap);
deba@2498:       }
deba@2498: 
deba@2498:       template <typename CMap>
deba@2498:       NodeMap& operator=(const CMap& cmap) {
deba@2498:         Parent::operator=(cmap);
deba@2498:         return *this;
deba@2498:       }
deba@2498:     };
deba@2498: 
deba@2498:   };
deba@2498: 
deba@1866:   /// \ingroup semi_adaptors
deba@1842:   ///
deba@1842:   /// \brief Graph using a node set of another graph and an
klao@1909:   /// own uedge set.
deba@1842:   ///
deba@1842:   /// This structure can be used to establish another graph over a node set
deba@1842:   /// of an existing one. The node iterator will go through the nodes of the
deba@1842:   /// original graph.
deba@1842:   ///
deba@1842:   /// \param _Graph The type of the graph which shares its node set with 
alpar@2260:   /// this class. Its interface must conform to the \ref concepts::Graph
deba@2111:   /// "Graph" concept.
deba@1842:   ///
deba@1842:   /// In the edge extension and removing it conforms to the 
alpar@2260:   /// \ref concepts::UGraph "UGraph" concept.
deba@1842:   template <typename _Graph>
deba@2498:   class ListUEdgeSet : public UEdgeSetExtender<ListUEdgeSetBase<_Graph> > {
deba@1842: 
deba@1842:   public:
deba@1842: 
deba@2498:     typedef UEdgeSetExtender<ListUEdgeSetBase<_Graph> > Parent;
deba@1842:     
deba@1842:     typedef typename Parent::Node Node;
deba@1842:     typedef typename Parent::Edge Edge;
deba@1842:     
deba@1842:     typedef _Graph Graph;
deba@1842: 
deba@1842: 
deba@1842:     typedef typename Parent::NodesImplBase NodesImplBase;
deba@1842: 
deba@1842:     void eraseNode(const Node& node) {
deba@1842:       Edge edge;
deba@1842:       Parent::firstOut(edge, node);
deba@1842:       while (edge != INVALID ) {
deba@1842: 	erase(edge);
deba@1842: 	Parent::firstOut(edge, node);
deba@1842:       } 
deba@1842: 
deba@1842:     }
deba@1842:     
deba@1842:     void clearNodes() {
deba@1842:       Parent::clear();
deba@1842:     }
deba@1842: 
deba@1842:     class NodesImpl : public NodesImplBase {
deba@1842:     public:
deba@1842:       typedef NodesImplBase Parent;
deba@1842:       
klao@1909:       NodesImpl(const Graph& graph, ListUEdgeSet& edgeset) 
deba@1842: 	: Parent(graph), _edgeset(edgeset) {}
deba@1962: 
deba@1962:       virtual ~NodesImpl() {}
deba@1842:       
deba@1842:     protected:
deba@1842: 
deba@1842:       virtual void erase(const Node& node) {
deba@1842: 	_edgeset.eraseNode(node);
deba@1842: 	Parent::erase(node);
deba@1842:       }
deba@1866:       virtual void erase(const std::vector<Node>& nodes) {
deba@2386: 	for (int i = 0; i < int(nodes.size()); ++i) {
deba@1866: 	  _edgeset.eraseNode(nodes[i]);
deba@1866: 	}
deba@1866: 	Parent::erase(nodes);
deba@1866:       }
deba@1842:       virtual void clear() {
deba@1842: 	_edgeset.clearNodes();
deba@1842: 	Parent::clear();
deba@1842:       }
deba@1842: 
deba@1842:     private:
klao@1909:       ListUEdgeSet& _edgeset;
deba@1842:     };
deba@1842: 
deba@1842:     NodesImpl nodes;
deba@1842:     
deba@1842:   public:
deba@1842: 
deba@1842:     /// \brief Constructor of the adaptor.
deba@1842:     /// 
deba@1842:     /// Constructor of the adaptor.
klao@1909:     ListUEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@1842:       Parent::initalize(graph, nodes);
deba@1842:     }
deba@1842:     
deba@1842:   };
deba@1842: 
deba@1962:   template <typename _Graph>
deba@1962:   class SmartEdgeSetBase {
deba@1962:   public:
deba@1962: 
deba@1962:     typedef _Graph Graph;
deba@1962:     typedef typename Graph::Node Node;
deba@1962:     typedef typename Graph::NodeIt NodeIt;
deba@1962: 
deba@1962:   protected:
deba@1962: 
deba@1962:     struct NodeT {
deba@1962:       int first_out, first_in;
deba@1962:       NodeT() : first_out(-1), first_in(-1) {}
deba@1962:     };
deba@1962: 
deba@1990:     typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
deba@1962: 
deba@1962:     NodesImplBase* nodes;
deba@1962: 
deba@1962:     struct EdgeT {
deba@1962:       Node source, target;
deba@1962:       int next_out, next_in;
deba@1962:       EdgeT() {}
deba@1962:     };
deba@1962: 
deba@1962:     std::vector<EdgeT> edges;
deba@1962: 
deba@1962:     const Graph* graph;
deba@1962: 
deba@1962:     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@1962:       graph = &_graph;
deba@1962:       nodes = &_nodes;
deba@1962:     }
deba@1962:     
deba@1962:   public:
deba@1962: 
deba@1962:     class Edge {
deba@1962:       friend class SmartEdgeSetBase<Graph>;
deba@1962:     protected:
deba@1962:       Edge(int _id) : id(_id) {}
deba@1962:       int id;
deba@1962:     public:
deba@1962:       Edge() {}
deba@1962:       Edge(Invalid) : id(-1) {}
deba@1962:       bool operator==(const Edge& edge) const { return id == edge.id; }
deba@1962:       bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@1962:       bool operator<(const Edge& edge) const { return id < edge.id; }
deba@1962:     };
deba@1962: 
deba@1962:     SmartEdgeSetBase() {} 
deba@1962: 
deba@2386:     Edge addEdge(const Node& u, const Node& v) {
deba@1962:       int n = edges.size();
deba@1962:       edges.push_back(EdgeT());
deba@2386:       edges[n].next_in = (*nodes)[v].first_in;
deba@2386:       (*nodes)[v].first_in = n;
deba@2386:       edges[n].next_out = (*nodes)[u].first_out;
deba@2386:       (*nodes)[u].first_out = n;
deba@2386:       edges[n].source = u;
deba@2386:       edges[n].target = v;
deba@1962:       return Edge(n);
deba@1962:     }
deba@1962: 
deba@1962:     void clear() {
deba@1962:       Node node;
deba@1962:       for (first(node); node != INVALID; next(node)) {
deba@1962:         (*nodes)[node].first_in = -1;
deba@1962:         (*nodes)[node].first_out = -1;
deba@1962:       }
deba@1962:       edges.clear();
deba@1962:     }
deba@1962: 
deba@1962:     void first(Node& node) const {
deba@1962:       graph->first(node);
deba@1962:     }
deba@1962: 
deba@1962:     void next(Node& node) const {
deba@1962:       graph->next(node);
deba@1962:     }
deba@1962: 
deba@1962:     void first(Edge& edge) const {
deba@1962:       edge.id = edges.size() - 1;
deba@1962:     }
deba@1962: 
deba@1962:     void next(Edge& edge) const {
deba@1962:       --edge.id;
deba@1962:     }
deba@1962: 
deba@1962:     void firstOut(Edge& edge, const Node& node) const {
deba@1962:       edge.id = (*nodes)[node].first_out;    
deba@1962:     }
deba@1962:     
deba@1962:     void nextOut(Edge& edge) const {
deba@1962:       edge.id = edges[edge.id].next_out;        
deba@1962:     }
deba@1962: 
deba@1962:     void firstIn(Edge& edge, const Node& node) const {
deba@1962:       edge.id = (*nodes)[node].first_in;          
deba@1962:     }
deba@1962: 
deba@1962:     void nextIn(Edge& edge) const {
deba@1962:       edge.id = edges[edge.id].next_in;    
deba@1962:     }
deba@1962: 
deba@1962:     int id(const Node& node) const { return graph->id(node); }
deba@1962:     int id(const Edge& edge) const { return edge.id; }
deba@1962: 
deba@2386:     Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
deba@2386:     Edge edgeFromId(int ix) const { return Edge(ix); }
deba@1962: 
deba@1962:     int maxNodeId() const { return graph->maxNodeId(); };
deba@1962:     int maxEdgeId() const { return edges.size() - 1; }
deba@1962: 
deba@1962:     Node source(const Edge& edge) const { return edges[edge.id].source;}
deba@1962:     Node target(const Edge& edge) const { return edges[edge.id].target;}
deba@1962: 
deba@1990:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@1990: 
deba@2384:     NodeNotifier& notifier(Node) const {
deba@2384:       return graph->notifier(Node());
deba@1990:     } 
deba@1990: 
deba@1962:     template <typename _Value>
deba@1962:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@1962:     public:
deba@2031: 
deba@1962:       typedef typename _Graph::template NodeMap<_Value> Parent;
deba@2031: 
deba@1962:       explicit NodeMap(const SmartEdgeSetBase<Graph>& edgeset) 
deba@1962: 	: Parent(*edgeset.graph) { }
deba@2031: 
deba@1962:       NodeMap(const SmartEdgeSetBase<Graph>& edgeset, const _Value& value)
deba@1962: 	: Parent(*edgeset.graph, value) { }
deba@2031: 
deba@2031:       NodeMap& operator=(const NodeMap& cmap) {
deba@2031:         return operator=<NodeMap>(cmap);
deba@2031:       }
deba@2031: 
deba@2031:       template <typename CMap>
deba@2031:       NodeMap& operator=(const CMap& cmap) {
deba@2031:         Parent::operator=(cmap);
deba@2031:         return *this;
deba@2031:       }
deba@1962:     };
deba@1962: 
deba@1962:   };
deba@1962: 
deba@1962: 
deba@1962:   /// \ingroup semi_adaptors
deba@1962:   ///
deba@1962:   /// \brief Graph using a node set of another graph and an
deba@1962:   /// own edge set.
deba@1962:   ///
deba@1962:   /// This structure can be used to establish another graph over a node set
deba@1962:   /// of an existing one. The node iterator will go through the nodes of the
deba@1962:   /// original graph.
deba@1962:   ///
deba@1962:   /// \param _Graph The type of the graph which shares its node set with 
alpar@2260:   /// this class. Its interface must conform to the \ref concepts::Graph
deba@2111:   /// "Graph" concept.
deba@1962:   ///
deba@1962:   /// In the edge extension and removing it conforms to the 
alpar@2260:   /// \ref concepts::Graph "Graph" concept.
deba@1962:   template <typename _Graph>
deba@1979:   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
deba@1962: 
deba@1962:   public:
deba@1962: 
deba@1979:     typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
deba@1962:     
deba@1962:     typedef typename Parent::Node Node;
deba@1962:     typedef typename Parent::Edge Edge;
deba@1962:     
deba@1962:     typedef _Graph Graph;
deba@1962: 
deba@1962:   protected:
deba@1962: 
deba@1962:     typedef typename Parent::NodesImplBase NodesImplBase;
deba@1962: 
deba@1999:     void eraseNode(const Node& node) {
deba@1999:       if (Parent::InEdgeIt(*this, node) == INVALID &&
deba@1999:           Parent::OutEdgeIt(*this, node) == INVALID) {
deba@1999:         return;
deba@1999:       }
deba@2191:       throw typename NodesImplBase::Notifier::ImmediateDetach();
deba@1962:     }
deba@1962:     
deba@1962:     void clearNodes() {
deba@1962:       Parent::clear();
deba@1962:     }
deba@1962: 
deba@1962:     class NodesImpl : public NodesImplBase {
deba@1962:     public:
deba@1962:       typedef NodesImplBase Parent;
deba@1962:       
deba@1962:       NodesImpl(const Graph& graph, SmartEdgeSet& edgeset) 
deba@1962: 	: Parent(graph), _edgeset(edgeset) {}
deba@1962: 
deba@1962:       virtual ~NodesImpl() {}
deba@1962:       
deba@2193:       bool attached() const {
deba@2193:         return Parent::attached();
deba@2193:       }
deba@2193: 
deba@1962:     protected:
deba@1962: 
deba@1962:       virtual void erase(const Node& node) {
deba@2191:         try {
deba@2191:           _edgeset.eraseNode(node);
deba@2191:           Parent::erase(node);
deba@2191:         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@2191:           Parent::clear();
deba@2193:           throw;
deba@2191:         }
deba@1962:       }
deba@1962:       virtual void erase(const std::vector<Node>& nodes) {
deba@2191:         try {
deba@2386:           for (int i = 0; i < int(nodes.size()); ++i) {
deba@2191:             _edgeset.eraseNode(nodes[i]);
deba@2191:           }
deba@2191:           Parent::erase(nodes);
deba@2191:         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@2191:           Parent::clear();
deba@2193:           throw;
deba@1962:         }
deba@1962:       }
deba@1962:       virtual void clear() {
deba@1962: 	_edgeset.clearNodes();
deba@1962: 	Parent::clear();
deba@1962:       }
deba@1962: 
deba@1962:     private:
deba@1962:       SmartEdgeSet& _edgeset;
deba@1962:     };
deba@1962: 
deba@1962:     NodesImpl nodes;
deba@1962:     
deba@1962:   public:
deba@1962: 
deba@1962:     /// \brief Constructor of the adaptor.
deba@1962:     /// 
deba@1962:     /// Constructor of the adaptor.
deba@1962:     SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@1962:       Parent::initalize(graph, nodes);
deba@1962:     }
deba@2193: 
deba@2193:     bool valid() const {
deba@2193:       return nodes.attached();
deba@2193:     }
deba@1962:     
deba@1962:   };
deba@1962: 
deba@2498: 
deba@2498:   template <typename _Graph>
deba@2498:   class SmartUEdgeSetBase {
deba@2498:   public:
deba@2498: 
deba@2498:     typedef _Graph Graph;
deba@2498:     typedef typename Graph::Node Node;
deba@2498:     typedef typename Graph::NodeIt NodeIt;
deba@2498: 
deba@2498:   protected:
deba@2498: 
deba@2498:     struct NodeT {
deba@2498:       int first_out;
deba@2498:       NodeT() : first_out(-1) {}
deba@2498:     };
deba@2498: 
deba@2498:     typedef DefaultMap<Graph, Node, NodeT> NodesImplBase;
deba@2498: 
deba@2498:     NodesImplBase* nodes;
deba@2498: 
deba@2498:     struct EdgeT {
deba@2498:       Node target;
deba@2498:       int next_out;
deba@2498:       EdgeT() {}
deba@2498:     };
deba@2498: 
deba@2498:     std::vector<EdgeT> edges;
deba@2498: 
deba@2498:     const Graph* graph;
deba@2498: 
deba@2498:     void initalize(const Graph& _graph, NodesImplBase& _nodes) {
deba@2498:       graph = &_graph;
deba@2498:       nodes = &_nodes;
deba@2498:     }
deba@2498:     
deba@2498:   public:
deba@2498: 
deba@2498:     class UEdge {
deba@2498:       friend class SmartUEdgeSetBase;
deba@2498:     protected:
deba@2498: 
deba@2498:       int id;
deba@2498:       explicit UEdge(int _id) { id = _id;}
deba@2498: 
deba@2498:     public:
deba@2498:       UEdge() {}
deba@2498:       UEdge (Invalid) { id = -1; }
deba@2498:       bool operator==(const UEdge& edge) const {return id == edge.id;}
deba@2498:       bool operator!=(const UEdge& edge) const {return id != edge.id;}
deba@2498:       bool operator<(const UEdge& edge) const {return id < edge.id;}
deba@2498:     };
deba@2498: 
deba@2498:     class Edge {
deba@2498:       friend class SmartUEdgeSetBase;
deba@2498:     protected:
deba@2498:       Edge(int _id) : id(_id) {}
deba@2498:       int id;
deba@2498:     public:
deba@2498:       operator UEdge() const { return uEdgeFromId(id / 2); }
deba@2498: 
deba@2498:       Edge() {}
deba@2498:       Edge(Invalid) : id(-1) {}
deba@2498:       bool operator==(const Edge& edge) const { return id == edge.id; }
deba@2498:       bool operator!=(const Edge& edge) const { return id != edge.id; }
deba@2498:       bool operator<(const Edge& edge) const { return id < edge.id; }
deba@2498:     };
deba@2498: 
deba@2498:     SmartUEdgeSetBase() {} 
deba@2498: 
deba@2498:     UEdge addEdge(const Node& u, const Node& v) {
deba@2498:       int n = edges.size();
deba@2498:       edges.push_back(EdgeT());
deba@2498:       edges.push_back(EdgeT());
deba@2498:       
deba@2498:       edges[n].target = u;
deba@2498:       edges[n | 1].target = v;
deba@2498: 
deba@2498:       edges[n].next_out = (*nodes)[v].first_out;
deba@2498:       (*nodes)[v].first_out = n;
deba@2498: 
deba@2498:       edges[n | 1].next_out = (*nodes)[u].first_out;	
deba@2498:       (*nodes)[u].first_out = (n | 1);
deba@2498: 
deba@2498:       return UEdge(n / 2);
deba@2498:     }
deba@2498: 
deba@2498:     void clear() {
deba@2498:       Node node;
deba@2498:       for (first(node); node != INVALID; next(node)) {
deba@2498:         (*nodes)[node].first_out = -1;
deba@2498:       }
deba@2498:       edges.clear();
deba@2498:     }
deba@2498: 
deba@2498:     void first(Node& node) const {
deba@2498:       graph->first(node);
deba@2498:     }
deba@2498: 
deba@2498:     void next(Node& node) const {
deba@2498:       graph->next(node);
deba@2498:     }
deba@2498: 
deba@2498:     void first(Edge& edge) const { 
deba@2498:       edge.id = edges.size() - 1;
deba@2498:     }
deba@2498: 
deba@2498:     void next(Edge& edge) const {
deba@2498:       --edge.id;
deba@2498:     }
deba@2498: 
deba@2498:     void first(UEdge& edge) const { 
deba@2498:       edge.id = edges.size() / 2 - 1;
deba@2498:     }
deba@2498: 
deba@2498:     void next(UEdge& edge) const {
deba@2498:       --edge.id;
deba@2498:     }
deba@2498: 
deba@2498:     void firstOut(Edge& edge, const Node& node) const {
deba@2498:       edge.id = (*nodes)[node].first_out;    
deba@2498:     }
deba@2498:     
deba@2498:     void nextOut(Edge& edge) const {
deba@2498:       edge.id = edges[edge.id].next_out;        
deba@2498:     }
deba@2498: 
deba@2498:     void firstIn(Edge& edge, const Node& node) const {
deba@2498:       edge.id = (((*nodes)[node].first_out) ^ 1);
deba@2498:       if (edge.id == -2) edge.id = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void nextIn(Edge& edge) const {
deba@2498:       edge.id = ((edges[edge.id ^ 1].next_out) ^ 1);
deba@2498:       if (edge.id == -2) edge.id = -1;
deba@2498:     }
deba@2498: 
deba@2498:     void firstInc(UEdge &edge, bool& dir, const Node& node) const {
deba@2498:       int de = (*nodes)[node].first_out;
deba@2498:       if (de != -1 ) {
deba@2498:         edge.id = de / 2;
deba@2498:         dir = ((de & 1) == 1);
deba@2498:       } else {
deba@2498:         edge.id = -1;
deba@2498:         dir = true;
deba@2498:       }
deba@2498:     }
deba@2498:     void nextInc(UEdge &edge, bool& dir) const {
deba@2498:       int de = (edges[(edge.id * 2) | (dir ? 1 : 0)].next_out);
deba@2498:       if (de != -1 ) {
deba@2498:         edge.id = de / 2;
deba@2498:         dir = ((de & 1) == 1);
deba@2498:       } else {
deba@2498:         edge.id = -1;
deba@2498:         dir = true;
deba@2498:       }
deba@2498:     }
deba@2498: 
deba@2498:     static bool direction(Edge edge) {
deba@2498:       return (edge.id & 1) == 1;
deba@2498:     }
deba@2498: 
deba@2498:     static Edge direct(UEdge uedge, bool dir) {
deba@2498:       return Edge(uedge.id * 2 + (dir ? 1 : 0));
deba@2498:     }
deba@2498: 
deba@2498:     int id(Node node) const { return graph->id(node); }
deba@2498:     static int id(Edge edge) { return edge.id; }
deba@2498:     static int id(UEdge edge) { return edge.id; }
deba@2498: 
deba@2498:     Node nodeFromId(int id) const { return graph->nodeFromId(id); }
deba@2498:     static Edge edgeFromId(int id) { return Edge(id); }
deba@2498:     static UEdge uEdgeFromId(int id) { return UEdge(id);}
deba@2498: 
deba@2498:     int maxNodeId() const { return graph->maxNodeId(); };
deba@2498:     int maxEdgeId() const { return edges.size() - 1; }
deba@2498:     int maxUEdgeId() const { return edges.size() / 2 - 1; }
deba@2498: 
deba@2498:     Node source(Edge e) const { return edges[e.id ^ 1].target; }
deba@2498:     Node target(Edge e) const { return edges[e.id].target; }
deba@2498: 
deba@2498:     Node source(UEdge e) const { return edges[2 * e.id].target; }
deba@2498:     Node target(UEdge e) const { return edges[2 * e.id + 1].target; }
deba@2498: 
deba@2498:     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
deba@2498: 
deba@2498:     NodeNotifier& notifier(Node) const {
deba@2498:       return graph->notifier(Node());
deba@2498:     } 
deba@2498: 
deba@2498:     template <typename _Value>
deba@2498:     class NodeMap : public Graph::template NodeMap<_Value> {
deba@2498:     public:
deba@2498: 
deba@2498:       typedef typename _Graph::template NodeMap<_Value> Parent;
deba@2498: 
deba@2498:       explicit NodeMap(const SmartUEdgeSetBase<Graph>& edgeset) 
deba@2498: 	: Parent(*edgeset.graph) { }
deba@2498: 
deba@2498:       NodeMap(const SmartUEdgeSetBase<Graph>& edgeset, const _Value& value)
deba@2498: 	: Parent(*edgeset.graph, value) { }
deba@2498: 
deba@2498:       NodeMap& operator=(const NodeMap& cmap) {
deba@2498:         return operator=<NodeMap>(cmap);
deba@2498:       }
deba@2498: 
deba@2498:       template <typename CMap>
deba@2498:       NodeMap& operator=(const CMap& cmap) {
deba@2498:         Parent::operator=(cmap);
deba@2498:         return *this;
deba@2498:       }
deba@2498:     };
deba@2498: 
deba@2498:   };
deba@2498: 
deba@1962:   /// \ingroup semi_adaptors
deba@1962:   ///
deba@1962:   /// \brief Graph using a node set of another graph and an
deba@1962:   /// own uedge set.
deba@1962:   ///
deba@1962:   /// This structure can be used to establish another graph over a node set
deba@1962:   /// of an existing one. The node iterator will go through the nodes of the
deba@1962:   /// original graph.
deba@1962:   ///
deba@1962:   /// \param _Graph The type of the graph which shares its node set with 
alpar@2260:   /// this class. Its interface must conform to the \ref concepts::Graph
deba@2111:   /// "Graph" concept.
deba@1962:   ///
deba@1962:   /// In the edge extension and removing it conforms to the 
alpar@2260:   /// \ref concepts::UGraph "UGraph" concept.
deba@1962:   template <typename _Graph>
deba@2498:   class SmartUEdgeSet : public UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > {
deba@1962: 
deba@1962:   public:
deba@1962: 
deba@2498:     typedef UEdgeSetExtender<SmartUEdgeSetBase<_Graph> > Parent;
deba@1962:     
deba@1962:     typedef typename Parent::Node Node;
deba@1962:     typedef typename Parent::Edge Edge;
deba@1962:     
deba@1962:     typedef _Graph Graph;
deba@1962: 
deba@1962:   protected:
deba@1962: 
deba@1962:     typedef typename Parent::NodesImplBase NodesImplBase;
deba@1962: 
deba@1999:     void eraseNode(const Node& node) {
deba@2031:       if (typename Parent::IncEdgeIt(*this, node) == INVALID) {
deba@1999:         return;
deba@1999:       }
deba@2191:       throw typename NodesImplBase::Notifier::ImmediateDetach();
deba@1962:     }
deba@1962:     
deba@1962:     void clearNodes() {
deba@1962:       Parent::clear();
deba@1962:     }
deba@1962: 
deba@1962:     class NodesImpl : public NodesImplBase {
deba@1962:     public:
deba@1962:       typedef NodesImplBase Parent;
deba@1962:       
deba@1962:       NodesImpl(const Graph& graph, SmartUEdgeSet& edgeset) 
deba@1962: 	: Parent(graph), _edgeset(edgeset) {}
deba@1962: 
deba@1962:       virtual ~NodesImpl() {}
deba@2193: 
deba@2193:       bool attached() const {
deba@2193:         return Parent::attached();
deba@2193:       }
deba@1962:       
deba@1962:     protected:
deba@1962: 
deba@1962:       virtual void erase(const Node& node) {
deba@2191:         try {
deba@2191:           _edgeset.eraseNode(node);
deba@2191:           Parent::erase(node);
deba@2191:         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@2191:           Parent::clear();
deba@2192:           throw;
deba@2191:         }
deba@1962:       }
deba@1962:       virtual void erase(const std::vector<Node>& nodes) {
deba@2191:         try {
deba@2386:           for (int i = 0; i < int(nodes.size()); ++i) {
deba@2191:             _edgeset.eraseNode(nodes[i]);
deba@2191:           }
deba@2191:           Parent::erase(nodes);
deba@2191:         } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) {
deba@2191:           Parent::clear();
deba@2192:           throw;
deba@2191:         }
deba@1962:       }
deba@1962:       virtual void clear() {
deba@1962: 	_edgeset.clearNodes();
deba@1962: 	Parent::clear();
deba@1962:       }
deba@1962: 
deba@1962:     private:
deba@1962:       SmartUEdgeSet& _edgeset;
deba@1962:     };
deba@1962: 
deba@1962:     NodesImpl nodes;
deba@1962:     
deba@1962:   public:
deba@1962: 
deba@1962:     /// \brief Constructor of the adaptor.
deba@1962:     /// 
deba@1962:     /// Constructor of the adaptor.
deba@1962:     SmartUEdgeSet(const Graph& graph) : nodes(graph, *this) {
deba@1962:       Parent::initalize(graph, nodes);
deba@1962:     }
deba@2193: 
deba@2193:     bool valid() const {
deba@2193:       return nodes.attached();
deba@2193:     }
deba@1962:     
deba@1962:   };
deba@1962: 
deba@1842: }
deba@1842: 
deba@1842: #endif