lemon/static_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Sat, 06 Mar 2010 14:35:12 +0000
changeset 956 141f9c0db4a3
parent 834 c2230649a493
child 1328 d51126dc39fa
permissions -rw-r--r--
Unify the sources (#339)
alpar@956
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@820
     2
 *
alpar@956
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@820
     4
 *
alpar@956
     5
 * Copyright (C) 2003-2010
kpeter@820
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@820
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@820
     8
 *
kpeter@820
     9
 * Permission to use, modify and distribute this software is granted
kpeter@820
    10
 * provided that this copyright notice appears in all copies. For
kpeter@820
    11
 * precise terms see the accompanying LICENSE file.
kpeter@820
    12
 *
kpeter@820
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@820
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@820
    15
 * purpose.
kpeter@820
    16
 *
kpeter@820
    17
 */
kpeter@820
    18
kpeter@820
    19
#ifndef LEMON_STATIC_GRAPH_H
kpeter@820
    20
#define LEMON_STATIC_GRAPH_H
kpeter@820
    21
kpeter@820
    22
///\ingroup graphs
kpeter@820
    23
///\file
kpeter@820
    24
///\brief StaticDigraph class.
kpeter@820
    25
kpeter@820
    26
#include <lemon/core.h>
kpeter@820
    27
#include <lemon/bits/graph_extender.h>
kpeter@820
    28
kpeter@820
    29
namespace lemon {
kpeter@820
    30
kpeter@820
    31
  class StaticDigraphBase {
kpeter@820
    32
  public:
kpeter@820
    33
alpar@956
    34
    StaticDigraphBase()
alpar@956
    35
      : built(false), node_num(0), arc_num(0),
kpeter@820
    36
        node_first_out(NULL), node_first_in(NULL),
alpar@956
    37
        arc_source(NULL), arc_target(NULL),
kpeter@820
    38
        arc_next_in(NULL), arc_next_out(NULL) {}
alpar@956
    39
kpeter@820
    40
    ~StaticDigraphBase() {
kpeter@821
    41
      if (built) {
kpeter@820
    42
        delete[] node_first_out;
kpeter@820
    43
        delete[] node_first_in;
kpeter@820
    44
        delete[] arc_source;
kpeter@820
    45
        delete[] arc_target;
kpeter@820
    46
        delete[] arc_next_out;
kpeter@820
    47
        delete[] arc_next_in;
kpeter@820
    48
      }
kpeter@820
    49
    }
kpeter@820
    50
kpeter@820
    51
    class Node {
kpeter@820
    52
      friend class StaticDigraphBase;
kpeter@820
    53
    protected:
kpeter@820
    54
      int id;
kpeter@820
    55
      Node(int _id) : id(_id) {}
kpeter@820
    56
    public:
kpeter@820
    57
      Node() {}
kpeter@820
    58
      Node (Invalid) : id(-1) {}
kpeter@820
    59
      bool operator==(const Node& node) const { return id == node.id; }
kpeter@820
    60
      bool operator!=(const Node& node) const { return id != node.id; }
kpeter@820
    61
      bool operator<(const Node& node) const { return id < node.id; }
kpeter@820
    62
    };
kpeter@820
    63
kpeter@820
    64
    class Arc {
alpar@956
    65
      friend class StaticDigraphBase;
kpeter@820
    66
    protected:
kpeter@820
    67
      int id;
kpeter@820
    68
      Arc(int _id) : id(_id) {}
kpeter@820
    69
    public:
kpeter@820
    70
      Arc() { }
kpeter@820
    71
      Arc (Invalid) : id(-1) {}
kpeter@820
    72
      bool operator==(const Arc& arc) const { return id == arc.id; }
kpeter@820
    73
      bool operator!=(const Arc& arc) const { return id != arc.id; }
kpeter@820
    74
      bool operator<(const Arc& arc) const { return id < arc.id; }
kpeter@820
    75
    };
kpeter@820
    76
kpeter@820
    77
    Node source(const Arc& e) const { return Node(arc_source[e.id]); }
kpeter@820
    78
    Node target(const Arc& e) const { return Node(arc_target[e.id]); }
kpeter@820
    79
kpeter@820
    80
    void first(Node& n) const { n.id = node_num - 1; }
kpeter@820
    81
    static void next(Node& n) { --n.id; }
kpeter@820
    82
kpeter@820
    83
    void first(Arc& e) const { e.id = arc_num - 1; }
kpeter@820
    84
    static void next(Arc& e) { --e.id; }
kpeter@820
    85
alpar@956
    86
    void firstOut(Arc& e, const Node& n) const {
alpar@956
    87
      e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
kpeter@820
    88
        node_first_out[n.id] : -1;
kpeter@820
    89
    }
kpeter@820
    90
    void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
kpeter@820
    91
kpeter@820
    92
    void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
kpeter@820
    93
    void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
kpeter@820
    94
kpeter@825
    95
    static int id(const Node& n) { return n.id; }
kpeter@825
    96
    static Node nodeFromId(int id) { return Node(id); }
kpeter@820
    97
    int maxNodeId() const { return node_num - 1; }
kpeter@820
    98
kpeter@825
    99
    static int id(const Arc& e) { return e.id; }
kpeter@825
   100
    static Arc arcFromId(int id) { return Arc(id); }
kpeter@820
   101
    int maxArcId() const { return arc_num - 1; }
kpeter@820
   102
kpeter@820
   103
    typedef True NodeNumTag;
kpeter@820
   104
    typedef True ArcNumTag;
kpeter@820
   105
kpeter@820
   106
    int nodeNum() const { return node_num; }
kpeter@820
   107
    int arcNum() const { return arc_num; }
kpeter@820
   108
kpeter@820
   109
  private:
kpeter@820
   110
kpeter@820
   111
    template <typename Digraph, typename NodeRefMap>
kpeter@820
   112
    class ArcLess {
kpeter@820
   113
    public:
kpeter@820
   114
      typedef typename Digraph::Arc Arc;
kpeter@820
   115
alpar@956
   116
      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
kpeter@820
   117
        : digraph(_graph), nodeRef(_nodeRef) {}
alpar@956
   118
kpeter@820
   119
      bool operator()(const Arc& left, const Arc& right) const {
alpar@956
   120
        return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
kpeter@820
   121
      }
kpeter@820
   122
    private:
kpeter@820
   123
      const Digraph& digraph;
kpeter@820
   124
      const NodeRefMap& nodeRef;
kpeter@820
   125
    };
alpar@956
   126
kpeter@820
   127
  public:
kpeter@820
   128
kpeter@820
   129
    typedef True BuildTag;
alpar@956
   130
kpeter@821
   131
    void clear() {
kpeter@821
   132
      if (built) {
kpeter@820
   133
        delete[] node_first_out;
kpeter@820
   134
        delete[] node_first_in;
kpeter@820
   135
        delete[] arc_source;
kpeter@820
   136
        delete[] arc_target;
kpeter@820
   137
        delete[] arc_next_out;
kpeter@820
   138
        delete[] arc_next_in;
kpeter@820
   139
      }
kpeter@821
   140
      built = false;
kpeter@821
   141
      node_num = 0;
kpeter@821
   142
      arc_num = 0;
kpeter@821
   143
    }
alpar@956
   144
kpeter@821
   145
    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
kpeter@821
   146
    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
kpeter@820
   147
      typedef typename Digraph::Node GNode;
kpeter@820
   148
      typedef typename Digraph::Arc GArc;
kpeter@820
   149
kpeter@821
   150
      built = true;
kpeter@821
   151
kpeter@820
   152
      node_num = countNodes(digraph);
kpeter@820
   153
      arc_num = countArcs(digraph);
kpeter@820
   154
kpeter@820
   155
      node_first_out = new int[node_num + 1];
kpeter@820
   156
      node_first_in = new int[node_num];
kpeter@820
   157
kpeter@820
   158
      arc_source = new int[arc_num];
kpeter@820
   159
      arc_target = new int[arc_num];
kpeter@820
   160
      arc_next_out = new int[arc_num];
kpeter@820
   161
      arc_next_in = new int[arc_num];
kpeter@820
   162
kpeter@820
   163
      int node_index = 0;
kpeter@820
   164
      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
kpeter@820
   165
        nodeRef[n] = Node(node_index);
kpeter@820
   166
        node_first_in[node_index] = -1;
kpeter@820
   167
        ++node_index;
kpeter@820
   168
      }
kpeter@820
   169
kpeter@820
   170
      ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
kpeter@820
   171
kpeter@820
   172
      int arc_index = 0;
kpeter@820
   173
      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
kpeter@820
   174
        int source = nodeRef[n].id;
kpeter@820
   175
        std::vector<GArc> arcs;
kpeter@820
   176
        for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
kpeter@820
   177
          arcs.push_back(e);
kpeter@820
   178
        }
kpeter@820
   179
        if (!arcs.empty()) {
kpeter@820
   180
          node_first_out[source] = arc_index;
kpeter@820
   181
          std::sort(arcs.begin(), arcs.end(), arcLess);
kpeter@820
   182
          for (typename std::vector<GArc>::iterator it = arcs.begin();
kpeter@820
   183
               it != arcs.end(); ++it) {
kpeter@820
   184
            int target = nodeRef[digraph.target(*it)].id;
kpeter@820
   185
            arcRef[*it] = Arc(arc_index);
alpar@956
   186
            arc_source[arc_index] = source;
kpeter@820
   187
            arc_target[arc_index] = target;
kpeter@820
   188
            arc_next_in[arc_index] = node_first_in[target];
kpeter@820
   189
            node_first_in[target] = arc_index;
kpeter@820
   190
            arc_next_out[arc_index] = arc_index + 1;
kpeter@820
   191
            ++arc_index;
kpeter@820
   192
          }
kpeter@820
   193
          arc_next_out[arc_index - 1] = -1;
kpeter@820
   194
        } else {
kpeter@820
   195
          node_first_out[source] = arc_index;
kpeter@820
   196
        }
kpeter@820
   197
      }
