deba@1842: /* -*- C++ -*- deba@1842: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 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 deba@1979: #include 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 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 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@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::ItemNotifier NodeNotifier; deba@1990: deba@2384: NodeNotifier& notifier(Node) const { deba@2384: return graph->notifier(Node()); deba@1990: } deba@1990: deba@1842: template 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& edgeset) deba@2031: : Parent(*edgeset.graph) {} deba@2031: deba@1842: NodeMap(const ListEdgeSetBase& edgeset, const _Value& value) deba@2031: : Parent(*edgeset.graph, value) {} deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template 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 deba@1979: class ListEdgeSet : public EdgeSetExtender > { deba@1842: deba@1842: public: deba@1842: deba@1979: typedef EdgeSetExtender > 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@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 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 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 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::ItemNotifier NodeNotifier; deba@2498: deba@2498: NodeNotifier& notifier(Node) const { deba@2498: return graph->notifier(Node()); deba@2498: } deba@2498: deba@2498: template 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& edgeset) deba@2498: : Parent(*edgeset.graph) {} deba@2498: deba@2498: NodeMap(const ListUEdgeSetBase& edgeset, const _Value& value) deba@2498: : Parent(*edgeset.graph, value) {} deba@2498: deba@2498: NodeMap& operator=(const NodeMap& cmap) { deba@2498: return operator=(cmap); deba@2498: } deba@2498: deba@2498: template 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 deba@2498: class ListUEdgeSet : public UEdgeSetExtender > { deba@1842: deba@1842: public: deba@1842: deba@2498: typedef UEdgeSetExtender > 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@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 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 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@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::ItemNotifier NodeNotifier; deba@1990: deba@2384: NodeNotifier& notifier(Node) const { deba@2384: return graph->notifier(Node()); deba@1990: } deba@1990: deba@1962: template 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& edgeset) deba@1962: : Parent(*edgeset.graph) { } deba@2031: deba@1962: NodeMap(const SmartEdgeSetBase& edgeset, const _Value& value) deba@1962: : Parent(*edgeset.graph, value) { } deba@2031: deba@2031: NodeMap& operator=(const NodeMap& cmap) { deba@2031: return operator=(cmap); deba@2031: } deba@2031: deba@2031: template 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 deba@1979: class SmartEdgeSet : public EdgeSetExtender > { deba@1962: deba@1962: public: deba@1962: deba@1979: typedef EdgeSetExtender > 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& 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 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 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 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::ItemNotifier NodeNotifier; deba@2498: deba@2498: NodeNotifier& notifier(Node) const { deba@2498: return graph->notifier(Node()); deba@2498: } deba@2498: deba@2498: template 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& edgeset) deba@2498: : Parent(*edgeset.graph) { } deba@2498: deba@2498: NodeMap(const SmartUEdgeSetBase& edgeset, const _Value& value) deba@2498: : Parent(*edgeset.graph, value) { } deba@2498: deba@2498: NodeMap& operator=(const NodeMap& cmap) { deba@2498: return operator=(cmap); deba@2498: } deba@2498: deba@2498: template 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 deba@2498: class SmartUEdgeSet : public UEdgeSetExtender > { deba@1962: deba@1962: public: deba@1962: deba@2498: typedef UEdgeSetExtender > 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& 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