lemon/bits/graph_adaptor_extender.h
changeset 435 30d22b636e57
parent 414 05357da973ce
child 440 88ed40ad0d4f
child 453 c246659c8b19
equal deleted inserted replaced
0:f845889889f3 1:5a0a229fa7a9
     1 /* -*- C++ -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2008
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
    22 #include <lemon/core.h>
    22 #include <lemon/core.h>
    23 #include <lemon/error.h>
    23 #include <lemon/error.h>
    24 
    24 
    25 #include <lemon/bits/default_map.h>
    25 #include <lemon/bits/default_map.h>
    26 
    26 
    27 
       
    28 ///\ingroup digraphbits
       
    29 ///\file
       
    30 ///\brief Extenders for the digraph adaptor types
       
    31 namespace lemon {
    27 namespace lemon {
    32 
    28 
    33   /// \ingroup digraphbits
       
    34   ///
       
    35   /// \brief Extender for the DigraphAdaptors
       
    36   template <typename _Digraph>
    29   template <typename _Digraph>
    37   class DigraphAdaptorExtender : public _Digraph {
    30   class DigraphAdaptorExtender : public _Digraph {
    38   public:
    31   public:
    39 
    32 
    40     typedef _Digraph Parent;
    33     typedef _Digraph Parent;
    62       return Parent::arcFromId(id);
    55       return Parent::arcFromId(id);
    63     }
    56     }
    64 
    57 
    65     Node oppositeNode(const Node &n, const Arc &e) const {
    58     Node oppositeNode(const Node &n, const Arc &e) const {
    66       if (n == Parent::source(e))
    59       if (n == Parent::source(e))
    67 	return Parent::target(e);
    60         return Parent::target(e);
    68       else if(n==Parent::target(e))
    61       else if(n==Parent::target(e))
    69 	return Parent::source(e);
    62         return Parent::source(e);
    70       else
    63       else
    71 	return INVALID;
    64         return INVALID;
    72     }
    65     }
    73 
    66 
    74     class NodeIt : public Node { 
    67     class NodeIt : public Node {
    75       const Adaptor* _adaptor;
    68       const Adaptor* _adaptor;
    76     public:
    69     public:
    77 
    70 
    78       NodeIt() {}
    71       NodeIt() {}
    79 
    72 
    80       NodeIt(Invalid i) : Node(i) { }
    73       NodeIt(Invalid i) : Node(i) { }
    81 
    74 
    82       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    75       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    83 	_adaptor->first(static_cast<Node&>(*this));
    76         _adaptor->first(static_cast<Node&>(*this));
    84       }
    77       }
    85 
    78 
    86       NodeIt(const Adaptor& adaptor, const Node& node) 
    79       NodeIt(const Adaptor& adaptor, const Node& node)
    87 	: Node(node), _adaptor(&adaptor) {}
    80         : Node(node), _adaptor(&adaptor) {}
    88 
    81 
    89       NodeIt& operator++() { 
    82       NodeIt& operator++() {
    90 	_adaptor->next(*this);
    83         _adaptor->next(*this);
    91 	return *this; 
    84         return *this;
    92       }
    85       }
    93 
    86 
    94     };
    87     };
    95 
    88 
    96 
    89 
    97     class ArcIt : public Arc { 
    90     class ArcIt : public Arc {
    98       const Adaptor* _adaptor;
    91       const Adaptor* _adaptor;
    99     public:
    92     public:
   100 
    93 
   101       ArcIt() { }
    94       ArcIt() { }
   102 
    95 
   103       ArcIt(Invalid i) : Arc(i) { }
    96       ArcIt(Invalid i) : Arc(i) { }
   104 
    97 
   105       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    98       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   106 	_adaptor->first(static_cast<Arc&>(*this));
    99         _adaptor->first(static_cast<Arc&>(*this));
   107       }
   100       }
   108 
   101 
   109       ArcIt(const Adaptor& adaptor, const Arc& e) : 
   102       ArcIt(const Adaptor& adaptor, const Arc& e) :
   110 	Arc(e), _adaptor(&adaptor) { }
   103         Arc(e), _adaptor(&adaptor) { }
   111 
   104 
   112       ArcIt& operator++() { 
   105       ArcIt& operator++() {
   113 	_adaptor->next(*this);
   106         _adaptor->next(*this);
   114 	return *this; 
   107         return *this;
   115       }
   108       }
   116 
   109 
   117     };
   110     };
   118 
   111 
   119 
   112 
   120     class OutArcIt : public Arc { 
   113     class OutArcIt : public Arc {
   121       const Adaptor* _adaptor;
   114       const Adaptor* _adaptor;
   122     public:
   115     public:
   123 
   116 
   124       OutArcIt() { }
   117       OutArcIt() { }
   125 
   118 
   126       OutArcIt(Invalid i) : Arc(i) { }
   119       OutArcIt(Invalid i) : Arc(i) { }
   127 
   120 
   128       OutArcIt(const Adaptor& adaptor, const Node& node) 
   121       OutArcIt(const Adaptor& adaptor, const Node& node)
   129 	: _adaptor(&adaptor) {
   122         : _adaptor(&adaptor) {
   130 	_adaptor->firstOut(*this, node);
   123         _adaptor->firstOut(*this, node);
   131       }
   124       }
   132 
   125 
   133       OutArcIt(const Adaptor& adaptor, const Arc& arc) 
   126       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   134 	: Arc(arc), _adaptor(&adaptor) {}
   127         : Arc(arc), _adaptor(&adaptor) {}
   135 
   128 
   136       OutArcIt& operator++() { 
   129       OutArcIt& operator++() {
   137 	_adaptor->nextOut(*this);
   130         _adaptor->nextOut(*this);
   138 	return *this; 
   131         return *this;
   139       }
   132       }
   140 
   133 
   141     };
   134     };
   142 
   135 
   143 
   136 
   144     class InArcIt : public Arc { 
   137     class InArcIt : public Arc {
   145       const Adaptor* _adaptor;
   138       const Adaptor* _adaptor;
   146     public:
   139     public:
   147 
   140 
   148       InArcIt() { }
   141       InArcIt() { }
   149 
   142 
   150       InArcIt(Invalid i) : Arc(i) { }
   143       InArcIt(Invalid i) : Arc(i) { }
   151 
   144 
   152       InArcIt(const Adaptor& adaptor, const Node& node) 
   145       InArcIt(const Adaptor& adaptor, const Node& node)
   153 	: _adaptor(&adaptor) {
   146         : _adaptor(&adaptor) {
   154 	_adaptor->firstIn(*this, node);
   147         _adaptor->firstIn(*this, node);
   155       }
   148       }
   156 
   149 
   157       InArcIt(const Adaptor& adaptor, const Arc& arc) : 
   150       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   158 	Arc(arc), _adaptor(&adaptor) {}
   151         Arc(arc), _adaptor(&adaptor) {}
   159 
   152 
   160       InArcIt& operator++() { 
   153       InArcIt& operator++() {
   161 	_adaptor->nextIn(*this);
   154         _adaptor->nextIn(*this);
   162 	return *this; 
   155         return *this;
   163       }
   156       }
   164 
   157 
   165     };
   158     };
   166 
   159 
   167     /// \brief Base node of the iterator
       
   168     ///
       
   169     /// Returns the base node (ie. the source in this case) of the iterator
       
   170     Node baseNode(const OutArcIt &e) const {
   160     Node baseNode(const OutArcIt &e) const {
   171       return Parent::source(e);
   161       return Parent::source(e);
   172     }
   162     }
   173     /// \brief Running node of the iterator
       
   174     ///
       
   175     /// Returns the running node (ie. the target in this case) of the
       
   176     /// iterator
       
   177     Node runningNode(const OutArcIt &e) const {
   163     Node runningNode(const OutArcIt &e) const {
   178       return Parent::target(e);
   164       return Parent::target(e);
   179     }
   165     }
   180 
   166 
   181     /// \brief Base node of the iterator
       
   182     ///
       
   183     /// Returns the base node (ie. the target in this case) of the iterator
       
   184     Node baseNode(const InArcIt &e) const {
   167     Node baseNode(const InArcIt &e) const {
   185       return Parent::target(e);
   168       return Parent::target(e);
   186     }
   169     }
   187     /// \brief Running node of the iterator
       
   188     ///
       
   189     /// Returns the running node (ie. the source in this case) of the
       
   190     /// iterator
       
   191     Node runningNode(const InArcIt &e) const {
   170     Node runningNode(const InArcIt &e) const {
   192       return Parent::source(e);
   171       return Parent::source(e);
   193     }
   172     }
   194 
   173 
   195   };
   174   };
   196 
   175 
   197 
   176 
   198   /// \ingroup digraphbits
   177   /// \ingroup digraphbits
   199   ///
   178   ///
   200   /// \brief Extender for the GraphAdaptors
   179   /// \brief Extender for the GraphAdaptors
   201   template <typename _Graph> 
   180   template <typename _Graph>
   202   class GraphAdaptorExtender : public _Graph {
   181   class GraphAdaptorExtender : public _Graph {
   203   public:
   182   public:
   204     
   183 
   205     typedef _Graph Parent;
   184     typedef _Graph Parent;
   206     typedef _Graph Graph;
   185     typedef _Graph Graph;
   207     typedef GraphAdaptorExtender Adaptor;
   186     typedef GraphAdaptorExtender Adaptor;
   208 
   187 
   209     typedef typename Parent::Node Node;
   188     typedef typename Parent::Node Node;
   210     typedef typename Parent::Arc Arc;
   189     typedef typename Parent::Arc Arc;
   211     typedef typename Parent::Edge Edge;
   190     typedef typename Parent::Edge Edge;
   212 
   191 
   213     // Graph extension    
   192     // Graph extension
   214 
   193 
   215     int maxId(Node) const {
   194     int maxId(Node) const {
   216       return Parent::maxNodeId();
   195       return Parent::maxNodeId();
   217     }
   196     }
   218 
   197 
   236       return Parent::edgeFromId(id);
   215       return Parent::edgeFromId(id);
   237     }
   216     }
   238 
   217 
   239     Node oppositeNode(const Node &n, const Edge &e) const {
   218     Node oppositeNode(const Node &n, const Edge &e) const {
   240       if( n == Parent::u(e))
   219       if( n == Parent::u(e))
   241 	return Parent::v(e);
   220         return Parent::v(e);
   242       else if( n == Parent::v(e))
   221       else if( n == Parent::v(e))
   243 	return Parent::u(e);
   222         return Parent::u(e);
   244       else
   223       else
   245 	return INVALID;
   224         return INVALID;
   246     }
   225     }
   247 
   226 
   248     Arc oppositeArc(const Arc &a) const {
   227     Arc oppositeArc(const Arc &a) const {
   249       return Parent::direct(a, !Parent::direction(a));
   228       return Parent::direct(a, !Parent::direction(a));
   250     }
   229     }
   253     Arc direct(const Edge &e, const Node &s) const {
   232     Arc direct(const Edge &e, const Node &s) const {
   254       return Parent::direct(e, Parent::u(e) == s);
   233       return Parent::direct(e, Parent::u(e) == s);
   255     }
   234     }
   256 
   235 
   257 
   236 
   258     class NodeIt : public Node { 
   237     class NodeIt : public Node {
   259       const Adaptor* _adaptor;
   238       const Adaptor* _adaptor;
   260     public:
   239     public:
   261 
   240 
   262       NodeIt() {}
   241       NodeIt() {}
   263 
   242 
   264       NodeIt(Invalid i) : Node(i) { }
   243       NodeIt(Invalid i) : Node(i) { }
   265 
   244 
   266       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   245       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   267 	_adaptor->first(static_cast<Node&>(*this));
   246         _adaptor->first(static_cast<Node&>(*this));
   268       }
   247       }
   269 
   248 
   270       NodeIt(const Adaptor& adaptor, const Node& node) 
   249       NodeIt(const Adaptor& adaptor, const Node& node)
   271 	: Node(node), _adaptor(&adaptor) {}
   250         : Node(node), _adaptor(&adaptor) {}
   272 
   251 
   273       NodeIt& operator++() { 
   252       NodeIt& operator++() {
   274 	_adaptor->next(*this);
   253         _adaptor->next(*this);
   275 	return *this; 
   254         return *this;
   276       }
   255       }
   277 
   256 
   278     };
   257     };
   279 
   258 
   280 
   259 
   281     class ArcIt : public Arc { 
   260     class ArcIt : public Arc {
   282       const Adaptor* _adaptor;
   261       const Adaptor* _adaptor;
   283     public:
   262     public:
   284 
   263 
   285       ArcIt() { }
   264       ArcIt() { }
   286 
   265 
   287       ArcIt(Invalid i) : Arc(i) { }
   266       ArcIt(Invalid i) : Arc(i) { }
   288 
   267 
   289       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   268       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   290 	_adaptor->first(static_cast<Arc&>(*this));
   269         _adaptor->first(static_cast<Arc&>(*this));
   291       }
   270       }
   292 
   271 
   293       ArcIt(const Adaptor& adaptor, const Arc& e) : 
   272       ArcIt(const Adaptor& adaptor, const Arc& e) :
   294 	Arc(e), _adaptor(&adaptor) { }
   273         Arc(e), _adaptor(&adaptor) { }
   295 
   274 
   296       ArcIt& operator++() { 
   275       ArcIt& operator++() {
   297 	_adaptor->next(*this);
   276         _adaptor->next(*this);
   298 	return *this; 
   277         return *this;
   299       }
   278       }
   300 
   279 
   301     };
   280     };
   302 
   281 
   303 
   282 
   304     class OutArcIt : public Arc { 
   283     class OutArcIt : public Arc {
   305       const Adaptor* _adaptor;
   284       const Adaptor* _adaptor;
   306     public:
   285     public:
   307 
   286 
   308       OutArcIt() { }
   287       OutArcIt() { }
   309 
   288 
   310       OutArcIt(Invalid i) : Arc(i) { }
   289       OutArcIt(Invalid i) : Arc(i) { }
   311 
   290 
   312       OutArcIt(const Adaptor& adaptor, const Node& node) 
   291       OutArcIt(const Adaptor& adaptor, const Node& node)
   313 	: _adaptor(&adaptor) {
   292         : _adaptor(&adaptor) {
   314 	_adaptor->firstOut(*this, node);
   293         _adaptor->firstOut(*this, node);
   315       }
   294       }
   316 
   295 
   317       OutArcIt(const Adaptor& adaptor, const Arc& arc) 
   296       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   318 	: Arc(arc), _adaptor(&adaptor) {}
   297         : Arc(arc), _adaptor(&adaptor) {}
   319 
   298 
   320       OutArcIt& operator++() { 
   299       OutArcIt& operator++() {
   321 	_adaptor->nextOut(*this);
   300         _adaptor->nextOut(*this);
   322 	return *this; 
   301         return *this;
   323       }
   302       }
   324 
   303 
   325     };
   304     };
   326 
   305 
   327 
   306 
   328     class InArcIt : public Arc { 
   307     class InArcIt : public Arc {
   329       const Adaptor* _adaptor;
   308       const Adaptor* _adaptor;
   330     public:
   309     public:
   331 
   310 
   332       InArcIt() { }
   311       InArcIt() { }
   333 
   312 
   334       InArcIt(Invalid i) : Arc(i) { }
   313       InArcIt(Invalid i) : Arc(i) { }
   335 
   314 
   336       InArcIt(const Adaptor& adaptor, const Node& node) 
   315       InArcIt(const Adaptor& adaptor, const Node& node)
   337 	: _adaptor(&adaptor) {
   316         : _adaptor(&adaptor) {
   338 	_adaptor->firstIn(*this, node);
   317         _adaptor->firstIn(*this, node);
   339       }
   318       }
   340 
   319 
   341       InArcIt(const Adaptor& adaptor, const Arc& arc) : 
   320       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   342 	Arc(arc), _adaptor(&adaptor) {}
   321         Arc(arc), _adaptor(&adaptor) {}
   343 
   322 
   344       InArcIt& operator++() { 
   323       InArcIt& operator++() {
   345 	_adaptor->nextIn(*this);
   324         _adaptor->nextIn(*this);
   346 	return *this; 
   325         return *this;
   347       }
   326       }
   348 
   327 
   349     };
   328     };
   350 
   329 
   351     class EdgeIt : public Parent::Edge { 
   330     class EdgeIt : public Parent::Edge {
   352       const Adaptor* _adaptor;
   331       const Adaptor* _adaptor;
   353     public:
   332     public:
   354 
   333 
   355       EdgeIt() { }
   334       EdgeIt() { }
   356 
   335 
   357       EdgeIt(Invalid i) : Edge(i) { }
   336       EdgeIt(Invalid i) : Edge(i) { }
   358 
   337 
   359       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   338       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   360 	_adaptor->first(static_cast<Edge&>(*this));
   339         _adaptor->first(static_cast<Edge&>(*this));
   361       }
   340       }
   362 
   341 
   363       EdgeIt(const Adaptor& adaptor, const Edge& e) : 
   342       EdgeIt(const Adaptor& adaptor, const Edge& e) :
   364 	Edge(e), _adaptor(&adaptor) { }
   343         Edge(e), _adaptor(&adaptor) { }
   365 
   344 
   366       EdgeIt& operator++() { 
   345       EdgeIt& operator++() {
   367 	_adaptor->next(*this);
   346         _adaptor->next(*this);
   368 	return *this; 
   347         return *this;
   369       }
   348       }
   370 
   349 
   371     };
   350     };
   372 
   351 
   373     class IncEdgeIt : public Edge { 
   352     class IncEdgeIt : public Edge {
   374       friend class GraphAdaptorExtender;
   353       friend class GraphAdaptorExtender;
   375       const Adaptor* _adaptor;
   354       const Adaptor* _adaptor;
   376       bool direction;
   355       bool direction;
   377     public:
   356     public:
   378 
   357 
   379       IncEdgeIt() { }
   358       IncEdgeIt() { }
   380 
   359 
   381       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   360       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   382 
   361 
   383       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
   362       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
   384 	_adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
   363         _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
   385       }
   364       }
   386 
   365 
   387       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
   366       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
   388 	: _adaptor(&adaptor), Edge(e) {
   367         : _adaptor(&adaptor), Edge(e) {
   389 	direction = (_adaptor->u(e) == n);
   368         direction = (_adaptor->u(e) == n);
   390       }
   369       }
   391 
   370 
   392       IncEdgeIt& operator++() {
   371       IncEdgeIt& operator++() {
   393 	_adaptor->nextInc(*this, direction);
   372         _adaptor->nextInc(*this, direction);
   394 	return *this; 
   373         return *this;
   395       }
   374       }
   396     };
   375     };
   397 
   376 
   398     /// \brief Base node of the iterator
       
   399     ///
       
   400     /// Returns the base node (ie. the source in this case) of the iterator
       
   401     Node baseNode(const OutArcIt &a) const {
   377     Node baseNode(const OutArcIt &a) const {
   402       return Parent::source(a);
   378       return Parent::source(a);
   403     }
   379     }
   404     /// \brief Running node of the iterator
       
   405     ///
       
   406     /// Returns the running node (ie. the target in this case) of the
       
   407     /// iterator
       
   408     Node runningNode(const OutArcIt &a) const {
   380     Node runningNode(const OutArcIt &a) const {
   409       return Parent::target(a);
   381       return Parent::target(a);
   410     }
   382     }
   411 
   383 
   412     /// \brief Base node of the iterator
       
   413     ///
       
   414     /// Returns the base node (ie. the target in this case) of the iterator
       
   415     Node baseNode(const InArcIt &a) const {
   384     Node baseNode(const InArcIt &a) const {
   416       return Parent::target(a);
   385       return Parent::target(a);
   417     }
   386     }
   418     /// \brief Running node of the iterator
       
   419     ///
       
   420     /// Returns the running node (ie. the source in this case) of the
       
   421     /// iterator
       
   422     Node runningNode(const InArcIt &a) const {
   387     Node runningNode(const InArcIt &a) const {
   423       return Parent::source(a);
   388       return Parent::source(a);
   424     }
   389     }
   425 
   390 
   426     /// Base node of the iterator
       
   427     ///
       
   428     /// Returns the base node of the iterator
       
   429     Node baseNode(const IncEdgeIt &e) const {
   391     Node baseNode(const IncEdgeIt &e) const {
   430       return e.direction ? Parent::u(e) : Parent::v(e);
   392       return e.direction ? Parent::u(e) : Parent::v(e);
   431     }
   393     }
   432     /// Running node of the iterator
       
   433     ///
       
   434     /// Returns the running node of the iterator
       
   435     Node runningNode(const IncEdgeIt &e) const {
   394     Node runningNode(const IncEdgeIt &e) const {
   436       return e.direction ? Parent::v(e) : Parent::u(e);
   395       return e.direction ? Parent::v(e) : Parent::u(e);
   437     }
   396     }
   438 
   397 
   439   };
   398   };