Changeset 1019:4c89e925cfe2 in lemon-main for lemon/bits

Timestamp:

11/14/10 20:06:23 (13 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

SmartBpGraph? implementation (#69)

Location:

lemon/bits

Files:

• graph_extender.h (modified) (1 diff)
• traits.h (modified) (1 diff)

lemon/bits/graph_extender.h

@@ -747 +747 @@
   };
 
+  // \ingroup _graphbits
+  //
+  // \brief Extender for the BpGraphs
+  template <typename Base>
+  class BpGraphExtender : public Base {
+    typedef Base Parent;
+
+  public:
+
+    typedef BpGraphExtender BpGraph;
+
+    typedef True UndirectedTag;
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Arc Arc;
+    typedef typename Parent::Edge Edge;
+
+    // BpGraph extension
+
+    class RedNode : public Node {
+    public:
+      RedNode() {}
+      RedNode(const RedNode& node) : Node(node) {}
+      RedNode(Invalid) : Node(INVALID){}
+      RedNode(const Node& node) : Node(node) {}
+    };
+    class BlueNode : public Node {
+    public:
+      BlueNode() {}
+      BlueNode(const BlueNode& node) : Node(node) {}
+      BlueNode(Invalid) : Node(INVALID){}
+      BlueNode(const Node& node) : Node(node) {}
+    };
+
+    using Parent::first;
+    using Parent::next;
+
+    void first(RedNode& node) const {
+      Parent::firstRed(node);
+    }
+    
+    void next(RedNode& node) const {
+      Parent::nextRed(node);
+    }
+
+    void first(BlueNode& node) const {
+      Parent::firstBlue(node);
+    }
+
+    void next(BlueNode& node) const {
+      Parent::nextBlue(node);
+    }
+
+    using Parent::id;
+
+    int id(const RedNode& node) const {
+      return Parent::redId(node);
+    }
+
+    int id(const BlueNode& node) const {
+      return Parent::blueId(node);
+    }
+
+    int maxId(Node) const {
+      return Parent::maxNodeId();
+    }
+
+    int maxId(RedNode) const {
+      return Parent::maxRedId();
+    }
+
+    int maxId(BlueNode) const {
+      return Parent::maxBlueId();
+    }
+
+    int maxId(Arc) const {
+      return Parent::maxArcId();
+    }
+
+    int maxId(Edge) const {
+      return Parent::maxEdgeId();
+    }
+
+    static Node fromId(int id, Node) {
+      return Parent::nodeFromId(id);
+    }
+
+    static Arc fromId(int id, Arc) {
+      return Parent::arcFromId(id);
+    }
+
+    static Edge fromId(int id, Edge) {
+      return Parent::edgeFromId(id);
+    }
+
+    Node oppositeNode(const Node &n, const Edge &e) const {
+      if( n == Parent::u(e))
+        return Parent::v(e);
+      else if( n == Parent::v(e))
+        return Parent::u(e);
+      else
+        return INVALID;
+    }
+
+    Arc oppositeArc(const Arc &arc) const {
+      return Parent::direct(arc, !Parent::direction(arc));
+    }
+
+    using Parent::direct;
+    Arc direct(const Edge &edge, const Node &node) const {
+      return Parent::direct(edge, Parent::u(edge) == node);
+    }
+
+    // Alterable extension
+
+    typedef AlterationNotifier<BpGraphExtender, Node> NodeNotifier;
+    typedef AlterationNotifier<BpGraphExtender, RedNode> RedNodeNotifier; 
+    typedef AlterationNotifier<BpGraphExtender, BlueNode> BlueNodeNotifier;
+    typedef AlterationNotifier<BpGraphExtender, Arc> ArcNotifier;
+    typedef AlterationNotifier<BpGraphExtender, Edge> EdgeNotifier;
+
+
+  protected:
+
+    mutable NodeNotifier node_notifier;
+    mutable RedNodeNotifier red_node_notifier;
+    mutable BlueNodeNotifier blue_node_notifier;
+    mutable ArcNotifier arc_notifier;
+    mutable EdgeNotifier edge_notifier;
+
+  public:
+
+    NodeNotifier& notifier(Node) const {
+      return node_notifier;
+    }
+
+    RedNodeNotifier& notifier(RedNode) const {
+      return red_node_notifier;
+    }
+
+    BlueNodeNotifier& notifier(BlueNode) const {
+      return blue_node_notifier;
+    }
+
+    ArcNotifier& notifier(Arc) const {
+      return arc_notifier;
+    }
+
+    EdgeNotifier& notifier(Edge) const {
+      return edge_notifier;
+    }
+
+
+
+    class NodeIt : public Node {
+      const BpGraph* _graph;
+    public:
+
+      NodeIt() {}
+
+      NodeIt(Invalid i) : Node(i) { }
+
+      explicit NodeIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<Node&>(*this));
+      }
+
+      NodeIt(const BpGraph& graph, const Node& node)
+        : Node(node), _graph(&graph) {}
+
+      NodeIt& operator++() {
+        _graph->next(*this);
+        return *this;
+      }
+
+    };
+
+    class RedIt : public Node {
+      const BpGraph* _graph;
+    public:
+
+      RedIt() {}
+
+      RedIt(Invalid i) : Node(i) { }
+
+      explicit RedIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->firstRed(static_cast<Node&>(*this));
+      }
+
+      RedIt(const BpGraph& graph, const Node& node)
+        : Node(node), _graph(&graph) {
+        LEMON_DEBUG(_graph->red(node), "Node has to be red.");
+      }
+
+      RedIt& operator++() {
+        _graph->nextRed(*this);
+        return *this;
+      }
+
+    };
+
+    class BlueIt : public Node {
+      const BpGraph* _graph;
+    public:
+
+      BlueIt() {}
+
+      BlueIt(Invalid i) : Node(i) { }
+
+      explicit BlueIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->firstBlue(static_cast<Node&>(*this));
+      }
+
+      BlueIt(const BpGraph& graph, const Node& node)
+        : Node(node), _graph(&graph) {
+        LEMON_DEBUG(_graph->blue(node), "Node has to be blue.");
+      }
+
+      BlueIt& operator++() {
+        _graph->nextBlue(*this);
+        return *this;
+      }
+
+    };
+
+
+    class ArcIt : public Arc {
+      const BpGraph* _graph;
+    public:
+
+      ArcIt() { }
+
+      ArcIt(Invalid i) : Arc(i) { }
+
+      explicit ArcIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<Arc&>(*this));
+      }
+
+      ArcIt(const BpGraph& graph, const Arc& arc) :
+        Arc(arc), _graph(&graph) { }
+
+      ArcIt& operator++() {
+        _graph->next(*this);
+        return *this;
+      }
+
+    };
+
+
+    class OutArcIt : public Arc {
+      const BpGraph* _graph;
+    public:
+
+      OutArcIt() { }
+
+      OutArcIt(Invalid i) : Arc(i) { }
+
+      OutArcIt(const BpGraph& graph, const Node& node)
+        : _graph(&graph) {
+        _graph->firstOut(*this, node);
+      }
+
+      OutArcIt(const BpGraph& graph, const Arc& arc)
+        : Arc(arc), _graph(&graph) {}
+
+      OutArcIt& operator++() {
+        _graph->nextOut(*this);
+        return *this;
+      }
+
+    };
+
+
+    class InArcIt : public Arc {
+      const BpGraph* _graph;
+    public:
+
+      InArcIt() { }
+
+      InArcIt(Invalid i) : Arc(i) { }
+
+      InArcIt(const BpGraph& graph, const Node& node)
+        : _graph(&graph) {
+        _graph->firstIn(*this, node);
+      }
+
+      InArcIt(const BpGraph& graph, const Arc& arc) :
+        Arc(arc), _graph(&graph) {}
+
+      InArcIt& operator++() {
+        _graph->nextIn(*this);
+        return *this;
+      }
+
+    };
+
+
+    class EdgeIt : public Parent::Edge {
+      const BpGraph* _graph;
+    public:
+
+      EdgeIt() { }
+
+      EdgeIt(Invalid i) : Edge(i) { }
+
+      explicit EdgeIt(const BpGraph& graph) : _graph(&graph) {
+        _graph->first(static_cast<Edge&>(*this));
+      }
+
+      EdgeIt(const BpGraph& graph, const Edge& edge) :
+        Edge(edge), _graph(&graph) { }
+
+      EdgeIt& operator++() {
+        _graph->next(*this);
+        return *this;
+      }
+
+    };
+
+    class IncEdgeIt : public Parent::Edge {
+      friend class BpGraphExtender;
+      const BpGraph* _graph;
+      bool _direction;
+    public:
+
+      IncEdgeIt() { }
+
+      IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
+
+      IncEdgeIt(const BpGraph& graph, const Node &node) : _graph(&graph) {
+        _graph->firstInc(*this, _direction, node);
+      }
+
+      IncEdgeIt(const BpGraph& graph, const Edge &edge, const Node &node)
+        : _graph(&graph), Edge(edge) {
+        _direction = (_graph->source(edge) == node);
+      }
+
+      IncEdgeIt& operator++() {
+        _graph->nextInc(*this, _direction);
+        return *this;
+      }
+    };
+
+    // \brief Base node of the iterator
+    //
+    // Returns the base node (ie. the source in this case) of the iterator
+    Node baseNode(const OutArcIt &arc) const {
+      return Parent::source(static_cast<const Arc&>(arc));
+    }
+    // \brief Running node of the iterator
+    //
+    // Returns the running node (ie. the target in this case) of the
+    // iterator
+    Node runningNode(const OutArcIt &arc) const {
+      return Parent::target(static_cast<const Arc&>(arc));
+    }
+
+    // \brief Base node of the iterator
+    //
+    // Returns the base node (ie. the target in this case) of the iterator
+    Node baseNode(const InArcIt &arc) const {
+      return Parent::target(static_cast<const Arc&>(arc));
+    }
+    // \brief Running node of the iterator
+    //
+    // Returns the running node (ie. the source in this case) of the
+    // iterator
+    Node runningNode(const InArcIt &arc) const {
+      return Parent::source(static_cast<const Arc&>(arc));
+    }
+
+    // Base node of the iterator
+    //
+    // Returns the base node of the iterator
+    Node baseNode(const IncEdgeIt &edge) const {
+      return edge._direction ? this->u(edge) : this->v(edge);
+    }
+    // Running node of the iterator
+    //
+    // Returns the running node of the iterator
+    Node runningNode(const IncEdgeIt &edge) const {
+      return edge._direction ? this->v(edge) : this->u(edge);
+    }
+
+    // Mappable extension
+
+    template <typename _Value>
+    class NodeMap
+      : public MapExtender<DefaultMap<BpGraph, Node, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, Node, _Value> > Parent;
+
+    public:
+      explicit NodeMap(const BpGraph& bpgraph)
+        : Parent(bpgraph) {}
+      NodeMap(const BpGraph& bpgraph, const _Value& value)
+        : Parent(bpgraph, value) {}
+
+    private:
+      NodeMap& operator=(const NodeMap& cmap) {
+        return operator=<NodeMap>(cmap);
+      }
+
+      template <typename CMap>
+      NodeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+
+    };
+
+    template <typename _Value>
+    class RedMap
+      : public MapExtender<DefaultMap<BpGraph, RedNode, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, RedNode, _Value> > Parent;
+
+    public:
+      explicit RedMap(const BpGraph& bpgraph)
+        : Parent(bpgraph) {}
+      RedMap(const BpGraph& bpgraph, const _Value& value)
+        : Parent(bpgraph, value) {}
+
+    private:
+      RedMap& operator=(const RedMap& cmap) {
+        return operator=<RedMap>(cmap);
+      }
+
+      template <typename CMap>
+      RedMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+
+    };
+
+    template <typename _Value>
+    class BlueMap
+      : public MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, BlueNode, _Value> > Parent;
+
+    public:
+      explicit BlueMap(const BpGraph& bpgraph)
+        : Parent(bpgraph) {}
+      BlueMap(const BpGraph& bpgraph, const _Value& value)
+        : Parent(bpgraph, value) {}
+
+    private:
+      BlueMap& operator=(const BlueMap& cmap) {
+        return operator=<BlueMap>(cmap);
+      }
+
+      template <typename CMap>
+      BlueMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+
+    };
+
+    template <typename _Value>
+    class ArcMap
+      : public MapExtender<DefaultMap<BpGraph, Arc, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, Arc, _Value> > Parent;
+
+    public:
+      explicit ArcMap(const BpGraph& graph)
+        : Parent(graph) {}
+      ArcMap(const BpGraph& graph, const _Value& value)
+        : Parent(graph, value) {}
+
+    private:
+      ArcMap& operator=(const ArcMap& cmap) {
+        return operator=<ArcMap>(cmap);
+      }
+
+      template <typename CMap>
+      ArcMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+    };
+
+
+    template <typename _Value>
+    class EdgeMap
+      : public MapExtender<DefaultMap<BpGraph, Edge, _Value> > {
+      typedef MapExtender<DefaultMap<BpGraph, Edge, _Value> > Parent;
+
+    public:
+      explicit EdgeMap(const BpGraph& graph)
+        : Parent(graph) {}
+
+      EdgeMap(const BpGraph& graph, const _Value& value)
+        : Parent(graph, value) {}
+
+    private:
+      EdgeMap& operator=(const EdgeMap& cmap) {
+        return operator=<EdgeMap>(cmap);
+      }
+
+      template <typename CMap>
+      EdgeMap& operator=(const CMap& cmap) {
+        Parent::operator=(cmap);
+        return *this;
+      }
+
+    };
+
+    // Alteration extension
+
+    Node addRedNode() {
+      Node node = Parent::addRedNode();
+      notifier(RedNode()).add(node);
+      notifier(Node()).add(node);
+      return node;
+    }
+
+    Node addBlueNode() {
+      Node node = Parent::addBlueNode();
+      notifier(BlueNode()).add(node);
+      notifier(Node()).add(node);
+      return node;
+    }
+
+    Edge addEdge(const Node& from, const Node& to) {
+      Edge edge = Parent::addEdge(from, to);
+      notifier(Edge()).add(edge);
+      std::vector<Arc> av;
+      av.push_back(Parent::direct(edge, true));
+      av.push_back(Parent::direct(edge, false));
+      notifier(Arc()).add(av);
+      return edge;
+    }
+
+    void clear() {
+      notifier(Arc()).clear();
+      notifier(Edge()).clear();
+      notifier(Node()).clear();
+      notifier(BlueNode()).clear();
+      notifier(RedNode()).clear();
+      Parent::clear();
+    }
+
+    template <typename BpGraph, typename NodeRefMap, typename EdgeRefMap>
+    void build(const BpGraph& graph, NodeRefMap& nodeRef,
+               EdgeRefMap& edgeRef) {
+      Parent::build(graph, nodeRef, edgeRef);
+      notifier(RedNode()).build();
+      notifier(BlueNode()).build();
+      notifier(Node()).build();
+      notifier(Edge()).build();
+      notifier(Arc()).build();
+    }
+
+    void erase(const Node& node) {
+      Arc arc;
+      Parent::firstOut(arc, node);
+      while (arc != INVALID ) {
+        erase(arc);
+        Parent::firstOut(arc, node);
+      }
+
+      Parent::firstIn(arc, node);
+      while (arc != INVALID ) {
+        erase(arc);
+        Parent::firstIn(arc, node);
+      }
+
+      if (Parent::red(node)) {
+        notifier(RedNode()).erase(node);
+      } else {
+        notifier(BlueNode()).erase(node);        
+      }
+
+      notifier(Node()).erase(node);
+      Parent::erase(node);
+    }
+
+    void erase(const Edge& edge) {
+      std::vector<Arc> av;
+      av.push_back(Parent::direct(edge, true));
+      av.push_back(Parent::direct(edge, false));
+      notifier(Arc()).erase(av);
+      notifier(Edge()).erase(edge);
+      Parent::erase(edge);
+    }
+
+    BpGraphExtender() {
+      red_node_notifier.setContainer(*this);
+      blue_node_notifier.setContainer(*this);
+      node_notifier.setContainer(*this);
+      arc_notifier.setContainer(*this);
+      edge_notifier.setContainer(*this);
+    }
+
+    ~BpGraphExtender() {
+      edge_notifier.clear();
+      arc_notifier.clear();
+      node_notifier.clear();
+      blue_node_notifier.clear();
+      red_node_notifier.clear();
+    }
+
+  };
+
 }
 

