lemon/bits/undir_graph_extender.h
author deba
Mon, 17 Oct 2005 10:28:48 +0000
changeset 1729 06f939455cb1
parent 1627 3fd1ba6e9872
permissions -rw-r--r--
Removing signal/commit Change from alteration notifier

It makes slower the change Target/Source functions
and used only by the In/Out DegMap
     1 /* -*- C++ -*-
     2  *
     3  * lemon/undir_graph_extender.h - Part of LEMON, a generic C++
     4  * optimization library
     5  *
     6  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
     7  * Kutatocsoport (Egervary Research Group on Combinatorial Optimization,
     8  * EGRES).
     9  *
    10  * Permission to use, modify and distribute this software is granted
    11  * provided that this copyright notice appears in all copies. For
    12  * precise terms see the accompanying LICENSE file.
    13  *
    14  * This software is provided "AS IS" with no warranty of any kind,
    15  * express or implied, and with no claim as to its suitability for any
    16  * purpose.
    17  *
    18  */
    19 
    20 #ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
    21 #define LEMON_UNDIR_GRAPH_EXTENDER_H
    22 
    23 #include <lemon/invalid.h>
    24 
    25 namespace lemon {
    26 
    27   template <typename _Base>
    28   class UndirGraphExtender : public _Base {
    29     typedef _Base Parent;
    30     typedef UndirGraphExtender Graph;
    31 
    32   public:
    33 
    34     typedef typename Parent::Edge UndirEdge;
    35     typedef typename Parent::Node Node;
    36 
    37     class Edge : public UndirEdge {
    38       friend class UndirGraphExtender;
    39 
    40     protected:
    41       // FIXME: Marci use opposite logic in his graph adaptors. It would
    42       // be reasonable to syncronize...
    43       bool forward;
    44 
    45       Edge(const UndirEdge &ue, bool _forward) :
    46         UndirEdge(ue), forward(_forward) {}
    47 
    48     public:
    49       Edge() {}
    50 
    51       /// Invalid edge constructor
    52       Edge(Invalid i) : UndirEdge(i), forward(true) {}
    53 
    54       bool operator==(const Edge &that) const {
    55 	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
    56       }
    57       bool operator!=(const Edge &that) const {
    58 	return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
    59       }
    60       bool operator<(const Edge &that) const {
    61 	return forward<that.forward ||
    62 	  (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
    63       }
    64     };
    65 
    66 
    67     /// \brief Edge of opposite direction.
    68     ///
    69     /// Returns the Edge of opposite direction.
    70     Edge oppositeEdge(const Edge &e) const {
    71       return Edge(e,!e.forward);
    72     }
    73 
    74   public:
    75     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    76     /// or something???
    77     using Parent::source;
    78 
    79     /// Source of the given Edge.
    80     Node source(const Edge &e) const {
    81       return e.forward ? Parent::source(e) : Parent::target(e);
    82     }
    83 
    84     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    85     /// or something???
    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     Node oppositeNode(const Node &n, const UndirEdge &e) const {
    94       if( n == Parent::source(e))
    95 	return Parent::target(e);
    96       else if( n == Parent::target(e))
    97 	return Parent::source(e);
    98       else
    99 	return INVALID;
   100     }
   101 
   102     /// \brief Directed edge from an undirected edge and a source node.
   103     ///
   104     /// Returns a (directed) Edge corresponding to the specified UndirEdge
   105     /// and source Node.
   106     ///
   107     Edge direct(const UndirEdge &ue, const Node &s) const {
   108       return Edge(ue, s == source(ue));
   109     }
   110 
   111     /// \brief Directed edge from an undirected edge.
   112     ///
   113     /// Returns a directed edge corresponding to the specified UndirEdge.
   114     /// If the given bool is true the given undirected edge and the
   115     /// returned edge have the same source node.
   116     Edge direct(const UndirEdge &ue, bool d) const {
   117       return Edge(ue, d);
   118     }
   119 
   120     /// Returns whether the given directed edge is same orientation as the
   121     /// corresponding undirected edge.
   122     ///
   123     /// \todo reference to the corresponding point of the undirected graph
   124     /// concept. "What does the direction of an undirected edge mean?"
   125     bool direction(const Edge &e) const { return e.forward; }
   126 
   127 
   128     using Parent::first;
   129     void first(Edge &e) const {
   130       Parent::first(e);
   131       e.forward=true;
   132     }
   133 
   134     using Parent::next;
   135     void next(Edge &e) const {
   136       if( e.forward ) {
   137 	e.forward = false;
   138       }
   139       else {
   140 	Parent::next(e);
   141 	e.forward = true;
   142       }
   143     }
   144 
   145   public:
   146 
   147     void firstOut(Edge &e, const Node &n) const {
   148       Parent::firstIn(e,n);
   149       if( UndirEdge(e) != INVALID ) {
   150 	e.forward = false;
   151       }
   152       else {
   153 	Parent::firstOut(e,n);
   154 	e.forward = true;
   155       }
   156     }
   157     void nextOut(Edge &e) const {
   158       if( ! e.forward ) {
   159 	Node n = Parent::target(e);
   160 	Parent::nextIn(e);
   161 	if( UndirEdge(e) == INVALID ) {
   162 	  Parent::firstOut(e, n);
   163 	  e.forward = true;
   164 	}
   165       }
   166       else {
   167 	Parent::nextOut(e);
   168       }
   169     }
   170 
   171     void firstIn(Edge &e, const Node &n) const {
   172       Parent::firstOut(e,n);
   173       if( UndirEdge(e) != INVALID ) {
   174 	e.forward = false;
   175       }
   176       else {
   177 	Parent::firstIn(e,n);
   178 	e.forward = true;
   179       }
   180     }
   181     void nextIn(Edge &e) const {
   182       if( ! e.forward ) {
   183 	Node n = Parent::source(e);
   184 	Parent::nextOut(e);
   185 	if( UndirEdge(e) == INVALID ) {
   186 	  Parent::firstIn(e, n);
   187 	  e.forward = true;
   188 	}
   189       }
   190       else {
   191 	Parent::nextIn(e);
   192       }
   193     }
   194 
   195     void firstInc(UndirEdge &e, const Node &n) const {
   196       Parent::firstOut(e, n);
   197       if (e != INVALID) return;
   198       Parent::firstIn(e, n);
   199     }
   200     void nextInc(UndirEdge &e, const Node &n) const {
   201       if (Parent::source(e) == n) {
   202 	Parent::nextOut(e);
   203 	if (e != INVALID) return;
   204 	Parent::firstIn(e, n);
   205       } else {
   206 	Parent::nextIn(e);
   207       }
   208     }
   209 
   210     void firstInc(UndirEdge &e, bool &d, const Node &n) const {
   211       d = true;
   212       Parent::firstOut(e, n);
   213       if (e != INVALID) return;
   214       d = false;
   215       Parent::firstIn(e, n);
   216     }
   217     void nextInc(UndirEdge &e, bool &d) const {
   218       if (d) {
   219 	Node s = Parent::source(e);
   220 	Parent::nextOut(e);
   221 	if (e != INVALID) return;
   222 	d = false;
   223 	Parent::firstIn(e, s);
   224       } else {
   225 	Parent::nextIn(e);
   226       }
   227     }
   228 
   229     // Miscellaneous stuff:
   230 
   231     /// \todo these methods (id, maxEdgeId) should be moved into separate
   232     /// Extender
   233 
   234     // using Parent::id;
   235     // Using "using" is not a good idea, cause it could be that there is
   236     // no "id" in Parent...
   237 
   238     int id(const Node &n) const {
   239       return Parent::id(n);
   240     }
   241 
   242     int id(const UndirEdge &e) const {
   243       return Parent::id(e);
   244     }
   245 
   246     int id(const Edge &e) const {
   247       return 2 * Parent::id(e) + int(e.forward);
   248     }
   249 
   250 
   251     int maxId(Node) const {
   252       return Parent::maxId(Node());
   253     }
   254 
   255     int maxId(Edge) const {
   256       return 2 * Parent::maxId(typename Parent::Edge()) + 1;
   257     }
   258     int maxId(UndirEdge) const {
   259       return Parent::maxId(typename Parent::Edge());
   260     }
   261 
   262 
   263     int edgeNum() const {
   264       return 2 * Parent::edgeNum();
   265     }
   266 
   267     int undirEdgeNum() const {
   268       return Parent::edgeNum();
   269     }
   270 
   271     Edge findEdge(Node source, Node target, Edge prev) const {
   272       if (prev == INVALID) {
   273 	UndirEdge edge = Parent::findEdge(source, target);
   274 	if (edge != INVALID) return direct(edge, true);
   275 	edge = Parent::findEdge(target, source);
   276 	if (edge != INVALID) return direct(edge, false);
   277       } else if (direction(prev)) {
   278 	UndirEdge edge = Parent::findEdge(source, target, prev);
   279 	if (edge != INVALID) return direct(edge, true);
   280 	edge = Parent::findEdge(target, source);
   281 	if (edge != INVALID) return direct(edge, false);	
   282       } else {
   283 	UndirEdge edge = Parent::findEdge(target, source, prev);
   284 	if (edge != INVALID) return direct(edge, false);	      
   285       }
   286       return INVALID;
   287     }
   288 
   289     UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
   290       if (prev == INVALID) {
   291 	UndirEdge edge = Parent::findEdge(source, target);
   292 	if (edge != INVALID) return edge;
   293 	edge = Parent::findEdge(target, source);
   294 	if (edge != INVALID) return edge;
   295       } else if (Parent::source(prev) == source) {
   296 	UndirEdge edge = Parent::findEdge(source, target, prev);
   297 	if (edge != INVALID) return edge;
   298 	edge = Parent::findEdge(target, source);
   299 	if (edge != INVALID) return edge;	
   300       } else {
   301 	UndirEdge edge = Parent::findEdge(target, source, prev);
   302 	if (edge != INVALID) return edge;	      
   303       }
   304       return INVALID;
   305     }
   306 
   307   };
   308 
   309 }
   310 
   311 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H