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 <lemon/core.h>
deba@468: #include <lemon/bits/edge_set_extender.h>
deba@468: 
kpeter@660: /// \ingroup graphs
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@488:   template <typename GR>
deba@468:   class ListArcSetBase {
deba@468:   public:
deba@468: 
deba@488:     typedef typename GR::Node Node;
deba@488:     typedef typename GR::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@488:     typedef typename ItemSetTraits<GR, Node>::
deba@468:     template Map<NodeT>::Type NodesImplBase;
deba@468: 
deba@488:     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<ArcT> arcs;
deba@468: 
deba@468:     int first_arc;
deba@468:     int first_free_arc;
deba@468: 
deba@488:     const GR* _graph;
deba@468: 
deba@488:     void initalize(const GR& graph, NodesImplBase& nodes) {
deba@488:       _graph = &graph;
deba@488:       _nodes = &nodes;
deba@468:     }
deba@468: 
deba@468:   public:
deba@468: 
deba@468:     class Arc {
deba@488:       friend class ListArcSetBase<GR>;
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: 
kpeter@670:     Node addNode() {
kpeter@670:       LEMON_ASSERT(false,
kpeter@670:         "This graph structure does not support node insertion");
kpeter@670:       return INVALID; // avoid warning
kpeter@670:     }
kpeter@670: 
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@488:       arcs[n].next_in = (*_nodes)[v].first_in;
deba@488:       if ((*_nodes)[v].first_in != -1) {
deba@488:         arcs[(*_nodes)[v].first_in].prev_in = n;
deba@468:       }
deba@488:       (*_nodes)[v].first_in = n;
deba@488:       arcs[n].next_out = (*_nodes)[u].first_out;
deba@488:       if ((*_nodes)[u].first_out != -1) {
deba@488:         arcs[(*_nodes)[u].first_out].prev_out = n;
deba@468:       }
deba@488:       (*_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@488:         (*_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@488:         (*_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@488:         (*_nodes)[node].first_in = -1;
deba@488:         (*_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@488:       _graph->first(node);
deba@468:     }
deba@468: 
deba@468:     void next(Node& node) const {
deba@488:       _graph->next(node);
deba@468:     }
deba@468: 
deba@468:     void first(Arc& arc) const {
deba@468:       Node node;
deba@468:       first(node);
deba@488:       while (node != INVALID && (*_nodes)[node].first_in == -1) {
deba@468:         next(node);
deba@468:       }
deba@488:       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@488:         while (node != INVALID && (*_nodes)[node].first_in == -1) {
deba@468:           next(node);
deba@468:         }
deba@488:         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@488:       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@488:       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@488:     int id(const Node& node) const { return _graph->id(node); }
deba@468:     int id(const Arc& arc) const { return arc.id; }
deba@468: 
deba@488:     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@468:     Arc arcFromId(int ix) const { return Arc(ix); }
deba@468: 
deba@488:     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@488:     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468: 
deba@468:     NodeNotifier& notifier(Node) const {
deba@488:       return _graph->notifier(Node());
deba@468:     }
deba@468: 
deba@488:     template <typename V>
deba@488:     class NodeMap : public GR::template NodeMap<V> {
kpeter@617:       typedef typename GR::template NodeMap<V> Parent;
kpeter@617: 
deba@468:     public:
deba@468: 
deba@488:       explicit NodeMap(const ListArcSetBase<GR>& arcset)
deba@488:         : Parent(*arcset._graph) {}
deba@468: 
deba@488:       NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
deba@488:         : Parent(*arcset._graph, value) {}
deba@468: 
deba@468:       NodeMap& operator=(const NodeMap& cmap) {
deba@468:         return operator=<NodeMap>(cmap);
deba@468:       }
deba@468: 
deba@468:       template <typename CMap>
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: 
kpeter@660:   /// \ingroup graphs
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@488:   /// \param GR 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:   ///
kpeter@559:   /// This class fully conforms to the \ref concepts::Digraph
deba@468:   /// "Digraph" concept.
deba@488:   template <typename GR>
deba@488:   class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
kpeter@617:     typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
deba@468: 
deba@468:   public:
deba@468: 
deba@468:     typedef typename Parent::Node Node;
deba@468:     typedef typename Parent::Arc Arc;
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:       typedef NodesImplBase Parent;
deba@468: 
kpeter@617:     public:
deba@488:       NodesImpl(const GR& 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<Node>& 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@488:     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@488:     ListArcSet(const GR& graph) : _nodes(graph, *this) {
deba@488:       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.
kpeter@559:     /// \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@488:   template <typename GR>
deba@468:   class ListEdgeSetBase {
deba@468:   public:
deba@468: 
deba@488:     typedef typename GR::Node Node;
deba@488:     typedef typename GR::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@488:     typedef typename ItemSetTraits<GR, Node>::
deba@468:     template Map<NodeT>::Type NodesImplBase;
deba@468: 
deba@488:     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<ArcT> arcs;
deba@468: 
deba@468:     int first_arc;
deba@468:     int first_free_arc;
deba@468: 
deba@488:     const GR* _graph;
deba@468: 
deba@488:     void initalize(const GR& graph, NodesImplBase& nodes) {
deba@488:       _graph = &graph;
deba@488:       _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: 
kpeter@670:     Node addNode() {
kpeter@670:       LEMON_ASSERT(false,
kpeter@670:         "This graph structure does not support node insertion");
kpeter@670:       return INVALID; // avoid warning
kpeter@670:     }
kpeter@670: 
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@488:       arcs[n].next_out = (*_nodes)[v].first_out;
deba@488:       if ((*_nodes)[v].first_out != -1) {
deba@488:         arcs[(*_nodes)[v].first_out].prev_out = n;
deba@468:       }
deba@488:       (*_nodes)[v].first_out = n;
deba@468:       arcs[n].prev_out = -1;
deba@468: 
deba@488:       if ((*_nodes)[u].first_out != -1) {
deba@488:         arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
deba@468:       }
deba@488:       arcs[n | 1].next_out = (*_nodes)[u].first_out;
deba@488:       (*_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@488:         (*_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@488:         (*_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@488:         (*_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@488:       _graph->first(node);
deba@468:     }
deba@468: 
deba@468:     void next(Node& node) const {
deba@488:       _graph->next(node);
deba@468:     }
deba@468: 
deba@468:     void first(Arc& arc) const {
deba@468:       Node node;
deba@468:       first(node);
deba@488:       while (node != INVALID && (*_nodes)[node].first_out == -1) {
deba@468:         next(node);
deba@468:       }
deba@488:       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@488:         while(node != INVALID && (*_nodes)[node].first_out == -1) {
deba@468:           next(node);
deba@468:         }
deba@488:         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@488:         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@488:         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@488:       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@488:       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@488:       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@488:     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@488:     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@488:     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@488:     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468: 
deba@468:     NodeNotifier& notifier(Node) const {
deba@488:       return _graph->notifier(Node());
deba@468:     }
deba@468: 
deba@488:     template <typename V>
deba@488:     class NodeMap : public GR::template NodeMap<V> {
kpeter@617:       typedef typename GR::template NodeMap<V> Parent;
kpeter@617: 
deba@468:     public:
deba@468: 
deba@488:       explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
deba@488:         : Parent(*arcset._graph) {}
deba@468: 
deba@488:       NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
deba@488:         : Parent(*arcset._graph, value) {}
deba@468: 
deba@468:       NodeMap& operator=(const NodeMap& cmap) {
deba@468:         return operator=<NodeMap>(cmap);
deba@468:       }
deba@468: 
deba@468:       template <typename CMap>
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: 
kpeter@660:   /// \ingroup graphs
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@488:   /// \param GR 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:   ///
kpeter@559:   /// This class fully conforms to the \ref concepts::Graph "Graph"
deba@468:   /// concept.
deba@488:   template <typename GR>
deba@488:   class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
kpeter@617:     typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
deba@468: 
deba@468:   public:
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 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:       typedef NodesImplBase Parent;
deba@468: 
kpeter@617:     public:
deba@488:       NodesImpl(const GR& 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<Node>& 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@488:     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@488:     ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
deba@488:       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.
kpeter@559:     /// \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@488:   template <typename GR>
deba@468:   class SmartArcSetBase {
deba@468:   public:
deba@468: 
kpeter@617:     typedef typename GR::Node Node;
kpeter@617:     typedef typename GR::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@488:     typedef typename ItemSetTraits<GR, Node>::
deba@468:     template Map<NodeT>::Type NodesImplBase;
deba@468: 
deba@488:     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<ArcT> arcs;
deba@468: 
deba@488:     const GR* _graph;
deba@468: 
deba@488:     void initalize(const GR& graph, NodesImplBase& nodes) {
deba@488:       _graph = &graph;
deba@488:       _nodes = &nodes;
deba@468:     }
deba@468: 
deba@468:   public:
deba@468: 
deba@468:     class Arc {
deba@488:       friend class SmartArcSetBase<GR>;
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: 
kpeter@670:     Node addNode() {
kpeter@670:       LEMON_ASSERT(false,
kpeter@670:         "This graph structure does not support node insertion");
kpeter@670:       return INVALID; // avoid warning
kpeter@670:     }
kpeter@670: 
deba@468:     Arc addArc(const Node& u, const Node& v) {
deba@468:       int n = arcs.size();
deba@468:       arcs.push_back(ArcT());
deba@488:       arcs[n].next_in = (*_nodes)[v].first_in;
deba@488:       (*_nodes)[v].first_in = n;
deba@488:       arcs[n].next_out = (*_nodes)[u].first_out;
deba@488:       (*_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@488:         (*_nodes)[node].first_in = -1;
deba@488:         (*_nodes)[node].first_out = -1;
deba@468:       }
deba@468:       arcs.clear();
deba@468:     }
deba@468: 
deba@468:     void first(Node& node) const {
deba@488:       _graph->first(node);
deba@468:     }
deba@468: 
deba@468:     void next(Node& node) const {
deba@488:       _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: 
kpeter@778:     static void next(Arc& arc) {
deba@468:       --arc.id;
deba@468:     }
deba@468: 
deba@468:     void firstOut(Arc& arc, const Node& node) const {
deba@488:       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@488:       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@488:     int id(const Node& node) const { return _graph->id(node); }
deba@468:     int id(const Arc& arc) const { return arc.id; }
deba@468: 
deba@488:     Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
deba@468:     Arc arcFromId(int ix) const { return Arc(ix); }
deba@468: 
deba@488:     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@488:     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468: 
deba@468:     NodeNotifier& notifier(Node) const {
deba@488:       return _graph->notifier(Node());
deba@468:     }
deba@468: 
deba@488:     template <typename V>
deba@488:     class NodeMap : public GR::template NodeMap<V> {
kpeter@617:       typedef typename GR::template NodeMap<V> Parent;
kpeter@617: 
deba@468:     public:
deba@468: 
deba@488:       explicit NodeMap(const SmartArcSetBase<GR>& arcset)
deba@488:         : Parent(*arcset._graph) { }
deba@468: 
deba@488:       NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
deba@488:         : Parent(*arcset._graph, value) { }
deba@468: 
deba@468:       NodeMap& operator=(const NodeMap& cmap) {
deba@468:         return operator=<NodeMap>(cmap);
deba@468:       }
deba@468: 
deba@468:       template <typename CMap>
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: 
kpeter@660:   /// \ingroup graphs
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@488:   /// \param GR 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:   ///
kpeter@559:   /// This class fully conforms to the \ref concepts::Digraph
deba@468:   /// "Digraph" concept.
deba@488:   template <typename GR>
deba@488:   class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
kpeter@617:     typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
deba@468: 
deba@468:   public:
deba@468: 
deba@468:     typedef typename Parent::Node Node;
deba@468:     typedef typename Parent::Arc Arc;
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:       typedef NodesImplBase Parent;
deba@468: 
kpeter@617:     public:
deba@488:       NodesImpl(const GR& 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<Node>& 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@488:     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@488:     SmartArcSet(const GR& graph) : _nodes(graph, *this) {
deba@488:       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.
kpeter@559:     /// \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@488:       return _nodes.attached();
deba@468:     }
deba@468: 
deba@468:   };
deba@468: 
deba@468: 
deba@488:   template <typename GR>
deba@468:   class SmartEdgeSetBase {
deba@468:   public:
deba@468: 
deba@488:     typedef typename GR::Node Node;
deba@488:     typedef typename GR::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@488:     typedef typename ItemSetTraits<GR, Node>::
deba@468:     template Map<NodeT>::Type NodesImplBase;
deba@468: 
deba@488:     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<ArcT> arcs;
deba@468: 
deba@488:     const GR* _graph;
deba@468: 
deba@488:     void initalize(const GR& graph, NodesImplBase& nodes) {
deba@488:       _graph = &graph;
deba@488:       _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: 
kpeter@670:     Node addNode() {
kpeter@670:       LEMON_ASSERT(false,
kpeter@670:         "This graph structure does not support node insertion");
kpeter@670:       return INVALID; // avoid warning
kpeter@670:     }
kpeter@670: 
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@488:       arcs[n].next_out = (*_nodes)[v].first_out;
deba@488:       (*_nodes)[v].first_out = n;
deba@468: 
deba@488:       arcs[n | 1].next_out = (*_nodes)[u].first_out;
deba@488:       (*_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@488:         (*_nodes)[node].first_out = -1;
deba@468:       }
deba@468:       arcs.clear();
deba@468:     }
deba@468: 
deba@468:     void first(Node& node) const {
deba@488:       _graph->first(node);
deba@468:     }
deba@468: 
deba@468:     void next(Node& node) const {
deba@488:       _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: 
kpeter@778:     static void next(Arc& arc) {
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: 
kpeter@778:     static void next(Edge& arc) {
deba@468:       --arc.id;
deba@468:     }
deba@468: 
deba@468:     void firstOut(Arc& arc, const Node& node) const {
deba@488:       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@488:       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@488:       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@488:     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@488:     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@488:     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@488:     typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
deba@468: 
deba@468:     NodeNotifier& notifier(Node) const {
deba@488:       return _graph->notifier(Node());
deba@468:     }
deba@468: 
deba@488:     template <typename V>
deba@488:     class NodeMap : public GR::template NodeMap<V> {
kpeter@617:       typedef typename GR::template NodeMap<V> Parent;
kpeter@617: 
deba@468:     public:
deba@468: 
deba@488:       explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
deba@488:         : Parent(*arcset._graph) { }
deba@468: 
deba@488:       NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
deba@488:         : Parent(*arcset._graph, value) { }
deba@468: 
deba@468:       NodeMap& operator=(const NodeMap& cmap) {
deba@468:         return operator=<NodeMap>(cmap);
deba@468:       }
deba@468: 
deba@468:       template <typename CMap>
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: 
kpeter@660:   /// \ingroup graphs
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@488:   /// \param GR 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:   ///
kpeter@559:   /// This class fully conforms to the \ref concepts::Graph
deba@468:   /// "Graph" concept.
deba@488:   template <typename GR>
deba@488:   class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
kpeter@617:     typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
deba@468: 
deba@468:   public:
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:   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:       typedef NodesImplBase Parent;
deba@468: 
kpeter@617:     public:
deba@488:       NodesImpl(const GR& 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<Node>& 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@488:     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@488:     SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
deba@488:       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.
kpeter@559:     /// \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@488:       return _nodes.attached();
deba@468:     }
deba@468: 
deba@468:   };
deba@468: 
deba@468: }
deba@468: 
deba@468: #endif