Mercuriallemon-0.x / 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 deba
Tue, 04 Apr 2006 17:45:35 +0000
changeset 2038 33db14058543
parent 1999 2ff283124dfc
child 2076 10681ee9d8ae
permissions -rw-r--r--
LinearHeap is renamed to BucketHeap which is more conform
and widely used name for this data structure 
     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     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/concept/maps.h>

    30 

    31 ///\ingroup graphbits

    32 ///\file

    33 ///\brief Extenders for the graph types

    34 namespace lemon {

    35 

    36   /// \ingroup graphbits

    37   ///

    38   /// \brief BaseExtender for the UGraphs

    39   template <typename Base>

    40   class UGraphBaseExtender : public Base {

    41 

    42   public:

    43 

    44     typedef Base Parent;

    45     typedef typename Parent::Edge UEdge;

    46     typedef typename Parent::Node Node;

    47 

    48     typedef True UndirectedTag;

    49 

    50     class Edge : public UEdge {

    51       friend class UGraphBaseExtender;

    52 

    53     protected:

    54       bool forward;

    55 

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

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

    58 

    59     public:

    60       Edge() {}

    61 

    62       /// Invalid edge constructor

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

    64 

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

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

    67       }

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

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

    70       }

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

    72 	return forward<that.forward ||

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

    74       }

    75     };

    76 

    77 

    78 

    79     using Parent::source;

    80 

    81     /// Source of the given Edge.

    82     Node source(const Edge &e) const {

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

    84     }

    85 

    86     using Parent::target;

    87 

    88     /// Target of the given Edge.

    89     Node target(const Edge &e) const {

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

    91     }

    92 

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

    94     ///

    95     /// Returns a directed edge corresponding to the specified UEdge.

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

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

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

    99       return Edge(ue, d);

   100     }

   101 

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

   103     /// corresponding undirected edge.

   104     ///

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

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

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

   108 

   109 

   110     using Parent::first;

   111     using Parent::next;

   112 

   113     void first(Edge &e) const {

   114       Parent::first(e);

   115       e.forward=true;

   116     }

   117 

   118     void next(Edge &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(Edge &e, const Node &n) const {

   129       Parent::firstIn(e,n);

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

   131 	e.forward = false;

   132       }

   133       else {

   134 	Parent::firstOut(e,n);

   135 	e.forward = true;

   136       }

   137     }

   138     void nextOut(Edge &e) const {

   139       if( ! e.forward ) {

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

   141 	Parent::nextIn(e);

   142 	if( UEdge(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(Edge &e, const Node &n) const {

   153       Parent::firstOut(e,n);

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

   155 	e.forward = false;

   156       }

   157       else {

   158 	Parent::firstIn(e,n);

   159 	e.forward = true;

   160       }

   161     }

   162     void nextIn(Edge &e) const {

   163       if( ! e.forward ) {

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

   165 	Parent::nextOut(e);

   166 	if( UEdge(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(UEdge &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(UEdge &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 id) const {

   197       return Parent::nodeFromId(id);

   198     }

   199 

   200     Edge edgeFromId(int id) const {

   201       return direct(Parent::edgeFromId(id >> 1), bool(id & 1));

   202     }

   203 

   204     UEdge uEdgeFromId(int id) const {

   205       return Parent::edgeFromId(id >> 1);

   206     }

   207 

   208     int id(const Node &n) const {

   209       return Parent::id(n);

   210     }

   211 

   212     int id(const UEdge &e) const {

   213       return Parent::id(e);

   214     }

   215 

   216     int id(const Edge &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 maxEdgeId() const {

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

   226     }

   227 

   228     int maxUEdgeId() const {

   229       return Parent::maxEdgeId();

   230     }

   231 

   232 

   233     int edgeNum() const {

   234       return 2 * Parent::edgeNum();

   235     }

   236 

   237     int uEdgeNum() const {

   238       return Parent::edgeNum();

   239     }

   240 

   241     Edge findEdge(Node source, Node target, Edge prev) const {

   242       if (prev == INVALID) {

   243 	UEdge edge = Parent::findEdge(source, target);

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

   245 	edge = Parent::findEdge(target, source);

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

   247       } else if (direction(prev)) {

   248 	UEdge edge = Parent::findEdge(source, target, prev);

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

   250 	edge = Parent::findEdge(target, source);

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

   252       } else {

   253 	UEdge edge = Parent::findEdge(target, source, prev);

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

   255       }

   256       return INVALID;

   257     }

   258 

   259     UEdge findUEdge(Node source, Node target, UEdge prev) const {

   260       if (prev == INVALID) {

   261 	UEdge edge = Parent::findEdge(source, target);

   262 	if (edge != INVALID) return edge;

   263 	edge = Parent::findEdge(target, source);

   264 	if (edge != INVALID) return edge;

   265       } else if (Parent::source(prev) == source) {

   266 	UEdge edge = Parent::findEdge(source, target, prev);

   267 	if (edge != INVALID) return edge;

   268 	edge = Parent::findEdge(target, source);

   269 	if (edge != INVALID) return edge;	

   270       } else {

   271 	UEdge edge = Parent::findEdge(target, source, prev);

   272 	if (edge != INVALID) return edge;	      

   273       }

   274       return INVALID;

   275     }

   276   };

   277 

   278 

   279   /// \ingroup graphbits

   280   ///

   281   /// \brief BaseExtender for the BpUGraphs

   282   template <typename Base>

   283   class BpUGraphBaseExtender : public Base {

   284   public:

   285     typedef Base Parent;

   286     typedef BpUGraphBaseExtender Graph;

   287 

   288     typedef typename Parent::Node Node;

   289     typedef typename Parent::Edge UEdge;

   290 

   291 

   292     using Parent::first;

   293     using Parent::next;

   294 

   295     using Parent::id;

   296 

   297     class ANode : public Node {

   298       friend class BpUGraphBaseExtender;

   299     public:

   300       ANode() {}

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

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

   303 		     typename Parent::NodeSetError());

   304       }

   305       ANode(Invalid) : Node(INVALID) {}

   306     };

   307 

   308     void first(ANode& node) const {

   309       Parent::firstANode(static_cast<Node&>(node));

   310     }

   311     void next(ANode& node) const {

   312       Parent::nextANode(static_cast<Node&>(node));

   313     }

   314 

   315     int id(const ANode& node) const {

   316       return Parent::aNodeId(node);

   317     }

   318 

   319     class BNode : public Node {

   320       friend class BpUGraphBaseExtender;

   321     public:

   322       BNode() {}

   323       BNode(const Node& node) : Node(node) {

   324 	LEMON_ASSERT(Parent::bNode(node) || node == INVALID,

   325 		     typename Parent::NodeSetError());

   326       }

   327       BNode(Invalid) : Node(INVALID) {}

   328     };

   329 

   330     void first(BNode& node) const {

   331       Parent::firstBNode(static_cast<Node&>(node));

   332     }

   333     void next(BNode& node) const {

   334       Parent::nextBNode(static_cast<Node&>(node));

   335     }

   336   

   337     int id(const BNode& node) const {

   338       return Parent::aNodeId(node);

   339     }

   340 

   341     Node source(const UEdge& edge) const {

   342       return aNode(edge);

   343     }

   344     Node target(const UEdge& edge) const {

   345       return bNode(edge);

   346     }

   347 

   348     void firstInc(UEdge& edge, bool& direction, const Node& node) const {

   349       if (Parent::aNode(node)) {

   350 	Parent::firstOut(edge, node);

   351 	direction = true;

   352       } else {

   353 	Parent::firstIn(edge, node);

   354 	direction = static_cast<UEdge&>(edge) == INVALID;

   355       }

   356     }

   357     void nextInc(UEdge& edge, bool& direction) const {

   358       if (direction) {

   359 	Parent::nextOut(edge);

   360       } else {

   361 	Parent::nextIn(edge);

   362 	if (edge == INVALID) direction = true;

   363       }

   364     }

   365 

   366     int maxUEdgeId() const {

   367       return Parent::maxEdgeId();

   368     }

   369 

   370     UEdge uEdgeFromId(int id) const {

   371       return Parent::edgeFromId(id);

   372     }

   373 

   374     class Edge : public UEdge {

   375       friend class BpUGraphBaseExtender;

   376     protected:

   377       bool forward;

   378 

   379       Edge(const UEdge& edge, bool _forward)

   380 	: UEdge(edge), forward(_forward) {}

   381 

   382     public:

   383       Edge() {}

   384       Edge (Invalid) : UEdge(INVALID), forward(true) {}

   385       bool operator==(const Edge& i) const {

   386 	return UEdge::operator==(i) && forward == i.forward;

   387       }

   388       bool operator!=(const Edge& i) const {

   389 	return UEdge::operator!=(i) || forward != i.forward;

   390       }

   391       bool operator<(const Edge& i) const {

   392 	return UEdge::operator<(i) || 

   393 	  (!(i.forward<forward) && UEdge(*this)<UEdge(i));

   394       }

   395     };

   396 

   397     void first(Edge& edge) const {

   398       Parent::first(static_cast<UEdge&>(edge));

   399       edge.forward = true;

   400     }

   401 

   402     void next(Edge& edge) const {

   403       if (!edge.forward) {

   404 	Parent::next(static_cast<UEdge&>(edge));

   405       }

   406       edge.forward = !edge.forward;

   407     }

   408 

   409     void firstOut(Edge& edge, const Node& node) const {

   410       if (Parent::aNode(node)) {

   411 	Parent::firstOut(edge, node);

   412 	edge.forward = true;

   413       } else {

   414 	Parent::firstIn(edge, node);

   415 	edge.forward = static_cast<UEdge&>(edge) == INVALID;

   416       }

   417     }

   418     void nextOut(Edge& edge) const {

   419       if (edge.forward) {

   420 	Parent::nextOut(edge);

   421       } else {

   422 	Parent::nextIn(edge);

   423         edge.forward = static_cast<UEdge&>(edge) == INVALID;

   424       }

   425     }

   426 

   427     void firstIn(Edge& edge, const Node& node) const {

   428       if (Parent::bNode(node)) {

   429 	Parent::firstIn(edge, node);

   430 	edge.forward = true;	

   431       } else {

   432 	Parent::firstOut(edge, node);

   433 	edge.forward = static_cast<UEdge&>(edge) == INVALID;

   434       }

   435     }

   436     void nextIn(Edge& edge) const {

   437       if (edge.forward) {

   438 	Parent::nextIn(edge);

   439       } else {

   440 	Parent::nextOut(edge);

   441 	edge.forward = static_cast<UEdge&>(edge) == INVALID;

   442       }

   443     }

   444 

   445     Node source(const Edge& edge) const {

   446       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);

   447     }

   448     Node target(const Edge& edge) const {

   449       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);

   450     }

   451 

   452     int id(const Edge& edge) const {

   453       return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);

   454     }

   455     Edge edgeFromId(int id) const {

   456       return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);

   457     }

   458     int maxEdgeId() const {

   459       return (Parent::maxId(UEdge()) << 1) + 1;

   460     }

   461 

   462     bool direction(const Edge& edge) const {

   463       return edge.forward;

   464     }

   465 

   466     Edge direct(const UEdge& edge, bool direction) const {

   467       return Edge(edge, direction);

   468     }

   469 

   470     int edgeNum() const {

   471       return 2 * Parent::edgeNum();

   472     }

   473 

   474     int uEdgeNum() const {

   475       return Parent::edgeNum();

   476     }

   477 

   478   };

   479 

   480 }

   481 

   482 #endif
lemon-0.x