lemon/static_graph.h
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 25 Aug 2009 16:32:47 +0200
changeset 822 6cab2ab9d8e7
parent 821 f4b5c2d5449d
child 823 eff1caf6d32e
permissions -rw-r--r--
Add documentation for StaticDigraph (#68)
kpeter@820
     1
/* -*- C++ -*-
kpeter@820
     2
 *
kpeter@820
     3
 * This file is a part of LEMON, a generic C++ optimization library
kpeter@820
     4
 *
kpeter@820
     5
 * Copyright (C) 2003-2008
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
kpeter@820
    34
    StaticDigraphBase() 
kpeter@821
    35
      : built(false), node_num(0), arc_num(0), 
kpeter@820
    36
        node_first_out(NULL), node_first_in(NULL),
kpeter@820
    37
        arc_source(NULL), arc_target(NULL), 
kpeter@820
    38
        arc_next_in(NULL), arc_next_out(NULL) {}
kpeter@820
    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 {
kpeter@820
    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
kpeter@820
    86
    void firstOut(Arc& e, const Node& n) const { 
kpeter@820
    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@820
    95
    int id(const Node& n) const { return n.id; }
kpeter@820
    96
    Node nodeFromId(int id) const { return Node(id); }
kpeter@820
    97
    int maxNodeId() const { return node_num - 1; }
kpeter@820
    98
kpeter@820
    99
    int id(const Arc& e) const { return e.id; }
kpeter@820
   100
    Arc arcFromId(int id) const { 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
kpeter@820
   116
      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef) 
kpeter@820
   117
        : digraph(_graph), nodeRef(_nodeRef) {}
kpeter@820
   118
      
kpeter@820
   119
      bool operator()(const Arc& left, const Arc& right) const {
kpeter@820
   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
    };
kpeter@820
   126
    
kpeter@820
   127
  public:
kpeter@820
   128
kpeter@820
   129
    typedef True BuildTag;
kpeter@820
   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
    }
kpeter@821
   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);
kpeter@820
   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
    }
kpeter@820
   200
kpeter@820
   201
  protected:
kpeter@820
   202
kpeter@820
   203
    void fastFirstOut(Arc& e, const Node& n) const {
kpeter@820
   204
      e.id = node_first_out[n.id];
kpeter@820
   205
    }
kpeter@820
   206
kpeter@820
   207
    static void fastNextOut(Arc& e) {
kpeter@820
   208
      ++e.id;
kpeter@820
   209
    }
kpeter@820
   210
    void fastLastOut(Arc& e, const Node& n) const {
kpeter@820
   211
      e.id = node_first_out[n.id + 1];
kpeter@820
   212
    }
kpeter@820
   213
kpeter@821
   214
  protected:
kpeter@821
   215
    bool built;
kpeter@820
   216
    int node_num;
kpeter@820
   217
    int arc_num;
kpeter@820
   218
    int *node_first_out;
kpeter@820
   219
    int *node_first_in;
kpeter@820
   220
    int *arc_source;
kpeter@820
   221
    int *arc_target;
kpeter@820
   222
    int *arc_next_in;
kpeter@820
   223
    int *arc_next_out;
kpeter@820
   224
  };
kpeter@820
   225
kpeter@820
   226
  typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
kpeter@820
   227
kpeter@820
   228
kpeter@822
   229
  /// \ingroup graphs
kpeter@822
   230
  ///
kpeter@822
   231
  /// \brief A static directed graph class.
kpeter@822
   232
  ///
kpeter@822
   233
  /// \ref StaticDigraph is a highly efficient digraph implementation,
kpeter@822
   234
  /// but it is fully static.
kpeter@822
   235
  /// It stores only two \c int values for each node and only four \c int
kpeter@822
   236
  /// values for each arc. Moreover it provides faster item iteration than
kpeter@822
   237
  /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
kpeter@822
   238
  /// iterators, since its arcs are stored in an appropriate order.
kpeter@822
   239
  /// However it only provides build() and clear() functions and does not
kpeter@822
   240
  /// support any other modification of the digraph.
kpeter@822
   241
  ///
kpeter@822
   242
  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
kpeter@822
   243
  /// Most of its member functions and nested classes are documented
kpeter@822
   244
  /// only in the concept class.
kpeter@822
   245
  ///
kpeter@822
   246
  /// \sa concepts::Digraph
kpeter@820
   247
  class StaticDigraph : public ExtendedStaticDigraphBase {
kpeter@820
   248
  public:
kpeter@820
   249
kpeter@820
   250
    typedef ExtendedStaticDigraphBase Parent;
kpeter@821
   251
  
kpeter@821
   252
  public:
kpeter@821
   253
  
kpeter@822
   254
    /// \brief Clear the digraph.
kpeter@822
   255
    ///
kpeter@822
   256
    /// This function erases all nodes and arcs from the digraph.
kpeter@822
   257
    void clear() {
kpeter@822
   258
      Parent::clear();
kpeter@822
   259
    }
kpeter@822
   260
    
kpeter@822
   261
    /// \brief Build the digraph copying another digraph.
kpeter@822
   262
    ///
kpeter@822
   263
    /// This function builds the digraph copying another digraph of any
kpeter@822
   264
    /// kind. It can be called more than once, but in such case, the whole
kpeter@822
   265
    /// structure and all maps will be cleared and rebuilt.
kpeter@822
   266
    ///
kpeter@822
   267
    /// This method also makes possible to copy a digraph to a StaticDigraph
kpeter@822
   268
    /// structure using \ref DigraphCopy.
kpeter@822
   269
    /// 
kpeter@822
   270
    /// \param digraph An existing digraph to be copied.
kpeter@822
   271
    /// \param nodeRef The node references will be copied into this map.
kpeter@822
   272
    /// Its key type must be \c Digraph::Node and its value type must be
kpeter@822
   273
    /// \c StaticDigraph::Node.
kpeter@822
   274
    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
kpeter@822
   275
    /// concept.
kpeter@822
   276
    /// \param arcRef The arc references will be copied into this map.
kpeter@822
   277
    /// Its key type must be \c Digraph::Arc and its value type must be
kpeter@822
   278
    /// \c StaticDigraph::Arc.
kpeter@822
   279
    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
kpeter@822
   280
    ///
kpeter@822
   281
    /// \note If you do not need the arc references, then you could use
kpeter@822
   282
    /// \ref NullMap for the last parameter. However the node references
kpeter@822
   283
    /// are required by the function itself, thus they must be readable
kpeter@822
   284
    /// from the map.
kpeter@821
   285
    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
kpeter@821
   286
    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
kpeter@821
   287
      if (built) Parent::clear();
kpeter@821
   288
      Parent::build(digraph, nodeRef, arcRef);
kpeter@821
   289
    }
kpeter@821
   290
  
kpeter@820
   291
kpeter@820
   292
  protected:
kpeter@820
   293
kpeter@820
   294
    using Parent::fastFirstOut;
kpeter@820
   295
    using Parent::fastNextOut;
kpeter@820
   296
    using Parent::fastLastOut;
kpeter@820
   297
    
kpeter@820
   298
  public:
kpeter@820
   299
kpeter@820
   300
    class OutArcIt : public Arc {
kpeter@820
   301
    public:
kpeter@820
   302
kpeter@820
   303
      OutArcIt() { }
kpeter@820
   304
kpeter@820
   305
      OutArcIt(Invalid i) : Arc(i) { }
kpeter@820
   306
kpeter@820
   307
      OutArcIt(const StaticDigraph& digraph, const Node& node) {
kpeter@820
   308
	digraph.fastFirstOut(*this, node);
kpeter@820
   309
	digraph.fastLastOut(last, node);
kpeter@820
   310
        if (last == *this) *this = INVALID;
kpeter@820
   311
      }
kpeter@820
   312
kpeter@820
   313
      OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
kpeter@820
   314
        if (arc != INVALID) {
kpeter@820
   315
          digraph.fastLastOut(last, digraph.source(arc));
kpeter@820
   316
        }
kpeter@820
   317
      }
kpeter@820
   318
kpeter@820
   319
      OutArcIt& operator++() { 
kpeter@820
   320
        StaticDigraph::fastNextOut(*this);
kpeter@820
   321
        if (last == *this) *this = INVALID;
kpeter@820
   322
        return *this; 
kpeter@820
   323
      }
kpeter@820
   324
kpeter@820
   325
    private:
kpeter@820
   326
      Arc last;
kpeter@820
   327
    };
kpeter@820
   328
kpeter@821
   329
    Node baseNode(const OutArcIt &arc) const {
kpeter@821
   330
      return Parent::source(static_cast<const Arc&>(arc));
kpeter@821
   331
    }
kpeter@821
   332
kpeter@821
   333
    Node runningNode(const OutArcIt &arc) const {
kpeter@821
   334
      return Parent::target(static_cast<const Arc&>(arc));
kpeter@821
   335
    }
kpeter@821
   336
kpeter@821
   337
    Node baseNode(const InArcIt &arc) const {
kpeter@821
   338
      return Parent::target(static_cast<const Arc&>(arc));
kpeter@821
   339
    }
kpeter@821
   340
kpeter@821
   341
    Node runningNode(const InArcIt &arc) const {
kpeter@821
   342
      return Parent::source(static_cast<const Arc&>(arc));
kpeter@821
   343
    }
kpeter@821
   344
kpeter@820
   345
  };
kpeter@820
   346
kpeter@820
   347
}
kpeter@820
   348
kpeter@820
   349
#endif