deba@1979: /* -*- C++ -*- deba@1979: * deba@1979: * This file is a part of LEMON, a generic C++ optimization library deba@1979: * alpar@2553: * Copyright (C) 2003-2008 deba@1979: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@1979: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1979: * deba@1979: * Permission to use, modify and distribute this software is granted deba@1979: * provided that this copyright notice appears in all copies. For deba@1979: * precise terms see the accompanying LICENSE file. deba@1979: * deba@1979: * This software is provided "AS IS" with no warranty of any kind, deba@1979: * express or implied, and with no claim as to its suitability for any deba@1979: * purpose. deba@1979: * deba@1979: */ deba@1979: deba@1996: #ifndef LEMON_BITS_EDGE_SET_EXTENDER_H deba@1996: #define LEMON_BITS_EDGE_SET_EXTENDER_H deba@1979: deba@1996: #include deba@1996: #include deba@1996: deba@1996: #include deba@1996: deba@1996: ///\ingroup graphbits deba@1996: ///\file deba@1996: ///\brief Extenders for the edge set types deba@1979: namespace lemon { deba@1979: deba@1996: /// \ingroup graphbits deba@1996: /// deba@1996: /// \brief Extender for the EdgeSets deba@1979: template deba@1979: class EdgeSetExtender : public Base { deba@1979: public: deba@1979: deba@1979: typedef Base Parent; deba@1979: typedef EdgeSetExtender Graph; deba@1979: deba@1979: // Base extensions deba@1979: deba@1979: typedef typename Parent::Node Node; deba@1979: typedef typename Parent::Edge Edge; deba@1979: deba@1979: int maxId(Node) const { deba@1979: return Parent::maxNodeId(); deba@1979: } deba@1979: deba@1979: int maxId(Edge) const { deba@1979: return Parent::maxEdgeId(); deba@1979: } deba@1979: deba@1979: Node fromId(int id, Node) const { deba@1979: return Parent::nodeFromId(id); deba@1979: } deba@1979: deba@1979: Edge fromId(int id, Edge) const { deba@1979: return Parent::edgeFromId(id); deba@1979: } deba@1979: deba@1979: Node oppositeNode(const Node &n, const Edge &e) const { deba@1979: if (n == Parent::source(e)) deba@1979: return Parent::target(e); deba@1979: else if(n==Parent::target(e)) deba@1979: return Parent::source(e); deba@1979: else deba@1979: return INVALID; deba@1979: } deba@1979: deba@1979: deba@1979: // Alteration notifier extensions deba@1979: deba@1979: /// The edge observer registry. deba@1999: typedef AlterationNotifier EdgeNotifier; deba@1979: deba@1979: protected: deba@1979: deba@1979: mutable EdgeNotifier edge_notifier; deba@1979: deba@1979: public: deba@1979: deba@2384: using Parent::notifier; deba@1991: deba@1979: /// \brief Gives back the edge alteration notifier. deba@1979: /// deba@1979: /// Gives back the edge alteration notifier. deba@2384: EdgeNotifier& notifier(Edge) const { deba@1979: return edge_notifier; deba@1979: } deba@1979: deba@1979: // Iterable extensions deba@1979: deba@1979: class NodeIt : public Node { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: NodeIt() {} deba@1979: deba@1979: NodeIt(Invalid i) : Node(i) { } deba@1979: deba@1979: explicit NodeIt(const Graph& _graph) : graph(&_graph) { deba@2031: _graph.first(static_cast(*this)); deba@1979: } deba@1979: deba@1979: NodeIt(const Graph& _graph, const Node& node) deba@1979: : Node(node), graph(&_graph) {} deba@1979: deba@1979: NodeIt& operator++() { deba@1979: graph->next(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class EdgeIt : public Edge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: EdgeIt() { } deba@1979: deba@1979: EdgeIt(Invalid i) : Edge(i) { } deba@1979: deba@1979: explicit EdgeIt(const Graph& _graph) : graph(&_graph) { deba@2031: _graph.first(static_cast(*this)); deba@1979: } deba@1979: deba@1979: EdgeIt(const Graph& _graph, const Edge& e) : deba@1979: Edge(e), graph(&_graph) { } deba@1979: deba@1979: EdgeIt& operator++() { deba@1979: graph->next(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class OutEdgeIt : public Edge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: OutEdgeIt() { } deba@1979: deba@1979: OutEdgeIt(Invalid i) : Edge(i) { } deba@1979: deba@1979: OutEdgeIt(const Graph& _graph, const Node& node) deba@1979: : graph(&_graph) { deba@1979: _graph.firstOut(*this, node); deba@1979: } deba@1979: deba@1979: OutEdgeIt(const Graph& _graph, const Edge& edge) deba@1979: : Edge(edge), graph(&_graph) {} deba@1979: deba@1979: OutEdgeIt& operator++() { deba@1979: graph->nextOut(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class InEdgeIt : public Edge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: InEdgeIt() { } deba@1979: deba@1979: InEdgeIt(Invalid i) : Edge(i) { } deba@1979: deba@1979: InEdgeIt(const Graph& _graph, const Node& node) deba@1979: : graph(&_graph) { deba@1979: _graph.firstIn(*this, node); deba@1979: } deba@1979: deba@1979: InEdgeIt(const Graph& _graph, const Edge& edge) : deba@1979: Edge(edge), graph(&_graph) {} deba@1979: deba@1979: InEdgeIt& operator++() { deba@1979: graph->nextIn(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: /// \brief Base node of the iterator deba@1979: /// deba@1979: /// Returns the base node (ie. the source in this case) of the iterator deba@1979: Node baseNode(const OutEdgeIt &e) const { deba@2386: return Parent::source(static_cast(e)); deba@1979: } deba@1979: /// \brief Running node of the iterator deba@1979: /// deba@1979: /// Returns the running node (ie. the target in this case) of the deba@1979: /// iterator deba@1979: Node runningNode(const OutEdgeIt &e) const { deba@2386: return Parent::target(static_cast(e)); deba@1979: } deba@1979: deba@1979: /// \brief Base node of the iterator deba@1979: /// deba@1979: /// Returns the base node (ie. the target in this case) of the iterator deba@1979: Node baseNode(const InEdgeIt &e) const { deba@2386: return Parent::target(static_cast(e)); deba@1979: } deba@1979: /// \brief Running node of the iterator deba@1979: /// deba@1979: /// Returns the running node (ie. the source in this case) of the deba@1979: /// iterator deba@1979: Node runningNode(const InEdgeIt &e) const { deba@2386: return Parent::source(static_cast(e)); deba@1979: } deba@1979: deba@1979: using Parent::first; deba@1979: deba@1979: // Mappable extension deba@1979: deba@1979: template deba@1979: class EdgeMap deba@1999: : public MapExtender > { deba@1979: public: deba@1979: typedef EdgeSetExtender Graph; deba@1999: typedef MapExtender > Parent; deba@1979: klao@2046: explicit EdgeMap(const Graph& _g) deba@1979: : Parent(_g) {} deba@1979: EdgeMap(const Graph& _g, const _Value& _v) deba@1979: : Parent(_g, _v) {} deba@1979: deba@1979: EdgeMap& operator=(const EdgeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@1979: return *this; deba@1979: } deba@2031: deba@1979: }; deba@1979: deba@1979: deba@1979: // Alteration extension deba@1979: deba@1979: Edge addEdge(const Node& from, const Node& to) { deba@1979: Edge edge = Parent::addEdge(from, to); deba@2384: notifier(Edge()).add(edge); deba@1979: return edge; deba@1979: } deba@1979: deba@1979: void clear() { deba@2384: notifier(Edge()).clear(); deba@1979: Parent::clear(); deba@1979: } deba@1979: deba@1979: void erase(const Edge& edge) { deba@2384: notifier(Edge()).erase(edge); deba@1979: Parent::erase(edge); deba@1979: } deba@1979: deba@1999: EdgeSetExtender() { deba@1999: edge_notifier.setContainer(*this); deba@1999: } deba@1979: deba@1979: ~EdgeSetExtender() { deba@1979: edge_notifier.clear(); deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1996: /// \ingroup graphbits deba@1996: /// deba@1996: /// \brief Extender for the UEdgeSets deba@1979: template deba@1979: class UEdgeSetExtender : public Base { deba@1979: deba@1979: public: deba@1979: deba@1979: typedef Base Parent; deba@1979: typedef UEdgeSetExtender Graph; deba@1979: deba@1979: typedef typename Parent::Node Node; deba@1979: typedef typename Parent::Edge Edge; deba@1979: typedef typename Parent::UEdge UEdge; deba@1979: deba@1979: deba@1979: int maxId(Node) const { deba@1979: return Parent::maxNodeId(); deba@1979: } deba@1979: deba@1979: int maxId(Edge) const { deba@1979: return Parent::maxEdgeId(); deba@1979: } deba@1979: deba@1979: int maxId(UEdge) const { deba@1979: return Parent::maxUEdgeId(); deba@1979: } deba@1979: deba@1979: Node fromId(int id, Node) const { deba@1979: return Parent::nodeFromId(id); deba@1979: } deba@1979: deba@1979: Edge fromId(int id, Edge) const { deba@1979: return Parent::edgeFromId(id); deba@1979: } deba@1979: deba@1979: UEdge fromId(int id, UEdge) const { deba@1979: return Parent::uEdgeFromId(id); deba@1979: } deba@1979: deba@1979: Node oppositeNode(const Node &n, const UEdge &e) const { deba@1979: if( n == Parent::source(e)) deba@1979: return Parent::target(e); deba@1979: else if( n == Parent::target(e)) deba@1979: return Parent::source(e); deba@1979: else deba@1979: return INVALID; deba@1979: } deba@1979: deba@1979: Edge oppositeEdge(const Edge &e) const { deba@1979: return Parent::direct(e, !Parent::direction(e)); deba@1979: } deba@1979: deba@1979: using Parent::direct; deba@1979: Edge direct(const UEdge &ue, const Node &s) const { deba@1979: return Parent::direct(ue, Parent::source(ue) == s); deba@1979: } deba@1979: deba@1999: typedef AlterationNotifier EdgeNotifier; deba@1999: typedef AlterationNotifier UEdgeNotifier; deba@1979: deba@1979: deba@1979: protected: deba@1979: deba@1979: mutable EdgeNotifier edge_notifier; deba@1979: mutable UEdgeNotifier uedge_notifier; deba@1979: deba@1979: public: deba@1991: deba@2384: using Parent::notifier; deba@1979: deba@2384: EdgeNotifier& notifier(Edge) const { deba@1979: return edge_notifier; deba@1979: } deba@1979: deba@2384: UEdgeNotifier& notifier(UEdge) const { deba@1979: return uedge_notifier; deba@1979: } deba@1979: deba@1979: deba@1979: class NodeIt : public Node { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: NodeIt() {} deba@1979: deba@1979: NodeIt(Invalid i) : Node(i) { } deba@1979: deba@1979: explicit NodeIt(const Graph& _graph) : graph(&_graph) { deba@2031: _graph.first(static_cast(*this)); deba@1979: } deba@1979: deba@1979: NodeIt(const Graph& _graph, const Node& node) deba@1979: : Node(node), graph(&_graph) {} deba@1979: deba@1979: NodeIt& operator++() { deba@1979: graph->next(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class EdgeIt : public Edge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: EdgeIt() { } deba@1979: deba@1979: EdgeIt(Invalid i) : Edge(i) { } deba@1979: deba@1979: explicit EdgeIt(const Graph& _graph) : graph(&_graph) { deba@2031: _graph.first(static_cast(*this)); deba@1979: } deba@1979: deba@1979: EdgeIt(const Graph& _graph, const Edge& e) : deba@1979: Edge(e), graph(&_graph) { } deba@1979: deba@1979: EdgeIt& operator++() { deba@1979: graph->next(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class OutEdgeIt : public Edge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: OutEdgeIt() { } deba@1979: deba@1979: OutEdgeIt(Invalid i) : Edge(i) { } deba@1979: deba@1979: OutEdgeIt(const Graph& _graph, const Node& node) deba@1979: : graph(&_graph) { deba@1979: _graph.firstOut(*this, node); deba@1979: } deba@1979: deba@1979: OutEdgeIt(const Graph& _graph, const Edge& edge) deba@1979: : Edge(edge), graph(&_graph) {} deba@1979: deba@1979: OutEdgeIt& operator++() { deba@1979: graph->nextOut(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class InEdgeIt : public Edge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: InEdgeIt() { } deba@1979: deba@1979: InEdgeIt(Invalid i) : Edge(i) { } deba@1979: deba@1979: InEdgeIt(const Graph& _graph, const Node& node) deba@1979: : graph(&_graph) { deba@1979: _graph.firstIn(*this, node); deba@1979: } deba@1979: deba@1979: InEdgeIt(const Graph& _graph, const Edge& edge) : deba@1979: Edge(edge), graph(&_graph) {} deba@1979: deba@1979: InEdgeIt& operator++() { deba@1979: graph->nextIn(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: deba@1979: class UEdgeIt : public Parent::UEdge { deba@1979: const Graph* graph; deba@1979: public: deba@1979: deba@1979: UEdgeIt() { } deba@1979: deba@1979: UEdgeIt(Invalid i) : UEdge(i) { } deba@1979: deba@1979: explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { deba@2031: _graph.first(static_cast(*this)); deba@1979: } deba@1979: deba@1979: UEdgeIt(const Graph& _graph, const UEdge& e) : deba@1979: UEdge(e), graph(&_graph) { } deba@1979: deba@1979: UEdgeIt& operator++() { deba@1979: graph->next(*this); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: class IncEdgeIt : public Parent::UEdge { deba@1979: friend class UEdgeSetExtender; deba@1979: const Graph* graph; deba@1979: bool direction; deba@1979: public: deba@1979: deba@1979: IncEdgeIt() { } deba@1979: deba@1979: IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } deba@1979: deba@1979: IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { deba@1979: _graph.firstInc(*this, direction, n); deba@1979: } deba@1979: deba@1979: IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) deba@1979: : graph(&_graph), UEdge(ue) { deba@1979: direction = (_graph.source(ue) == n); deba@1979: } deba@1979: deba@1979: IncEdgeIt& operator++() { deba@1979: graph->nextInc(*this, direction); deba@1979: return *this; deba@1979: } deba@1979: }; deba@1979: deba@1979: /// \brief Base node of the iterator deba@1979: /// deba@1979: /// Returns the base node (ie. the source in this case) of the iterator deba@1979: Node baseNode(const OutEdgeIt &e) const { deba@2386: return Parent::source(static_cast(e)); deba@1979: } deba@1979: /// \brief Running node of the iterator deba@1979: /// deba@1979: /// Returns the running node (ie. the target in this case) of the deba@1979: /// iterator deba@1979: Node runningNode(const OutEdgeIt &e) const { deba@2386: return Parent::target(static_cast(e)); deba@1979: } deba@1979: deba@1979: /// \brief Base node of the iterator deba@1979: /// deba@1979: /// Returns the base node (ie. the target in this case) of the iterator deba@1979: Node baseNode(const InEdgeIt &e) const { deba@2386: return Parent::target(static_cast(e)); deba@1979: } deba@1979: /// \brief Running node of the iterator deba@1979: /// deba@1979: /// Returns the running node (ie. the source in this case) of the deba@1979: /// iterator deba@1979: Node runningNode(const InEdgeIt &e) const { deba@2386: return Parent::source(static_cast(e)); deba@1979: } deba@1979: deba@1979: /// Base node of the iterator deba@1979: /// deba@1979: /// Returns the base node of the iterator deba@1979: Node baseNode(const IncEdgeIt &e) const { deba@1979: return e.direction ? source(e) : target(e); deba@1979: } deba@1979: /// Running node of the iterator deba@1979: /// deba@1979: /// Returns the running node of the iterator deba@1979: Node runningNode(const IncEdgeIt &e) const { deba@1979: return e.direction ? target(e) : source(e); deba@1979: } deba@1979: deba@1979: deba@1979: template deba@1979: class EdgeMap deba@1999: : public MapExtender > { deba@1979: public: deba@1979: typedef UEdgeSetExtender Graph; deba@1999: typedef MapExtender > Parent; deba@1979: deba@1979: EdgeMap(const Graph& _g) deba@1979: : Parent(_g) {} deba@1979: EdgeMap(const Graph& _g, const _Value& _v) deba@1979: : Parent(_g, _v) {} deba@1979: deba@1979: EdgeMap& operator=(const EdgeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: EdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@1979: return *this; deba@1979: } deba@2031: deba@1979: }; deba@1979: deba@1979: deba@1979: template deba@1979: class UEdgeMap deba@1999: : public MapExtender > { deba@1979: public: deba@1979: typedef UEdgeSetExtender Graph; deba@1999: typedef MapExtender > Parent; deba@1979: deba@1979: UEdgeMap(const Graph& _g) deba@1979: : Parent(_g) {} deba@2031: deba@1979: UEdgeMap(const Graph& _g, const _Value& _v) deba@1979: : Parent(_g, _v) {} deba@1979: deba@1979: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: UEdgeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@1979: return *this; deba@1979: } deba@2031: deba@1979: }; deba@1979: deba@1979: deba@1979: // Alteration extension deba@1979: deba@1979: UEdge addEdge(const Node& from, const Node& to) { deba@1979: UEdge uedge = Parent::addEdge(from, to); deba@2384: notifier(UEdge()).add(uedge); deba@2498: std::vector edges; deba@2498: edges.push_back(Parent::direct(uedge, true)); deba@2498: edges.push_back(Parent::direct(uedge, false)); deba@2498: notifier(Edge()).add(edges); deba@1979: return uedge; deba@1979: } deba@1979: deba@1979: void clear() { deba@2384: notifier(Edge()).clear(); deba@2384: notifier(UEdge()).clear(); deba@1979: Parent::clear(); deba@1979: } deba@1979: deba@1979: void erase(const UEdge& uedge) { deba@2498: std::vector edges; deba@2498: edges.push_back(Parent::direct(uedge, true)); deba@2498: edges.push_back(Parent::direct(uedge, false)); deba@2498: notifier(Edge()).erase(edges); deba@2384: notifier(UEdge()).erase(uedge); deba@1979: Parent::erase(uedge); deba@1979: } deba@1979: deba@1979: deba@1999: UEdgeSetExtender() { deba@1999: edge_notifier.setContainer(*this); deba@1999: uedge_notifier.setContainer(*this); deba@1999: } deba@1999: deba@1979: ~UEdgeSetExtender() { deba@1999: uedge_notifier.clear(); deba@1999: edge_notifier.clear(); deba@1979: } deba@1979: deba@1979: }; deba@1996: deba@1979: } deba@1996: deba@1996: #endif