lemon/bits/graph_adaptor_extender.h
author Balazs Dezso <deba@google.com>
Tue, 14 Apr 2015 16:36:45 +0200
changeset 1133 93d455c647be
parent 1130 0759d974de81
permissions -rw-r--r--
Fix problem with temporal iterator parameters (#325)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     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 namespace lemon {
    26 
    27   template <typename _Digraph>
    28   class DigraphAdaptorExtender : public _Digraph {
    29     typedef _Digraph Parent;
    30 
    31   public:
    32 
    33     typedef _Digraph Digraph;
    34     typedef DigraphAdaptorExtender Adaptor;
    35 
    36     // Base extensions
    37 
    38     typedef typename Parent::Node Node;
    39     typedef typename Parent::Arc Arc;
    40 
    41     int maxId(Node) const {
    42       return Parent::maxNodeId();
    43     }
    44 
    45     int maxId(Arc) const {
    46       return Parent::maxArcId();
    47     }
    48 
    49     Node fromId(int id, Node) const {
    50       return Parent::nodeFromId(id);
    51     }
    52 
    53     Arc fromId(int id, Arc) const {
    54       return Parent::arcFromId(id);
    55     }
    56 
    57     Node oppositeNode(const Node &n, const Arc &e) const {
    58       if (n == Parent::source(e))
    59         return Parent::target(e);
    60       else if(n==Parent::target(e))
    61         return Parent::source(e);
    62       else
    63         return INVALID;
    64     }
    65 
    66     class NodeIt : public Node {
    67       const Adaptor* _adaptor;
    68     public:
    69 
    70       NodeIt() {}
    71 
    72       NodeIt(Invalid i) : Node(i) { }
    73 
    74       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
    75         _adaptor->first(static_cast<Node&>(*this));
    76       }
    77 
    78       NodeIt(const Adaptor& adaptor, const Node& node)
    79         : Node(node), _adaptor(&adaptor) {}
    80 
    81       NodeIt& operator++() {
    82         _adaptor->next(*this);
    83         return *this;
    84       }
    85 
    86     };
    87 
    88     LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
    89       return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
    90     }
    91 
    92     class ArcIt : public Arc {
    93       const Adaptor* _adaptor;
    94     public:
    95 
    96       ArcIt() { }
    97 
    98       ArcIt(Invalid i) : Arc(i) { }
    99 
   100       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   101         _adaptor->first(static_cast<Arc&>(*this));
   102       }
   103 
   104       ArcIt(const Adaptor& adaptor, const Arc& e) :
   105         Arc(e), _adaptor(&adaptor) { }
   106 
   107       ArcIt& operator++() {
   108         _adaptor->next(*this);
   109         return *this;
   110       }
   111 
   112     };
   113 
   114     LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
   115       return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
   116     }
   117 
   118 
   119     class OutArcIt : public Arc {
   120       const Adaptor* _adaptor;
   121     public:
   122 
   123       OutArcIt() { }
   124 
   125       OutArcIt(Invalid i) : Arc(i) { }
   126 
   127       OutArcIt(const Adaptor& adaptor, const Node& node)
   128         : _adaptor(&adaptor) {
   129         _adaptor->firstOut(*this, node);
   130       }
   131 
   132       OutArcIt(const Adaptor& adaptor, const Arc& arc)
   133         : Arc(arc), _adaptor(&adaptor) {}
   134 
   135       OutArcIt& operator++() {
   136         _adaptor->nextOut(*this);
   137         return *this;
   138       }
   139 
   140     };
   141 
   142     LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
   143       return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
   144     }
   145 
   146 
   147     class InArcIt : public Arc {
   148       const Adaptor* _adaptor;
   149     public:
   150 
   151       InArcIt() { }
   152 
   153       InArcIt(Invalid i) : Arc(i) { }
   154 
   155       InArcIt(const Adaptor& adaptor, const Node& node)
   156         : _adaptor(&adaptor) {
   157         _adaptor->firstIn(*this, node);
   158       }
   159 
   160       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   161         Arc(arc), _adaptor(&adaptor) {}
   162 
   163       InArcIt& operator++() {
   164         _adaptor->nextIn(*this);
   165         return *this;
   166       }
   167 
   168     };
   169 
   170     LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
   171       return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
   172     }
   173 
   174     Node baseNode(const OutArcIt &e) const {
   175       return Parent::source(e);
   176     }
   177     Node runningNode(const OutArcIt &e) const {
   178       return Parent::target(e);
   179     }
   180 
   181     Node baseNode(const InArcIt &e) const {
   182       return Parent::target(e);
   183     }
   184     Node runningNode(const InArcIt &e) const {
   185       return Parent::source(e);
   186     }
   187 
   188   };
   189 
   190   template <typename _Graph>
   191   class GraphAdaptorExtender : public _Graph {
   192     typedef _Graph Parent;
   193 
   194   public:
   195 
   196     typedef _Graph Graph;
   197     typedef GraphAdaptorExtender Adaptor;
   198 
   199     typedef True UndirectedTag;
   200 
   201     typedef typename Parent::Node Node;
   202     typedef typename Parent::Arc Arc;
   203     typedef typename Parent::Edge Edge;
   204 
   205     // Graph extension
   206 
   207     int maxId(Node) const {
   208       return Parent::maxNodeId();
   209     }
   210 
   211     int maxId(Arc) const {
   212       return Parent::maxArcId();
   213     }
   214 
   215     int maxId(Edge) const {
   216       return Parent::maxEdgeId();
   217     }
   218 
   219     Node fromId(int id, Node) const {
   220       return Parent::nodeFromId(id);
   221     }
   222 
   223     Arc fromId(int id, Arc) const {
   224       return Parent::arcFromId(id);
   225     }
   226 
   227     Edge fromId(int id, Edge) const {
   228       return Parent::edgeFromId(id);
   229     }
   230 
   231     Node oppositeNode(const Node &n, const Edge &e) const {
   232       if( n == Parent::u(e))
   233         return Parent::v(e);
   234       else if( n == Parent::v(e))
   235         return Parent::u(e);
   236       else
   237         return INVALID;
   238     }
   239 
   240     Arc oppositeArc(const Arc &a) const {
   241       return Parent::direct(a, !Parent::direction(a));
   242     }
   243 
   244     using Parent::direct;
   245     Arc direct(const Edge &e, const Node &s) const {
   246       return Parent::direct(e, Parent::u(e) == s);
   247     }
   248 
   249 
   250     class NodeIt : public Node {
   251       const Adaptor* _adaptor;
   252     public:
   253 
   254       NodeIt() {}
   255 
   256       NodeIt(Invalid i) : Node(i) { }
   257 
   258       explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   259         _adaptor->first(static_cast<Node&>(*this));
   260       }
   261 
   262       NodeIt(const Adaptor& adaptor, const Node& node)
   263         : Node(node), _adaptor(&adaptor) {}
   264 
   265       NodeIt& operator++() {
   266         _adaptor->next(*this);
   267         return *this;
   268       }
   269 
   270     };
   271 
   272     LemonRangeWrapper1<NodeIt, Adaptor> nodes() const {
   273       return LemonRangeWrapper1<NodeIt, Adaptor>(*this);
   274     }
   275 
   276 
   277     class ArcIt : public Arc {
   278       const Adaptor* _adaptor;
   279     public:
   280 
   281       ArcIt() { }
   282 
   283       ArcIt(Invalid i) : Arc(i) { }
   284 
   285       explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   286         _adaptor->first(static_cast<Arc&>(*this));
   287       }
   288 
   289       ArcIt(const Adaptor& adaptor, const Arc& e) :
   290         Arc(e), _adaptor(&adaptor) { }
   291 
   292       ArcIt& operator++() {
   293         _adaptor->next(*this);
   294         return *this;
   295       }
   296 
   297     };
   298 
   299     LemonRangeWrapper1<ArcIt, Adaptor> arcs() const {
   300       return LemonRangeWrapper1<ArcIt, Adaptor>(*this);
   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     LemonRangeWrapper2<OutArcIt, Adaptor, Node> outArcs(const Node& u) const {
   328       return LemonRangeWrapper2<OutArcIt, Adaptor, Node>(*this, u);
   329     }
   330 
   331 
   332     class InArcIt : public Arc {
   333       const Adaptor* _adaptor;
   334     public:
   335 
   336       InArcIt() { }
   337 
   338       InArcIt(Invalid i) : Arc(i) { }
   339 
   340       InArcIt(const Adaptor& adaptor, const Node& node)
   341         : _adaptor(&adaptor) {
   342         _adaptor->firstIn(*this, node);
   343       }
   344 
   345       InArcIt(const Adaptor& adaptor, const Arc& arc) :
   346         Arc(arc), _adaptor(&adaptor) {}
   347 
   348       InArcIt& operator++() {
   349         _adaptor->nextIn(*this);
   350         return *this;
   351       }
   352 
   353     };
   354 
   355     LemonRangeWrapper2<InArcIt, Adaptor, Node> inArcs(const Node& u) const {
   356       return LemonRangeWrapper2<InArcIt, Adaptor, Node>(*this, u);
   357     }
   358 
   359     class EdgeIt : public Parent::Edge {
   360       const Adaptor* _adaptor;
   361     public:
   362 
   363       EdgeIt() { }
   364 
   365       EdgeIt(Invalid i) : Edge(i) { }
   366 
   367       explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
   368         _adaptor->first(static_cast<Edge&>(*this));
   369       }
   370 
   371       EdgeIt(const Adaptor& adaptor, const Edge& e) :
   372         Edge(e), _adaptor(&adaptor) { }
   373 
   374       EdgeIt& operator++() {
   375         _adaptor->next(*this);
   376         return *this;
   377       }
   378 
   379     };
   380 
   381     LemonRangeWrapper1<EdgeIt, Adaptor> edges() const {
   382       return LemonRangeWrapper1<EdgeIt, Adaptor>(*this);
   383     }
   384 
   385 
   386     class IncEdgeIt : public Edge {
   387       friend class GraphAdaptorExtender;
   388       const Adaptor* _adaptor;
   389       bool direction;
   390     public:
   391 
   392       IncEdgeIt() { }
   393 
   394       IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
   395 
   396       IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
   397         _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
   398       }
   399 
   400       IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
   401         : _adaptor(&adaptor), Edge(e) {
   402         direction = (_adaptor->u(e) == n);
   403       }
   404 
   405       IncEdgeIt& operator++() {
   406         _adaptor->nextInc(*this, direction);
   407         return *this;
   408       }
   409     };
   410 
   411     LemonRangeWrapper2<IncEdgeIt, Adaptor, Node> incEdges(const Node& u) const {
   412       return LemonRangeWrapper2<IncEdgeIt, Adaptor, Node>(*this, u);
   413     }
   414 
   415 
   416     Node baseNode(const OutArcIt &a) const {
   417       return Parent::source(a);
   418     }
   419     Node runningNode(const OutArcIt &a) const {
   420       return Parent::target(a);
   421     }
   422 
   423     Node baseNode(const InArcIt &a) const {
   424       return Parent::target(a);
   425     }
   426     Node runningNode(const InArcIt &a) const {
   427       return Parent::source(a);
   428     }
   429 
   430     Node baseNode(const IncEdgeIt &e) const {
   431       return e.direction ? Parent::u(e) : Parent::v(e);
   432     }
   433     Node runningNode(const IncEdgeIt &e) const {
   434       return e.direction ? Parent::v(e) : Parent::u(e);
   435     }
   436 
   437   };
   438 
   439 }
   440 
   441 
   442 #endif