lemon/bits/graph_extender.h
author alpar
Wed, 16 Nov 2005 13:19:05 +0000
changeset 1805 d284f81f02a5
child 1820 22099ef840d7
permissions -rw-r--r--
Iterable Bool maps can count the number of true and false values.
     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 
    23 namespace lemon {
    24 
    25   template <typename _Base>
    26   class GraphExtender : public _Base {
    27   public:
    28 
    29     typedef _Base Parent;
    30     typedef GraphExtender Graph;
    31 
    32     typedef typename Parent::Node Node;
    33     typedef typename Parent::Edge Edge;
    34 
    35     int maxId(Node) const {
    36       return Parent::maxNodeId();
    37     }
    38 
    39     int maxId(Edge) const {
    40       return Parent::maxEdgeId();
    41     }
    42 
    43     Node fromId(int id, Node) const {
    44       return Parent::nodeFromId(id);
    45     }
    46 
    47     Edge fromId(int id, Edge) const {
    48       return Parent::edgeFromId(id);
    49     }
    50 
    51     Node oppositeNode(const Node &n, const Edge &e) const {
    52       if (n == Parent::source(e))
    53 	return Parent::target(e);
    54       else if(n==Parent::target(e))
    55 	return Parent::source(e);
    56       else
    57 	return INVALID;
    58     }
    59 
    60   };
    61 
    62   template <typename _Base>
    63   class UndirGraphExtender : public _Base {
    64     typedef _Base Parent;
    65     typedef UndirGraphExtender Graph;
    66 
    67   public:
    68 
    69     typedef typename Parent::Edge UndirEdge;
    70     typedef typename Parent::Node Node;
    71 
    72     class Edge : public UndirEdge {
    73       friend class UndirGraphExtender;
    74 
    75     protected:
    76       // FIXME: Marci use opposite logic in his graph adaptors. It would
    77       // be reasonable to syncronize...
    78       bool forward;
    79 
    80       Edge(const UndirEdge &ue, bool _forward) :
    81         UndirEdge(ue), forward(_forward) {}
    82 
    83     public:
    84       Edge() {}
    85 
    86       /// Invalid edge constructor
    87       Edge(Invalid i) : UndirEdge(i), forward(true) {}
    88 
    89       bool operator==(const Edge &that) const {
    90 	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
    91       }
    92       bool operator!=(const Edge &that) const {
    93 	return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
    94       }
    95       bool operator<(const Edge &that) const {
    96 	return forward<that.forward ||
    97 	  (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
    98       }
    99     };
   100 
   101 
   102     /// \brief Edge of opposite direction.
   103     ///
   104     /// Returns the Edge of opposite direction.
   105     Edge oppositeEdge(const Edge &e) const {
   106       return Edge(e,!e.forward);
   107     }
   108 
   109   public:
   110     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
   111     /// or something???
   112     using Parent::source;
   113 
   114     /// Source of the given Edge.
   115     Node source(const Edge &e) const {
   116       return e.forward ? Parent::source(e) : Parent::target(e);
   117     }
   118 
   119     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
   120     /// or something???
   121     using Parent::target;
   122 
   123     /// Target of the given Edge.
   124     Node target(const Edge &e) const {
   125       return e.forward ? Parent::target(e) : Parent::source(e);
   126     }
   127 
   128     Node oppositeNode(const Node &n, const UndirEdge &e) const {
   129       if( n == Parent::source(e))
   130 	return Parent::target(e);
   131       else if( n == Parent::target(e))
   132 	return Parent::source(e);
   133       else
   134 	return INVALID;
   135     }
   136 
   137     /// \brief Directed edge from an undirected edge and a source node.
   138     ///
   139     /// Returns a (directed) Edge corresponding to the specified UndirEdge
   140     /// and source Node.
   141     ///
   142     Edge direct(const UndirEdge &ue, const Node &s) const {
   143       return Edge(ue, s == source(ue));
   144     }
   145 
   146     /// \brief Directed edge from an undirected edge.
   147     ///
   148     /// Returns a directed edge corresponding to the specified UndirEdge.
   149     /// If the given bool is true the given undirected edge and the
   150     /// returned edge have the same source node.
   151     Edge direct(const UndirEdge &ue, bool d) const {
   152       return Edge(ue, d);
   153     }
   154 
   155     /// Returns whether the given directed edge is same orientation as the
   156     /// corresponding undirected edge.
   157     ///
   158     /// \todo reference to the corresponding point of the undirected graph
   159     /// concept. "What does the direction of an undirected edge mean?"
   160     bool direction(const Edge &e) const { return e.forward; }
   161 
   162 
   163     using Parent::first;
   164     void first(Edge &e) const {
   165       Parent::first(e);
   166       e.forward=true;
   167     }
   168 
   169     using Parent::next;
   170     void next(Edge &e) const {
   171       if( e.forward ) {
   172 	e.forward = false;
   173       }
   174       else {
   175 	Parent::next(e);
   176 	e.forward = true;
   177       }
   178     }
   179 
   180   public:
   181 
   182     void firstOut(Edge &e, const Node &n) const {
   183       Parent::firstIn(e,n);
   184       if( UndirEdge(e) != INVALID ) {
   185 	e.forward = false;
   186       }
   187       else {
   188 	Parent::firstOut(e,n);
   189 	e.forward = true;
   190       }
   191     }
   192     void nextOut(Edge &e) const {
   193       if( ! e.forward ) {
   194 	Node n = Parent::target(e);
   195 	Parent::nextIn(e);
   196 	if( UndirEdge(e) == INVALID ) {
   197 	  Parent::firstOut(e, n);
   198 	  e.forward = true;
   199 	}
   200       }
   201       else {
   202 	Parent::nextOut(e);
   203       }
   204     }
   205 
   206     void firstIn(Edge &e, const Node &n) const {
   207       Parent::firstOut(e,n);
   208       if( UndirEdge(e) != INVALID ) {
   209 	e.forward = false;
   210       }
   211       else {
   212 	Parent::firstIn(e,n);
   213 	e.forward = true;
   214       }
   215     }
   216     void nextIn(Edge &e) const {
   217       if( ! e.forward ) {
   218 	Node n = Parent::source(e);
   219 	Parent::nextOut(e);
   220 	if( UndirEdge(e) == INVALID ) {
   221 	  Parent::firstIn(e, n);
   222 	  e.forward = true;
   223 	}
   224       }
   225       else {
   226 	Parent::nextIn(e);
   227       }
   228     }
   229 
   230     void firstInc(UndirEdge &e, const Node &n) const {
   231       Parent::firstOut(e, n);
   232       if (e != INVALID) return;
   233       Parent::firstIn(e, n);
   234     }
   235     void nextInc(UndirEdge &e, const Node &n) const {
   236       if (Parent::source(e) == n) {
   237 	Parent::nextOut(e);
   238 	if (e != INVALID) return;
   239 	Parent::firstIn(e, n);
   240       } else {
   241 	Parent::nextIn(e);
   242       }
   243     }
   244 
   245     void firstInc(UndirEdge &e, bool &d, const Node &n) const {
   246       d = true;
   247       Parent::firstOut(e, n);
   248       if (e != INVALID) return;
   249       d = false;
   250       Parent::firstIn(e, n);
   251     }
   252     void nextInc(UndirEdge &e, bool &d) const {
   253       if (d) {
   254 	Node s = Parent::source(e);
   255 	Parent::nextOut(e);
   256 	if (e != INVALID) return;
   257 	d = false;
   258 	Parent::firstIn(e, s);
   259       } else {
   260 	Parent::nextIn(e);
   261       }
   262     }
   263 
   264     // Miscellaneous stuff:
   265 
   266     /// \todo these methods (id, maxEdgeId) should be moved into separate
   267     /// Extender
   268 
   269     // using Parent::id;
   270     // Using "using" is not a good idea, cause it could be that there is
   271     // no "id" in Parent...
   272 
   273     int id(const Node &n) const {
   274       return Parent::id(n);
   275     }
   276 
   277     int id(const UndirEdge &e) const {
   278       return Parent::id(e);
   279     }
   280 
   281     int id(const Edge &e) const {
   282       return 2 * Parent::id(e) + int(e.forward);
   283     }
   284 
   285     int maxNodeId() const {
   286       return Parent::maxNodeId();
   287     }
   288 
   289     int maxEdgeId() const {
   290       return 2 * Parent::maxEdgeId() + 1;
   291     }
   292 
   293     int maxUndirEdgeId() const {
   294       return Parent::maxEdgeId();
   295     }
   296 
   297     int maxId(Node) const {
   298       return maxNodeId();
   299     }
   300 
   301     int maxId(Edge) const {
   302       return maxEdgeId();
   303     }
   304     int maxId(UndirEdge) const {
   305       return maxUndirEdgeId();
   306     }
   307 
   308     int edgeNum() const {
   309       return 2 * Parent::edgeNum();
   310     }
   311 
   312     int undirEdgeNum() const {
   313       return Parent::edgeNum();
   314     }
   315 
   316     Node nodeFromId(int id) const {
   317       return Parent::nodeFromId(id);
   318     }
   319 
   320     Edge edgeFromId(int id) const {
   321       return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
   322     }
   323 
   324     UndirEdge undirEdgeFromId(int id) const {
   325       return Parent::edgeFromId(id >> 1);
   326     }
   327 
   328     Node fromId(int id, Node) const {
   329       return nodeFromId(id);
   330     }
   331 
   332     Edge fromId(int id, Edge) const {
   333       return edgeFromId(id);
   334     }
   335 
   336     UndirEdge fromId(int id, UndirEdge) const {
   337       return undirEdgeFromId(id);
   338     }
   339 
   340 
   341     Edge findEdge(Node source, Node target, Edge prev) const {
   342       if (prev == INVALID) {
   343 	UndirEdge edge = Parent::findEdge(source, target);
   344 	if (edge != INVALID) return direct(edge, true);
   345 	edge = Parent::findEdge(target, source);
   346 	if (edge != INVALID) return direct(edge, false);
   347       } else if (direction(prev)) {
   348 	UndirEdge edge = Parent::findEdge(source, target, prev);
   349 	if (edge != INVALID) return direct(edge, true);
   350 	edge = Parent::findEdge(target, source);
   351 	if (edge != INVALID) return direct(edge, false);	
   352       } else {
   353 	UndirEdge edge = Parent::findEdge(target, source, prev);
   354 	if (edge != INVALID) return direct(edge, false);	      
   355       }
   356       return INVALID;
   357     }
   358 
   359     UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
   360       if (prev == INVALID) {
   361 	UndirEdge edge = Parent::findEdge(source, target);
   362 	if (edge != INVALID) return edge;
   363 	edge = Parent::findEdge(target, source);
   364 	if (edge != INVALID) return edge;
   365       } else if (Parent::source(prev) == source) {
   366 	UndirEdge edge = Parent::findEdge(source, target, prev);
   367 	if (edge != INVALID) return edge;
   368 	edge = Parent::findEdge(target, source);
   369 	if (edge != INVALID) return edge;	
   370       } else {
   371 	UndirEdge edge = Parent::findEdge(target, source, prev);
   372 	if (edge != INVALID) return edge;	      
   373       }
   374       return INVALID;
   375     }
   376 
   377   };
   378 
   379 }
   380 
   381 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H