deba@1791: /* -*- C++ -*- deba@1791: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1956: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@1791: * deba@1791: * Permission to use, modify and distribute this software is granted deba@1791: * provided that this copyright notice appears in all copies. For deba@1791: * precise terms see the accompanying LICENSE file. deba@1791: * deba@1791: * This software is provided "AS IS" with no warranty of any kind, deba@1791: * express or implied, and with no claim as to its suitability for any deba@1791: * purpose. deba@1791: * deba@1791: */ deba@1791: deba@1996: #ifndef LEMON_BITS_GRAPH_EXTENDER_H deba@1996: #define LEMON_BITS_GRAPH_EXTENDER_H deba@1791: deba@1993: #include deba@2116: #include deba@1791: deba@1999: #include deba@1979: #include deba@1979: deba@2116: #include deba@2116: #include deba@2116: deba@1996: ///\ingroup graphbits deba@1996: ///\file deba@1996: ///\brief Extenders for the graph types deba@1791: namespace lemon { deba@1791: deba@1996: /// \ingroup graphbits deba@1996: /// deba@1996: /// \brief Extender for the Graphs deba@1979: template deba@1979: class GraphExtender : public Base { deba@1791: public: deba@1791: deba@1979: typedef Base Parent; deba@1791: typedef GraphExtender Graph; deba@1791: deba@1979: // Base extensions deba@1979: deba@1791: typedef typename Parent::Node Node; deba@1791: typedef typename Parent::Edge Edge; deba@1791: deba@1791: int maxId(Node) const { deba@1791: return Parent::maxNodeId(); deba@1791: } deba@1791: deba@1791: int maxId(Edge) const { deba@1791: return Parent::maxEdgeId(); deba@1791: } deba@1791: deba@1791: Node fromId(int id, Node) const { deba@1791: return Parent::nodeFromId(id); deba@1791: } deba@1791: deba@1791: Edge fromId(int id, Edge) const { deba@1791: return Parent::edgeFromId(id); deba@1791: } deba@1791: deba@1791: Node oppositeNode(const Node &n, const Edge &e) const { deba@1791: if (n == Parent::source(e)) deba@1791: return Parent::target(e); deba@1791: else if(n==Parent::target(e)) deba@1791: return Parent::source(e); deba@1791: else deba@1791: return INVALID; deba@1791: } deba@1791: deba@1979: // Alterable extension deba@1791: deba@1999: typedef AlterationNotifier NodeNotifier; deba@1999: typedef AlterationNotifier EdgeNotifier; deba@1979: deba@1979: deba@1979: protected: deba@1979: deba@1979: mutable NodeNotifier node_notifier; deba@1979: mutable EdgeNotifier edge_notifier; deba@1791: deba@1791: public: deba@1791: deba@1979: NodeNotifier& getNotifier(Node) const { deba@1979: return node_notifier; deba@1979: } deba@1979: deba@1979: EdgeNotifier& getNotifier(Edge) const { deba@1979: return edge_notifier; 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: /// \brief Base node of the iterator deba@1979: /// athos@2102: /// Returns the base node (i.e. the source in this case) of the iterator deba@1979: Node baseNode(const OutEdgeIt &e) const { deba@1979: return Parent::source(e); deba@1979: } deba@1979: /// \brief Running node of the iterator deba@1979: /// athos@2102: /// Returns the running node (i.e. the target in this case) of the deba@1979: /// iterator deba@1979: Node runningNode(const OutEdgeIt &e) const { deba@1979: return Parent::target(e); deba@1979: } deba@1979: deba@1979: /// \brief Base node of the iterator deba@1979: /// athos@2102: /// Returns the base node (i.e. the target in this case) of the iterator deba@1979: Node baseNode(const InEdgeIt &e) const { deba@1979: return Parent::target(e); deba@1979: } deba@1979: /// \brief Running node of the iterator deba@1979: /// athos@2102: /// Returns the running node (i.e. the source in this case) of the deba@1979: /// iterator deba@1979: Node runningNode(const InEdgeIt &e) const { deba@1979: return Parent::source(e); deba@1979: } deba@1979: deba@1979: deba@1979: template deba@1979: class NodeMap deba@1999: : public MapExtender > { deba@1979: public: deba@1979: typedef GraphExtender Graph; deba@1999: typedef MapExtender > Parent; deba@1979: klao@2046: explicit NodeMap(const Graph& graph) deba@1999: : Parent(graph) {} deba@1999: NodeMap(const Graph& graph, const _Value& value) deba@1999: : Parent(graph, value) {} deba@1979: deba@1979: NodeMap& operator=(const NodeMap& cmap) { deba@1979: return operator=(cmap); deba@1979: } deba@1979: deba@1979: template deba@1979: NodeMap& operator=(const CMap& cmap) { deba@2031: Parent::operator=(cmap); deba@1979: return *this; deba@1979: } deba@1979: deba@1979: }; deba@1979: deba@1979: template deba@1979: class EdgeMap deba@1999: : public MapExtender > { deba@1979: public: deba@1979: typedef GraphExtender Graph; deba@1999: typedef MapExtender > Parent; deba@1979: klao@2046: explicit EdgeMap(const Graph& graph) deba@1999: : Parent(graph) {} deba@1999: EdgeMap(const Graph& graph, const _Value& value) deba@1999: : Parent(graph, value) {} 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@1979: }; deba@1979: deba@1979: deba@1979: Node addNode() { deba@1979: Node node = Parent::addNode(); deba@1979: getNotifier(Node()).add(node); deba@1979: return node; deba@1979: } deba@1979: deba@1979: Edge addEdge(const Node& from, const Node& to) { deba@1979: Edge edge = Parent::addEdge(from, to); deba@1979: getNotifier(Edge()).add(edge); deba@1979: return edge; deba@1979: } deba@1979: deba@1979: void clear() { deba@1979: getNotifier(Edge()).clear(); deba@1979: getNotifier(Node()).clear(); deba@1979: Parent::clear(); deba@1979: } deba@1979: deba@1979: deba@1979: void erase(const Node& node) { deba@1979: Edge edge; deba@1979: Parent::firstOut(edge, node); deba@1979: while (edge != INVALID ) { deba@1979: erase(edge); deba@1979: Parent::firstOut(edge, node); deba@1979: } deba@1979: deba@1979: Parent::firstIn(edge, node); deba@1979: while (edge != INVALID ) { deba@1979: erase(edge); deba@1979: Parent::firstIn(edge, node); deba@1979: } deba@1979: deba@1979: getNotifier(Node()).erase(node); deba@1979: Parent::erase(node); deba@1979: } deba@1979: deba@1979: void erase(const Edge& edge) { deba@1979: getNotifier(Edge()).erase(edge); deba@1979: Parent::erase(edge); deba@1979: } deba@1979: deba@1999: GraphExtender() { deba@1999: node_notifier.setContainer(*this); deba@1999: edge_notifier.setContainer(*this); deba@1999: } deba@1999: deba@1979: deba@1979: ~GraphExtender() { deba@1999: edge_notifier.clear(); deba@1999: node_notifier.clear(); deba@1979: } deba@1979: }; deba@1979: deba@2116: /// \ingroup graphbits deba@2116: /// deba@2116: /// \brief Extender for the UGraphs deba@2116: template deba@2116: class UGraphExtender : public Base { deba@2116: public: deba@2116: deba@2116: typedef Base Parent; deba@2116: typedef UGraphExtender Graph; deba@2116: deba@2116: typedef typename Parent::Node Node; deba@2116: typedef typename Parent::Edge Edge; deba@2116: typedef typename Parent::UEdge UEdge; deba@2116: deba@2116: // UGraph extension deba@2116: deba@2116: int maxId(Node) const { deba@2116: return Parent::maxNodeId(); deba@2116: } deba@2116: deba@2116: int maxId(Edge) const { deba@2116: return Parent::maxEdgeId(); deba@2116: } deba@2116: deba@2116: int maxId(UEdge) const { deba@2116: return Parent::maxUEdgeId(); deba@2116: } deba@2116: deba@2116: Node fromId(int id, Node) const { deba@2116: return Parent::nodeFromId(id); deba@2116: } deba@2116: deba@2116: Edge fromId(int id, Edge) const { deba@2116: return Parent::edgeFromId(id); deba@2116: } deba@2116: deba@2116: UEdge fromId(int id, UEdge) const { deba@2116: return Parent::uEdgeFromId(id); deba@2116: } deba@2116: deba@2116: Node oppositeNode(const Node &n, const UEdge &e) const { deba@2116: if( n == Parent::source(e)) deba@2116: return Parent::target(e); deba@2116: else if( n == Parent::target(e)) deba@2116: return Parent::source(e); deba@2116: else deba@2116: return INVALID; deba@2116: } deba@2116: deba@2116: Edge oppositeEdge(const Edge &e) const { deba@2116: return Parent::direct(e, !Parent::direction(e)); deba@2116: } deba@2116: deba@2116: using Parent::direct; deba@2116: Edge direct(const UEdge &ue, const Node &s) const { deba@2116: return Parent::direct(ue, Parent::source(ue) == s); deba@2116: } deba@2116: deba@2116: // Alterable extension deba@2116: deba@2116: typedef AlterationNotifier NodeNotifier; deba@2116: typedef AlterationNotifier EdgeNotifier; deba@2116: typedef AlterationNotifier UEdgeNotifier; deba@2116: deba@2116: deba@2116: protected: deba@2116: deba@2116: mutable NodeNotifier node_notifier; deba@2116: mutable EdgeNotifier edge_notifier; deba@2116: mutable UEdgeNotifier uedge_notifier; deba@2116: deba@2116: public: deba@2116: deba@2116: NodeNotifier& getNotifier(Node) const { deba@2116: return node_notifier; deba@2116: } deba@2116: deba@2116: EdgeNotifier& getNotifier(Edge) const { deba@2116: return edge_notifier; deba@2116: } deba@2116: deba@2116: UEdgeNotifier& getNotifier(UEdge) const { deba@2116: return uedge_notifier; deba@2116: } deba@2116: deba@2116: deba@2116: deba@2116: class NodeIt : public Node { deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: NodeIt() {} deba@2116: deba@2116: NodeIt(Invalid i) : Node(i) { } deba@2116: deba@2116: explicit NodeIt(const Graph& _graph) : graph(&_graph) { deba@2116: _graph.first(static_cast(*this)); deba@2116: } deba@2116: deba@2116: NodeIt(const Graph& _graph, const Node& node) deba@2116: : Node(node), graph(&_graph) {} deba@2116: deba@2116: NodeIt& operator++() { deba@2116: graph->next(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2116: class EdgeIt : public Edge { deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: EdgeIt() { } deba@2116: deba@2116: EdgeIt(Invalid i) : Edge(i) { } deba@2116: deba@2116: explicit EdgeIt(const Graph& _graph) : graph(&_graph) { deba@2116: _graph.first(static_cast(*this)); deba@2116: } deba@2116: deba@2116: EdgeIt(const Graph& _graph, const Edge& e) : deba@2116: Edge(e), graph(&_graph) { } deba@2116: deba@2116: EdgeIt& operator++() { deba@2116: graph->next(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2116: class OutEdgeIt : public Edge { deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: OutEdgeIt() { } deba@2116: deba@2116: OutEdgeIt(Invalid i) : Edge(i) { } deba@2116: deba@2116: OutEdgeIt(const Graph& _graph, const Node& node) deba@2116: : graph(&_graph) { deba@2116: _graph.firstOut(*this, node); deba@2116: } deba@2116: deba@2116: OutEdgeIt(const Graph& _graph, const Edge& edge) deba@2116: : Edge(edge), graph(&_graph) {} deba@2116: deba@2116: OutEdgeIt& operator++() { deba@2116: graph->nextOut(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2116: class InEdgeIt : public Edge { deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: InEdgeIt() { } deba@2116: deba@2116: InEdgeIt(Invalid i) : Edge(i) { } deba@2116: deba@2116: InEdgeIt(const Graph& _graph, const Node& node) deba@2116: : graph(&_graph) { deba@2116: _graph.firstIn(*this, node); deba@2116: } deba@2116: deba@2116: InEdgeIt(const Graph& _graph, const Edge& edge) : deba@2116: Edge(edge), graph(&_graph) {} deba@2116: deba@2116: InEdgeIt& operator++() { deba@2116: graph->nextIn(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2116: class UEdgeIt : public Parent::UEdge { deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: UEdgeIt() { } deba@2116: deba@2116: UEdgeIt(Invalid i) : UEdge(i) { } deba@2116: deba@2116: explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { deba@2116: _graph.first(static_cast(*this)); deba@2116: } deba@2116: deba@2116: UEdgeIt(const Graph& _graph, const UEdge& e) : deba@2116: UEdge(e), graph(&_graph) { } deba@2116: deba@2116: UEdgeIt& operator++() { deba@2116: graph->next(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: class IncEdgeIt : public Parent::UEdge { deba@2116: friend class UGraphExtender; deba@2116: const Graph* graph; deba@2116: bool direction; deba@2116: public: deba@2116: deba@2116: IncEdgeIt() { } deba@2116: deba@2116: IncEdgeIt(Invalid i) : UEdge(i), direction(false) { } deba@2116: deba@2116: IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { deba@2116: _graph.firstInc(*this, direction, n); deba@2116: } deba@2116: deba@2116: IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) deba@2116: : graph(&_graph), UEdge(ue) { deba@2116: direction = (_graph.source(ue) == n); deba@2116: } deba@2116: deba@2116: IncEdgeIt& operator++() { deba@2116: graph->nextInc(*this, direction); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: /// \brief Base node of the iterator deba@2116: /// deba@2116: /// Returns the base node (ie. the source in this case) of the iterator deba@2116: Node baseNode(const OutEdgeIt &e) const { deba@2116: return Parent::source((Edge)e); deba@2116: } deba@2116: /// \brief Running node of the iterator deba@2116: /// deba@2116: /// Returns the running node (ie. the target in this case) of the deba@2116: /// iterator deba@2116: Node runningNode(const OutEdgeIt &e) const { deba@2116: return Parent::target((Edge)e); deba@2116: } deba@2116: deba@2116: /// \brief Base node of the iterator deba@2116: /// deba@2116: /// Returns the base node (ie. the target in this case) of the iterator deba@2116: Node baseNode(const InEdgeIt &e) const { deba@2116: return Parent::target((Edge)e); deba@2116: } deba@2116: /// \brief Running node of the iterator deba@2116: /// deba@2116: /// Returns the running node (ie. the source in this case) of the deba@2116: /// iterator deba@2116: Node runningNode(const InEdgeIt &e) const { deba@2116: return Parent::source((Edge)e); deba@2116: } deba@2116: deba@2116: /// Base node of the iterator deba@2116: /// deba@2116: /// Returns the base node of the iterator deba@2116: Node baseNode(const IncEdgeIt &e) const { deba@2116: return e.direction ? source(e) : target(e); deba@2116: } deba@2116: /// Running node of the iterator deba@2116: /// deba@2116: /// Returns the running node of the iterator deba@2116: Node runningNode(const IncEdgeIt &e) const { deba@2116: return e.direction ? target(e) : source(e); deba@2116: } deba@2116: deba@2116: // Mappable extension deba@2116: deba@2116: template deba@2116: class NodeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef UGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: NodeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: NodeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: NodeMap& operator=(const NodeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: NodeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: template deba@2116: class EdgeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef UGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: EdgeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: EdgeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: EdgeMap& operator=(const EdgeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: EdgeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: deba@2116: template deba@2116: class UEdgeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef UGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: UEdgeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: deba@2116: UEdgeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: UEdgeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: // Alteration extension deba@2116: deba@2116: Node addNode() { deba@2116: Node node = Parent::addNode(); deba@2116: getNotifier(Node()).add(node); deba@2116: return node; deba@2116: } deba@2116: deba@2116: UEdge addEdge(const Node& from, const Node& to) { deba@2116: UEdge uedge = Parent::addEdge(from, to); deba@2116: getNotifier(UEdge()).add(uedge); deba@2116: getNotifier(Edge()).add(Parent::direct(uedge, true)); deba@2116: getNotifier(Edge()).add(Parent::direct(uedge, false)); deba@2116: return uedge; deba@2116: } deba@2116: deba@2116: void clear() { deba@2116: getNotifier(Edge()).clear(); deba@2116: getNotifier(UEdge()).clear(); deba@2116: getNotifier(Node()).clear(); deba@2116: Parent::clear(); deba@2116: } deba@2116: deba@2116: void erase(const Node& node) { deba@2116: Edge edge; deba@2116: Parent::firstOut(edge, node); deba@2116: while (edge != INVALID ) { deba@2116: erase(edge); deba@2116: Parent::firstOut(edge, node); deba@2116: } deba@2116: deba@2116: Parent::firstIn(edge, node); deba@2116: while (edge != INVALID ) { deba@2116: erase(edge); deba@2116: Parent::firstIn(edge, node); deba@2116: } deba@2116: deba@2116: getNotifier(Node()).erase(node); deba@2116: Parent::erase(node); deba@2116: } deba@2116: deba@2116: void erase(const UEdge& uedge) { deba@2116: getNotifier(Edge()).erase(Parent::direct(uedge, true)); deba@2116: getNotifier(Edge()).erase(Parent::direct(uedge, false)); deba@2116: getNotifier(UEdge()).erase(uedge); deba@2116: Parent::erase(uedge); deba@2116: } deba@2116: deba@2116: UGraphExtender() { deba@2116: node_notifier.setContainer(*this); deba@2116: edge_notifier.setContainer(*this); deba@2116: uedge_notifier.setContainer(*this); deba@2116: } deba@2116: deba@2116: ~UGraphExtender() { deba@2116: uedge_notifier.clear(); deba@2116: edge_notifier.clear(); deba@2116: node_notifier.clear(); deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: /// \ingroup graphbits deba@2116: /// deba@2116: /// \brief Extender for the BpUGraphs deba@2116: template deba@2116: class BpUGraphExtender : public Base { deba@2116: public: deba@2116: typedef Base Parent; deba@2116: typedef BpUGraphExtender Graph; deba@2116: deba@2116: typedef typename Parent::Node Node; deba@2116: typedef typename Parent::UEdge UEdge; deba@2116: deba@2116: deba@2116: using Parent::first; deba@2116: using Parent::next; deba@2116: deba@2116: using Parent::id; deba@2116: deba@2116: class ANode : public Node { deba@2116: friend class BpUGraphExtender; deba@2116: public: deba@2116: ANode() {} deba@2116: ANode(const Node& node) : Node(node) { deba@2116: LEMON_ASSERT(Parent::aNode(node) || node == INVALID, deba@2116: typename Parent::NodeSetError()); deba@2116: } deba@2116: ANode(Invalid) : Node(INVALID) {} deba@2116: }; deba@2116: deba@2116: void first(ANode& node) const { deba@2116: Parent::firstANode(static_cast(node)); deba@2116: } deba@2116: void next(ANode& node) const { deba@2116: Parent::nextANode(static_cast(node)); deba@2116: } deba@2116: deba@2116: int id(const ANode& node) const { deba@2116: return Parent::aNodeId(node); deba@2116: } deba@2116: deba@2116: class BNode : public Node { deba@2116: friend class BpUGraphExtender; deba@2116: public: deba@2116: BNode() {} deba@2116: BNode(const Node& node) : Node(node) { deba@2116: LEMON_ASSERT(Parent::bNode(node) || node == INVALID, deba@2116: typename Parent::NodeSetError()); deba@2116: } deba@2116: BNode(Invalid) : Node(INVALID) {} deba@2116: }; deba@2116: deba@2116: void first(BNode& node) const { deba@2116: Parent::firstBNode(static_cast(node)); deba@2116: } deba@2116: void next(BNode& node) const { deba@2116: Parent::nextBNode(static_cast(node)); deba@2116: } deba@2116: deba@2116: int id(const BNode& node) const { deba@2116: return Parent::aNodeId(node); deba@2116: } deba@2116: deba@2116: Node source(const UEdge& edge) const { deba@2116: return aNode(edge); deba@2116: } deba@2116: Node target(const UEdge& edge) const { deba@2116: return bNode(edge); deba@2116: } deba@2116: deba@2116: void firstInc(UEdge& edge, bool& direction, const Node& node) const { deba@2116: if (Parent::aNode(node)) { deba@2116: Parent::firstFromANode(edge, node); deba@2116: direction = true; deba@2116: } else { deba@2116: Parent::firstFromBNode(edge, node); deba@2116: direction = static_cast(edge) == INVALID; deba@2116: } deba@2116: } deba@2116: void nextInc(UEdge& edge, bool& direction) const { deba@2116: if (direction) { deba@2116: Parent::nextFromANode(edge); deba@2116: } else { deba@2116: Parent::nextFromBNode(edge); deba@2116: if (edge == INVALID) direction = true; deba@2116: } deba@2116: } deba@2116: deba@2116: class Edge : public UEdge { deba@2116: friend class BpUGraphExtender; deba@2116: protected: deba@2116: bool forward; deba@2116: deba@2116: Edge(const UEdge& edge, bool _forward) deba@2116: : UEdge(edge), forward(_forward) {} deba@2116: deba@2116: public: deba@2116: Edge() {} deba@2116: Edge (Invalid) : UEdge(INVALID), forward(true) {} deba@2116: bool operator==(const Edge& i) const { deba@2116: return UEdge::operator==(i) && forward == i.forward; deba@2116: } deba@2116: bool operator!=(const Edge& i) const { deba@2116: return UEdge::operator!=(i) || forward != i.forward; deba@2116: } deba@2116: bool operator<(const Edge& i) const { deba@2116: return UEdge::operator<(i) || deba@2116: (!(i.forward(edge)); deba@2116: edge.forward = true; deba@2116: } deba@2116: deba@2116: void next(Edge& edge) const { deba@2116: if (!edge.forward) { deba@2116: Parent::next(static_cast(edge)); deba@2116: } deba@2116: edge.forward = !edge.forward; deba@2116: } deba@2116: deba@2116: void firstOut(Edge& edge, const Node& node) const { deba@2116: if (Parent::aNode(node)) { deba@2116: Parent::firstFromANode(edge, node); deba@2116: edge.forward = true; deba@2116: } else { deba@2116: Parent::firstFromBNode(edge, node); deba@2116: edge.forward = static_cast(edge) == INVALID; deba@2116: } deba@2116: } deba@2116: void nextOut(Edge& edge) const { deba@2116: if (edge.forward) { deba@2116: Parent::nextFromANode(edge); deba@2116: } else { deba@2116: Parent::nextFromBNode(edge); deba@2116: edge.forward = static_cast(edge) == INVALID; deba@2116: } deba@2116: } deba@2116: deba@2116: void firstIn(Edge& edge, const Node& node) const { deba@2116: if (Parent::bNode(node)) { deba@2116: Parent::firstFromBNode(edge, node); deba@2116: edge.forward = true; deba@2116: } else { deba@2116: Parent::firstFromANode(edge, node); deba@2116: edge.forward = static_cast(edge) == INVALID; deba@2116: } deba@2116: } deba@2116: void nextIn(Edge& edge) const { deba@2116: if (edge.forward) { deba@2116: Parent::nextFromBNode(edge); deba@2116: } else { deba@2116: Parent::nextFromANode(edge); deba@2116: edge.forward = static_cast(edge) == INVALID; deba@2116: } deba@2116: } deba@2116: deba@2116: Node source(const Edge& edge) const { deba@2116: return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge); deba@2116: } deba@2116: Node target(const Edge& edge) const { deba@2116: return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge); deba@2116: } deba@2116: deba@2116: int id(const Edge& edge) const { deba@2116: return (Parent::id(static_cast(edge)) << 1) + deba@2116: (edge.forward ? 0 : 1); deba@2116: } deba@2116: Edge edgeFromId(int id) const { deba@2116: return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0); deba@2116: } deba@2116: int maxEdgeId() const { deba@2116: return (Parent::maxUEdgeId(UEdge()) << 1) + 1; deba@2116: } deba@2116: deba@2116: bool direction(const Edge& edge) const { deba@2116: return edge.forward; deba@2116: } deba@2116: deba@2116: Edge direct(const UEdge& edge, bool direction) const { deba@2116: return Edge(edge, direction); deba@2116: } deba@2116: deba@2116: int edgeNum() const { deba@2116: return 2 * Parent::uEdgeNum(); deba@2116: } deba@2116: deba@2116: int uEdgeNum() const { deba@2116: return Parent::uEdgeNum(); deba@2116: } deba@2116: deba@2116: Node oppositeNode(const UEdge& edge, const Node& node) const { deba@2116: return source(edge) == node ? deba@2116: target(edge) : source(edge); deba@2116: } deba@2116: deba@2116: Edge direct(const UEdge& edge, const Node& node) const { deba@2116: return Edge(edge, node == Parent::source(edge)); deba@2116: } deba@2116: deba@2116: Edge oppositeEdge(const Edge& edge) const { deba@2116: return Parent::direct(edge, !Parent::direction(edge)); deba@2116: } deba@2116: deba@2116: deba@2116: int maxId(Node) const { deba@2116: return Parent::maxNodeId(); deba@2116: } deba@2116: int maxId(BNode) const { deba@2116: return Parent::maxBNodeId(); deba@2116: } deba@2116: int maxId(ANode) const { deba@2116: return Parent::maxANodeId(); deba@2116: } deba@2116: int maxId(Edge) const { deba@2116: return maxEdgeId(); deba@2116: } deba@2116: int maxId(UEdge) const { deba@2116: return Parent::maxUEdgeId(); deba@2116: } deba@2116: deba@2116: deba@2116: Node fromId(int id, Node) const { deba@2116: return Parent::nodeFromId(id); deba@2116: } deba@2116: ANode fromId(int id, ANode) const { deba@2116: return Parent::fromANodeId(id); deba@2116: } deba@2116: BNode fromId(int id, BNode) const { deba@2116: return Parent::fromBNodeId(id); deba@2116: } deba@2116: Edge fromId(int id, Edge) const { deba@2116: return Parent::edgeFromId(id); deba@2116: } deba@2116: UEdge fromId(int id, UEdge) const { deba@2116: return Parent::uEdgeFromId(id); deba@2116: } deba@2116: deba@2116: typedef AlterationNotifier ANodeNotifier; deba@2116: typedef AlterationNotifier BNodeNotifier; deba@2116: typedef AlterationNotifier NodeNotifier; deba@2116: typedef AlterationNotifier EdgeNotifier; deba@2116: typedef AlterationNotifier UEdgeNotifier; deba@2116: deba@2116: protected: deba@2116: deba@2116: mutable ANodeNotifier anode_notifier; deba@2116: mutable BNodeNotifier bnode_notifier; deba@2116: mutable NodeNotifier node_notifier; deba@2116: mutable EdgeNotifier edge_notifier; deba@2116: mutable UEdgeNotifier uedge_notifier; deba@2116: deba@2116: public: deba@2116: deba@2116: NodeNotifier& getNotifier(Node) const { deba@2116: return node_notifier; deba@2116: } deba@2116: deba@2116: ANodeNotifier& getNotifier(ANode) const { deba@2116: return anode_notifier; deba@2116: } deba@2116: deba@2116: BNodeNotifier& getNotifier(BNode) const { deba@2116: return bnode_notifier; deba@2116: } deba@2116: deba@2116: EdgeNotifier& getNotifier(Edge) const { deba@2116: return edge_notifier; deba@2116: } deba@2116: deba@2116: UEdgeNotifier& getNotifier(UEdge) const { deba@2116: return uedge_notifier; deba@2116: } deba@2116: deba@2116: class NodeIt : public Node { deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: NodeIt() { } deba@2116: deba@2116: NodeIt(Invalid i) : Node(INVALID) { } deba@2116: deba@2116: explicit NodeIt(const Graph& _graph) : graph(&_graph) { deba@2116: graph->first(static_cast(*this)); deba@2116: } deba@2116: deba@2116: NodeIt(const Graph& _graph, const Node& node) deba@2116: : Node(node), graph(&_graph) { } deba@2116: deba@2116: NodeIt& operator++() { deba@2116: graph->next(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: class ANodeIt : public Node { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: ANodeIt() { } deba@2116: deba@2116: ANodeIt(Invalid i) : Node(INVALID) { } deba@2116: deba@2116: explicit ANodeIt(const Graph& _graph) : graph(&_graph) { deba@2116: graph->firstANode(static_cast(*this)); deba@2116: } deba@2116: deba@2116: ANodeIt(const Graph& _graph, const Node& node) deba@2116: : Node(node), graph(&_graph) {} deba@2116: deba@2116: ANodeIt& operator++() { deba@2116: graph->nextANode(*this); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: class BNodeIt : public Node { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: BNodeIt() { } deba@2116: deba@2116: BNodeIt(Invalid i) : Node(INVALID) { } deba@2116: deba@2116: explicit BNodeIt(const Graph& _graph) : graph(&_graph) { deba@2116: graph->firstBNode(static_cast(*this)); deba@2116: } deba@2116: deba@2116: BNodeIt(const Graph& _graph, const Node& node) deba@2116: : Node(node), graph(&_graph) {} deba@2116: deba@2116: BNodeIt& operator++() { deba@2116: graph->nextBNode(*this); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: class EdgeIt : public Edge { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: EdgeIt() { } deba@2116: deba@2116: EdgeIt(Invalid i) : Edge(INVALID) { } deba@2116: deba@2116: explicit EdgeIt(const Graph& _graph) : graph(&_graph) { deba@2116: graph->first(static_cast(*this)); deba@2116: } deba@2116: deba@2116: EdgeIt(const Graph& _graph, const Edge& edge) deba@2116: : Edge(edge), graph(&_graph) { } deba@2116: deba@2116: EdgeIt& operator++() { deba@2116: graph->next(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: class UEdgeIt : public UEdge { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: UEdgeIt() { } deba@2116: deba@2116: UEdgeIt(Invalid i) : UEdge(INVALID) { } deba@2116: deba@2116: explicit UEdgeIt(const Graph& _graph) : graph(&_graph) { deba@2116: graph->first(static_cast(*this)); deba@2116: } deba@2116: deba@2116: UEdgeIt(const Graph& _graph, const UEdge& edge) deba@2116: : UEdge(edge), graph(&_graph) { } deba@2116: deba@2116: UEdgeIt& operator++() { deba@2116: graph->next(*this); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: class OutEdgeIt : public Edge { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: OutEdgeIt() { } deba@2116: deba@2116: OutEdgeIt(Invalid i) : Edge(i) { } deba@2116: deba@2116: OutEdgeIt(const Graph& _graph, const Node& node) deba@2116: : graph(&_graph) { deba@2116: graph->firstOut(*this, node); deba@2116: } deba@2116: deba@2116: OutEdgeIt(const Graph& _graph, const Edge& edge) deba@2116: : Edge(edge), graph(&_graph) {} deba@2116: deba@2116: OutEdgeIt& operator++() { deba@2116: graph->nextOut(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: deba@2116: class InEdgeIt : public Edge { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: public: deba@2116: deba@2116: InEdgeIt() { } deba@2116: deba@2116: InEdgeIt(Invalid i) : Edge(i) { } deba@2116: deba@2116: InEdgeIt(const Graph& _graph, const Node& node) deba@2116: : graph(&_graph) { deba@2116: graph->firstIn(*this, node); deba@2116: } deba@2116: deba@2116: InEdgeIt(const Graph& _graph, const Edge& edge) : deba@2116: Edge(edge), graph(&_graph) {} deba@2116: deba@2116: InEdgeIt& operator++() { deba@2116: graph->nextIn(*this); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: /// \brief Base node of the iterator deba@2116: /// deba@2116: /// Returns the base node (ie. the source in this case) of the iterator deba@2116: Node baseNode(const OutEdgeIt &e) const { deba@2116: return Parent::source((Edge&)e); deba@2116: } deba@2116: /// \brief Running node of the iterator deba@2116: /// deba@2116: /// Returns the running node (ie. the target in this case) of the deba@2116: /// iterator deba@2116: Node runningNode(const OutEdgeIt &e) const { deba@2116: return Parent::target((Edge&)e); deba@2116: } deba@2116: deba@2116: /// \brief Base node of the iterator deba@2116: /// deba@2116: /// Returns the base node (ie. the target in this case) of the iterator deba@2116: Node baseNode(const InEdgeIt &e) const { deba@2116: return Parent::target((Edge&)e); deba@2116: } deba@2116: /// \brief Running node of the iterator deba@2116: /// deba@2116: /// Returns the running node (ie. the source in this case) of the deba@2116: /// iterator deba@2116: Node runningNode(const InEdgeIt &e) const { deba@2116: return Parent::source((Edge&)e); deba@2116: } deba@2116: deba@2116: class IncEdgeIt : public Parent::UEdge { deba@2116: friend class BpUGraphExtender; deba@2116: const Graph* graph; deba@2116: bool direction; deba@2116: public: deba@2116: deba@2116: IncEdgeIt() { } deba@2116: deba@2116: IncEdgeIt(Invalid i) : UEdge(i), direction(true) { } deba@2116: deba@2116: IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { deba@2116: graph->firstInc(*this, direction, n); deba@2116: } deba@2116: deba@2116: IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n) deba@2116: : graph(&_graph), UEdge(ue) { deba@2116: direction = (graph->source(ue) == n); deba@2116: } deba@2116: deba@2116: IncEdgeIt& operator++() { deba@2116: graph->nextInc(*this, direction); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: deba@2116: /// Base node of the iterator deba@2116: /// deba@2116: /// Returns the base node of the iterator deba@2116: Node baseNode(const IncEdgeIt &e) const { deba@2116: return e.direction ? source(e) : target(e); deba@2116: } deba@2116: deba@2116: /// Running node of the iterator deba@2116: /// deba@2116: /// Returns the running node of the iterator deba@2116: Node runningNode(const IncEdgeIt &e) const { deba@2116: return e.direction ? target(e) : source(e); deba@2116: } deba@2116: deba@2116: template deba@2116: class ANodeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef BpUGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: ANodeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: ANodeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: ANodeMap& operator=(const ANodeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: ANodeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: template deba@2116: class BNodeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef BpUGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: BNodeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: BNodeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: BNodeMap& operator=(const BNodeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: BNodeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: deba@2116: }; deba@2116: deba@2116: public: deba@2116: deba@2116: template deba@2116: class NodeMap { deba@2116: public: deba@2116: typedef BpUGraphExtender Graph; deba@2116: deba@2116: typedef Node Key; deba@2116: typedef _Value Value; deba@2116: deba@2116: /// The reference type of the map; deba@2116: typedef typename ANodeMap<_Value>::Reference Reference; deba@2116: /// The const reference type of the map; deba@2116: typedef typename ANodeMap<_Value>::ConstReference ConstReference; deba@2116: deba@2116: typedef True ReferenceMapTag; deba@2116: deba@2116: NodeMap(const Graph& _graph) deba@2116: : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {} deba@2116: NodeMap(const Graph& _graph, const _Value& _value) deba@2116: : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {} deba@2116: deba@2116: NodeMap& operator=(const NodeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: NodeMap& operator=(const CMap& cmap) { deba@2116: checkConcept, CMap>(); deba@2116: const typename Parent::Notifier* notifier = Parent::getNotifier(); deba@2116: Edge it; deba@2116: for (graph.first(it); it != INVALID; graph.next(it)) { deba@2116: Parent::set(it, cmap[it]); deba@2116: } deba@2116: return *this; deba@2116: } deba@2116: deba@2116: ConstReference operator[](const Key& node) const { deba@2116: if (Parent::aNode(node)) { deba@2116: return aNodeMap[node]; deba@2116: } else { deba@2116: return bNodeMap[node]; deba@2116: } deba@2116: } deba@2116: deba@2116: Reference operator[](const Key& node) { deba@2116: if (Parent::aNode(node)) { deba@2116: return aNodeMap[node]; deba@2116: } else { deba@2116: return bNodeMap[node]; deba@2116: } deba@2116: } deba@2116: deba@2116: void set(const Key& node, const Value& value) { deba@2116: if (Parent::aNode(node)) { deba@2116: aNodeMap.set(node, value); deba@2116: } else { deba@2116: bNodeMap.set(node, value); deba@2116: } deba@2116: } deba@2116: deba@2116: class MapIt : public NodeIt { deba@2116: public: deba@2116: deba@2116: typedef NodeIt Parent; deba@2116: deba@2116: explicit MapIt(NodeMap& _map) deba@2116: : Parent(_map.graph), map(_map) {} deba@2116: deba@2116: typename MapTraits::ConstReturnValue operator*() const { deba@2116: return map[*this]; deba@2116: } deba@2116: deba@2116: typename MapTraits::ReturnValue operator*() { deba@2116: return map[*this]; deba@2116: } deba@2116: deba@2116: void set(const Value& value) { deba@2116: map.set(*this, value); deba@2116: } deba@2116: deba@2116: private: deba@2116: NodeMap& map; deba@2116: }; deba@2116: deba@2116: class ConstMapIt : public NodeIt { deba@2116: public: deba@2116: deba@2116: typedef NodeIt Parent; deba@2116: deba@2116: explicit ConstMapIt(const NodeMap& _map) deba@2116: : Parent(_map.graph), map(_map) {} deba@2116: deba@2116: typename MapTraits::ConstReturnValue operator*() const { deba@2116: return map[*this]; deba@2116: } deba@2116: deba@2116: private: deba@2116: const NodeMap& map; deba@2116: }; deba@2116: deba@2116: class ItemIt : public NodeIt { deba@2116: public: deba@2116: deba@2116: typedef NodeIt Parent; deba@2116: deba@2116: explicit ItemIt(const NodeMap& _map) deba@2116: : Parent(_map.graph) {} deba@2116: deba@2116: }; deba@2116: deba@2116: private: deba@2116: const Graph& graph; deba@2116: ANodeMap<_Value> aNodeMap; deba@2116: BNodeMap<_Value> bNodeMap; deba@2116: }; deba@2116: deba@2116: deba@2116: template deba@2116: class EdgeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef BpUGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: EdgeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: EdgeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: EdgeMap& operator=(const EdgeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: EdgeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: template deba@2116: class UEdgeMap deba@2116: : public MapExtender > { deba@2116: public: deba@2116: typedef BpUGraphExtender Graph; deba@2116: typedef MapExtender > Parent; deba@2116: deba@2116: UEdgeMap(const Graph& graph) deba@2116: : Parent(graph) {} deba@2116: UEdgeMap(const Graph& graph, const _Value& value) deba@2116: : Parent(graph, value) {} deba@2116: deba@2116: UEdgeMap& operator=(const UEdgeMap& cmap) { deba@2116: return operator=(cmap); deba@2116: } deba@2116: deba@2116: template deba@2116: UEdgeMap& operator=(const CMap& cmap) { deba@2116: Parent::operator=(cmap); deba@2116: return *this; deba@2116: } deba@2116: }; deba@2116: deba@2116: deba@2116: Node addANode() { deba@2116: Node node = Parent::addANode(); deba@2116: getNotifier(ANode()).add(node); deba@2116: getNotifier(Node()).add(node); deba@2116: return node; deba@2116: } deba@2116: deba@2116: Node addBNode() { deba@2116: Node node = Parent::addBNode(); deba@2116: getNotifier(BNode()).add(node); deba@2116: getNotifier(Node()).add(node); deba@2116: return node; deba@2116: } deba@2116: deba@2116: UEdge addEdge(const Node& source, const Node& target) { deba@2116: UEdge uedge = Parent::addEdge(source, target); deba@2116: getNotifier(UEdge()).add(uedge); deba@2116: deba@2116: std::vector edges; deba@2116: edges.push_back(direct(uedge, true)); deba@2116: edges.push_back(direct(uedge, false)); deba@2116: getNotifier(Edge()).add(edges); deba@2116: deba@2116: return uedge; deba@2116: } deba@2116: deba@2116: void clear() { deba@2116: getNotifier(Edge()).clear(); deba@2116: getNotifier(UEdge()).clear(); deba@2116: getNotifier(Node()).clear(); deba@2116: getNotifier(BNode()).clear(); deba@2116: getNotifier(ANode()).clear(); deba@2116: Parent::clear(); deba@2116: } deba@2116: deba@2116: void erase(const Node& node) { deba@2116: UEdge uedge; deba@2116: if (Parent::aNode(node)) { deba@2116: Parent::firstFromANode(uedge, node); deba@2116: while (uedge != INVALID) { deba@2116: erase(uedge); deba@2116: Parent::firstFromANode(uedge, node); deba@2116: } deba@2203: getNotifier(ANode()).erase(node); deba@2116: } else { deba@2116: Parent::firstFromBNode(uedge, node); deba@2116: while (uedge != INVALID) { deba@2116: erase(uedge); deba@2116: Parent::firstFromBNode(uedge, node); deba@2116: } deba@2203: getNotifier(BNode()).erase(node); deba@2116: } deba@2116: deba@2116: getNotifier(Node()).erase(node); deba@2116: Parent::erase(node); deba@2116: } deba@2116: deba@2116: void erase(const UEdge& uedge) { deba@2116: std::vector edges; deba@2116: edges.push_back(direct(uedge, true)); deba@2116: edges.push_back(direct(uedge, false)); deba@2116: getNotifier(Edge()).erase(edges); deba@2116: getNotifier(UEdge()).erase(uedge); deba@2116: Parent::erase(uedge); deba@2116: } deba@2116: deba@2116: deba@2116: BpUGraphExtender() { deba@2116: anode_notifier.setContainer(*this); deba@2116: bnode_notifier.setContainer(*this); deba@2116: node_notifier.setContainer(*this); deba@2116: edge_notifier.setContainer(*this); deba@2116: uedge_notifier.setContainer(*this); deba@2116: } deba@2116: deba@2116: ~BpUGraphExtender() { deba@2116: uedge_notifier.clear(); deba@2116: edge_notifier.clear(); deba@2116: node_notifier.clear(); deba@2116: anode_notifier.clear(); deba@2116: bnode_notifier.clear(); deba@2116: } deba@2116: deba@2222: Edge findEdge(Node u, Node v, Edge prev = INVALID) const { deba@2222: UEdge uedge = Parent::findUEdge(u, v, prev); deba@2222: if (uedge != INVALID) { deba@2222: return direct(uedge, Parent::aNode(u)); deba@2222: } else { deba@2222: return INVALID; deba@2222: } deba@2222: } deba@2116: deba@2116: }; deba@2116: deba@1791: } deba@1791: deba@1996: #endif