kpeter@820
   198
      node_first_out[node_num] = arc_num;
kpeter@820
   199
    }
alpar@956
   200
kpeter@824
   201
    template <typename ArcListIterator>
kpeter@824
   202
    void build(int n, ArcListIterator first, ArcListIterator last) {
kpeter@824
   203
      built = true;
kpeter@824
   204
kpeter@824
   205
      node_num = n;
kpeter@824
   206
      arc_num = std::distance(first, last);
kpeter@824
   207
kpeter@824
   208
      node_first_out = new int[node_num + 1];
kpeter@824
   209
      node_first_in = new int[node_num];
kpeter@824
   210
kpeter@824
   211
      arc_source = new int[arc_num];
kpeter@824
   212
      arc_target = new int[arc_num];
kpeter@824
   213
      arc_next_out = new int[arc_num];
kpeter@824
   214
      arc_next_in = new int[arc_num];
alpar@956
   215
kpeter@824
   216
      for (int i = 0; i != node_num; ++i) {
kpeter@824
   217
        node_first_in[i] = -1;
alpar@956
   218
      }
alpar@956
   219
kpeter@824
   220
      int arc_index = 0;
kpeter@824
   221
      for (int i = 0; i != node_num; ++i) {
kpeter@824
   222
        node_first_out[i] = arc_index;
kpeter@824
   223
        for ( ; first != last && (*first).first == i; ++first) {
kpeter@824
   224
          int j = (*first).second;
kpeter@824
   225
          LEMON_ASSERT(j >= 0 && j < node_num,
kpeter@824
   226
            "Wrong arc list for StaticDigraph::build()");
kpeter@824
   227
          arc_source[arc_index] = i;
kpeter@824
   228
          arc_target[arc_index] = j;
kpeter@824
   229
          arc_next_in[arc_index] = node_first_in[j];
kpeter@824
   230
          node_first_in[j] = arc_index;
kpeter@824
   231
          arc_next_out[arc_index] = arc_index + 1;
kpeter@824
   232
          ++arc_index;
kpeter@824
   233
        }
kpeter@824
   234
        if (arc_index > node_first_out[i])
kpeter@824
   235
          arc_next_out[arc_index - 1] = -1;
kpeter@824
   236
      }
kpeter@824
   237
      LEMON_ASSERT(first == last,
kpeter@824
   238
        "Wrong arc list for StaticDigraph::build()");
kpeter@824
   239
      node_first_out[node_num] = arc_num;
kpeter@824
   240
    }
