src/lemon/undir_graph_extender.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 1164 80bb73097736
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
klao@962
     1
/* -*- C++ -*-
klao@962
     2
 *
klao@962
     3
 * src/lemon/undir_graph_extender.h - Part of LEMON, a generic C++
klao@962
     4
 * optimization library
klao@962
     5
 *
alpar@1164
     6
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi
klao@962
     7
 * Kutatocsoport (Egervary Combinatorial Optimization Research Group,
klao@962
     8
 * EGRES).
klao@962
     9
 *
klao@962
    10
 * Permission to use, modify and distribute this software is granted
klao@962
    11
 * provided that this copyright notice appears in all copies. For
klao@962
    12
 * precise terms see the accompanying LICENSE file.
klao@962
    13
 *
klao@962
    14
 * This software is provided "AS IS" with no warranty of any kind,
klao@962
    15
 * express or implied, and with no claim as to its suitability for any
klao@962
    16
 * purpose.
klao@962
    17
 *
klao@962
    18
 */
klao@962
    19
klao@962
    20
#ifndef LEMON_UNDIR_GRAPH_EXTENDER_H
klao@962
    21
#define LEMON_UNDIR_GRAPH_EXTENDER_H
klao@962
    22
klao@962
    23
#include <lemon/invalid.h>
klao@962
    24
klao@962
    25
