Mercuriallemon-main / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/base_extender.h
author Balazs Dezso <deba@inf.elte.hu>
Sun, 21 Dec 2008 00:13:02 +0100
changeset 436 561be42c4b99
parent 289 d91884dcd572
child 361 f58410582b9b
permissions -rw-r--r--
Bug fix in heap unionfind (ticket #197)

The minimum item in the unionfind tree might become inconsistent when
the split operation merges two subtrees which have equal keys. The
current changeset fix the problem. It also fix a wrong index. 
     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-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_BASE_EXTENDER_H

    20 #define LEMON_BITS_BASE_EXTENDER_H

    21 

    22 #include <lemon/core.h>

    23 #include <lemon/error.h>

    24 

    25 #include <lemon/bits/map_extender.h>

    26 #include <lemon/bits/default_map.h>

    27 

    28 #include <lemon/concept_check.h>

    29 #include <lemon/concepts/maps.h>

    30 

    31 //\ingroup digraphbits

    32 //\file

    33 //\brief Extenders for the digraph types

    34 namespace lemon {

    35 

    36   // \ingroup digraphbits

    37   //

    38   // \brief BaseDigraph to BaseGraph extender

    39   template <typename Base>

    40   class UndirDigraphExtender : public Base {

    41 

    42   public:

    43 

    44     typedef Base Parent;

    45     typedef typename Parent::Arc Edge;

    46     typedef typename Parent::Node Node;

    47 

    48     typedef True UndirectedTag;

    49 

    50     class Arc : public Edge {

    51       friend class UndirDigraphExtender;

    52 

    53     protected:

    54       bool forward;

    55 

    56       Arc(const Edge &ue, bool _forward) :

    57         Edge(ue), forward(_forward) {}

    58 

    59     public:

    60       Arc() {}

    61 

    62       // Invalid arc constructor

    63       Arc(Invalid i) : Edge(i), forward(true) {}

    64 

    65       bool operator==(const Arc &that) const {

    66         return forward==that.forward && Edge(*this)==Edge(that);

    67       }

    68       bool operator!=(const Arc &that) const {

    69         return forward!=that.forward || Edge(*this)!=Edge(that);

    70       }

    71       bool operator<(const Arc &that) const {

    72         return forward<that.forward ||

    73           (!(that.forward<forward) && Edge(*this)<Edge(that));

    74       }

    75     };

    76 

    77     // First node of the edge

    78     Node u(const Edge &e) const {

    79       return Parent::source(e);

    80     }

    81 

    82     // Source of the given arc

    83     Node source(const Arc &e) const {

    84       return e.forward ? Parent::source(e) : Parent::target(e);

    85     }

    86 

    87     // Second node of the edge

    88     Node v(const Edge &e) const {

    89       return Parent::target(e);

    90     }

    91 

    92     // Target of the given arc

    93     Node target(const Arc &e) const {

    94       return e.forward ? Parent::target(e) : Parent::source(e);

    95     }

    96 

    97     // \brief Directed arc from an edge.

    98     //

    99     // Returns a directed arc corresponding to the specified edge.

   100     // If the given bool is true, the first node of the given edge and

   101     // the source node of the returned arc are the same.

   102     static Arc direct(const Edge &e, bool d) {

   103       return Arc(e, d);

   104     }

   105 

   106     // Returns whether the given directed arc has the same orientation

   107     // as the corresponding edge.

   108     static bool direction(const Arc &a) { return a.forward; }

   109 

   110     using Parent::first;

   111     using Parent::next;

   112 

   113     void first(Arc &e) const {

   114       Parent::first(e);

   115       e.forward=true;

   116     }

   117 

   118     void next(Arc &e) const {

   119       if( e.forward ) {

   120         e.forward = false;

   121       }

   122       else {

   123         Parent::next(e);

   124         e.forward = true;

   125       }

   126     }

   127 

   128     void firstOut(Arc &e, const Node &n) const {

   129       Parent::firstIn(e,n);

   130       if( Edge(e) != INVALID ) {

   131         e.forward = false;

   132       }

   133       else {

   134         Parent::firstOut(e,n);

   135         e.forward = true;

   136       }

   137     }

   138     void nextOut(Arc &e) const {

   139       if( ! e.forward ) {

   140         Node n = Parent::target(e);

   141         Parent::nextIn(e);

   142         if( Edge(e) == INVALID ) {

   143           Parent::firstOut(e, n);

   144           e.forward = true;

   145         }

   146       }

   147       else {

   148         Parent::nextOut(e);

   149       }

   150     }

   151 

   152     void firstIn(Arc &e, const Node &n) const {

   153       Parent::firstOut(e,n);

   154       if( Edge(e) != INVALID ) {

   155         e.forward = false;

   156       }

   157       else {

   158         Parent::firstIn(e,n);

   159         e.forward = true;

   160       }

   161     }

   162     void nextIn(Arc &e) const {

   163       if( ! e.forward ) {

   164         Node n = Parent::source(e);

   165         Parent::nextOut(e);

   166         if( Edge(e) == INVALID ) {

   167           Parent::firstIn(e, n);

   168           e.forward = true;

   169         }

   170       }

   171       else {

   172         Parent::nextIn(e);

   173       }

   174     }

   175 

   176     void firstInc(Edge &e, bool &d, const Node &n) const {

   177       d = true;

   178       Parent::firstOut(e, n);

   179       if (e != INVALID) return;

   180       d = false;

   181       Parent::firstIn(e, n);

   182     }

   183 

   184     void nextInc(Edge &e, bool &d) const {

   185       if (d) {

   186         Node s = Parent::source(e);

   187         Parent::nextOut(e);

   188         if (e != INVALID) return;

   189         d = false;

   190         Parent::firstIn(e, s);

   191       } else {

   192         Parent::nextIn(e);

   193       }

   194     }

   195 

   196     Node nodeFromId(int ix) const {

   197       return Parent::nodeFromId(ix);

   198     }

   199 

   200     Arc arcFromId(int ix) const {

   201       return direct(Parent::arcFromId(ix >> 1), bool(ix & 1));

   202     }

   203 

   204     Edge edgeFromId(int ix) const {

   205       return Parent::arcFromId(ix);

   206     }

   207 

   208     int id(const Node &n) const {

   209       return Parent::id(n);

   210     }

   211 

   212     int id(const Edge &e) const {

   213       return Parent::id(e);

   214     }

   215 

   216     int id(const Arc &e) const {

   217       return 2 * Parent::id(e) + int(e.forward);

   218     }

   219 

   220     int maxNodeId() const {

   221       return Parent::maxNodeId();

   222     }

   223 

   224     int maxArcId() const {

   225       return 2 * Parent::maxArcId() + 1;

   226     }

   227 

   228     int maxEdgeId() const {

   229       return Parent::maxArcId();

   230     }

   231 

   232     int arcNum() const {

   233       return 2 * Parent::arcNum();

   234     }

   235 

   236     int edgeNum() const {

   237       return Parent::arcNum();

   238     }

   239 

   240     Arc findArc(Node s, Node t, Arc p = INVALID) const {

   241       if (p == INVALID) {

   242         Edge arc = Parent::findArc(s, t);

   243         if (arc != INVALID) return direct(arc, true);

   244         arc = Parent::findArc(t, s);

   245         if (arc != INVALID) return direct(arc, false);

   246       } else if (direction(p)) {

   247         Edge arc = Parent::findArc(s, t, p);

   248         if (arc != INVALID) return direct(arc, true);

   249         arc = Parent::findArc(t, s);

   250         if (arc != INVALID) return direct(arc, false);

   251       } else {

   252         Edge arc = Parent::findArc(t, s, p);

   253         if (arc != INVALID) return direct(arc, false);

   254       }

   255       return INVALID;

   256     }

   257 

   258     Edge findEdge(Node s, Node t, Edge p = INVALID) const {

   259       if (s != t) {

   260         if (p == INVALID) {

   261           Edge arc = Parent::findArc(s, t);

   262           if (arc != INVALID) return arc;

   263           arc = Parent::findArc(t, s);

   264           if (arc != INVALID) return arc;

   265         } else if (Parent::s(p) == s) {

   266           Edge arc = Parent::findArc(s, t, p);

   267           if (arc != INVALID) return arc;

   268           arc = Parent::findArc(t, s);

   269           if (arc != INVALID) return arc;

   270         } else {

   271           Edge arc = Parent::findArc(t, s, p);

   272           if (arc != INVALID) return arc;

   273         }

   274       } else {

   275         return Parent::findArc(s, t, p);

   276       }

   277       return INVALID;

   278     }

   279   };

   280 

   281   template <typename Base>

   282   class BidirBpGraphExtender : public Base {

   283   public:

   284     typedef Base Parent;

   285     typedef BidirBpGraphExtender Digraph;

   286 

   287     typedef typename Parent::Node Node;

   288     typedef typename Parent::Edge Edge;

   289 

   290 

   291     using Parent::first;

   292     using Parent::next;

   293 

   294     using Parent::id;

   295 

   296     class Red : public Node {

   297       friend class BidirBpGraphExtender;

   298     public:

   299       Red() {}

   300       Red(const Node& node) : Node(node) {

   301         LEMON_DEBUG(Parent::red(node) || node == INVALID,

   302                     typename Parent::NodeSetError());

   303       }

   304       Red& operator=(const Node& node) {

   305         LEMON_DEBUG(Parent::red(node) || node == INVALID,

   306                     typename Parent::NodeSetError());

   307         Node::operator=(node);

   308         return *this;

   309       }

   310       Red(Invalid) : Node(INVALID) {}

   311       Red& operator=(Invalid) {

   312         Node::operator=(INVALID);

   313         return *this;

   314       }

   315     };

   316 

   317     void first(Red& node) const {

   318       Parent::firstRed(static_cast<Node&>(node));

   319     }

   320     void next(Red& node) const {

   321       Parent::nextRed(static_cast<Node&>(node));

   322     }

   323 

   324     int id(const Red& node) const {

   325       return Parent::redId(node);

   326     }

   327 

   328     class Blue : public Node {

   329       friend class BidirBpGraphExtender;

   330     public:

   331       Blue() {}

   332       Blue(const Node& node) : Node(node) {

   333         LEMON_DEBUG(Parent::blue(node) || node == INVALID,

   334                     typename Parent::NodeSetError());

   335       }

   336       Blue& operator=(const Node& node) {

   337         LEMON_DEBUG(Parent::blue(node) || node == INVALID,

   338                     typename Parent::NodeSetError());

   339         Node::operator=(node);

   340         return *this;

   341       }

   342       Blue(Invalid) : Node(INVALID) {}

   343       Blue& operator=(Invalid) {

   344         Node::operator=(INVALID);

   345         return *this;

   346       }

   347     };

   348 

   349     void first(Blue& node) const {

   350       Parent::firstBlue(static_cast<Node&>(node));

   351     }

   352     void next(Blue& node) const {

   353       Parent::nextBlue(static_cast<Node&>(node));

   354     }

   355 

   356     int id(const Blue& node) const {

   357       return Parent::redId(node);

   358     }

   359 

   360     Node source(const Edge& arc) const {

   361       return red(arc);

   362     }

   363     Node target(const Edge& arc) const {

   364       return blue(arc);

   365     }

   366 

   367     void firstInc(Edge& arc, bool& dir, const Node& node) const {

   368       if (Parent::red(node)) {

   369         Parent::firstFromRed(arc, node);

   370         dir = true;

   371       } else {

   372         Parent::firstFromBlue(arc, node);

   373         dir = static_cast<Edge&>(arc) == INVALID;

   374       }

   375     }

   376     void nextInc(Edge& arc, bool& dir) const {

   377       if (dir) {

   378         Parent::nextFromRed(arc);

   379       } else {

   380         Parent::nextFromBlue(arc);

   381         if (arc == INVALID) dir = true;

   382       }

   383     }

   384 

   385     class Arc : public Edge {

   386       friend class BidirBpGraphExtender;

   387     protected:

   388       bool forward;

   389 

   390       Arc(const Edge& arc, bool _forward)

   391         : Edge(arc), forward(_forward) {}

   392 

   393     public:

   394       Arc() {}

   395       Arc (Invalid) : Edge(INVALID), forward(true) {}

   396       bool operator==(const Arc& i) const {

   397         return Edge::operator==(i) && forward == i.forward;

   398       }

   399       bool operator!=(const Arc& i) const {

   400         return Edge::operator!=(i) || forward != i.forward;

   401       }

   402       bool operator<(const Arc& i) const {

   403         return Edge::operator<(i) ||

   404           (!(i.forward<forward) && Edge(*this)<Edge(i));

   405       }

   406     };

   407 

   408     void first(Arc& arc) const {

   409       Parent::first(static_cast<Edge&>(arc));

   410       arc.forward = true;

   411     }

   412 

   413     void next(Arc& arc) const {

   414       if (!arc.forward) {

   415         Parent::next(static_cast<Edge&>(arc));

   416       }

   417       arc.forward = !arc.forward;

   418     }

   419 

   420     void firstOut(Arc& arc, const Node& node) const {

   421       if (Parent::red(node)) {

   422         Parent::firstFromRed(arc, node);

   423         arc.forward = true;

   424       } else {

   425         Parent::firstFromBlue(arc, node);

   426         arc.forward = static_cast<Edge&>(arc) == INVALID;

   427       }

   428     }

   429     void nextOut(Arc& arc) const {

   430       if (arc.forward) {

   431         Parent::nextFromRed(arc);

   432       } else {

   433         Parent::nextFromBlue(arc);

   434         arc.forward = static_cast<Edge&>(arc) == INVALID;

   435       }

   436     }

   437 

   438     void firstIn(Arc& arc, const Node& node) const {

   439       if (Parent::blue(node)) {

   440         Parent::firstFromBlue(arc, node);

   441         arc.forward = true;

   442       } else {

   443         Parent::firstFromRed(arc, node);

   444         arc.forward = static_cast<Edge&>(arc) == INVALID;

   445       }

   446     }

   447     void nextIn(Arc& arc) const {

   448       if (arc.forward) {

   449         Parent::nextFromBlue(arc);

   450       } else {

   451         Parent::nextFromRed(arc);

   452         arc.forward = static_cast<Edge&>(arc) == INVALID;

   453       }

   454     }

   455 

   456     Node source(const Arc& arc) const {

   457       return arc.forward ? Parent::red(arc) : Parent::blue(arc);

   458     }

   459     Node target(const Arc& arc) const {

   460       return arc.forward ? Parent::blue(arc) : Parent::red(arc);

   461     }

   462 

   463     int id(const Arc& arc) const {

   464       return (Parent::id(static_cast<const Edge&>(arc)) << 1) +

   465         (arc.forward ? 0 : 1);

   466     }

   467     Arc arcFromId(int ix) const {

   468       return Arc(Parent::fromEdgeId(ix >> 1), (ix & 1) == 0);

   469     }

   470     int maxArcId() const {

   471       return (Parent::maxEdgeId() << 1) + 1;

   472     }

   473 

   474     bool direction(const Arc& arc) const {

   475       return arc.forward;

   476     }

   477 

   478     Arc direct(const Edge& arc, bool dir) const {

   479       return Arc(arc, dir);

   480     }

   481 

   482     int arcNum() const {

   483       return 2 * Parent::edgeNum();

   484     }

   485 

   486     int edgeNum() const {

   487       return Parent::edgeNum();

   488     }

   489 

   490 

   491   };

   492 }

   493 

   494 #endif
lemon-main