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, 17 Oct 2006 10:50:57 +0000
changeset 2247 269a0dcee70b
parent 2222 a24939ee343c
child 2260 4274224f8a7d
permissions -rw-r--r--
Update the Path concept
Concept check for paths

DirPath renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed
// I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation 
     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 BaseGraph to BaseUGraph extender

    39   template <typename Base>

    40   class UndirGraphExtender : 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 UndirGraphExtender;

    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);

   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 = INVALID) 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 = INVALID) const {

   260       if (source != target) {

   261         if (prev == INVALID) {

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

   263           if (edge != INVALID) return edge;

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

   265           if (edge != INVALID) return edge;

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

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

   268           if (edge != INVALID) return edge;

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

   270           if (edge != INVALID) return edge;	

   271         } else {

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

   273           if (edge != INVALID) return edge;	      

   274         }

   275       } else {

   276         return Parent::findEdge(source, target, prev);

   277       }

   278       return INVALID;

   279     }

   280   };

   281 

   282   template <typename Base>

   283   class BidirBpUGraphExtender : public Base {

   284   public:

   285     typedef Base Parent;

   286     typedef BidirBpUGraphExtender Graph;

   287 

   288     typedef typename Parent::Node Node;

   289     typedef typename Parent::UEdge 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 BidirBpUGraphExtender;

   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& operator=(const Node& node) {

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

   307 		     typename Parent::NodeSetError());

   308         Node::operator=(node);

   309         return *this;

   310       }

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

   312     };

   313 

   314     void first(ANode& node) const {

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

   316     }

   317     void next(ANode& node) const {

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

   319     }

   320 

   321     int id(const ANode& node) const {

   322       return Parent::aNodeId(node);

   323     }

   324 

   325     class BNode : public Node {

   326       friend class BidirBpUGraphExtender;

   327     public:

   328       BNode() {}

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

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

   331 		     typename Parent::NodeSetError());

   332       }

   333       BNode& operator=(const Node& node) {

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

   335 		     typename Parent::NodeSetError());

   336         Node::operator=(node);

   337         return *this;

   338       }

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

   340     };

   341 

   342     void first(BNode& node) const {

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

   344     }

   345     void next(BNode& node) const {

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

   347     }

   348   

   349     int id(const BNode& node) const {

   350       return Parent::aNodeId(node);

   351     }

   352 

   353     Node source(const UEdge& edge) const {

   354       return aNode(edge);

   355     }

   356     Node target(const UEdge& edge) const {

   357       return bNode(edge);

   358     }

   359 

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

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

   362 	Parent::firstFromANode(edge, node);

   363 	direction = true;

   364       } else {

   365 	Parent::firstFromBNode(edge, node);

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

   367       }

   368     }

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

   370       if (direction) {

   371 	Parent::nextFromANode(edge);

   372       } else {

   373 	Parent::nextFromBNode(edge);

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

   375       }

   376     }

   377 

   378     class Edge : public UEdge {

   379       friend class BidirBpUGraphExtender;

   380     protected:

   381       bool forward;

   382 

   383       Edge(const UEdge& edge, bool _forward)

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

   385 

   386     public:

   387       Edge() {}

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

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

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

   391       }

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

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

   394       }

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

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

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

   398       }

   399     };

   400 

   401     void first(Edge& edge) const {

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

   403       edge.forward = true;

   404     }

   405 

   406     void next(Edge& edge) const {

   407       if (!edge.forward) {

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

   409       }

   410       edge.forward = !edge.forward;

   411     }

   412 

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

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

   415 	Parent::firstFromANode(edge, node);

   416 	edge.forward = true;

   417       } else {

   418 	Parent::firstFromBNode(edge, node);

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

   420       }

   421     }

   422     void nextOut(Edge& edge) const {

   423       if (edge.forward) {

   424 	Parent::nextFromANode(edge);

   425       } else {

   426 	Parent::nextFromBNode(edge);

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

   428       }

   429     }

   430 

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

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

   433 	Parent::firstFromBNode(edge, node);

   434 	edge.forward = true;	

   435       } else {

   436 	Parent::firstFromANode(edge, node);

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

   438       }

   439     }

   440     void nextIn(Edge& edge) const {

   441       if (edge.forward) {

   442 	Parent::nextFromBNode(edge);

   443       } else {

   444 	Parent::nextFromANode(edge);

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

   446       }

   447     }

   448 

   449     Node source(const Edge& edge) const {

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

   451     }

   452     Node target(const Edge& edge) const {

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

   454     }

   455 

   456     int id(const Edge& edge) const {

   457       return (Parent::id(static_cast<const UEdge&>(edge)) << 1) + 

   458         (edge.forward ? 0 : 1);

   459     }

   460     Edge edgeFromId(int id) const {

   461       return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);

   462     }

   463     int maxEdgeId() const {

   464       return (Parent::maxUEdgeId() << 1) + 1;

   465     }

   466 

   467     bool direction(const Edge& edge) const {

   468       return edge.forward;

   469     }

   470 

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

   472       return Edge(edge, direction);

   473     }

   474 

   475     int edgeNum() const {

   476       return 2 * Parent::uEdgeNum();

   477     }

   478 

   479     int uEdgeNum() const {

   480       return Parent::uEdgeNum();

   481     }

   482 

   483 

   484   };

   485 }

   486 

   487 #endif
lemon-0.x