lemon/bits/undir_graph_extender.h
author alpar
Sat, 27 Aug 2005 11:37:05 +0000
changeset 1660 93792a112fd5
parent 1435 8e85e6bbefdf
child 1704 467d7927a901
permissions -rw-r--r--
- Doc images partly turned on again.
     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   protected:
    75 
    76     template <typename E>
    77     Node _dirSource(const E &e) const {
    78       return e.forward ? Parent::source(e) : Parent::target(e);
    79     }
    80 
    81     template <typename E>
    82     Node _dirTarget(const E &e) const {
    83       return e.forward ? Parent::target(e) : Parent::source(e);
    84     }
    85 
    86   public:
    87     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    88     /// or something???
    89     using Parent::source;
    90 
    91     /// Source of the given Edge.
    92     Node source(const Edge &e) const {
    93       return _dirSource(e);
    94     }
    95 
    96     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    97     /// or something???
    98     using Parent::target;
    99 
   100     /// Target of the given Edge.
   101     Node target(const Edge &e) const {
   102       return _dirTarget(e);
   103     }
   104 
   105     Node oppositeNode(const Node &n, const UndirEdge &e) const {
   106       if( n == Parent::source(e))
   107 	return Parent::target(e);
   108       else if( n == Parent::target(e))
   109 	return Parent::source(e);
   110       else
   111 	return INVALID;
   112     }
   113 
   114     /// \brief Directed edge from an undirected edge and a source node.
   115     ///
   116     /// Returns a (directed) Edge corresponding to the specified UndirEdge
   117     /// and source Node.
   118     ///
   119     Edge direct(const UndirEdge &ue, const Node &s) const {
   120       return Edge(ue, s == source(ue));
   121     }
   122 
   123     /// \brief Directed edge from an undirected edge.
   124     ///
   125     /// Returns a directed edge corresponding to the specified UndirEdge.
   126     /// If the given bool is true the given undirected edge and the
   127     /// returned edge have the same source node.
   128     Edge direct(const UndirEdge &ue, bool d) const {
   129       return Edge(ue, d);
   130     }
   131 
   132     /// Returns whether the given directed edge is same orientation as the
   133     /// corresponding undirected edge.
   134     ///
   135     /// \todo reference to the corresponding point of the undirected graph
   136     /// concept. "What does the direction of an undirected edge mean?"
   137     bool direction(const Edge &e) const { return e.forward; }
   138 
   139 
   140     using Parent::first;
   141     void first(Edge &e) const {
   142       Parent::first(e);
   143       e.forward=true;
   144     }
   145 
   146     using Parent::next;
   147     void next(Edge &e) const {
   148       if( e.forward ) {
   149 	e.forward = false;
   150       }
   151       else {
   152 	Parent::next(e);
   153 	e.forward = true;
   154       }
   155     }
   156 
   157     
   158   protected:
   159 
   160     template <typename E>
   161     void _dirFirstOut(E &e, const Node &n) const {
   162       Parent::firstIn(e,n);
   163       if( UndirEdge(e) != INVALID ) {
   164 	e.forward = false;
   165       }
   166       else {
   167 	Parent::firstOut(e,n);
   168 	e.forward = true;
   169       }
   170     }
   171     template <typename E>
   172     void _dirFirstIn(E &e, const Node &n) const {
   173       Parent::firstOut(e,n);
   174       if( UndirEdge(e) != INVALID ) {
   175 	e.forward = false;
   176       }
   177       else {
   178 	Parent::firstIn(e,n);
   179 	e.forward = true;
   180       }
   181     }
   182 
   183     template <typename E>
   184     void _dirNextOut(E &e) const {
   185       if( ! e.forward ) {
   186 	Node n = Parent::target(e);
   187 	Parent::nextIn(e);
   188 	if( UndirEdge(e) == INVALID ) {
   189 	  Parent::firstOut(e, n);
   190 	  e.forward = true;
   191 	}
   192       }
   193       else {
   194 	Parent::nextOut(e);
   195       }
   196     }
   197     template <typename E>
   198     void _dirNextIn(E &e) const {
   199       if( ! e.forward ) {
   200 	Node n = Parent::source(e);
   201 	Parent::nextOut(e);
   202 	if( UndirEdge(e) == INVALID ) {
   203 	  Parent::firstIn(e, n);
   204 	  e.forward = true;
   205 	}
   206       }
   207       else {
   208 	Parent::nextIn(e);
   209       }
   210     }
   211 
   212   public:
   213 
   214     void firstOut(Edge &e, const Node &n) const {
   215       _dirFirstOut(e, n);
   216     }
   217     void firstIn(Edge &e, const Node &n) const {
   218       _dirFirstIn(e, n);
   219     }
   220 
   221     void nextOut(Edge &e) const {
   222       _dirNextOut(e);
   223     }
   224     void nextIn(Edge &e) const {
   225       _dirNextIn(e);
   226     }
   227 
   228     // Miscellaneous stuff:
   229 
   230     /// \todo these methods (id, maxEdgeId) should be moved into separate
   231     /// Extender
   232 
   233     // using Parent::id;
   234     // Using "using" is not a good idea, cause it could be that there is
   235     // no "id" in Parent...
   236 
   237     int id(const Node &n) const {
   238       return Parent::id(n);
   239     }
   240 
   241     int id(const UndirEdge &e) const {
   242       return Parent::id(e);
   243     }
   244 
   245     int id(const Edge &e) const {
   246       return 2 * Parent::id(e) + int(e.forward);
   247     }
   248 
   249 
   250     int maxId(Node) const {
   251       return Parent::maxId(Node());
   252     }
   253 
   254     int maxId(Edge) const {
   255       return 2 * Parent::maxId(typename Parent::Edge()) + 1;
   256     }
   257     int maxId(UndirEdge) const {
   258       return Parent::maxId(typename Parent::Edge());
   259     }
   260 
   261 
   262     int edgeNum() const {
   263       return 2 * Parent::edgeNum();
   264     }
   265     int undirEdgeNum() const {
   266       return Parent::edgeNum();
   267     }
   268 
   269   };
   270 
   271 }
   272 
   273 #endif // LEMON_UNDIR_GRAPH_EXTENDER_H