namespace lemon {
klao@962
    26
klao@962
    27
  template <typename _Base>
klao@962
    28
  class UndirGraphExtender : public _Base {
klao@962
    29
    typedef _Base Parent;
klao@962
    30
    typedef UndirGraphExtender Graph;
klao@962
    31
klao@962
    32
  public:
klao@962
    33
klao@962
    34
    typedef typename Parent::Edge UndirEdge;
klao@962
    35
    typedef typename Parent::Node Node;
klao@962
    36
klao@962
    37
    class Edge : public UndirEdge {
klao@978
    38
      friend class UndirGraphExtender;
klao@962
    39
klao@962
    40
    protected:
klao@962
    41
      // FIXME: Marci use opposite logic in his graph wrappers. It would
klao@962
    42
      // be reasonable to syncronize...
klao@962
    43
      bool forward;
klao@962
    44
klao@962
    45
    public:
klao@962
    46
      Edge() {}
klao@1158
    47
klao@1158
    48
      /// \brief Directed edge from undirected edge and a direction.
klao@1158
    49
      ///
klao@1158
    50
      /// This constructor is not a part of the concept interface of
klao@1158
    51
      /// undirected graph, so please avoid using it if possible!
klao@962
    52
      Edge(const UndirEdge &ue, bool _forward) :
klao@1158
    53
        UndirEdge(ue), forward(_forward) {}
klao@1158
    54
klao@1158
    55
      /// \brief Directed edge from undirected edge and a source node.
klao@1158
    56
      ///
klao@1158
    57
      /// Constructs a directed edge from undirected edge and a source node.
klao@1158
    58
      ///
klao@1158
    59
      /// \note You have to specify the graph for this constructor.
klao@1158
    60
      Edge(const Graph &g, const UndirEdge &ue, const Node &n) :
klao@1158
    61
	UndirEdge(ue) { forward = (g.source(ue) == n); }
klao@1158
    62
klao@962
    63
      /// Invalid edge constructor
klao@1053
    64
      Edge(Invalid i) : UndirEdge(i), forward(true) {}
klao@962
    65
klao@962
    66
      bool operator==(const Edge &that) const {
klao@962
    67
	return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
klao@962
    68
      }
klao@962
    69
      bool operator!=(const Edge &that) const {
klao@962
    70
	return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
klao@962
    71
      }
klao@962
    72
      bool operator<(const Edge &that) const {
klao@962
    73
	return forward<that.forward ||
klao@962
    74
	  (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
klao@962
    75
      }
klao@962
    76
    };
klao@962
    77
klao@962
    78
klao@1158
    79
    /// \brief Edge of opposite direction.
klao@962
    80
    ///
klao@1158
    81
    /// Returns the Edge of opposite direction.
klao@962
    82
    Edge opposite(const Edge &e) const {
klao@962
    83
      return Edge(e,!e.forward);
klao@962
    84
    }
klao@962
    85
klao@1021
    86
  protected:
klao@1021
    87
klao@1021
    88
    template <typename E>
klao@1021
    89
    Node _dirSource(const E &e) const {
alpar@986
    90
      return e.forward ? Parent::source(e) : Parent::target(e);
klao@962
    91
    }
klao@962
    92
klao@1021
    93
    template <typename E>
klao@1021
    94
    Node _dirTarget(const E &e) const {
klao@1021
    95
      return e.forward ? Parent::target(e) : Parent::source(e);
klao@1021
    96
    }
klao@1021
    97
klao@1021
    98
  public:
alpar@986
    99
    /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
klao@962
   100
    /// or something???
alpar@986
   101
    using Parent::source;
klao@962
   102
klao@1021
   103
    /// Source of the given Edge.
klao@1021
   104
    Node source(const Edge &e) const {
klao@1021
   105
      return _dirSource(e);
klao@962
   106
    }
klao@962
   107
alpar@986
   108
    /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
klao@962
   109
    /// or something???
alpar@986
   110
    using Parent::target;
klao@962
   111
klao@1021
   112
    /// Target of the given Edge.
klao@1021
   113
    Node target(const Edge &e) const {
klao@1021
   114
      return _dirTarget(e);
klao@1021
   115
    }
klao@1021
   116
klao@962
   117
    /// Returns whether the given directed edge is same orientation as the
klao@962
   118
    /// corresponding undirected edge.
klao@962
   119
    ///
klao@962
   120
    /// \todo reference to the corresponding point of the undirected graph
klao@962
   121
    /// concept. "What does the direction of an undirected edge mean?"
klao@962
   122
    bool forward(const Edge &e) const { return e.forward; }
klao@962
   123
klao@1030
   124
    Node oppositeNode(const Node &n, const UndirEdge &e) const {
alpar@986
   125
      if( n == Parent::source(e))
alpar@986
   126
	return Parent::target(e);
alpar@986
   127
      else if( n == Parent::target(e))
alpar@986
   128
	return Parent::source(e);
klao@962
   129
      else
klao@962
   130
	return INVALID;
klao@962
   131
    }
klao@962
   132
klao@1158
   133
    /// Directed edge from an undirected edge and a source node.
klao@1158
   134
    ///
klao@1158
   135
    /// Returns a (directed) Edge corresponding to the specified UndirEdge
klao@1158
   136
    /// and source Node.
klao@1158
   137
    ///
klao@1158
   138
    ///\todo Do we need this?
klao@1158
   139
    ///
klao@1158
   140
    ///\todo Better name...
klao@1158
   141
    Edge edgeWithSource(const UndirEdge &ue, const Node &s) const {
deba@1189
   142
      return Edge(*this, ue, s);
klao@1158
   143
    }
klao@962
   144
klao@962
   145
    using Parent::first;
klao@962
   146
    void first(Edge &e) const {
klao@962
   147
      Parent::first(e);
klao@962
   148
      e.forward=true;
klao@962
   149
    }
klao@962
   150
klao@962
   151
    using Parent::next;
klao@962
   152
    void next(Edge &e) const {
klao@962
   153
      if( e.forward ) {
klao@962
   154
	e.forward = false;
klao@962
   155
      }
klao@962
   156
      else {
klao@962
   157
	Parent::next(e);
klao@962
   158
	e.forward = true;
klao@962
   159
      }
klao@962
   160
    }
klao@962
   161
klao@1021
   162
    
klao@1021
   163
  protected:
klao@1021
   164
klao@1021
   165
    template <typename E>
klao@1021
   166
    void _dirFirstOut(E &e, const Node &n) const {
klao@1060
   167
      Parent::firstIn(e,n);
klao@962
   168
      if( UndirEdge(e) != INVALID ) {
klao@1060
   169
	e.forward = false;
klao@962
   170
      }
klao@962
   171
      else {
klao@1060
   172
	Parent::firstOut(e,n);
klao@1060
   173
	e.forward = true;
klao@962
   174
      }
klao@962
   175
    }
klao@1021
   176
    template <typename E>
klao@1021
   177
    void _dirFirstIn(E &e, const Node &n) const {
klao@1060
   178
      Parent::firstOut(e,n);
klao@962
   179
      if( UndirEdge(e) != INVALID ) {
klao@1060
   180
	e.forward = false;
klao@962
   181
      }
klao@962
   182
      else {
klao@1060
   183
	Parent::firstIn(e,n);
klao@1060
   184
	e.forward = true;
klao@962
   185
      }
klao@962
   186
    }
klao@962
   187
klao@1021
   188
    template <typename E>
klao@1021
   189
    void _dirNextOut(E &e) const {
klao@1060
   190
      if( ! e.forward ) {
klao@1060
   191
	Node n = Parent::target(e);
klao@1060
   192
	Parent::nextIn(e);
klao@1060
   193
	if( UndirEdge(e) == INVALID ) {
klao@1060
   194
	  Parent::firstOut(e, n);
klao@1060
   195
	  e.forward = true;
klao@1060
   196
	}
klao@1060
   197
      }
klao@1060
   198
      else {
klao@1060
   199
	Parent::nextOut(e);
klao@1060
   200
      }
klao@1060
   201
    }
klao@1060
   202
    template <typename E>
klao@1060
   203
    void _dirNextIn(E &e) const {
klao@1060
   204
      if( ! e.forward ) {
klao@1060
   205
	Node n = Parent::source(e);
klao@962
   206
	Parent::nextOut(e);
klao@962
   207
	if( UndirEdge(e) == INVALID ) {
klao@1060
   208
	  Parent::firstIn(e, n);
klao@1060
   209
	  e.forward = true;
klao@962
   210
	}
klao@962
   211
      }
klao@962
   212
      else {
klao@962
   213
	Parent::nextIn(e);
klao@962
   214
      }
klao@962
   215
    }
klao@962
   216
klao@1021
   217
  public:
klao@1021
   218
klao@1021
   219
    void firstOut(Edge &e, const Node &n) const {
klao@1021
   220
      _dirFirstOut(e, n);
klao@1021
   221
    }
klao@1021
   222
    void firstIn(Edge &e, const Node &n) const {
klao@1021
   223
      _dirFirstIn(e, n);
klao@1021
   224
    }
klao@1021
   225
klao@1021
   226
    void nextOut(Edge &e) const {
klao@1021
   227
      _dirNextOut(e);
klao@1021
   228
    }
klao@1021
   229
    void nextIn(Edge &e) const {
klao@1021
   230
      _dirNextIn(e);
klao@1021
   231
    }
klao@1021
   232
klao@962
   233
    // Miscellaneous stuff:
klao@962
   234
klao@962
   235
    /// \todo these methods (id, maxEdgeId) should be moved into separate
klao@962
   236
    /// Extender
klao@962
   237
klao@1021
   238
    // using Parent::id;
klao@1021
   239
    // Using "using" is not a good idea, cause it could be that there is
klao@1021
   240
    // no "id" in Parent...
klao@1021
   241
klao@1021
   242
    int id(const Node &n) const {
klao@1021
   243
      return Parent::id(n);
klao@1021
   244
    }
klao@1021
   245
klao@1021
   246
    int id(const UndirEdge &e) const {
klao@1021
   247
      return Parent::id(e);
klao@1021
   248
    }
klao@962
   249
klao@962
   250
    int id(const Edge &e) const {
deba@981
   251
      return 2 * Parent::id(e) + int(e.forward);
klao@962
   252
    }
klao@962
   253
klao@1021
   254
klao@1060
   255
    int maxId(Node) const {
klao@1021
   256
      return Parent::maxId(Node());
klao@1021
   257
    }
klao@1021
   258
klao@1021
   259
    int maxId(Edge) const {
deba@981
   260
      return 2 * Parent::maxId(typename Parent::Edge()) + 1;
klao@962
   261
    }
klao@1021
   262
    int maxId(UndirEdge) const {
deba@981
   263
      return Parent::maxId(typename Parent::Edge());
klao@962
   264
    }
klao@962
   265
klao@1054
   266
klao@1054
   267
    int edgeNum() const {
klao@1054
   268
      return 2 * Parent::edgeNum();
klao@1054
   269
    }
klao@1054
   270
    int undirEdgeNum() const {
klao@1054
   271
      return Parent::edgeNum();
klao@1054
   272
    }
klao@1054
   273
klao@962
   274
  };
klao@962
   275
klao@962
   276
}
klao@962
   277
klao@962
   278
#endif // LEMON_UNDIR_GRAPH_EXTENDER_H