Various bug fixes and code improvements in adaptors.h (#67)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 12 Dec 2008 22:59:17 +0100
changeset 44991fcb8ed4cdc
parent 448 9d9990909fc8
child 450 14bb8812b8af
Various bug fixes and code improvements in adaptors.h (#67)

- Fix UndirectorBase::nodeNum().
- Fix UndirectorBase::findEdge().
- Fix OrienterBase::addArc().
- Fix OrienterBase::findArc().
- Improve SplitNodesBase::findArc().
- Add missing notifier() function in UndirectorBase.
- Add missing typedefs for maps (conform to the ReferenceMap concept).
- Add some useful typedefs for graph adaptors.
lemon/adaptors.h
     1.1 --- a/lemon/adaptors.h	Fri Dec 12 22:18:41 2008 +0100
     1.2 +++ b/lemon/adaptors.h	Fri Dec 12 22:59:17 2008 +0100
     1.3 @@ -817,11 +817,14 @@
     1.4    }
     1.5  
     1.6  
     1.7 -  template <typename _Graph, typename NodeFilterMap,
     1.8 -            typename EdgeFilterMap, bool _checked = true>
     1.9 +  template <typename _Graph, typename _NodeFilterMap,
    1.10 +            typename _EdgeFilterMap, bool _checked = true>
    1.11    class SubGraphBase : public GraphAdaptorBase<_Graph> {
    1.12    public:
    1.13      typedef _Graph Graph;
    1.14 +    typedef _NodeFilterMap NodeFilterMap;
    1.15 +    typedef _EdgeFilterMap EdgeFilterMap;
    1.16 +
    1.17      typedef SubGraphBase Adaptor;
    1.18      typedef GraphAdaptorBase<_Graph> Parent;
    1.19    protected:
    1.20 @@ -1048,11 +1051,14 @@
    1.21  
    1.22    };
    1.23  
    1.24 -  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
    1.25 -  class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
    1.26 +  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
    1.27 +  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
    1.28      : public GraphAdaptorBase<_Graph> {
    1.29    public:
    1.30      typedef _Graph Graph;
    1.31 +    typedef _NodeFilterMap NodeFilterMap;
    1.32 +    typedef _EdgeFilterMap EdgeFilterMap;
    1.33 +
    1.34      typedef SubGraphBase Adaptor;
    1.35      typedef GraphAdaptorBase<_Graph> Parent;
    1.36    protected:
    1.37 @@ -1857,7 +1863,7 @@
    1.38      void clear() { _digraph->clear(); }
    1.39  
    1.40      typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    1.41 -    int nodeNum() const { return 2 * _digraph->arcNum(); }
    1.42 +    int nodeNum() const { return _digraph->nodeNum(); }
    1.43  
    1.44      typedef ArcNumTagIndicator<Digraph> ArcNumTag;
    1.45      int arcNum() const { return 2 * _digraph->arcNum(); }
    1.46 @@ -1892,7 +1898,7 @@
    1.47            if (arc != INVALID) return arc;
    1.48            arc = _digraph->findArc(t, s);
    1.49            if (arc != INVALID) return arc;
    1.50 -        } else if (_digraph->s(p) == s) {
    1.51 +        } else if (_digraph->source(p) == s) {
    1.52            Edge arc = _digraph->findArc(s, t, p);
    1.53            if (arc != INVALID) return arc;
    1.54            arc = _digraph->findArc(t, s);
    1.55 @@ -1921,6 +1927,10 @@
    1.56  
    1.57        typedef _Value Value;
    1.58        typedef Arc Key;
    1.59 +      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
    1.60 +      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
    1.61 +      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
    1.62 +      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
    1.63  
    1.64        ArcMapBase(const Adaptor& adaptor) :
    1.65          _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
    1.66 @@ -1936,8 +1946,7 @@
    1.67          }
    1.68        }
    1.69  
    1.70 -      typename MapTraits<MapImpl>::ConstReturnValue
    1.71 -      operator[](const Arc& a) const {
    1.72 +      ConstReturnValue operator[](const Arc& a) const {
    1.73          if (direction(a)) {
    1.74            return _forward[a];
    1.75          } else {
    1.76 @@ -1945,8 +1954,7 @@
    1.77          }
    1.78        }
    1.79  
    1.80 -      typename MapTraits<MapImpl>::ReturnValue
    1.81 -      operator[](const Arc& a) {
    1.82 +      ReturnValue operator[](const Arc& a) {
    1.83          if (direction(a)) {
    1.84            return _forward[a];
    1.85          } else {
    1.86 @@ -1996,7 +2004,7 @@
    1.87        typedef _Value Value;
    1.88        typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    1.89  
    1.90 -      ArcMap(const Adaptor& adaptor)
    1.91 +      explicit ArcMap(const Adaptor& adaptor)
    1.92          : Parent(adaptor) {}
    1.93  
    1.94        ArcMap(const Adaptor& adaptor, const Value& value)
    1.95 @@ -2043,6 +2051,9 @@
    1.96      typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
    1.97      NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
    1.98  
    1.99 +    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
   1.100 +    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
   1.101 +
   1.102    protected:
   1.103  
   1.104      UndirectorBase() : _digraph(0) {}
   1.105 @@ -2100,6 +2111,11 @@
   1.106        typedef typename ForwardMap::Value Value;
   1.107        typedef typename Parent::Arc Key;
   1.108  
   1.109 +      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
   1.110 +      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
   1.111 +      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
   1.112 +      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
   1.113 +
   1.114        /// \brief Constructor
   1.115        ///
   1.116        /// Constructor
   1.117 @@ -2121,8 +2137,7 @@
   1.118        /// \brief Returns the value associated with a key.
   1.119        ///
   1.120        /// Returns the value associated with a key.
   1.121 -      typename MapTraits<ForwardMap>::ConstReturnValue
   1.122 -      operator[](const Key& e) const {
   1.123 +      ConstReturnValue operator[](const Key& e) const {
   1.124          if (Parent::direction(e)) {
   1.125            return (*_forward)[e];
   1.126          } else {
   1.127 @@ -2133,8 +2148,7 @@
   1.128        /// \brief Returns the value associated with a key.
   1.129        ///
   1.130        /// Returns the value associated with a key.
   1.131 -      typename MapTraits<ForwardMap>::ReturnValue
   1.132 -      operator[](const Key& e) {
   1.133 +      ReturnValue operator[](const Key& e) {
   1.134          if (Parent::direction(e)) {
   1.135            return (*_forward)[e];
   1.136          } else {
   1.137 @@ -2246,18 +2260,9 @@
   1.138      typedef FindEdgeTagIndicator<Graph> FindArcTag;
   1.139      Arc findArc(const Node& u, const Node& v,
   1.140                  const Arc& prev = INVALID) const {
   1.141 -      Arc arc = prev;
   1.142 -      bool d = arc == INVALID ? true : (*_direction)[arc];
   1.143 -      if (d) {
   1.144 +      Arc arc = _graph->findEdge(u, v, prev);
   1.145 +      while (arc != INVALID && source(arc) != u) {
   1.146          arc = _graph->findEdge(u, v, arc);
   1.147 -        while (arc != INVALID && !(*_direction)[arc]) {
   1.148 -          _graph->findEdge(u, v, arc);
   1.149 -        }
   1.150 -        if (arc != INVALID) return arc;
   1.151 -      }
   1.152 -      _graph->findEdge(v, u, arc);
   1.153 -      while (arc != INVALID && (*_direction)[arc]) {
   1.154 -        _graph->findEdge(u, v, arc);
   1.155        }
   1.156        return arc;
   1.157      }
   1.158 @@ -2267,8 +2272,8 @@
   1.159      }
   1.160  
   1.161      Arc addArc(const Node& u, const Node& v) {
   1.162 -      Arc arc = _graph->addArc(u, v);
   1.163 -      _direction->set(arc, _graph->source(arc) == u);
   1.164 +      Arc arc = _graph->addEdge(u, v);
   1.165 +      _direction->set(arc, _graph->u(arc) == u);
   1.166        return arc;
   1.167      }
   1.168  
   1.169 @@ -2912,17 +2917,14 @@
   1.170      typedef True FindArcTag;
   1.171      Arc findArc(const Node& u, const Node& v,
   1.172                  const Arc& prev = INVALID) const {
   1.173 -      if (inNode(u)) {
   1.174 -        if (outNode(v)) {
   1.175 -          if (static_cast<const DigraphNode&>(u) ==
   1.176 -              static_cast<const DigraphNode&>(v) && prev == INVALID) {
   1.177 -            return Arc(u);
   1.178 -          }
   1.179 +      if (inNode(u) && outNode(v)) {
   1.180 +        if (static_cast<const DigraphNode&>(u) ==
   1.181 +            static_cast<const DigraphNode&>(v) && prev == INVALID) {
   1.182 +          return Arc(u);
   1.183          }
   1.184 -      } else {
   1.185 -        if (inNode(v)) {
   1.186 -          return Arc(::lemon::findArc(*_digraph, u, v, prev));
   1.187 -        }
   1.188 +      }
   1.189 +      else if (outNode(u) && inNode(v)) {
   1.190 +        return Arc(::lemon::findArc(*_digraph, u, v, prev));
   1.191        }
   1.192        return INVALID;
   1.193      }
   1.194 @@ -2936,6 +2938,11 @@
   1.195      public:
   1.196        typedef Node Key;
   1.197        typedef _Value Value;
   1.198 +      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
   1.199 +      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
   1.200 +      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
   1.201 +      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
   1.202 +      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
   1.203  
   1.204        NodeMapBase(const Adaptor& adaptor)
   1.205          : _in_map(*adaptor._digraph), _out_map(*adaptor._digraph) {}
   1.206 @@ -2948,14 +2955,12 @@
   1.207          else {_out_map.set(key, val); }
   1.208        }
   1.209  
   1.210 -      typename MapTraits<NodeImpl>::ReturnValue
   1.211 -      operator[](const Node& key) {
   1.212 +      ReturnValue operator[](const Node& key) {
   1.213          if (Adaptor::inNode(key)) { return _in_map[key]; }
   1.214          else { return _out_map[key]; }
   1.215        }
   1.216  
   1.217 -      typename MapTraits<NodeImpl>::ConstReturnValue
   1.218 -      operator[](const Node& key) const {
   1.219 +      ConstReturnValue operator[](const Node& key) const {
   1.220          if (Adaptor::inNode(key)) { return _in_map[key]; }
   1.221          else { return _out_map[key]; }
   1.222        }
   1.223 @@ -2972,6 +2977,11 @@
   1.224      public:
   1.225        typedef Arc Key;
   1.226        typedef _Value Value;
   1.227 +      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
   1.228 +      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
   1.229 +      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
   1.230 +      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
   1.231 +      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
   1.232  
   1.233        ArcMapBase(const Adaptor& adaptor)
   1.234          : _arc_map(*adaptor._digraph), _node_map(*adaptor._digraph) {}
   1.235 @@ -2987,8 +2997,7 @@
   1.236          }
   1.237        }
   1.238  
   1.239 -      typename MapTraits<ArcImpl>::ReturnValue
   1.240 -      operator[](const Arc& key) {
   1.241 +      ReturnValue operator[](const Arc& key) {
   1.242          if (Adaptor::origArc(key)) {
   1.243            return _arc_map[key._item.first()];
   1.244          } else {
   1.245 @@ -2996,8 +3005,7 @@
   1.246          }
   1.247        }
   1.248  
   1.249 -      typename MapTraits<ArcImpl>::ConstReturnValue
   1.250 -      operator[](const Arc& key) const {
   1.251 +      ConstReturnValue operator[](const Arc& key) const {
   1.252          if (Adaptor::origArc(key)) {
   1.253            return _arc_map[key._item.first()];
   1.254          } else {
   1.255 @@ -3184,6 +3192,12 @@
   1.256        typedef Node Key;
   1.257        typedef typename InNodeMap::Value Value;
   1.258  
   1.259 +      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
   1.260 +      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
   1.261 +      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
   1.262 +      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
   1.263 +      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
   1.264 +
   1.265        /// \brief Constructor
   1.266        ///
   1.267        /// Constructor.
   1.268 @@ -3270,6 +3284,17 @@
   1.269        typedef Arc Key;
   1.270        typedef typename DigraphArcMap::Value Value;
   1.271  
   1.272 +      typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag
   1.273 +        ReferenceMapTag;
   1.274 +      typedef typename MapTraits<DigraphArcMap>::ReturnValue
   1.275 +        ReturnValue;
   1.276 +      typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
   1.277 +        ConstReturnValue;
   1.278 +      typedef typename MapTraits<DigraphArcMap>::ReturnValue
   1.279 +        Reference;
   1.280 +      typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
   1.281 +        ConstReference;
   1.282 +
   1.283        /// \brief Constructor
   1.284        ///
   1.285        /// Constructor.