lemon/bits/traits.h

@@ -149 +149 @@
         : Parent(_digraph, _value) {}
     };
+
+  };
+
+  template <typename GR, typename Enable = void>
+  struct RedNodeNotifierIndicator {
+    typedef InvalidType Type;
+  };
+  template <typename GR>
+  struct RedNodeNotifierIndicator<
+    GR,
+    typename enable_if<typename GR::RedNodeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::RedNodeNotifier Type;
+  };
+
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::RedNode> {
+  public:
+
+    typedef GR BpGraph;
+    typedef GR Graph;
+    typedef GR Digraph;
+
+    typedef typename GR::RedNode Item;
+    typedef typename GR::RedIt ItemIt;
+
+    typedef typename RedNodeNotifierIndicator<GR>::Type ItemNotifier;
+
+    template <typename V>
+    class Map : public GR::template RedMap<V> {
+      typedef typename GR::template RedMap<V> Parent;
+
+    public:
+      typedef typename GR::template RedMap<V> Type;
+      typedef typename Parent::Value Value;
+
+      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
+      Map(const GR& _bpgraph, const Value& _value)
+        : Parent(_bpgraph, _value) {}
+
+     };
+
+  };
+
+  template <typename GR, typename Enable = void>
+  struct BlueNodeNotifierIndicator {
+    typedef InvalidType Type;
+  };
+  template <typename GR>
+  struct BlueNodeNotifierIndicator<
+    GR,
+    typename enable_if<typename GR::BlueNodeNotifier::Notifier, void>::type
+  > {
+    typedef typename GR::BlueNodeNotifier Type;
+  };
+
+  template <typename GR>
+  class ItemSetTraits<GR, typename GR::BlueNode> {
+  public:
+
+    typedef GR BpGraph;
+    typedef GR Graph;
+    typedef GR Digraph;
+
+    typedef typename GR::BlueNode Item;
+    typedef typename GR::BlueIt ItemIt;
+
+    typedef typename BlueNodeNotifierIndicator<GR>::Type ItemNotifier;
+
+    template <typename V>
+    class Map : public GR::template BlueMap<V> {
+      typedef typename GR::template BlueMap<V> Parent;
+
+    public:
+      typedef typename GR::template BlueMap<V> Type;
+      typedef typename Parent::Value Value;
+
+      Map(const GR& _bpgraph) : Parent(_bpgraph) {}
+      Map(const GR& _bpgraph, const Value& _value)
+        : Parent(_bpgraph, _value) {}
+
+     };
 
   };