kpeter@820
   241
kpeter@820
   242
  protected:
kpeter@820
   243
kpeter@820
   244
    void fastFirstOut(Arc& e, const Node& n) const {
kpeter@820
   245
      e.id = node_first_out[n.id];
kpeter@820
   246
    }
kpeter@820
   247
kpeter@820
   248
    static void fastNextOut(Arc& e) {
kpeter@820
   249
      ++e.id;
kpeter@820
   250
    }
kpeter@820
   251
    void fastLastOut(Arc& e, const Node& n) const {
kpeter@820
   252
      e.id = node_first_out[n.id + 1];
kpeter@820
   253
    }
kpeter@820
   254
kpeter@821
   255
  protected:
kpeter@821
   256
    bool built;
kpeter@820
   257
    int node_num;
kpeter@820
   258
    int arc_num;
kpeter@820
   259
    int *node_first_out;
kpeter@820
   260
    int *node_first_in;
kpeter@820
   261
    int *arc_source;
kpeter@820
   262
    int *arc_target;
kpeter@820
   263
    int *arc_next_in;
kpeter@820
   264
    int *arc_next_out;
kpeter@820
   265
  };
kpeter@820
   266
kpeter@820
   267
  typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
kpeter@820
   268
kpeter@820
   269
kpeter@822
   270
  /// \ingroup graphs
