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 Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 361 f58410582b9b
child 617 4137ef9aacc6
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread 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-2009

     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 graph 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