deba@1842: /* -*- C++ -*- deba@1842: * 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 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@1962: #include deba@1962: #include deba@1962: #include deba@1962: #include deba@1962: #include deba@1962: #include deba@1962: #include deba@1962: deba@1842: /// \ingroup graphs 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 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@1842: typedef typename Graph::template NodeMap 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 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; 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@1842: Edge addEdge(const Node& source, const Node& target) { 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@1842: edges[n].next_in = (*nodes)[target].first_in; deba@1962: if ((*nodes)[target].first_in != -1) { deba@1962: edges[(*nodes)[target].first_in].prev_in = n; deba@1962: } deba@1842: (*nodes)[target].first_in = n; deba@1842: edges[n].next_out = (*nodes)[source].first_out; deba@1962: if ((*nodes)[source].first_out != -1) { deba@1962: edges[(*nodes)[source].first_out].prev_out = n; deba@1962: } deba@1842: (*nodes)[source].first_out = n; deba@1842: edges[n].source = source; deba@1842: edges[n].target = target; 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@1962: Node nodeFromId(int id) const { return graph->nodeFromId(id); } deba@1842: Edge edgeFromId(int id) const { return Edge(id); } 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@1842: template deba@1842: class NodeMap : public Graph::template NodeMap<_Value> { deba@1842: public: deba@1842: typedef typename _Graph::template NodeMap<_Value> Parent; deba@1842: explicit NodeMap(const ListEdgeSetBase& edgeset) deba@1842: : Parent(*edgeset.graph) { } deba@1842: NodeMap(const ListEdgeSetBase& edgeset, const _Value& value) deba@1842: : Parent(*edgeset.graph, value) { } 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 deba@1842: /// this class. Its interface must conform to the \ref concept::StaticGraph deba@1842: /// "StaticGraph" concept. deba@1842: /// deba@1842: /// In the edge extension and removing it conforms to the deba@1962: /// \ref concept::ErasableGraph "ErasableGraph" concept. deba@1842: template deba@1842: class ListEdgeSet : deba@1842: public ErasableEdgeSetExtender< deba@1842: ClearableEdgeSetExtender< deba@1842: ExtendableEdgeSetExtender< deba@1842: MappableEdgeSetExtender< deba@1842: IterableGraphExtender< deba@1842: AlterableEdgeSetExtender< deba@1842: GraphExtender< deba@1842: ListEdgeSetBase<_Graph> > > > > > > > { deba@1842: deba@1842: public: deba@1842: deba@1842: typedef ErasableEdgeSetExtender< deba@1842: ClearableEdgeSetExtender< deba@1842: ExtendableEdgeSetExtender< deba@1842: MappableEdgeSetExtender< deba@1842: IterableGraphExtender< deba@1842: AlterableEdgeSetExtender< deba@1842: GraphExtender< deba@1842: 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& nodes) { deba@1962: 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@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 deba@1842: /// this class. Its interface must conform to the \ref concept::StaticGraph deba@1842: /// "StaticGraph" concept. deba@1842: /// deba@1842: /// In the edge extension and removing it conforms to the deba@1962: /// \ref concept::ErasableUGraph "ErasableUGraph" concept. deba@1842: template klao@1909: class ListUEdgeSet : klao@1909: public ErasableUEdgeSetExtender< klao@1909: ClearableUEdgeSetExtender< klao@1909: ExtendableUEdgeSetExtender< klao@1909: MappableUEdgeSetExtender< klao@1909: IterableUGraphExtender< klao@1909: AlterableUEdgeSetExtender< klao@1909: UGraphExtender< deba@1842: ListEdgeSetBase<_Graph> > > > > > > > { deba@1842: deba@1842: public: deba@1842: klao@1909: typedef ErasableUEdgeSetExtender< klao@1909: ClearableUEdgeSetExtender< klao@1909: ExtendableUEdgeSetExtender< klao@1909: MappableUEdgeSetExtender< klao@1909: IterableUGraphExtender< klao@1909: AlterableUEdgeSetExtender< klao@1909: UGraphExtender< deba@1842: 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: } 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& nodes) { deba@1962: 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 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@1962: typedef typename Graph::template NodeMap 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 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; 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@1962: Edge addEdge(const Node& source, const Node& target) { deba@1962: int n = edges.size(); deba@1962: edges.push_back(EdgeT()); deba@1962: edges[n].next_in = (*nodes)[target].first_in; deba@1962: (*nodes)[target].first_in = n; deba@1962: edges[n].next_out = (*nodes)[source].first_out; deba@1962: (*nodes)[source].first_out = n; deba@1962: edges[n].source = source; deba@1962: edges[n].target = target; 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@1962: Node nodeFromId(int id) const { return graph->nodeFromId(id); } deba@1962: Edge edgeFromId(int id) const { return Edge(id); } 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@1962: template deba@1962: class NodeMap : public Graph::template NodeMap<_Value> { deba@1962: public: deba@1962: typedef typename _Graph::template NodeMap<_Value> Parent; deba@1962: explicit NodeMap(const SmartEdgeSetBase& edgeset) deba@1962: : Parent(*edgeset.graph) { } deba@1962: NodeMap(const SmartEdgeSetBase& edgeset, const _Value& value) deba@1962: : Parent(*edgeset.graph, value) { } 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 deba@1962: /// this class. Its interface must conform to the \ref concept::StaticGraph deba@1962: /// "StaticGraph" concept. deba@1962: /// deba@1962: /// In the edge extension and removing it conforms to the deba@1962: /// \ref concept::ExtendableGraph "ExtendableGraph" concept. deba@1962: template deba@1962: class SmartEdgeSet : deba@1962: public ClearableEdgeSetExtender< deba@1962: ExtendableEdgeSetExtender< deba@1962: MappableEdgeSetExtender< deba@1962: IterableGraphExtender< deba@1962: AlterableEdgeSetExtender< deba@1962: GraphExtender< deba@1962: SmartEdgeSetBase<_Graph> > > > > > > { deba@1962: deba@1962: public: deba@1962: deba@1962: typedef ClearableEdgeSetExtender< deba@1962: ExtendableEdgeSetExtender< deba@1962: MappableEdgeSetExtender< deba@1962: IterableGraphExtender< deba@1962: AlterableEdgeSetExtender< deba@1962: GraphExtender< deba@1962: 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: class UnsupportedOperation : public LogicError { deba@1962: public: deba@1962: virtual const char* exceptionName() const { deba@1962: return "lemon::SmartEdgeSet::UnsupportedOperation"; deba@1962: } deba@1962: }; deba@1962: deba@1962: deba@1962: deba@1962: protected: deba@1962: deba@1962: typedef typename Parent::NodesImplBase NodesImplBase; deba@1962: deba@1962: void eraseNode(const Node&) { deba@1962: throw UnsupportedOperation(); 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@1962: protected: deba@1962: deba@1962: virtual void erase(const Node& node) { deba@1962: _edgeset.eraseNode(node); deba@1962: Parent::erase(node); deba@1962: } deba@1962: virtual void erase(const std::vector& nodes) { deba@1962: 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@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@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 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 deba@1962: /// this class. Its interface must conform to the \ref concept::StaticGraph deba@1962: /// "StaticGraph" concept. deba@1962: /// deba@1962: /// In the edge extension and removing it conforms to the deba@1962: /// \ref concept::ExtendableUGraph "ExtendableUGraph" concept. deba@1962: template deba@1962: class SmartUEdgeSet : deba@1962: public ClearableUEdgeSetExtender< deba@1962: ExtendableUEdgeSetExtender< deba@1962: MappableUEdgeSetExtender< deba@1962: IterableUGraphExtender< deba@1962: AlterableUEdgeSetExtender< deba@1962: UGraphExtender< deba@1962: SmartEdgeSetBase<_Graph> > > > > > > { deba@1962: deba@1962: public: deba@1962: deba@1962: typedef ClearableUEdgeSetExtender< deba@1962: ExtendableUEdgeSetExtender< deba@1962: MappableUEdgeSetExtender< deba@1962: IterableUGraphExtender< deba@1962: AlterableUEdgeSetExtender< deba@1962: UGraphExtender< deba@1962: 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: class UnsupportedOperation : public LogicError { deba@1962: public: deba@1962: virtual const char* exceptionName() const { deba@1962: return "lemon::SmartUEdgeSet::UnsupportedOperation"; deba@1962: } deba@1962: }; deba@1962: deba@1962: protected: deba@1962: deba@1962: typedef typename Parent::NodesImplBase NodesImplBase; deba@1962: deba@1962: void eraseNode(const Node&) { deba@1962: throw UnsupportedOperation(); 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@1962: deba@1962: protected: deba@1962: deba@1962: virtual void erase(const Node& node) { deba@1962: _edgeset.eraseNode(node); deba@1962: Parent::erase(node); deba@1962: } deba@1962: virtual void erase(const std::vector& nodes) { deba@1962: 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@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@1962: deba@1962: }; deba@1962: deba@1842: } deba@1842: deba@1842: #endif