kpeter@822
   271
  ///
kpeter@822
   272
  /// \brief A static directed graph class.
kpeter@822
   273
  ///
kpeter@822
   274
  /// \ref StaticDigraph is a highly efficient digraph implementation,
kpeter@822
   275
  /// but it is fully static.
kpeter@822
   276
  /// It stores only two \c int values for each node and only four \c int
kpeter@822
   277
  /// values for each arc. Moreover it provides faster item iteration than
kpeter@822
   278
  /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
kpeter@822
   279
  /// iterators, since its arcs are stored in an appropriate order.
kpeter@822
   280
  /// However it only provides build() and clear() functions and does not
kpeter@822
   281
  /// support any other modification of the digraph.
kpeter@822
   282
  ///
kpeter@823
   283
  /// Since this digraph structure is completely static, its nodes and arcs
kpeter@823
   284
  /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
alpar@956
   285
  /// and <tt>[0..arcNum()-1]</tt>, respectively.
kpeter@823
   286
  /// The index of an item is the same as its ID, it can be obtained
kpeter@823
   287
  /// using the corresponding \ref index() or \ref concepts::Digraph::id()
kpeter@823
   288
  /// "id()" function. A node or arc with a certain index can be obtained
kpeter@823
   289
  /// using node() or arc().
kpeter@823
   290
  ///
kpeter@822
   291
  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
kpeter@822
   292
  /// Most of its member functions and nested classes are documented
kpeter@822
   293
  /// only in the concept class.
kpeter@822
   294
  ///
kpeter@834
   295
  /// This class provides constant time counting for nodes and arcs.
kpeter@834
   296
  ///
kpeter@822
   297
  /// \sa concepts::Digraph
