deba@468: /* -*- mode: C++; indent-tabs-mode: nil; -*- deba@468: * deba@468: * This file is a part of LEMON, a generic C++ optimization library. deba@468: * deba@468: * Copyright (C) 2003-2008 deba@468: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@468: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@468: * deba@468: * Permission to use, modify and distribute this software is granted deba@468: * provided that this copyright notice appears in all copies. For deba@468: * precise terms see the accompanying LICENSE file. deba@468: * deba@468: * This software is provided "AS IS" with no warranty of any kind, deba@468: * express or implied, and with no claim as to its suitability for any deba@468: * purpose. deba@468: * deba@468: */ deba@468: deba@468: #ifndef LEMON_EDGE_SET_H deba@468: #define LEMON_EDGE_SET_H deba@468: deba@468: #include deba@468: #include deba@468: deba@468: /// \ingroup semi_adaptors deba@468: /// \file deba@468: /// \brief ArcSet and EdgeSet classes. deba@468: /// deba@468: /// Graphs which use another graph's node-set as own. deba@468: namespace lemon { deba@468: deba@468: template deba@468: class ListArcSetBase { deba@468: public: deba@468: deba@468: typedef _Graph Graph; deba@468: typedef typename Graph::Node Node; deba@468: typedef typename Graph::NodeIt NodeIt; deba@468: deba@468: protected: deba@468: deba@468: struct NodeT { deba@468: int first_out, first_in; deba@468: NodeT() : first_out(-1), first_in(-1) {} deba@468: }; deba@468: deba@468: typedef typename ItemSetTraits:: deba@468: template Map::Type NodesImplBase; deba@468: deba@468: NodesImplBase* nodes; deba@468: deba@468: struct ArcT { deba@468: Node source, target; deba@468: int next_out, next_in; deba@468: int prev_out, prev_in; deba@468: ArcT() : prev_out(-1), prev_in(-1) {} deba@468: }; deba@468: deba@468: std::vector arcs; deba@468: deba@468: int first_arc; deba@468: int first_free_arc; deba@468: deba@468: const Graph* graph; deba@468: deba@468: void initalize(const Graph& _graph, NodesImplBase& _nodes) { deba@468: graph = &_graph; deba@468: nodes = &_nodes; deba@468: } deba@468: deba@468: public: deba@468: deba@468: class Arc { deba@468: friend class ListArcSetBase; deba@468: protected: deba@468: Arc(int _id) : id(_id) {} deba@468: int id; deba@468: public: deba@468: Arc() {} deba@468: Arc(Invalid) : id(-1) {} deba@468: bool operator==(const Arc& arc) const { return id == arc.id; } deba@468: bool operator!=(const Arc& arc) const { return id != arc.id; } deba@468: bool operator<(const Arc& arc) const { return id < arc.id; } deba@468: }; deba@468: deba@468: ListArcSetBase() : first_arc(-1), first_free_arc(-1) {} deba@468: deba@468: Arc addArc(const Node& u, const Node& v) { deba@468: int n; deba@468: if (first_free_arc == -1) { deba@468: n = arcs.size(); deba@468: arcs.push_back(ArcT()); deba@468: } else { deba@468: n = first_free_arc; deba@468: first_free_arc = arcs[first_free_arc].next_in; deba@468: } deba@468: arcs[n].next_in = (*nodes)[v].first_in; deba@468: if ((*nodes)[v].first_in != -1) { deba@468: arcs[(*nodes)[v].first_in].prev_in = n; deba@468: } deba@468: (*nodes)[v].first_in = n; deba@468: arcs[n].next_out = (*nodes)[u].first_out; deba@468: if ((*nodes)[u].first_out != -1) { deba@468: arcs[(*nodes)[u].first_out].prev_out = n; deba@468: } deba@468: (*nodes)[u].first_out = n; deba@468: arcs[n].source = u; deba@468: arcs[n].target = v; deba@468: return Arc(n); deba@468: } deba@468: deba@468: void erase(const Arc& arc) { deba@468: int n = arc.id; deba@468: if (arcs[n].prev_in != -1) { deba@468: arcs[arcs[n].prev_in].next_in = arcs[n].next_in; deba@468: } else { deba@468: (*nodes)[arcs[n].target].first_in = arcs[n].next_in; deba@468: } deba@468: if (arcs[n].next_in != -1) { deba@468: arcs[arcs[n].next_in].prev_in = arcs[n].prev_in; deba@468: } deba@468: deba@468: if (arcs[n].prev_out != -1) { deba@468: arcs[arcs[n].prev_out].next_out = arcs[n].next_out; deba@468: } else { deba@468: (*nodes)[arcs[n].source].first_out = arcs[n].next_out; deba@468: } deba@468: if (arcs[n].next_out != -1) { deba@468: arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; deba@468: } deba@468: deba@468: } deba@468: deba@468: void clear() { deba@468: Node node; deba@468: for (first(node); node != INVALID; next(node)) { deba@468: (*nodes)[node].first_in = -1; deba@468: (*nodes)[node].first_out = -1; deba@468: } deba@468: arcs.clear(); deba@468: first_arc = -1; deba@468: first_free_arc = -1; deba@468: } deba@468: deba@468: void first(Node& node) const { deba@468: graph->first(node); deba@468: } deba@468: deba@468: void next(Node& node) const { deba@468: graph->next(node); deba@468: } deba@468: deba@468: void first(Arc& arc) const { deba@468: Node node; deba@468: first(node); deba@468: while (node != INVALID && (*nodes)[node].first_in == -1) { deba@468: next(node); deba@468: } deba@468: arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in; deba@468: } deba@468: deba@468: void next(Arc& arc) const { deba@468: if (arcs[arc.id].next_in != -1) { deba@468: arc.id = arcs[arc.id].next_in; deba@468: } else { deba@468: Node node = arcs[arc.id].target; deba@468: next(node); deba@468: while (node != INVALID && (*nodes)[node].first_in == -1) { deba@468: next(node); deba@468: } deba@468: arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in; deba@468: } deba@468: } deba@468: deba@468: void firstOut(Arc& arc, const Node& node) const { deba@468: arc.id = (*nodes)[node].first_out; deba@468: } deba@468: deba@468: void nextOut(Arc& arc) const { deba@468: arc.id = arcs[arc.id].next_out; deba@468: } deba@468: deba@468: void firstIn(Arc& arc, const Node& node) const { deba@468: arc.id = (*nodes)[node].first_in; deba@468: } deba@468: deba@468: void nextIn(Arc& arc) const { deba@468: arc.id = arcs[arc.id].next_in; deba@468: } deba@468: deba@468: int id(const Node& node) const { return graph->id(node); } deba@468: int id(const Arc& arc) const { return arc.id; } deba@468: deba@468: Node nodeFromId(int ix) const { return graph->nodeFromId(ix); } deba@468: Arc arcFromId(int ix) const { return Arc(ix); } deba@468: deba@468: int maxNodeId() const { return graph->maxNodeId(); }; deba@468: int maxArcId() const { return arcs.size() - 1; } deba@468: deba@468: Node source(const Arc& arc) const { return arcs[arc.id].source;} deba@468: Node target(const Arc& arc) const { return arcs[arc.id].target;} deba@468: deba@468: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@468: deba@468: NodeNotifier& notifier(Node) const { deba@468: return graph->notifier(Node()); deba@468: } deba@468: deba@468: template deba@468: class NodeMap : public Graph::template NodeMap<_Value> { deba@468: public: deba@468: deba@468: typedef typename _Graph::template NodeMap<_Value> Parent; deba@468: deba@468: explicit NodeMap(const ListArcSetBase& arcset) deba@468: : Parent(*arcset.graph) {} deba@468: deba@468: NodeMap(const ListArcSetBase& arcset, const _Value& value) deba@468: : Parent(*arcset.graph, value) {} deba@468: deba@468: NodeMap& operator=(const NodeMap& cmap) { deba@468: return operator=(cmap); deba@468: } deba@468: deba@468: template deba@468: NodeMap& operator=(const CMap& cmap) { deba@468: Parent::operator=(cmap); deba@468: return *this; deba@468: } deba@468: }; deba@468: deba@468: }; deba@468: deba@468: /// \ingroup semi_adaptors deba@468: /// deba@468: /// \brief Digraph using a node set of another digraph or graph and deba@468: /// an own arc set. deba@468: /// deba@468: /// This structure can be used to establish another directed graph deba@468: /// over a node set of an existing one. This class uses the same deba@468: /// Node type as the underlying graph, and each valid node of the deba@468: /// original graph is valid in this arc set, therefore the node deba@468: /// objects of the original graph can be used directly with this deba@468: /// class. The node handling functions (id handling, observing, and deba@468: /// iterators) works equivalently as in the original graph. deba@468: /// deba@468: /// This implementation is based on doubly-linked lists, from each deba@468: /// node the outgoing and the incoming arcs make up lists, therefore deba@468: /// one arc can be erased in constant time. It also makes possible, deba@468: /// that node can be removed from the underlying graph, in this case deba@468: /// all arcs incident to the given node is erased from the arc set. deba@468: /// deba@468: /// \param _Graph The type of the graph which shares its node set with deba@468: /// this class. Its interface must conform to the deba@468: /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" deba@468: /// concept. deba@468: /// deba@468: /// This class is fully conform to the \ref concepts::Digraph deba@468: /// "Digraph" concept. deba@468: template deba@468: class ListArcSet : public ArcSetExtender > { deba@468: deba@468: public: deba@468: deba@468: typedef ArcSetExtender > Parent; deba@468: deba@468: typedef typename Parent::Node Node; deba@468: typedef typename Parent::Arc Arc; deba@468: deba@468: typedef _Graph Graph; deba@468: deba@468: deba@468: typedef typename Parent::NodesImplBase NodesImplBase; deba@468: deba@468: void eraseNode(const Node& node) { deba@468: Arc arc; deba@468: Parent::firstOut(arc, node); deba@468: while (arc != INVALID ) { deba@468: erase(arc); deba@468: Parent::firstOut(arc, node); deba@468: } deba@468: deba@468: Parent::firstIn(arc, node); deba@468: while (arc != INVALID ) { deba@468: erase(arc); deba@468: Parent::firstIn(arc, node); deba@468: } deba@468: } deba@468: deba@468: void clearNodes() { deba@468: Parent::clear(); deba@468: } deba@468: deba@468: class NodesImpl : public NodesImplBase { deba@468: public: deba@468: typedef NodesImplBase Parent; deba@468: deba@468: NodesImpl(const Graph& graph, ListArcSet& arcset) deba@468: : Parent(graph), _arcset(arcset) {} deba@468: deba@468: virtual ~NodesImpl() {} deba@468: deba@468: protected: deba@468: deba@468: virtual void erase(const Node& node) { deba@468: _arcset.eraseNode(node); deba@468: Parent::erase(node); deba@468: } deba@468: virtual void erase(const std::vector& nodes) { deba@468: for (int i = 0; i < int(nodes.size()); ++i) { deba@468: _arcset.eraseNode(nodes[i]); deba@468: } deba@468: Parent::erase(nodes); deba@468: } deba@468: virtual void clear() { deba@468: _arcset.clearNodes(); deba@468: Parent::clear(); deba@468: } deba@468: deba@468: private: deba@468: ListArcSet& _arcset; deba@468: }; deba@468: deba@468: NodesImpl nodes; deba@468: deba@468: public: deba@468: deba@468: /// \brief Constructor of the ArcSet. deba@468: /// deba@468: /// Constructor of the ArcSet. deba@468: ListArcSet(const Graph& graph) : nodes(graph, *this) { deba@468: Parent::initalize(graph, nodes); deba@468: } deba@468: deba@468: /// \brief Add a new arc to the digraph. deba@468: /// deba@468: /// Add a new arc to the digraph with source node \c s deba@468: /// and target node \c t. deba@468: /// \return the new arc. deba@468: Arc addArc(const Node& s, const Node& t) { deba@468: return Parent::addArc(s, t); deba@468: } deba@468: deba@468: /// \brief Erase an arc from the digraph. deba@468: /// deba@468: /// Erase an arc \c a from the digraph. deba@468: void erase(const Arc& a) { deba@468: return Parent::erase(a); deba@468: } deba@468: deba@468: }; deba@468: deba@468: template deba@468: class ListEdgeSetBase { deba@468: public: deba@468: deba@468: typedef _Graph Graph; deba@468: typedef typename Graph::Node Node; deba@468: typedef typename Graph::NodeIt NodeIt; deba@468: deba@468: protected: deba@468: deba@468: struct NodeT { deba@468: int first_out; deba@468: NodeT() : first_out(-1) {} deba@468: }; deba@468: deba@468: typedef typename ItemSetTraits:: deba@468: template Map::Type NodesImplBase; deba@468: deba@468: NodesImplBase* nodes; deba@468: deba@468: struct ArcT { deba@468: Node target; deba@468: int prev_out, next_out; deba@468: ArcT() : prev_out(-1), next_out(-1) {} deba@468: }; deba@468: deba@468: std::vector arcs; deba@468: deba@468: int first_arc; deba@468: int first_free_arc; deba@468: deba@468: const Graph* graph; deba@468: deba@468: void initalize(const Graph& _graph, NodesImplBase& _nodes) { deba@468: graph = &_graph; deba@468: nodes = &_nodes; deba@468: } deba@468: deba@468: public: deba@468: deba@468: class Edge { deba@468: friend class ListEdgeSetBase; deba@468: protected: deba@468: deba@468: int id; deba@468: explicit Edge(int _id) { id = _id;} deba@468: deba@468: public: deba@468: Edge() {} deba@468: Edge (Invalid) { id = -1; } deba@468: bool operator==(const Edge& arc) const {return id == arc.id;} deba@468: bool operator!=(const Edge& arc) const {return id != arc.id;} deba@468: bool operator<(const Edge& arc) const {return id < arc.id;} deba@468: }; deba@468: deba@468: class Arc { deba@468: friend class ListEdgeSetBase; deba@468: protected: deba@468: Arc(int _id) : id(_id) {} deba@468: int id; deba@468: public: deba@468: operator Edge() const { return edgeFromId(id / 2); } deba@468: deba@468: Arc() {} deba@468: Arc(Invalid) : id(-1) {} deba@468: bool operator==(const Arc& arc) const { return id == arc.id; } deba@468: bool operator!=(const Arc& arc) const { return id != arc.id; } deba@468: bool operator<(const Arc& arc) const { return id < arc.id; } deba@468: }; deba@468: deba@468: ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {} deba@468: deba@468: Edge addEdge(const Node& u, const Node& v) { deba@468: int n; deba@468: deba@468: if (first_free_arc == -1) { deba@468: n = arcs.size(); deba@468: arcs.push_back(ArcT()); deba@468: arcs.push_back(ArcT()); deba@468: } else { deba@468: n = first_free_arc; deba@468: first_free_arc = arcs[n].next_out; deba@468: } deba@468: deba@468: arcs[n].target = u; deba@468: arcs[n | 1].target = v; deba@468: deba@468: arcs[n].next_out = (*nodes)[v].first_out; deba@468: if ((*nodes)[v].first_out != -1) { deba@468: arcs[(*nodes)[v].first_out].prev_out = n; deba@468: } deba@468: (*nodes)[v].first_out = n; deba@468: arcs[n].prev_out = -1; deba@468: deba@468: if ((*nodes)[u].first_out != -1) { deba@468: arcs[(*nodes)[u].first_out].prev_out = (n | 1); deba@468: } deba@468: arcs[n | 1].next_out = (*nodes)[u].first_out; deba@468: (*nodes)[u].first_out = (n | 1); deba@468: arcs[n | 1].prev_out = -1; deba@468: deba@468: return Edge(n / 2); deba@468: } deba@468: deba@468: void erase(const Edge& arc) { deba@468: int n = arc.id * 2; deba@468: deba@468: if (arcs[n].next_out != -1) { deba@468: arcs[arcs[n].next_out].prev_out = arcs[n].prev_out; deba@468: } deba@468: deba@468: if (arcs[n].prev_out != -1) { deba@468: arcs[arcs[n].prev_out].next_out = arcs[n].next_out; deba@468: } else { deba@468: (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out; deba@468: } deba@468: deba@468: if (arcs[n | 1].next_out != -1) { deba@468: arcs[arcs[n | 1].next_out].prev_out = arcs[n | 1].prev_out; deba@468: } deba@468: deba@468: if (arcs[n | 1].prev_out != -1) { deba@468: arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out; deba@468: } else { deba@468: (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out; deba@468: } deba@468: deba@468: arcs[n].next_out = first_free_arc; deba@468: first_free_arc = n; deba@468: deba@468: } deba@468: deba@468: void clear() { deba@468: Node node; deba@468: for (first(node); node != INVALID; next(node)) { deba@468: (*nodes)[node].first_out = -1; deba@468: } deba@468: arcs.clear(); deba@468: first_arc = -1; deba@468: first_free_arc = -1; deba@468: } deba@468: deba@468: void first(Node& node) const { deba@468: graph->first(node); deba@468: } deba@468: deba@468: void next(Node& node) const { deba@468: graph->next(node); deba@468: } deba@468: deba@468: void first(Arc& arc) const { deba@468: Node node; deba@468: first(node); deba@468: while (node != INVALID && (*nodes)[node].first_out == -1) { deba@468: next(node); deba@468: } deba@468: arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out; deba@468: } deba@468: deba@468: void next(Arc& arc) const { deba@468: if (arcs[arc.id].next_out != -1) { deba@468: arc.id = arcs[arc.id].next_out; deba@468: } else { deba@468: Node node = arcs[arc.id ^ 1].target; deba@468: next(node); deba@468: while(node != INVALID && (*nodes)[node].first_out == -1) { deba@468: next(node); deba@468: } deba@468: arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out; deba@468: } deba@468: } deba@468: deba@468: void first(Edge& edge) const { deba@468: Node node; deba@468: first(node); deba@468: while (node != INVALID) { deba@468: edge.id = (*nodes)[node].first_out; deba@468: while ((edge.id & 1) != 1) { deba@468: edge.id = arcs[edge.id].next_out; deba@468: } deba@468: if (edge.id != -1) { deba@468: edge.id /= 2; deba@468: return; deba@468: } deba@468: next(node); deba@468: } deba@468: edge.id = -1; deba@468: } deba@468: deba@468: void next(Edge& edge) const { deba@468: Node node = arcs[edge.id * 2].target; deba@468: edge.id = arcs[(edge.id * 2) | 1].next_out; deba@468: while ((edge.id & 1) != 1) { deba@468: edge.id = arcs[edge.id].next_out; deba@468: } deba@468: if (edge.id != -1) { deba@468: edge.id /= 2; deba@468: return; deba@468: } deba@468: next(node); deba@468: while (node != INVALID) { deba@468: edge.id = (*nodes)[node].first_out; deba@468: while ((edge.id & 1) != 1) { deba@468: edge.id = arcs[edge.id].next_out; deba@468: } deba@468: if (edge.id != -1) { deba@468: edge.id /= 2; deba@468: return; deba@468: } deba@468: next(node); deba@468: } deba@468: edge.id = -1; deba@468: } deba@468: deba@468: void firstOut(Arc& arc, const Node& node) const { deba@468: arc.id = (*nodes)[node].first_out; deba@468: } deba@468: deba@468: void nextOut(Arc& arc) const { deba@468: arc.id = arcs[arc.id].next_out; deba@468: } deba@468: deba@468: void firstIn(Arc& arc, const Node& node) const { deba@468: arc.id = (((*nodes)[node].first_out) ^ 1); deba@468: if (arc.id == -2) arc.id = -1; deba@468: } deba@468: deba@468: void nextIn(Arc& arc) const { deba@468: arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1); deba@468: if (arc.id == -2) arc.id = -1; deba@468: } deba@468: deba@468: void firstInc(Edge &arc, bool& dir, const Node& node) const { deba@468: int de = (*nodes)[node].first_out; deba@468: if (de != -1 ) { deba@468: arc.id = de / 2; deba@468: dir = ((de & 1) == 1); deba@468: } else { deba@468: arc.id = -1; deba@468: dir = true; deba@468: } deba@468: } deba@468: void nextInc(Edge &arc, bool& dir) const { deba@468: int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out); deba@468: if (de != -1 ) { deba@468: arc.id = de / 2; deba@468: dir = ((de & 1) == 1); deba@468: } else { deba@468: arc.id = -1; deba@468: dir = true; deba@468: } deba@468: } deba@468: deba@468: static bool direction(Arc arc) { deba@468: return (arc.id & 1) == 1; deba@468: } deba@468: deba@468: static Arc direct(Edge edge, bool dir) { deba@468: return Arc(edge.id * 2 + (dir ? 1 : 0)); deba@468: } deba@468: deba@468: int id(const Node& node) const { return graph->id(node); } deba@468: static int id(Arc e) { return e.id; } deba@468: static int id(Edge e) { return e.id; } deba@468: deba@468: Node nodeFromId(int id) const { return graph->nodeFromId(id); } deba@468: static Arc arcFromId(int id) { return Arc(id);} deba@468: static Edge edgeFromId(int id) { return Edge(id);} deba@468: deba@468: int maxNodeId() const { return graph->maxNodeId(); }; deba@468: int maxEdgeId() const { return arcs.size() / 2 - 1; } deba@468: int maxArcId() const { return arcs.size()-1; } deba@468: deba@468: Node source(Arc e) const { return arcs[e.id ^ 1].target; } deba@468: Node target(Arc e) const { return arcs[e.id].target; } deba@468: deba@468: Node u(Edge e) const { return arcs[2 * e.id].target; } deba@468: Node v(Edge e) const { return arcs[2 * e.id + 1].target; } deba@468: deba@468: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@468: deba@468: NodeNotifier& notifier(Node) const { deba@468: return graph->notifier(Node()); deba@468: } deba@468: deba@468: template deba@468: class NodeMap : public Graph::template NodeMap<_Value> { deba@468: public: deba@468: deba@468: typedef typename _Graph::template NodeMap<_Value> Parent; deba@468: deba@468: explicit NodeMap(const ListEdgeSetBase& arcset) deba@468: : Parent(*arcset.graph) {} deba@468: deba@468: NodeMap(const ListEdgeSetBase& arcset, const _Value& value) deba@468: : Parent(*arcset.graph, value) {} deba@468: deba@468: NodeMap& operator=(const NodeMap& cmap) { deba@468: return operator=(cmap); deba@468: } deba@468: deba@468: template deba@468: NodeMap& operator=(const CMap& cmap) { deba@468: Parent::operator=(cmap); deba@468: return *this; deba@468: } deba@468: }; deba@468: deba@468: }; deba@468: deba@468: /// \ingroup semi_adaptors deba@468: /// deba@468: /// \brief Graph using a node set of another digraph or graph and an deba@468: /// own edge set. deba@468: /// deba@468: /// This structure can be used to establish another graph over a deba@468: /// node set of an existing one. This class uses the same Node type deba@468: /// as the underlying graph, and each valid node of the original deba@468: /// graph is valid in this arc set, therefore the node objects of deba@468: /// the original graph can be used directly with this class. The deba@468: /// node handling functions (id handling, observing, and iterators) deba@468: /// works equivalently as in the original graph. deba@468: /// deba@468: /// This implementation is based on doubly-linked lists, from each deba@468: /// node the incident edges make up lists, therefore one edge can be deba@468: /// erased in constant time. It also makes possible, that node can deba@468: /// be removed from the underlying graph, in this case all edges deba@468: /// incident to the given node is erased from the arc set. deba@468: /// deba@468: /// \param _Graph The type of the graph which shares its node set deba@468: /// with this class. Its interface must conform to the deba@468: /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" deba@468: /// concept. deba@468: /// deba@468: /// This class is fully conform to the \ref concepts::Graph "Graph" deba@468: /// concept. deba@468: template deba@468: class ListEdgeSet : public EdgeSetExtender > { deba@468: deba@468: public: deba@468: deba@468: typedef EdgeSetExtender > Parent; deba@468: deba@468: typedef typename Parent::Node Node; deba@468: typedef typename Parent::Arc Arc; deba@468: typedef typename Parent::Edge Edge; deba@468: deba@468: typedef _Graph Graph; deba@468: deba@468: deba@468: typedef typename Parent::NodesImplBase NodesImplBase; deba@468: deba@468: void eraseNode(const Node& node) { deba@468: Arc arc; deba@468: Parent::firstOut(arc, node); deba@468: while (arc != INVALID ) { deba@468: erase(arc); deba@468: Parent::firstOut(arc, node); deba@468: } deba@468: deba@468: } deba@468: deba@468: void clearNodes() { deba@468: Parent::clear(); deba@468: } deba@468: deba@468: class NodesImpl : public NodesImplBase { deba@468: public: deba@468: typedef NodesImplBase Parent; deba@468: deba@468: NodesImpl(const Graph& graph, ListEdgeSet& arcset) deba@468: : Parent(graph), _arcset(arcset) {} deba@468: deba@468: virtual ~NodesImpl() {} deba@468: deba@468: protected: deba@468: deba@468: virtual void erase(const Node& node) { deba@468: _arcset.eraseNode(node); deba@468: Parent::erase(node); deba@468: } deba@468: virtual void erase(const std::vector& nodes) { deba@468: for (int i = 0; i < int(nodes.size()); ++i) { deba@468: _arcset.eraseNode(nodes[i]); deba@468: } deba@468: Parent::erase(nodes); deba@468: } deba@468: virtual void clear() { deba@468: _arcset.clearNodes(); deba@468: Parent::clear(); deba@468: } deba@468: deba@468: private: deba@468: ListEdgeSet& _arcset; deba@468: }; deba@468: deba@468: NodesImpl nodes; deba@468: deba@468: public: deba@468: deba@468: /// \brief Constructor of the EdgeSet. deba@468: /// deba@468: /// Constructor of the EdgeSet. deba@468: ListEdgeSet(const Graph& graph) : nodes(graph, *this) { deba@468: Parent::initalize(graph, nodes); deba@468: } deba@468: deba@468: /// \brief Add a new edge to the graph. deba@468: /// deba@468: /// Add a new edge to the graph with node \c u deba@468: /// and node \c v endpoints. deba@468: /// \return the new edge. deba@468: Edge addEdge(const Node& u, const Node& v) { deba@468: return Parent::addEdge(u, v); deba@468: } deba@468: deba@468: /// \brief Erase an edge from the graph. deba@468: /// deba@468: /// Erase the edge \c e from the graph. deba@468: void erase(const Edge& e) { deba@468: return Parent::erase(e); deba@468: } deba@468: deba@468: }; deba@468: deba@468: template deba@468: class SmartArcSetBase { deba@468: public: deba@468: deba@468: typedef _Graph Graph; deba@468: typedef typename Graph::Node Node; deba@468: typedef typename Graph::NodeIt NodeIt; deba@468: deba@468: protected: deba@468: deba@468: struct NodeT { deba@468: int first_out, first_in; deba@468: NodeT() : first_out(-1), first_in(-1) {} deba@468: }; deba@468: deba@468: typedef typename ItemSetTraits:: deba@468: template Map::Type NodesImplBase; deba@468: deba@468: NodesImplBase* nodes; deba@468: deba@468: struct ArcT { deba@468: Node source, target; deba@468: int next_out, next_in; deba@468: ArcT() {} deba@468: }; deba@468: deba@468: std::vector arcs; deba@468: deba@468: const Graph* graph; deba@468: deba@468: void initalize(const Graph& _graph, NodesImplBase& _nodes) { deba@468: graph = &_graph; deba@468: nodes = &_nodes; deba@468: } deba@468: deba@468: public: deba@468: deba@468: class Arc { deba@468: friend class SmartArcSetBase; deba@468: protected: deba@468: Arc(int _id) : id(_id) {} deba@468: int id; deba@468: public: deba@468: Arc() {} deba@468: Arc(Invalid) : id(-1) {} deba@468: bool operator==(const Arc& arc) const { return id == arc.id; } deba@468: bool operator!=(const Arc& arc) const { return id != arc.id; } deba@468: bool operator<(const Arc& arc) const { return id < arc.id; } deba@468: }; deba@468: deba@468: SmartArcSetBase() {} deba@468: deba@468: Arc addArc(const Node& u, const Node& v) { deba@468: int n = arcs.size(); deba@468: arcs.push_back(ArcT()); deba@468: arcs[n].next_in = (*nodes)[v].first_in; deba@468: (*nodes)[v].first_in = n; deba@468: arcs[n].next_out = (*nodes)[u].first_out; deba@468: (*nodes)[u].first_out = n; deba@468: arcs[n].source = u; deba@468: arcs[n].target = v; deba@468: return Arc(n); deba@468: } deba@468: deba@468: void clear() { deba@468: Node node; deba@468: for (first(node); node != INVALID; next(node)) { deba@468: (*nodes)[node].first_in = -1; deba@468: (*nodes)[node].first_out = -1; deba@468: } deba@468: arcs.clear(); deba@468: } deba@468: deba@468: void first(Node& node) const { deba@468: graph->first(node); deba@468: } deba@468: deba@468: void next(Node& node) const { deba@468: graph->next(node); deba@468: } deba@468: deba@468: void first(Arc& arc) const { deba@468: arc.id = arcs.size() - 1; deba@468: } deba@468: deba@468: void next(Arc& arc) const { deba@468: --arc.id; deba@468: } deba@468: deba@468: void firstOut(Arc& arc, const Node& node) const { deba@468: arc.id = (*nodes)[node].first_out; deba@468: } deba@468: deba@468: void nextOut(Arc& arc) const { deba@468: arc.id = arcs[arc.id].next_out; deba@468: } deba@468: deba@468: void firstIn(Arc& arc, const Node& node) const { deba@468: arc.id = (*nodes)[node].first_in; deba@468: } deba@468: deba@468: void nextIn(Arc& arc) const { deba@468: arc.id = arcs[arc.id].next_in; deba@468: } deba@468: deba@468: int id(const Node& node) const { return graph->id(node); } deba@468: int id(const Arc& arc) const { return arc.id; } deba@468: deba@468: Node nodeFromId(int ix) const { return graph->nodeFromId(ix); } deba@468: Arc arcFromId(int ix) const { return Arc(ix); } deba@468: deba@468: int maxNodeId() const { return graph->maxNodeId(); }; deba@468: int maxArcId() const { return arcs.size() - 1; } deba@468: deba@468: Node source(const Arc& arc) const { return arcs[arc.id].source;} deba@468: Node target(const Arc& arc) const { return arcs[arc.id].target;} deba@468: deba@468: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@468: deba@468: NodeNotifier& notifier(Node) const { deba@468: return graph->notifier(Node()); deba@468: } deba@468: deba@468: template deba@468: class NodeMap : public Graph::template NodeMap<_Value> { deba@468: public: deba@468: deba@468: typedef typename _Graph::template NodeMap<_Value> Parent; deba@468: deba@468: explicit NodeMap(const SmartArcSetBase& arcset) deba@468: : Parent(*arcset.graph) { } deba@468: deba@468: NodeMap(const SmartArcSetBase& arcset, const _Value& value) deba@468: : Parent(*arcset.graph, value) { } deba@468: deba@468: NodeMap& operator=(const NodeMap& cmap) { deba@468: return operator=(cmap); deba@468: } deba@468: deba@468: template deba@468: NodeMap& operator=(const CMap& cmap) { deba@468: Parent::operator=(cmap); deba@468: return *this; deba@468: } deba@468: }; deba@468: deba@468: }; deba@468: deba@468: deba@468: /// \ingroup semi_adaptors deba@468: /// deba@468: /// \brief Digraph using a node set of another digraph or graph and deba@468: /// an own arc set. deba@468: /// deba@468: /// This structure can be used to establish another directed graph deba@468: /// over a node set of an existing one. This class uses the same deba@468: /// Node type as the underlying graph, and each valid node of the deba@468: /// original graph is valid in this arc set, therefore the node deba@468: /// objects of the original graph can be used directly with this deba@468: /// class. The node handling functions (id handling, observing, and deba@468: /// iterators) works equivalently as in the original graph. deba@468: /// deba@468: /// \param _Graph The type of the graph which shares its node set with deba@468: /// this class. Its interface must conform to the deba@468: /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" deba@468: /// concept. deba@468: /// deba@468: /// This implementation is slightly faster than the \c ListArcSet, deba@468: /// because it uses continuous storage for arcs and it uses just deba@468: /// single-linked lists for enumerate outgoing and incoming deba@468: /// arcs. Therefore the arcs cannot be erased from the arc sets. deba@468: /// deba@468: /// \warning If a node is erased from the underlying graph and this deba@468: /// node is the source or target of one arc in the arc set, then deba@468: /// the arc set is invalidated, and it cannot be used anymore. The deba@468: /// validity can be checked with the \c valid() member function. deba@468: /// deba@468: /// This class is fully conform to the \ref concepts::Digraph deba@468: /// "Digraph" concept. deba@468: template deba@468: class SmartArcSet : public ArcSetExtender > { deba@468: deba@468: public: deba@468: deba@468: typedef ArcSetExtender > Parent; deba@468: deba@468: typedef typename Parent::Node Node; deba@468: typedef typename Parent::Arc Arc; deba@468: deba@468: typedef _Graph Graph; deba@468: deba@468: protected: deba@468: deba@468: typedef typename Parent::NodesImplBase NodesImplBase; deba@468: deba@468: void eraseNode(const Node& node) { deba@468: if (typename Parent::InArcIt(*this, node) == INVALID && deba@468: typename Parent::OutArcIt(*this, node) == INVALID) { deba@468: return; deba@468: } deba@468: throw typename NodesImplBase::Notifier::ImmediateDetach(); deba@468: } deba@468: deba@468: void clearNodes() { deba@468: Parent::clear(); deba@468: } deba@468: deba@468: class NodesImpl : public NodesImplBase { deba@468: public: deba@468: typedef NodesImplBase Parent; deba@468: deba@468: NodesImpl(const Graph& graph, SmartArcSet& arcset) deba@468: : Parent(graph), _arcset(arcset) {} deba@468: deba@468: virtual ~NodesImpl() {} deba@468: deba@468: bool attached() const { deba@468: return Parent::attached(); deba@468: } deba@468: deba@468: protected: deba@468: deba@468: virtual void erase(const Node& node) { deba@468: try { deba@468: _arcset.eraseNode(node); deba@468: Parent::erase(node); deba@468: } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { deba@468: Parent::clear(); deba@468: throw; deba@468: } deba@468: } deba@468: virtual void erase(const std::vector& nodes) { deba@468: try { deba@468: for (int i = 0; i < int(nodes.size()); ++i) { deba@468: _arcset.eraseNode(nodes[i]); deba@468: } deba@468: Parent::erase(nodes); deba@468: } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { deba@468: Parent::clear(); deba@468: throw; deba@468: } deba@468: } deba@468: virtual void clear() { deba@468: _arcset.clearNodes(); deba@468: Parent::clear(); deba@468: } deba@468: deba@468: private: deba@468: SmartArcSet& _arcset; deba@468: }; deba@468: deba@468: NodesImpl nodes; deba@468: deba@468: public: deba@468: deba@468: /// \brief Constructor of the ArcSet. deba@468: /// deba@468: /// Constructor of the ArcSet. deba@468: SmartArcSet(const Graph& graph) : nodes(graph, *this) { deba@468: Parent::initalize(graph, nodes); deba@468: } deba@468: deba@468: /// \brief Add a new arc to the digraph. deba@468: /// deba@468: /// Add a new arc to the digraph with source node \c s deba@468: /// and target node \c t. deba@468: /// \return the new arc. deba@468: Arc addArc(const Node& s, const Node& t) { deba@468: return Parent::addArc(s, t); deba@468: } deba@468: deba@468: /// \brief Validity check deba@468: /// deba@468: /// This functions gives back false if the ArcSet is deba@468: /// invalidated. It occurs when a node in the underlying graph is deba@468: /// erased and it is not isolated in the ArcSet. deba@468: bool valid() const { deba@468: return nodes.attached(); deba@468: } deba@468: deba@468: }; deba@468: deba@468: deba@468: template deba@468: class SmartEdgeSetBase { deba@468: public: deba@468: deba@468: typedef _Graph Graph; deba@468: typedef typename Graph::Node Node; deba@468: typedef typename Graph::NodeIt NodeIt; deba@468: deba@468: protected: deba@468: deba@468: struct NodeT { deba@468: int first_out; deba@468: NodeT() : first_out(-1) {} deba@468: }; deba@468: deba@468: typedef typename ItemSetTraits:: deba@468: template Map::Type NodesImplBase; deba@468: deba@468: NodesImplBase* nodes; deba@468: deba@468: struct ArcT { deba@468: Node target; deba@468: int next_out; deba@468: ArcT() {} deba@468: }; deba@468: deba@468: std::vector arcs; deba@468: deba@468: const Graph* graph; deba@468: deba@468: void initalize(const Graph& _graph, NodesImplBase& _nodes) { deba@468: graph = &_graph; deba@468: nodes = &_nodes; deba@468: } deba@468: deba@468: public: deba@468: deba@468: class Edge { deba@468: friend class SmartEdgeSetBase; deba@468: protected: deba@468: deba@468: int id; deba@468: explicit Edge(int _id) { id = _id;} deba@468: deba@468: public: deba@468: Edge() {} deba@468: Edge (Invalid) { id = -1; } deba@468: bool operator==(const Edge& arc) const {return id == arc.id;} deba@468: bool operator!=(const Edge& arc) const {return id != arc.id;} deba@468: bool operator<(const Edge& arc) const {return id < arc.id;} deba@468: }; deba@468: deba@468: class Arc { deba@468: friend class SmartEdgeSetBase; deba@468: protected: deba@468: Arc(int _id) : id(_id) {} deba@468: int id; deba@468: public: deba@468: operator Edge() const { return edgeFromId(id / 2); } deba@468: deba@468: Arc() {} deba@468: Arc(Invalid) : id(-1) {} deba@468: bool operator==(const Arc& arc) const { return id == arc.id; } deba@468: bool operator!=(const Arc& arc) const { return id != arc.id; } deba@468: bool operator<(const Arc& arc) const { return id < arc.id; } deba@468: }; deba@468: deba@468: SmartEdgeSetBase() {} deba@468: deba@468: Edge addEdge(const Node& u, const Node& v) { deba@468: int n = arcs.size(); deba@468: arcs.push_back(ArcT()); deba@468: arcs.push_back(ArcT()); deba@468: deba@468: arcs[n].target = u; deba@468: arcs[n | 1].target = v; deba@468: deba@468: arcs[n].next_out = (*nodes)[v].first_out; deba@468: (*nodes)[v].first_out = n; deba@468: deba@468: arcs[n | 1].next_out = (*nodes)[u].first_out; deba@468: (*nodes)[u].first_out = (n | 1); deba@468: deba@468: return Edge(n / 2); deba@468: } deba@468: deba@468: void clear() { deba@468: Node node; deba@468: for (first(node); node != INVALID; next(node)) { deba@468: (*nodes)[node].first_out = -1; deba@468: } deba@468: arcs.clear(); deba@468: } deba@468: deba@468: void first(Node& node) const { deba@468: graph->first(node); deba@468: } deba@468: deba@468: void next(Node& node) const { deba@468: graph->next(node); deba@468: } deba@468: deba@468: void first(Arc& arc) const { deba@468: arc.id = arcs.size() - 1; deba@468: } deba@468: deba@468: void next(Arc& arc) const { deba@468: --arc.id; deba@468: } deba@468: deba@468: void first(Edge& arc) const { deba@468: arc.id = arcs.size() / 2 - 1; deba@468: } deba@468: deba@468: void next(Edge& arc) const { deba@468: --arc.id; deba@468: } deba@468: deba@468: void firstOut(Arc& arc, const Node& node) const { deba@468: arc.id = (*nodes)[node].first_out; deba@468: } deba@468: deba@468: void nextOut(Arc& arc) const { deba@468: arc.id = arcs[arc.id].next_out; deba@468: } deba@468: deba@468: void firstIn(Arc& arc, const Node& node) const { deba@468: arc.id = (((*nodes)[node].first_out) ^ 1); deba@468: if (arc.id == -2) arc.id = -1; deba@468: } deba@468: deba@468: void nextIn(Arc& arc) const { deba@468: arc.id = ((arcs[arc.id ^ 1].next_out) ^ 1); deba@468: if (arc.id == -2) arc.id = -1; deba@468: } deba@468: deba@468: void firstInc(Edge &arc, bool& dir, const Node& node) const { deba@468: int de = (*nodes)[node].first_out; deba@468: if (de != -1 ) { deba@468: arc.id = de / 2; deba@468: dir = ((de & 1) == 1); deba@468: } else { deba@468: arc.id = -1; deba@468: dir = true; deba@468: } deba@468: } deba@468: void nextInc(Edge &arc, bool& dir) const { deba@468: int de = (arcs[(arc.id * 2) | (dir ? 1 : 0)].next_out); deba@468: if (de != -1 ) { deba@468: arc.id = de / 2; deba@468: dir = ((de & 1) == 1); deba@468: } else { deba@468: arc.id = -1; deba@468: dir = true; deba@468: } deba@468: } deba@468: deba@468: static bool direction(Arc arc) { deba@468: return (arc.id & 1) == 1; deba@468: } deba@468: deba@468: static Arc direct(Edge edge, bool dir) { deba@468: return Arc(edge.id * 2 + (dir ? 1 : 0)); deba@468: } deba@468: deba@468: int id(Node node) const { return graph->id(node); } deba@468: static int id(Arc arc) { return arc.id; } deba@468: static int id(Edge arc) { return arc.id; } deba@468: deba@468: Node nodeFromId(int id) const { return graph->nodeFromId(id); } deba@468: static Arc arcFromId(int id) { return Arc(id); } deba@468: static Edge edgeFromId(int id) { return Edge(id);} deba@468: deba@468: int maxNodeId() const { return graph->maxNodeId(); }; deba@468: int maxArcId() const { return arcs.size() - 1; } deba@468: int maxEdgeId() const { return arcs.size() / 2 - 1; } deba@468: deba@468: Node source(Arc e) const { return arcs[e.id ^ 1].target; } deba@468: Node target(Arc e) const { return arcs[e.id].target; } deba@468: deba@468: Node u(Edge e) const { return arcs[2 * e.id].target; } deba@468: Node v(Edge e) const { return arcs[2 * e.id + 1].target; } deba@468: deba@468: typedef typename ItemSetTraits::ItemNotifier NodeNotifier; deba@468: deba@468: NodeNotifier& notifier(Node) const { deba@468: return graph->notifier(Node()); deba@468: } deba@468: deba@468: template deba@468: class NodeMap : public Graph::template NodeMap<_Value> { deba@468: public: deba@468: deba@468: typedef typename _Graph::template NodeMap<_Value> Parent; deba@468: deba@468: explicit NodeMap(const SmartEdgeSetBase& arcset) deba@468: : Parent(*arcset.graph) { } deba@468: deba@468: NodeMap(const SmartEdgeSetBase& arcset, const _Value& value) deba@468: : Parent(*arcset.graph, value) { } deba@468: deba@468: NodeMap& operator=(const NodeMap& cmap) { deba@468: return operator=(cmap); deba@468: } deba@468: deba@468: template deba@468: NodeMap& operator=(const CMap& cmap) { deba@468: Parent::operator=(cmap); deba@468: return *this; deba@468: } deba@468: }; deba@468: deba@468: }; deba@468: deba@468: /// \ingroup semi_adaptors deba@468: /// deba@468: /// \brief Graph using a node set of another digraph or graph and an deba@468: /// own edge set. deba@468: /// deba@468: /// This structure can be used to establish another graph over a deba@468: /// node set of an existing one. This class uses the same Node type deba@468: /// as the underlying graph, and each valid node of the original deba@468: /// graph is valid in this arc set, therefore the node objects of deba@468: /// the original graph can be used directly with this class. The deba@468: /// node handling functions (id handling, observing, and iterators) deba@468: /// works equivalently as in the original graph. deba@468: /// deba@468: /// \param _Graph The type of the graph which shares its node set deba@468: /// with this class. Its interface must conform to the deba@468: /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" deba@468: /// concept. deba@468: /// deba@468: /// This implementation is slightly faster than the \c ListEdgeSet, deba@468: /// because it uses continuous storage for edges and it uses just deba@468: /// single-linked lists for enumerate incident edges. Therefore the deba@468: /// edges cannot be erased from the edge sets. deba@468: /// deba@468: /// \warning If a node is erased from the underlying graph and this deba@468: /// node is incident to one edge in the edge set, then the edge set deba@468: /// is invalidated, and it cannot be used anymore. The validity can deba@468: /// be checked with the \c valid() member function. deba@468: /// deba@468: /// This class is fully conform to the \ref concepts::Graph deba@468: /// "Graph" concept. deba@468: template deba@468: class SmartEdgeSet : public EdgeSetExtender > { deba@468: deba@468: public: deba@468: deba@468: typedef EdgeSetExtender > Parent; deba@468: deba@468: typedef typename Parent::Node Node; deba@468: typedef typename Parent::Arc Arc; deba@468: typedef typename Parent::Edge Edge; deba@468: deba@468: typedef _Graph Graph; deba@468: deba@468: protected: deba@468: deba@468: typedef typename Parent::NodesImplBase NodesImplBase; deba@468: deba@468: void eraseNode(const Node& node) { deba@468: if (typename Parent::IncEdgeIt(*this, node) == INVALID) { deba@468: return; deba@468: } deba@468: throw typename NodesImplBase::Notifier::ImmediateDetach(); deba@468: } deba@468: deba@468: void clearNodes() { deba@468: Parent::clear(); deba@468: } deba@468: deba@468: class NodesImpl : public NodesImplBase { deba@468: public: deba@468: typedef NodesImplBase Parent; deba@468: deba@468: NodesImpl(const Graph& graph, SmartEdgeSet& arcset) deba@468: : Parent(graph), _arcset(arcset) {} deba@468: deba@468: virtual ~NodesImpl() {} deba@468: deba@468: bool attached() const { deba@468: return Parent::attached(); deba@468: } deba@468: deba@468: protected: deba@468: deba@468: virtual void erase(const Node& node) { deba@468: try { deba@468: _arcset.eraseNode(node); deba@468: Parent::erase(node); deba@468: } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { deba@468: Parent::clear(); deba@468: throw; deba@468: } deba@468: } deba@468: virtual void erase(const std::vector& nodes) { deba@468: try { deba@468: for (int i = 0; i < int(nodes.size()); ++i) { deba@468: _arcset.eraseNode(nodes[i]); deba@468: } deba@468: Parent::erase(nodes); deba@468: } catch (const typename NodesImplBase::Notifier::ImmediateDetach&) { deba@468: Parent::clear(); deba@468: throw; deba@468: } deba@468: } deba@468: virtual void clear() { deba@468: _arcset.clearNodes(); deba@468: Parent::clear(); deba@468: } deba@468: deba@468: private: deba@468: SmartEdgeSet& _arcset; deba@468: }; deba@468: deba@468: NodesImpl nodes; deba@468: deba@468: public: deba@468: deba@468: /// \brief Constructor of the EdgeSet. deba@468: /// deba@468: /// Constructor of the EdgeSet. deba@468: SmartEdgeSet(const Graph& graph) : nodes(graph, *this) { deba@468: Parent::initalize(graph, nodes); deba@468: } deba@468: deba@468: /// \brief Add a new edge to the graph. deba@468: /// deba@468: /// Add a new edge to the graph with node \c u deba@468: /// and node \c v endpoints. deba@468: /// \return the new edge. deba@468: Edge addEdge(const Node& u, const Node& v) { deba@468: return Parent::addEdge(u, v); deba@468: } deba@468: deba@468: /// \brief Validity check deba@468: /// deba@468: /// This functions gives back false if the EdgeSet is deba@468: /// invalidated. It occurs when a node in the underlying graph is deba@468: /// erased and it is not isolated in the EdgeSet. deba@468: bool valid() const { deba@468: return nodes.attached(); deba@468: } deba@468: deba@468: }; deba@468: deba@468: } deba@468: deba@468: #endif