COIN-OR::LEMON - Graph Library

Changeset 472:91fcb8ed4cdc in lemon for lemon/adaptors.h


Ignore:
Timestamp:
12/12/08 22:59:17 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/adaptors.h

    r471 r472  
    818818
    819819
    820   template <typename _Graph, typename NodeFilterMap,
    821             typename EdgeFilterMap, bool _checked = true>
     820  template <typename _Graph, typename _NodeFilterMap,
     821            typename _EdgeFilterMap, bool _checked = true>
    822822  class SubGraphBase : public GraphAdaptorBase<_Graph> {
    823823  public:
    824824    typedef _Graph Graph;
     825    typedef _NodeFilterMap NodeFilterMap;
     826    typedef _EdgeFilterMap EdgeFilterMap;
     827
    825828    typedef SubGraphBase Adaptor;
    826829    typedef GraphAdaptorBase<_Graph> Parent;
     
    10491052  };
    10501053
    1051   template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
    1052   class SubGraphBase<_Graph, NodeFilterMap, EdgeFilterMap, false>
     1054  template <typename _Graph, typename _NodeFilterMap, typename _EdgeFilterMap>
     1055  class SubGraphBase<_Graph, _NodeFilterMap, _EdgeFilterMap, false>
    10531056    : public GraphAdaptorBase<_Graph> {
    10541057  public:
    10551058    typedef _Graph Graph;
     1059    typedef _NodeFilterMap NodeFilterMap;
     1060    typedef _EdgeFilterMap EdgeFilterMap;
     1061
    10561062    typedef SubGraphBase Adaptor;
    10571063    typedef GraphAdaptorBase<_Graph> Parent;
     
    18581864
    18591865    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
    1860     int nodeNum() const { return 2 * _digraph->arcNum(); }
     1866    int nodeNum() const { return _digraph->nodeNum(); }
    18611867
    18621868    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
     
    18931899          arc = _digraph->findArc(t, s);
    18941900          if (arc != INVALID) return arc;
    1895         } else if (_digraph->s(p) == s) {
     1901        } else if (_digraph->source(p) == s) {
    18961902          Edge arc = _digraph->findArc(s, t, p);
    18971903          if (arc != INVALID) return arc;
     
    19221928      typedef _Value Value;
    19231929      typedef Arc Key;
     1930      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
     1931      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
     1932      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
     1933      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
    19241934
    19251935      ArcMapBase(const Adaptor& adaptor) :
     
    19371947      }
    19381948
    1939       typename MapTraits<MapImpl>::ConstReturnValue
    1940       operator[](const Arc& a) const {
     1949      ConstReturnValue operator[](const Arc& a) const {
    19411950        if (direction(a)) {
    19421951          return _forward[a];
     
    19461955      }
    19471956
    1948       typename MapTraits<MapImpl>::ReturnValue
    1949       operator[](const Arc& a) {
     1957      ReturnValue operator[](const Arc& a) {
    19501958        if (direction(a)) {
    19511959          return _forward[a];
     
    19972005      typedef SubMapExtender<Adaptor, ArcMapBase<Value> > Parent;
    19982006
    1999       ArcMap(const Adaptor& adaptor)
     2007      explicit ArcMap(const Adaptor& adaptor)
    20002008        : Parent(adaptor) {}
    20012009
     
    20432051    typedef typename ItemSetTraits<Digraph, Node>::ItemNotifier NodeNotifier;
    20442052    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
     2053
     2054    typedef typename ItemSetTraits<Digraph, Edge>::ItemNotifier EdgeNotifier;
     2055    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
    20452056
    20462057  protected:
     
    21002111      typedef typename ForwardMap::Value Value;
    21012112      typedef typename Parent::Arc Key;
     2113
     2114      typedef typename MapTraits<ForwardMap>::ReturnValue ReturnValue;
     2115      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReturnValue;
     2116      typedef typename MapTraits<ForwardMap>::ReturnValue Reference;
     2117      typedef typename MapTraits<ForwardMap>::ConstReturnValue ConstReference;
    21022118
    21032119      /// \brief Constructor
     
    21222138      ///
    21232139      /// Returns the value associated with a key.
    2124       typename MapTraits<ForwardMap>::ConstReturnValue
    2125       operator[](const Key& e) const {
     2140      ConstReturnValue operator[](const Key& e) const {
    21262141        if (Parent::direction(e)) {
    21272142          return (*_forward)[e];
     
    21342149      ///
    21352150      /// Returns the value associated with a key.
    2136       typename MapTraits<ForwardMap>::ReturnValue
    2137       operator[](const Key& e) {
     2151      ReturnValue operator[](const Key& e) {
    21382152        if (Parent::direction(e)) {
    21392153          return (*_forward)[e];
     
    22472261    Arc findArc(const Node& u, const Node& v,
    22482262                const Arc& prev = INVALID) const {
    2249       Arc arc = prev;
    2250       bool d = arc == INVALID ? true : (*_direction)[arc];
    2251       if (d) {
     2263      Arc arc = _graph->findEdge(u, v, prev);
     2264      while (arc != INVALID && source(arc) != u) {
    22522265        arc = _graph->findEdge(u, v, arc);
    2253         while (arc != INVALID && !(*_direction)[arc]) {
    2254           _graph->findEdge(u, v, arc);
    2255         }
    2256         if (arc != INVALID) return arc;
    2257       }
    2258       _graph->findEdge(v, u, arc);
    2259       while (arc != INVALID && (*_direction)[arc]) {
    2260         _graph->findEdge(u, v, arc);
    22612266      }
    22622267      return arc;
     
    22682273
    22692274    Arc addArc(const Node& u, const Node& v) {
    2270       Arc arc = _graph->addArc(u, v);
    2271       _direction->set(arc, _graph->source(arc) == u);
     2275      Arc arc = _graph->addEdge(u, v);
     2276      _direction->set(arc, _graph->u(arc) == u);
    22722277      return arc;
    22732278    }
     
    29132918    Arc findArc(const Node& u, const Node& v,
    29142919                const Arc& prev = INVALID) const {
    2915       if (inNode(u)) {
    2916         if (outNode(v)) {
    2917           if (static_cast<const DigraphNode&>(u) ==
    2918               static_cast<const DigraphNode&>(v) && prev == INVALID) {
    2919             return Arc(u);
    2920           }
     2920      if (inNode(u) && outNode(v)) {
     2921        if (static_cast<const DigraphNode&>(u) ==
     2922            static_cast<const DigraphNode&>(v) && prev == INVALID) {
     2923          return Arc(u);
    29212924        }
    2922       } else {
    2923         if (inNode(v)) {
    2924           return Arc(::lemon::findArc(*_digraph, u, v, prev));
    2925         }
     2925      }
     2926      else if (outNode(u) && inNode(v)) {
     2927        return Arc(::lemon::findArc(*_digraph, u, v, prev));
    29262928      }
    29272929      return INVALID;
     
    29372939      typedef Node Key;
    29382940      typedef _Value Value;
     2941      typedef typename MapTraits<NodeImpl>::ReferenceMapTag ReferenceMapTag;
     2942      typedef typename MapTraits<NodeImpl>::ReturnValue ReturnValue;
     2943      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReturnValue;
     2944      typedef typename MapTraits<NodeImpl>::ReturnValue Reference;
     2945      typedef typename MapTraits<NodeImpl>::ConstReturnValue ConstReference;
    29392946
    29402947      NodeMapBase(const Adaptor& adaptor)
     
    29492956      }
    29502957
    2951       typename MapTraits<NodeImpl>::ReturnValue
    2952       operator[](const Node& key) {
     2958      ReturnValue operator[](const Node& key) {
    29532959        if (Adaptor::inNode(key)) { return _in_map[key]; }
    29542960        else { return _out_map[key]; }
    29552961      }
    29562962
    2957       typename MapTraits<NodeImpl>::ConstReturnValue
    2958       operator[](const Node& key) const {
     2963      ConstReturnValue operator[](const Node& key) const {
    29592964        if (Adaptor::inNode(key)) { return _in_map[key]; }
    29602965        else { return _out_map[key]; }
     
    29732978      typedef Arc Key;
    29742979      typedef _Value Value;
     2980      typedef typename MapTraits<ArcImpl>::ReferenceMapTag ReferenceMapTag;
     2981      typedef typename MapTraits<ArcImpl>::ReturnValue ReturnValue;
     2982      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReturnValue;
     2983      typedef typename MapTraits<ArcImpl>::ReturnValue Reference;
     2984      typedef typename MapTraits<ArcImpl>::ConstReturnValue ConstReference;
    29752985
    29762986      ArcMapBase(const Adaptor& adaptor)
     
    29882998      }
    29892999
    2990       typename MapTraits<ArcImpl>::ReturnValue
    2991       operator[](const Arc& key) {
     3000      ReturnValue operator[](const Arc& key) {
    29923001        if (Adaptor::origArc(key)) {
    29933002          return _arc_map[key._item.first()];
     
    29973006      }
    29983007
    2999       typename MapTraits<ArcImpl>::ConstReturnValue
    3000       operator[](const Arc& key) const {
     3008      ConstReturnValue operator[](const Arc& key) const {
    30013009        if (Adaptor::origArc(key)) {
    30023010          return _arc_map[key._item.first()];
     
    31853193      typedef typename InNodeMap::Value Value;
    31863194
     3195      typedef typename MapTraits<InNodeMap>::ReferenceMapTag ReferenceMapTag;
     3196      typedef typename MapTraits<InNodeMap>::ReturnValue ReturnValue;
     3197      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReturnValue;
     3198      typedef typename MapTraits<InNodeMap>::ReturnValue Reference;
     3199      typedef typename MapTraits<InNodeMap>::ConstReturnValue ConstReference;
     3200
    31873201      /// \brief Constructor
    31883202      ///
     
    32713285      typedef typename DigraphArcMap::Value Value;
    32723286
     3287      typedef typename MapTraits<DigraphArcMap>::ReferenceMapTag
     3288        ReferenceMapTag;
     3289      typedef typename MapTraits<DigraphArcMap>::ReturnValue
     3290        ReturnValue;
     3291      typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
     3292        ConstReturnValue;
     3293      typedef typename MapTraits<DigraphArcMap>::ReturnValue
     3294        Reference;
     3295      typedef typename MapTraits<DigraphArcMap>::ConstReturnValue
     3296        ConstReference;
     3297
    32733298      /// \brief Constructor
    32743299      ///
Note: See TracChangeset for help on using the changeset viewer.