kpeter@820
   298
  class StaticDigraph : public ExtendedStaticDigraphBase {
kpeter@820
   299
  public:
kpeter@820
   300
kpeter@820
   301
    typedef ExtendedStaticDigraphBase Parent;
alpar@956
   302
kpeter@821
   303
  public:
alpar@956
   304
kpeter@823
   305
    /// \brief Constructor
kpeter@822
   306
    ///
kpeter@823
   307
    /// Default constructor.
kpeter@823
   308
    StaticDigraph() : Parent() {}
kpeter@823
   309
kpeter@823
   310
    /// \brief The node with the given index.
kpeter@823
   311
    ///
kpeter@823
   312
    /// This function returns the node with the given index.
kpeter@823
   313
    /// \sa index()
kpeter@825
   314
    static Node node(int ix) { return Parent::nodeFromId(ix); }
kpeter@823
   315
kpeter@823
   316
    /// \brief The arc with the given index.
kpeter@823
   317
    ///
kpeter@823
   318
    /// This function returns the arc with the given index.
kpeter@823
   319
    /// \sa index()
kpeter@825
   320
    static Arc arc(int ix) { return Parent::arcFromId(ix); }
kpeter@823
   321
kpeter@823
   322
    /// \brief The index of the given node.
kpeter@823
   323
    ///
kpeter@823
   324
    /// This function returns the index of the the given node.
kpeter@823
   325
    /// \sa node()
kpeter@825
   326
    static int index(Node node) { return Parent::id(node); }
kpeter@823
   327
kpeter@823
   328
    /// \brief The index of the given arc.
kpeter@823
   329
    ///
kpeter@823
   330
    /// This function returns the index of the the given arc.
kpeter@823
   331
    /// \sa arc()
kpeter@825
   332
    static int index(Arc arc) { return Parent::id(arc); }
kpeter@823
   333
kpeter@823
   334
    /// \brief Number of nodes.
kpeter@823
   335
    ///
kpeter@823
   336
    /// This function returns the number of nodes.
kpeter@823
   337
    int nodeNum() const { return node_num; }
kpeter@823
   338
kpeter@823
   339
    /// \brief Number of arcs.
kpeter@823
   340
    ///
kpeter@823
   341
    /// This function returns the number of arcs.
kpeter@823
   342
    int arcNum() const { return arc_num; }
kpeter@823
   343
kpeter@822
   344
    /// \brief Build the digraph copying another digraph.
kpeter@822
   345
    ///
kpeter@822
   346
    /// This function builds the digraph copying another digraph of any
kpeter@822
   347
    /// kind. It can be called more than once, but in such case, the whole
kpeter@822
   348
    /// structure and all maps will be cleared and rebuilt.
kpeter@822
   349
    ///
kpeter@822
   350
    /// This method also makes possible to copy a digraph to a StaticDigraph
kpeter@822
   351
    /// structure using \ref DigraphCopy.
alpar@956
   352
    ///
kpeter@822
   353
    /// \param digraph An existing digraph to be copied.
kpeter@822
   354
    /// \param nodeRef The node references will be copied into this map.
kpeter@822
   355
    /// Its key type must be \c Digraph::Node and its value type must be
kpeter@822
   356
    /// \c StaticDigraph::Node.
kpeter@822
   357
    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@822
   358
    /// concept.
kpeter@822
   359
    /// \param arcRef The arc references will be copied into this map.
kpeter@822
   360
    /// Its key type must be \c Digraph::Arc and its value type must be
kpeter@822
   361
    /// \c StaticDigraph::Arc.
kpeter@822
   362
    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
kpeter@822
   363
    ///
kpeter@822
   364
    /// \note If you do not need the arc references, then you could use
kpeter@822
   365
    /// \ref NullMap for the last parameter. However the node references
kpeter@822
   366
    /// are required by the function itself, thus they must be readable
kpeter@822
   367
    /// from the map.
kpeter@821
   368
    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
kpeter@821
   369
    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
kpeter@821
   370
      if (built) Parent::clear();
kpeter@821
   371
      Parent::build(digraph, nodeRef, arcRef);
kpeter@821
   372
    }
alpar@956
   373
kpeter@824
   374
    /// \brief Build the digraph from an arc list.
kpeter@824
   375
    ///
kpeter@824
   376
    /// This function builds the digraph from the given arc list.
kpeter@824
   377
    /// It can be called more than once, but in such case, the whole
kpeter@824
   378
    /// structure and all maps will be cleared and rebuilt.
kpeter@824
   379
    ///
kpeter@824
   380
    /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
kpeter@824
   381
    /// specified by STL compatible itartors whose \c value_type must be
kpeter@824
   382
    /// <tt>std::pair<int,int></tt>.
kpeter@824
   383
    /// Each arc must be specified by a pair of integer indices
kpeter@824
   384
    /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
kpeter@824
   385
    /// non-decreasing order with respect to their first values.</i>
kpeter@824
   386
    /// If the k-th pair in the list is <tt>(i,j)</tt>, then
kpeter@824
   387
    /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
kpeter@824
   388
    ///
kpeter@824
   389
    /// \param n The number of nodes.
kpeter@824
   390
    /// \param begin An iterator pointing to the beginning of the arc list.
kpeter@824
   391
    /// \param end An iterator pointing to the end of the arc list.
kpeter@824
   392
    ///
kpeter@824
   393
    /// For example, a simple digraph can be constructed like this.
kpeter@824
   394
    /// \code
