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