lemon/bits/graph_adaptor_extender.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 30 Nov 2008 19:00:30 +0100
changeset 415 4b6112235fad
child 416 76287c8caa26
permissions -rw-r--r--
Improvements in graph adaptors (#67)

Remove DigraphAdaptor and GraphAdaptor
Remove docs of base classes
Move the member documentations to real adaptors
Minor improvements in documentation
     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