kpeter@824
   395
    ///   std::vector<std::pair<int,int> > arcs;
kpeter@824
   396
    ///   arcs.push_back(std::make_pair(0,1));
kpeter@824
   397
    ///   arcs.push_back(std::make_pair(0,2));
kpeter@824
   398
    ///   arcs.push_back(std::make_pair(1,3));
kpeter@824
   399
    ///   arcs.push_back(std::make_pair(1,2));
kpeter@824
   400
    ///   arcs.push_back(std::make_pair(3,0));
kpeter@824
   401
    ///   StaticDigraph gr;
kpeter@824
   402
    ///   gr.build(4, arcs.begin(), arcs.end());
kpeter@824
   403
    /// \endcode
kpeter@824
   404
    template <typename ArcListIterator>
kpeter@824
   405
    void build(int n, ArcListIterator begin, ArcListIterator end) {
kpeter@824
   406
      if (built) Parent::clear();
kpeter@824
   407
      StaticDigraphBase::build(n, begin, end);
kpeter@824
   408
      notifier(Node()).build();
kpeter@824
   409
      notifier(Arc()).build();
kpeter@824
   410
    }
kpeter@824
   411
kpeter@823
   412
    /// \brief Clear the digraph.
kpeter@823
   413
    ///
kpeter@823
   414
    /// This function erases all nodes and arcs from the digraph.
kpeter@823
   415
    void clear() {
kpeter@823
   416
      Parent::clear();
kpeter@823
   417
    }
kpeter@820
   418
kpeter@820
   419
  protected:
kpeter@820
   420
kpeter@820
   421
    using Parent::fastFirstOut;
kpeter@820
   422
    using Parent::fastNextOut;
kpeter@820
   423
    using Parent::fastLastOut;
alpar@956
   424
kpeter@820
   425
  public:
kpeter@820
   426
kpeter@820
   427
    class OutArcIt : public Arc {
kpeter@820
   428
    public:
kpeter@820
   429
kpeter@820
   430
      OutArcIt() { }
kpeter@820
   431
kpeter@820
   432
      OutArcIt(Invalid i) : Arc(i) { }
kpeter@820
   433
kpeter@820
   434
      OutArcIt(const StaticDigraph& digraph, const Node& node) {
alpar@956
   435
        digraph.fastFirstOut(*this, node);
alpar@956
   436
        digraph.fastLastOut(last, node);
kpeter@820
   437
        if (last == *this) *this = INVALID;
kpeter@820
   438
      }
kpeter@820
   439
kpeter@820
   440
      OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
kpeter@820
   441
        if (arc != INVALID) {
kpeter@820
   442
          digraph.fastLastOut(last, digraph.source(arc));
kpeter@820
   443
        }
kpeter@820
   444
      }
kpeter@820
   445
alpar@956
   446
      OutArcIt& operator++() {
kpeter@820
   447
        StaticDigraph::fastNextOut(*this);
kpeter@820
   448
        if (last == *this) *this = INVALID;
alpar@956
   449
        return *this;
kpeter@820
   450
      }
kpeter@820
   451
kpeter@820
   452
    private:
kpeter@820
   453
      Arc last;
kpeter@820
   454
    };
kpeter@820
   455
kpeter@821
   456
    Node baseNode(const OutArcIt &arc) const {
kpeter@821
   457
      return Parent::source(static_cast<const Arc&>(arc));
kpeter@821
   458
    }
kpeter@821
   459
kpeter@821
   460
    Node runningNode(const OutArcIt &arc) const {
kpeter@821
   461
      return Parent::target(static_cast<const Arc&>(arc));
kpeter@821
   462
    }
kpeter@821
   463
kpeter@821
   464
    Node baseNode(const InArcIt &arc) const {
kpeter@821
   465
      return Parent::target(static_cast<const Arc&>(arc));
kpeter@821
   466
    }
kpeter@821
   467
kpeter@821
   468
    Node runningNode(const InArcIt &arc) const {
kpeter@821
   469
      return Parent::source(static_cast<const Arc&>(arc));
kpeter@821
   470
    }
kpeter@821
   471
kpeter@820
   472
  };
kpeter@820
   473
kpeter@820
   474
}
kpeter@820
   475
kpeter@820
   476
#endif