Mercuriallemon-0.x / file revision
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
lemon/bits/graph_extender.h
author hegyi
Tue, 03 Jan 2006 14:56:45 +0000
changeset 1869 52f5a7f9fb48
parent 1820 22099ef840d7
child 1875 98698b69a902
permissions -rw-r--r--
Handling of tabs is rationalized a bit. More than one file can be given at startup in command prompt. If there is no file given in command prompt, an empty tab will be present at startup. 
     1 /* -*- C++ -*-

     2  * lemon/graph_extender.h - Part of LEMON, a generic C++ optimization library

     3  *

     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi

     5  * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,

     6  * EGRES).

     7  *

     8  * Permission to use, modify and distribute this software is granted

     9  * provided that this copyright notice appears in all copies. For

    10  * precise terms see the accompanying LICENSE file.

    11  *

    12  * This software is provided "AS IS" with no warranty of any kind,

    13  * express or implied, and with no claim as to its suitability for any

    14  * purpose.

    15  *

    16  */

    17 

    18 #ifndef LEMON_GRAPH_EXTENDER_H

    19 #define LEMON_GRAPH_EXTENDER_H

    20 

    21 #include <lemon/invalid.h>

    22 #include <lemon/error.h>

    23 

    24 namespace lemon {

    25 

    26   template <typename _Base>

    27   class GraphExtender : public _Base {

    28   public:

    29 

    30     typedef _Base Parent;

    31     typedef GraphExtender Graph;

    32 

    33     typedef typename Parent::Node Node;

    34     typedef typename Parent::Edge Edge;

    35 

    36     int maxId(Node) const {

    37       return Parent::maxNodeId();

    38     }

    39 

    40     int maxId(Edge) const {

    41       return Parent::maxEdgeId();

    42     }

    43 

    44     Node fromId(int id, Node) const {

    45       return Parent::nodeFromId(id);

    46     }

    47 

    48     Edge fromId(int id, Edge) const {

    49       return Parent::edgeFromId(id);

    50     }

    51 

    52     Node oppositeNode(const Node &n, const Edge &e) const {

    53       if (n == Parent::source(e))

    54 	return Parent::target(e);

    55       else if(n==Parent::target(e))

    56 	return Parent::source(e);

    57       else

    58 	return INVALID;

    59     }

    60 

    61   };

    62 

    63   template <typename _Base>

    64   class UndirGraphExtender : public _Base {

    65     typedef _Base Parent;

    66     typedef UndirGraphExtender Graph;

    67 

    68   public:

    69 

    70     typedef typename Parent::Edge UndirEdge;

    71     typedef typename Parent::Node Node;

    72 

    73     class Edge : public UndirEdge {

    74       friend class UndirGraphExtender;

    75 

    76     protected:

    77       // FIXME: Marci use opposite logic in his graph adaptors. It would

    78       // be reasonable to syncronize...

    79       bool forward;

    80 

    81       Edge(const UndirEdge &ue, bool _forward) :

    82         UndirEdge(ue), forward(_forward) {}

    83 

    84     public:

    85       Edge() {}

    86 

    87       /// Invalid edge constructor

    88       Edge(Invalid i) : UndirEdge(i), forward(true) {}

    89 

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

    91 	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);

    92       }

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

    94 	return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);

    95       }

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

    97 	return forward<that.forward ||

    98 	  (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));

    99       }

   100     };

   101 

   102 

   103     /// \brief Edge of opposite direction.

   104     ///

   105     /// Returns the Edge of opposite direction.

   106     Edge oppositeEdge(const Edge &e) const {

   107       return Edge(e,!e.forward);

   108     }

   109 

   110   public:

   111     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"

   112     /// or something???

   113     using Parent::source;

   114 

   115     /// Source of the given Edge.

   116     Node source(const Edge &e) const {

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

   118     }

   119 

   120     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"

   121     /// or something???

   122     using Parent::target;

   123 

   124     /// Target of the given Edge.

   125     Node target(const Edge &e) const {

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

   127     }

   128 

   129     Node oppositeNode(const Node &n, const UndirEdge &e) const {

   130       if( n == Parent::source(e))

   131 	return Parent::target(e);

   132       else if( n == Parent::target(e))

   133 	return Parent::source(e);

   134       else

   135 	return INVALID;

   136     }

   137 

   138     /// \brief Directed edge from an undirected edge and a source node.

   139     ///

   140     /// Returns a (directed) Edge corresponding to the specified UndirEdge

   141     /// and source Node.

   142     ///

   143     Edge direct(const UndirEdge &ue, const Node &s) const {

   144       return Edge(ue, s == source(ue));

   145     }

   146 

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

   148     ///

   149     /// Returns a directed edge corresponding to the specified UndirEdge.

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

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

   152     Edge direct(const UndirEdge &ue, bool d) const {

   153       return Edge(ue, d);

   154     }

   155 

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

   157     /// corresponding undirected edge.

   158     ///

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

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

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

   162 

   163 

   164     using Parent::first;

   165     void first(Edge &e) const {

   166       Parent::first(e);

   167       e.forward=true;

   168     }

   169 

   170     using Parent::next;

   171     void next(Edge &e) const {

   172       if( e.forward ) {

   173 	e.forward = false;

   174       }

   175       else {

   176 	Parent::next(e);

   177 	e.forward = true;

   178       }

   179     }

   180 

   181   public:

   182 

   183     void firstOut(Edge &e, const Node &n) const {

   184       Parent::firstIn(e,n);

   185       if( UndirEdge(e) != INVALID ) {

   186 	e.forward = false;

   187       }

   188       else {

   189 	Parent::firstOut(e,n);

   190 	e.forward = true;

   191       }

   192     }

   193     void nextOut(Edge &e) const {

   194       if( ! e.forward ) {

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

   196 	Parent::nextIn(e);

   197 	if( UndirEdge(e) == INVALID ) {

   198 	  Parent::firstOut(e, n);

   199 	  e.forward = true;

   200 	}

   201       }

   202       else {

   203 	Parent::nextOut(e);

   204       }

   205     }

   206 

   207     void firstIn(Edge &e, const Node &n) const {

   208       Parent::firstOut(e,n);

   209       if( UndirEdge(e) != INVALID ) {

   210 	e.forward = false;

   211       }

   212       else {

   213 	Parent::firstIn(e,n);

   214 	e.forward = true;

   215       }

   216     }

   217     void nextIn(Edge &e) const {

   218       if( ! e.forward ) {

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

   220 	Parent::nextOut(e);

   221 	if( UndirEdge(e) == INVALID ) {

   222 	  Parent::firstIn(e, n);

   223 	  e.forward = true;

   224 	}

   225       }

   226       else {

   227 	Parent::nextIn(e);

   228       }

   229     }

   230 

   231     void firstInc(UndirEdge &e, const Node &n) const {

   232       Parent::firstOut(e, n);

   233       if (e != INVALID) return;

   234       Parent::firstIn(e, n);

   235     }

   236     void nextInc(UndirEdge &e, const Node &n) const {

   237       if (Parent::source(e) == n) {

   238 	Parent::nextOut(e);

   239 	if (e != INVALID) return;

   240 	Parent::firstIn(e, n);

   241       } else {

   242 	Parent::nextIn(e);

   243       }

   244     }

   245 

   246     void firstInc(UndirEdge &e, bool &d, const Node &n) const {

   247       d = true;

   248       Parent::firstOut(e, n);

   249       if (e != INVALID) return;

   250       d = false;

   251       Parent::firstIn(e, n);

   252     }

   253     void nextInc(UndirEdge &e, bool &d) const {

   254       if (d) {

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

   256 	Parent::nextOut(e);

   257 	if (e != INVALID) return;

   258 	d = false;

   259 	Parent::firstIn(e, s);

   260       } else {

   261 	Parent::nextIn(e);

   262       }

   263     }

   264 

   265     // Miscellaneous stuff:

   266 

   267     /// \todo these methods (id, maxEdgeId) should be moved into separate

   268     /// Extender

   269 

   270     // using Parent::id;

   271     // Using "using" is not a good idea, cause it could be that there is

   272     // no "id" in Parent...

   273 

   274     int id(const Node &n) const {

   275       return Parent::id(n);

   276     }

   277 

   278     int id(const UndirEdge &e) const {

   279       return Parent::id(e);

   280     }

   281 

   282     int id(const Edge &e) const {

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

   284     }

   285 

   286     int maxNodeId() const {

   287       return Parent::maxNodeId();

   288     }

   289 

   290     int maxEdgeId() const {

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

   292     }

   293 

   294     int maxUndirEdgeId() const {

   295       return Parent::maxEdgeId();

   296     }

   297 

   298     int maxId(Node) const {

   299       return maxNodeId();

   300     }

   301 

   302     int maxId(Edge) const {

   303       return maxEdgeId();

   304     }

   305     int maxId(UndirEdge) const {

   306       return maxUndirEdgeId();

   307     }

   308 

   309     int edgeNum() const {

   310       return 2 * Parent::edgeNum();

   311     }

   312 

   313     int undirEdgeNum() const {

   314       return Parent::edgeNum();

   315     }

   316 

   317     Node nodeFromId(int id) const {

   318       return Parent::nodeFromId(id);

   319     }

   320 

   321     Edge edgeFromId(int id) const {

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

   323     }

   324 

   325     UndirEdge undirEdgeFromId(int id) const {

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

   327     }

   328 

   329     Node fromId(int id, Node) const {

   330       return nodeFromId(id);

   331     }

   332 

   333     Edge fromId(int id, Edge) const {

   334       return edgeFromId(id);

   335     }

   336 

   337     UndirEdge fromId(int id, UndirEdge) const {

   338       return undirEdgeFromId(id);

   339     }

   340 

   341 

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

   343       if (prev == INVALID) {

   344 	UndirEdge edge = Parent::findEdge(source, target);

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

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

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

   348       } else if (direction(prev)) {

   349 	UndirEdge edge = Parent::findEdge(source, target, prev);

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

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

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

   353       } else {

   354 	UndirEdge edge = Parent::findEdge(target, source, prev);

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

   356       }

   357       return INVALID;

   358     }

   359 

   360     UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {

   361       if (prev == INVALID) {

   362 	UndirEdge edge = Parent::findEdge(source, target);

   363 	if (edge != INVALID) return edge;

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

   365 	if (edge != INVALID) return edge;

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

   367 	UndirEdge edge = Parent::findEdge(source, target, prev);

   368 	if (edge != INVALID) return edge;

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

   370 	if (edge != INVALID) return edge;	

   371       } else {

   372 	UndirEdge edge = Parent::findEdge(target, source, prev);

   373 	if (edge != INVALID) return edge;	      

   374       }

   375       return INVALID;

   376     }

   377 

   378   };

   379 

   380 

   381   template <typename _Base>

   382   class UndirBipartiteGraphExtender : public _Base {

   383   public:

   384     typedef _Base Parent;

   385     typedef UndirBipartiteGraphExtender Graph;

   386 

   387     typedef typename Parent::Node Node;

   388     typedef typename Parent::Edge UndirEdge;

   389 

   390     using Parent::first;

   391     using Parent::next;

   392 

   393     using Parent::id;

   394 

   395     Node source(const UndirEdge& edge) const {

   396       return upperNode(edge);

   397     }

   398     Node target(const UndirEdge& edge) const {

   399       return lowerNode(edge);

   400     }

   401 

   402     void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {

   403       if (Parent::upper(node)) {

   404 	Parent::firstDown(edge, node);

   405 	direction = true;

   406       } else {

   407 	Parent::firstUp(edge, node);

   408 	direction = static_cast<UndirEdge&>(edge) == INVALID;

   409       }

   410     }

   411     void nextInc(UndirEdge& edge, bool& direction) const {

   412       if (direction) {

   413 	Parent::nextDown(edge);

   414       } else {

   415 	Parent::nextUp(edge);

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

   417       }

   418     }

   419 

   420     int maxUndirEdgeId() const {

   421       return Parent::maxEdgeId();

   422     }

   423 

   424     UndirEdge undirEdgeFromId(int id) const {

   425       return Parent::edgeFromId(id);

   426     }

   427 

   428     class Edge : public UndirEdge {

   429       friend class UndirBipartiteGraphExtender;

   430     protected:

   431       bool forward;

   432 

   433       Edge(const UndirEdge& edge, bool _forward)

   434 	: UndirEdge(edge), forward(_forward) {}

   435 

   436     public:

   437       Edge() {}

   438       Edge (Invalid) : UndirEdge(INVALID), forward(true) {}

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

   440 	return UndirEdge::operator==(i) && forward == i.forward;

   441       }

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

   443 	return UndirEdge::operator!=(i) || forward != i.forward;

   444       }

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

   446 	return UndirEdge::operator<(i) || 

   447 	  (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));

   448       }

   449     };

   450 

   451     void first(Edge& edge) const {

   452       Parent::first(static_cast<UndirEdge&>(edge));

   453       edge.forward = true;

   454     }

   455 

   456     void next(Edge& edge) const {

   457       if (!edge.forward) {

   458 	Parent::next(static_cast<UndirEdge&>(edge));

   459       }

   460       edge.forward = !edge.forward;

   461     }

   462 

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

   464       if (Parent::upper(node)) {

   465 	Parent::firstDown(edge, node);

   466 	edge.forward = true;

   467       } else {

   468 	Parent::firstUp(edge, node);

   469 	edge.forward = static_cast<UndirEdge&>(edge) == INVALID;

   470       }

   471     }

   472     void nextOut(Edge& edge) const {

   473       if (edge.forward) {

   474 	Parent::nextDown(edge);

   475       } else {

   476 	Parent::nextUp(edge);

   477         edge.forward = static_cast<UndirEdge&>(edge) == INVALID;

   478       }

   479     }

   480 

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

   482       if (Parent::lower(node)) {

   483 	Parent::firstUp(edge, node);

   484 	edge.forward = true;	

   485       } else {

   486 	Parent::firstDown(edge, node);

   487 	edge.forward = static_cast<UndirEdge&>(edge) == INVALID;

   488       }

   489     }

   490     void nextIn(Edge& edge) const {

   491       if (edge.forward) {

   492 	Parent::nextUp(edge);

   493       } else {

   494 	Parent::nextDown(edge);

   495 	edge.forward = static_cast<UndirEdge&>(edge) == INVALID;

   496       }

   497     }

   498 

   499     Node source(const Edge& edge) const {

   500       return edge.forward ? Parent::upperNode(edge) : Parent::lowerNode(edge);

   501     }

   502     Node target(const Edge& edge) const {

   503       return edge.forward ? Parent::lowerNode(edge) : Parent::upperNode(edge);

   504     }

   505 

   506     bool direction(const Edge& edge) const {

   507       return edge.forward;

   508     }

   509 

   510     Edge direct(const UndirEdge& edge, const Node& node) const {

   511       return Edge(edge, node == Parent::source(edge));

   512     }

   513 

   514     Edge direct(const UndirEdge& edge, bool direction) const {

   515       return Edge(edge, direction);

   516     }

   517 

   518     Node oppositeNode(const UndirEdge& edge, const Node& node) const {

   519       return source(edge) == node ? 

   520 	target(edge) : source(edge);

   521     }

   522 

   523     Edge oppositeEdge(const Edge& edge) const {

   524       return Edge(edge, !edge.forward);

   525     }

   526 

   527     int id(const Edge& edge) const {

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

   529     }

   530     Edge edgeFromId(int id) const {

   531       return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);

   532     }

   533     int maxEdgeId() const {

   534       return (Parent::maxId(UndirEdge()) << 1) + 1;

   535     }

   536 

   537     class UpperNode : public Node {

   538       friend class UndirBipartiteGraphExtender;

   539     public:

   540       UpperNode() {}

   541       UpperNode(const Node& node) : Node(node) {

   542 	LEMON_ASSERT(Parent::upper(node) || node == INVALID, 

   543 		     typename Parent::NodeSetError());

   544       }

   545       UpperNode(Invalid) : Node(INVALID) {}

   546     };

   547 

   548     void first(UpperNode& node) const {

   549       Parent::firstUpper(static_cast<Node&>(node));

   550     }

   551     void next(UpperNode& node) const {

   552       Parent::nextUpper(static_cast<Node&>(node));

   553     }

   554 

   555     int id(const UpperNode& node) const {

   556       return Parent::upperId(node);

   557     }

   558 

   559     class LowerNode : public Node {

   560       friend class UndirBipartiteGraphExtender;

   561     public:

   562       LowerNode() {}

   563       LowerNode(const Node& node) : Node(node) {

   564 	LEMON_ASSERT(Parent::lower(node) || node == INVALID,

   565 		     typename Parent::NodeSetError());

   566       }

   567       LowerNode(Invalid) : Node(INVALID) {}

   568     };

   569 

   570     void first(LowerNode& node) const {

   571       Parent::firstLower(static_cast<Node&>(node));

   572     }

   573     void next(LowerNode& node) const {

   574       Parent::nextLower(static_cast<Node&>(node));

   575     }

   576   

   577     int id(const LowerNode& node) const {

   578       return Parent::upperId(node);

   579     }

   580 

   581 

   582 

   583     int maxId(Node) const {

   584       return Parent::maxNodeId();

   585     }

   586     int maxId(LowerNode) const {

   587       return Parent::maxLowerId();

   588     }

   589     int maxId(UpperNode) const {

   590       return Parent::maxUpperId();

   591     }

   592     int maxId(Edge) const {

   593       return maxEdgeId();

   594     }

   595     int maxId(UndirEdge) const {

   596       return maxUndirEdgeId();

   597     }

   598 

   599 

   600     Node fromId(int id, Node) const {

   601       return Parent::nodeFromId(id);

   602     }

   603     UpperNode fromId(int id, UpperNode) const {

   604       return Parent::fromUpperId(id);

   605     }

   606     LowerNode fromId(int id, LowerNode) const {

   607       return Parent::fromLowerId(id);

   608     }

   609     Edge fromId(int id, Edge) const {

   610       return edgeFromId(id);

   611     }

   612     UndirEdge fromId(int id, UndirEdge) const {

   613       return undirEdgeFromId(id);

   614     }

   615 

   616   };

   617 

   618 }

   619 

   620 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H
lemon-0.x