Mercuriallemon-1.0 / 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 Alpar Juttner <alpar@cs.elte.hu>
Sat, 12 Apr 2008 19:41:48 +0100
changeset 121 91c0fed3181e
parent 57 c1acf0018c0a
child 209 765619b7cbb2
permissions -rw-r--r--
Change SubNoCounter to NoSubCounter 
     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_BASE_EXTENDER_H

    20 #define LEMON_BITS_BASE_EXTENDER_H

    21 

    22 #include <lemon/bits/invalid.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 

    78 

    79     using Parent::source;

    80 

    81     /// Source of the given Arc.

    82     Node source(const Arc &e) const {

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

    84     }

    85 

    86     using Parent::target;

    87 

    88     /// Target of the given Arc.

    89     Node target(const Arc &e) const {

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

    91     }

    92 

    93     /// \brief Directed arc from an edge.

    94     ///

    95     /// Returns a directed arc corresponding to the specified Edge.

    96     /// If the given bool is true the given edge and the

    97     /// returned arc have the same source node.

    98     static Arc direct(const Edge &ue, bool d) {

    99       return Arc(ue, d);

   100     }

   101 

   102     /// Returns whether the given directed arc is same orientation as the

   103     /// corresponding edge.

   104     ///

   105     /// \todo reference to the corresponding point of the undirected digraph

   106     /// concept. "What does the direction of an edge mean?"

   107     static bool direction(const Arc &e) { return e.forward; }

   108 

   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 

   233     int arcNum() const {

   234       return 2 * Parent::arcNum();

   235     }

   236 

   237     int edgeNum() const {

   238       return Parent::arcNum();

   239     }

   240 

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

   242       if (p == INVALID) {

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

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

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

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

   247       } else if (direction(p)) {

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

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

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

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

   252       } else {

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

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

   255       }

   256       return INVALID;

   257     }

   258 

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

   260       if (s != t) {

   261         if (p == INVALID) {

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

   263           if (arc != INVALID) return arc;

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

   265           if (arc != INVALID) return arc;

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

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

   268           if (arc != INVALID) return arc;

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

   270           if (arc != INVALID) return arc;	

   271         } else {

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

   273           if (arc != INVALID) return arc;	      

   274         }

   275       } else {

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

   277       }

   278       return INVALID;

   279     }

   280   };

   281 

   282   template <typename Base>

   283   class BidirBpGraphExtender : public Base {

   284   public:

   285     typedef Base Parent;

   286     typedef BidirBpGraphExtender Digraph;

   287 

   288     typedef typename Parent::Node Node;

   289     typedef typename Parent::Edge Edge;

   290 

   291 

   292     using Parent::first;

   293     using Parent::next;

   294 

   295     using Parent::id;

   296 

   297     class Red : public Node {

   298       friend class BidirBpGraphExtender;

   299     public:

   300       Red() {}

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

   302 	LEMON_ASSERT(Parent::red(node) || node == INVALID, 

   303 		     typename Parent::NodeSetError());

   304       }

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

   306 	LEMON_ASSERT(Parent::red(node) || node == INVALID, 

   307 		     typename Parent::NodeSetError());

   308         Node::operator=(node);

   309         return *this;

   310       }

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

   312       Red& operator=(Invalid) {

   313         Node::operator=(INVALID);

   314         return *this;

   315       }

   316     };

   317 

   318     void first(Red& node) const {

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

   320     }

   321     void next(Red& node) const {

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

   323     }

   324 

   325     int id(const Red& node) const {

   326       return Parent::redId(node);

   327     }

   328 

   329     class Blue : public Node {

   330       friend class BidirBpGraphExtender;

   331     public:

   332       Blue() {}

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

   334 	LEMON_ASSERT(Parent::blue(node) || node == INVALID,

   335 		     typename Parent::NodeSetError());

   336       }

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

   338 	LEMON_ASSERT(Parent::blue(node) || node == INVALID, 

   339 		     typename Parent::NodeSetError());

   340         Node::operator=(node);

   341         return *this;

   342       }

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

   344       Blue& operator=(Invalid) {

   345         Node::operator=(INVALID);

   346         return *this;

   347       }

   348     };

   349 

   350     void first(Blue& node) const {

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

   352     }

   353     void next(Blue& node) const {

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

   355     }

   356   

   357     int id(const Blue& node) const {

   358       return Parent::redId(node);

   359     }

   360 

   361     Node source(const Edge& arc) const {

   362       return red(arc);

   363     }

   364     Node target(const Edge& arc) const {

   365       return blue(arc);

   366     }

   367 

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

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

   370 	Parent::firstFromRed(arc, node);

   371 	dir = true;

   372       } else {

   373 	Parent::firstFromBlue(arc, node);

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

   375       }

   376     }

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

   378       if (dir) {

   379 	Parent::nextFromRed(arc);

   380       } else {

   381 	Parent::nextFromBlue(arc);

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

   383       }

   384     }

   385 

   386     class Arc : public Edge {

   387       friend class BidirBpGraphExtender;

   388     protected:

   389       bool forward;

   390 

   391       Arc(const Edge& arc, bool _forward)

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

   393 

   394     public:

   395       Arc() {}

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

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

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

   399       }

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

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

   402       }

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

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

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

   406       }

   407     };

   408 

   409     void first(Arc& arc) const {

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

   411       arc.forward = true;

   412     }

   413 

   414     void next(Arc& arc) const {

   415       if (!arc.forward) {

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

   417       }

   418       arc.forward = !arc.forward;

   419     }

   420 

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

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

   423 	Parent::firstFromRed(arc, node);

   424 	arc.forward = true;

   425       } else {

   426 	Parent::firstFromBlue(arc, node);

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

   428       }

   429     }

   430     void nextOut(Arc& arc) const {

   431       if (arc.forward) {

   432 	Parent::nextFromRed(arc);

   433       } else {

   434 	Parent::nextFromBlue(arc);

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

   436       }

   437     }

   438 

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

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

   441 	Parent::firstFromBlue(arc, node);

   442 	arc.forward = true;	

   443       } else {

   444 	Parent::firstFromRed(arc, node);

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

   446       }

   447     }

   448     void nextIn(Arc& arc) const {

   449       if (arc.forward) {

   450 	Parent::nextFromBlue(arc);

   451       } else {

   452 	Parent::nextFromRed(arc);

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

   454       }

   455     }

   456 

   457     Node source(const Arc& arc) const {

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

   459     }

   460     Node target(const Arc& arc) const {

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

   462     }

   463 

   464     int id(const Arc& arc) const {

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

   466         (arc.forward ? 0 : 1);

   467     }

   468     Arc arcFromId(int ix) const {

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

   470     }

   471     int maxArcId() const {

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

   473     }

   474 

   475     bool direction(const Arc& arc) const {

   476       return arc.forward;

   477     }

   478 

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

   480       return Arc(arc, dir);

   481     }

   482 

   483     int arcNum() const {

   484       return 2 * Parent::edgeNum();

   485     }

   486 

   487     int edgeNum() const {

   488       return Parent::edgeNum();

   489     }

   490 

   491 

   492   };

   493 }

   494 

   495 #endif
lemon-1.0