lemon/bits/graph_adaptor_extender.h
changeset 415 4b6112235fad
child 416 76287c8caa26
equal deleted inserted replaced
-1:000000000000 0:f845889889f3
       
     1 /* -*- C++ -*-
       
     2  *
       
     3  * This file is a part of LEMON, a generic C++ optimization library
       
     4  *
       
     5  * Copyright (C) 2003-2008
       
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
       
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
       
     8  *
       
     9  * Permission to use, modify and distribute this software is granted
       
    10  * provided that this copyright notice appears in all copies. For
       
    11  * precise terms see the accompanying LICENSE file.
       
    12  *
       
    13  * This software is provided "AS IS" with no warranty of any kind,
       
    14  * express or implied, and with no claim as to its suitability for any
       
    15  * purpose.
       
    16  *
       
    17  */
       
    18 
       
    19 #ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
       
    20 #define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
       
    21 
       
    22 #include <lemon/core.h>
       
    23 #include <lemon/error.h>
       
    24 
       
    25 #include <lemon/bits/default_map.h>
       
    26 
       
    27 
       
    28 ///\ingroup digraphbits
       
    29 ///\file
       
    30 ///\brief Extenders for the digraph adaptor types
       
    31 namespace lemon {
       
    32 
       
    33   /// \ingroup digraphbits
       
    34   ///
       
    35   /// \brief Extender for the DigraphAdaptors
       
    36   template <typename _Digraph>
       
    37   class DigraphAdaptorExtender : public _Digraph {
       
    38   public:
       
    39 
       
    40     typedef _Digraph Parent;
       
    41     typedef _Digraph Digraph;
       
    42     typedef DigraphAdaptorExtender Adaptor;
       
    43 
       
    44     // Base extensions
       
    45 
       
    46     typedef typename Parent::Node Node;
       
    47     typedef typename Parent::Arc Arc;
       
    48 
       
    49     int maxId(Node) const {
       
    50       return Parent::maxNodeId();
       
    51     }
       
    52 
       
    53     int maxId(Arc) const {
       
    54       return Parent::maxArcId();
       
    55     }
       
    56 
       
    57     Node fromId(int id, Node) const {
       
    58       return Parent::nodeFromId(id);
       
    59     }
       
    60 
       
    61     Arc fromId(int id, Arc) const {
       
    62       return Parent::arcFromId(id);
       
    63     }
       
    64 
       
    65     Node oppositeNode(const Node &n, const Arc &e) const {
       
    66       if (n == Parent::source(e))
       
    67 	return Parent::target(e);
       
    68       else if(n==Parent::target(e))
       
    69 	return Parent::source(e);
       
    70       else
       
    71 	return INVALID;
       
    72     }
       
    73 
       
    74     class NodeIt : public Node { 
       
    75       const Adaptor* _adaptor;
       
    76     public:
       
    77 
       
    78       NodeIt() {}
       
    79 
       
    80       NodeIt(Invalid i) : Node(i) { }
       
    81 
       
    82       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
       
    83 	_adaptor->first(static_cast<Node&>(*this));
       
    84       }
       
    85 
       
    86       NodeIt(const Adaptor& adaptor, const Node& node) 
       
    87 	: Node(node), _adaptor(&adaptor) {}
       
    88 
       
    89       NodeIt& operator++() { 
       
    90 	_adaptor->next(*this);
       
    91 	return *this; 
       
    92       }
       
    93 
       
    94     };
       
    95 
       
    96 
       
    97     class ArcIt : public Arc { 
       
    98       const Adaptor* _adaptor;
       
    99     public:
       
   100 
       
   101       ArcIt() { }
       
   102 
       
   103       ArcIt(Invalid i) : Arc(i) { }
       
   104 
       
   105       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
       
   106 	_adaptor->first(static_cast<Arc&>(*this));
       
   107       }
       
   108 
       
   109       ArcIt(const Adaptor& adaptor, const Arc& e) : 
       
   110 	Arc(e), _adaptor(&adaptor) { }
       
   111 
       
   112       ArcIt& operator++() { 
       
   113 	_adaptor->next(*this);
       
   114 	return *this; 
       
   115       }
       
   116 
       
   117     };
       
   118 
       
   119 
       
   120     class OutArcIt : public Arc { 
       
   121       const Adaptor* _adaptor;
       
   122     public:
       
   123 
       
   124       OutArcIt() { }
       
   125 
       
   126       OutArcIt(Invalid i) : Arc(i) { }
       
   127 
       
   128       OutArcIt(const Adaptor& adaptor, const Node& node) 
       
   129 	: _adaptor(&adaptor) {
       
   130 	_adaptor->firstOut(*this, node);
       
   131       }
       
   132 
       
   133       OutArcIt(const Adaptor& adaptor, const Arc& arc) 
       
   134 	: Arc(arc), _adaptor(&adaptor) {}
       
   135 
       
   136       OutArcIt& operator++() { 
       
   137 	_adaptor->nextOut(*this);
       
   138 	return *this; 
       
   139       }
       
   140 
       
   141     };
       
   142 
       
   143 
       
   144     class InArcIt : public Arc { 
       
   145       const Adaptor* _adaptor;
       
   146     public:
       
   147 
       
   148       InArcIt() { }
       
   149 
       
   150       InArcIt(Invalid i) : Arc(i) { }
       
   151 
       
   152       InArcIt(const Adaptor& adaptor, const Node& node) 
       
   153 	: _adaptor(&adaptor) {
       
   154 	_adaptor->firstIn(*this, node);
       
   155       }
       
   156 
       
   157       InArcIt(const Adaptor& adaptor, const Arc& arc) : 
       
   158 	Arc(arc), _adaptor(&adaptor) {}
       
   159 
       
   160       InArcIt& operator++() { 
       
   161 	_adaptor->nextIn(*this);
       
   162 	return *this; 
       
   163       }
       
   164 
       
   165     };
       
   166 
       
   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 {
       
   171       return Parent::source(e);
       
   172     }
       
   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 {
       
   178       return Parent::target(e);
       
   179     }
       
   180 
       
   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 {
       
   185       return Parent::target(e);
       
   186     }
       
   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 {
       
   192       return Parent::source(e);
       
   193     }
       
   194 
       
   195   };
       
   196 
       
   197 
       
   198   /// \ingroup digraphbits
       
   199   ///
       
   200   /// \brief Extender for the GraphAdaptors
       
   201   template <typename _Graph> 
       
   202   class GraphAdaptorExtender : public _Graph {
       
   203   public:
       
   204     
       
   205     typedef _Graph Parent;
       
   206     typedef _Graph Graph;
       
   207     typedef GraphAdaptorExtender Adaptor;
       
   208 
       
   209     typedef typename Parent::Node Node;
       
   210     typedef typename Parent::Arc Arc;
       
   211     typedef typename Parent::Edge Edge;
       
   212 
       
   213     // Graph extension    
       
   214 
       
   215     int maxId(Node) const {
       
   216       return Parent::maxNodeId();
       
   217     }
       
   218 
       
   219     int maxId(Arc) const {
       
   220       return Parent::maxArcId();
       
   221     }
       
   222 
       
   223     int maxId(Edge) const {
       
   224       return Parent::maxEdgeId();
       
   225     }
       
   226 
       
   227     Node fromId(int id, Node) const {
       
   228       return Parent::nodeFromId(id);
       
   229     }
       
   230 
       
   231     Arc fromId(int id, Arc) const {
       
   232       return Parent::arcFromId(id);
       
   233     }
       
   234 
       
   235     Edge fromId(int id, Edge) const {
       
   236       return Parent::edgeFromId(id);
       
   237     }
       
   238 
       
   239     Node oppositeNode(const Node &n, const Edge &e) const {
       
   240       if( n == Parent::u(e))
       
   241 	return Parent::v(e);
       
   242       else if( n == Parent::v(e))
       
   243 	return Parent::u(e);
       
   244       else
       
   245 	return INVALID;
       
   246     }
       
   247 
       
   248     Arc oppositeArc(const Arc &a) const {
       
   249       return Parent::direct(a, !Parent::direction(a));
       
   250     }
       
   251 
       
   252     using Parent::direct;
       
   253     Arc direct(const Edge &e, const Node &s) const {
       
   254       return Parent::direct(e, Parent::u(e) == s);
       
   255     }
       
   256 
       
   257 
       
   258     class NodeIt : public Node { 
       
   259       const Adaptor* _adaptor;
       
   260     public:
       
   261 
       
   262       NodeIt() {}
       
   263 
       
   264       NodeIt(Invalid i) : Node(i) { }
       
   265 
       
   266       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
       
   267 	_adaptor->first(static_cast<Node&>(*this));
       
   268       }
       
   269 
       
   270       NodeIt(const Adaptor& adaptor, const Node& node) 
       
   271 	: Node(node), _adaptor(&adaptor) {}
       
   272 
       
   273       NodeIt& operator++() { 
       
   274 	_adaptor->next(*this);
       
   275 	return *this; 
       
   276       }
       
   277 
       
   278     };
       
   279 
       
   280 
       
   281     class ArcIt : public Arc { 
       
   282       const Adaptor* _adaptor;
       
   283     public:
       
   284 
       
   285       ArcIt() { }
       
   286 
       
   287       ArcIt(Invalid i) : Arc(i) { }
       
   288 
       
   289       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
       
   290 	_adaptor->first(static_cast<Arc&>(*this));
       
   291       }
       
   292 
       
   293       ArcIt(const Adaptor& adaptor, const Arc& e) : 
       
   294 	Arc(e), _adaptor(&adaptor) { }
       
   295 
       
   296       ArcIt& operator++() { 
       
   297 	_adaptor->next(*this);
       
   298 	return *this; 
       
   299       }
       
   300 
       
   301     };
       
   302 
       
   303 
       
   304     class OutArcIt : public Arc { 
       
   305       const Adaptor* _adaptor;
       
   306     public:
       
   307 
       
   308       OutArcIt() { }
       
   309 
       
   310       OutArcIt(Invalid i) : Arc(i) { }
       
   311 
       
   312       OutArcIt(const Adaptor& adaptor, const Node& node) 
       
   313 	: _adaptor(&adaptor) {
       
   314 	_adaptor->firstOut(*this, node);
       
   315       }
       
   316 
       
   317       OutArcIt(const Adaptor& adaptor, const Arc& arc) 
       
   318 	: Arc(arc), _adaptor(&adaptor) {}
       
   319 
       
   320       OutArcIt& operator++() { 
       
   321 	_adaptor->nextOut(*this);
       
   322 	return *this; 
       
   323       }
       
   324 
       
   325     };
       
   326 
       
   327 
       
   328     class InArcIt : public Arc { 
       
   329       const Adaptor* _adaptor;
       
   330     public:
       
   331 
       
   332       InArcIt() { }
       
   333 
       
   334       InArcIt(Invalid i) : Arc(i) { }
       
   335 
       
   336       InArcIt(const Adaptor& adaptor, const Node& node) 
       
   337 	: _adaptor(&adaptor) {
       
   338 	_adaptor->firstIn(*this, node);
       
   339       }
       
   340 
       
   341       InArcIt(const Adaptor& adaptor, const Arc& arc) : 
       
   342 	Arc(arc), _adaptor(&adaptor) {}
       
   343 
       
   344       InArcIt& operator++() { 
       
   345 	_adaptor->nextIn(*this);
       
   346 	return *this; 
       
   347       }
       
   348 
       
   349     };
       
   350 
       
   351     class EdgeIt : public Parent::Edge { 
       
   352       const Adaptor* _adaptor;
       
   353     public:
       
   354 
       
   355       EdgeIt() { }
       
   356 
       
   357       EdgeIt(Invalid i) : Edge(i) { }
       
   358 
       
   359       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
       
   360 	_adaptor->first(static_cast<Edge&>(*this));
       
   361       }
       
   362 
       
   363       EdgeIt(const Adaptor& adaptor, const Edge& e) : 
       
   364 	Edge(e), _adaptor(&adaptor) { }
       
   365 
       
   366       EdgeIt& operator++() { 
       
   367 	_adaptor->next(*this);
       
   368 	return *this; 
       
   369       }
       
   370 
       
   371     };
       
   372 
       
   373     class IncEdgeIt : public Edge { 
       
   374       friend class GraphAdaptorExtender;
       
   375       const Adaptor* _adaptor;
       
   376       bool direction;
       
   377     public:
       
   378 
       
   379       IncEdgeIt() { }
       
   380 
       
   381       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
       
   382 
       
   383       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
       
   384 	_adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
       
   385       }
       
   386 
       
   387       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
       
   388 	: _adaptor(&adaptor), Edge(e) {
       
   389 	direction = (_adaptor->u(e) == n);
       
   390       }
       
   391 
       
   392       IncEdgeIt& operator++() {
       
   393 	_adaptor->nextInc(*this, direction);
       
   394 	return *this; 
       
   395       }
       
   396     };
       
   397 
       
   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 {
       
   402       return Parent::source(a);
       
   403     }
       
   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 {
       
   409       return Parent::target(a);
       
   410     }
       
   411 
       
   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 {
       
   416       return Parent::target(a);
       
   417     }
       
   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 {
       
   423       return Parent::source(a);
       
   424     }
       
   425 
       
   426     /// Base node of the iterator
       
   427     ///
       
   428     /// Returns the base node of the iterator
       
   429     Node baseNode(const IncEdgeIt &e) const {
       
   430       return e.direction ? Parent::u(e) : Parent::v(e);
       
   431     }
       
   432     /// Running node of the iterator
       
   433     ///
       
   434     /// Returns the running node of the iterator
       
   435     Node runningNode(const IncEdgeIt &e) const {
       
   436       return e.direction ? Parent::v(e) : Parent::u(e);
       
   437     }
       
   438 
       
   439   };
       
   440 
       
   441 }
       
   442 
       
   443 
       
   444 #endif