lemon/full_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 02 Dec 2008 10:31:20 +0000
changeset 408 69f33ef03334
parent 355 aa75d24ba7d0
child 440 88ed40ad0d4f
permissions -rw-r--r--
Merge
deba@353
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
deba@353
     2
 *
deba@353
     3
 * This file is a part of LEMON, a generic C++ optimization library.
deba@353
     4
 *
deba@353
     5
 * Copyright (C) 2003-2008
deba@353
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@353
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@353
     8
 *
deba@353
     9
 * Permission to use, modify and distribute this software is granted
deba@353
    10
 * provided that this copyright notice appears in all copies. For
deba@353
    11
 * precise terms see the accompanying LICENSE file.
deba@353
    12
 *
deba@353
    13
 * This software is provided "AS IS" with no warranty of any kind,
deba@353
    14
 * express or implied, and with no claim as to its suitability for any
deba@353
    15
 * purpose.
deba@353
    16
 *
deba@353
    17
 */
deba@353
    18
deba@353
    19
#ifndef LEMON_FULL_GRAPH_H
deba@353
    20
#define LEMON_FULL_GRAPH_H
deba@353
    21
deba@353
    22
#include <lemon/core.h>
deba@353
    23
#include <lemon/bits/graph_extender.h>
deba@353
    24
deba@353
    25
///\ingroup graphs
deba@353
    26
///\file
kpeter@354
    27
///\brief FullGraph and FullDigraph classes.
kpeter@354
    28
deba@353
    29
namespace lemon {
deba@353
    30
deba@353
    31
  class FullDigraphBase {
deba@353
    32
  public:
deba@353
    33
deba@353
    34
    typedef FullDigraphBase Graph;
deba@353
    35
deba@353
    36
    class Node;
deba@353
    37
    class Arc;
deba@353
    38
deba@353
    39
  protected:
deba@353
    40
deba@353
    41
    int _node_num;
deba@353
    42
    int _arc_num;
deba@353
    43
deba@353
    44
    FullDigraphBase() {}
deba@353
    45
deba@353
    46
    void construct(int n) { _node_num = n; _arc_num = n * n; }
deba@353
    47
deba@353
    48
  public:
deba@353
    49
deba@353
    50
    typedef True NodeNumTag;
deba@353
    51
    typedef True ArcNumTag;
deba@353
    52
deba@353
    53
    Node operator()(int ix) const { return Node(ix); }
deba@353
    54
    int index(const Node& node) const { return node._id; }
deba@353
    55
deba@353
    56
    Arc arc(const Node& s, const Node& t) const {
deba@353
    57
      return Arc(s._id * _node_num + t._id);
deba@353
    58
    }
deba@353
    59
deba@353
    60
    int nodeNum() const { return _node_num; }
deba@353
    61
    int arcNum() const { return _arc_num; }
deba@353
    62
deba@353
    63
    int maxNodeId() const { return _node_num - 1; }
deba@353
    64
    int maxArcId() const { return _arc_num - 1; }
deba@353
    65
deba@353
    66
    Node source(Arc arc) const { return arc._id / _node_num; }
deba@353
    67
    Node target(Arc arc) const { return arc._id % _node_num; }
deba@353
    68
deba@353
    69
    static int id(Node node) { return node._id; }
deba@353
    70
    static int id(Arc arc) { return arc._id; }
deba@353
    71
deba@353
    72
    static Node nodeFromId(int id) { return Node(id);}
deba@353
    73
    static Arc arcFromId(int id) { return Arc(id);}
deba@353
    74
deba@353
    75
    typedef True FindArcTag;
deba@353
    76
deba@353
    77
    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
kpeter@355
    78
      return prev == INVALID ? arc(s, t) : INVALID;
deba@353
    79
    }
deba@353
    80
deba@353
    81
    class Node {
deba@353
    82
      friend class FullDigraphBase;
deba@353
    83
deba@353
    84
    protected:
deba@353
    85
      int _id;
deba@353
    86
      Node(int id) : _id(id) {}
deba@353
    87
    public:
deba@353
    88
      Node() {}
deba@353
    89
      Node (Invalid) : _id(-1) {}
deba@353
    90
      bool operator==(const Node node) const {return _id == node._id;}
deba@353
    91
      bool operator!=(const Node node) const {return _id != node._id;}
deba@353
    92
      bool operator<(const Node node) const {return _id < node._id;}
deba@353
    93
    };
deba@353
    94
deba@353
    95
    class Arc {
deba@353
    96
      friend class FullDigraphBase;
deba@353
    97
deba@353
    98
    protected:
deba@353
    99
      int _id;  // _node_num * source + target;
deba@353
   100
deba@353
   101
      Arc(int id) : _id(id) {}
deba@353
   102
deba@353
   103
    public:
deba@353
   104
      Arc() { }
deba@353
   105
      Arc (Invalid) { _id = -1; }
deba@353
   106
      bool operator==(const Arc arc) const {return _id == arc._id;}
deba@353
   107
      bool operator!=(const Arc arc) const {return _id != arc._id;}
deba@353
   108
      bool operator<(const Arc arc) const {return _id < arc._id;}
deba@353
   109
    };
deba@353
   110
deba@353
   111
    void first(Node& node) const {
deba@353
   112
      node._id = _node_num - 1;
deba@353
   113
    }
deba@353
   114
deba@353
   115
    static void next(Node& node) {
deba@353
   116
      --node._id;
deba@353
   117
    }
deba@353
   118
deba@353
   119
    void first(Arc& arc) const {
deba@353
   120
      arc._id = _arc_num - 1;
deba@353
   121
    }
deba@353
   122
deba@353
   123
    static void next(Arc& arc) {
deba@353
   124
      --arc._id;
deba@353
   125
    }
deba@353
   126
deba@353
   127
    void firstOut(Arc& arc, const Node& node) const {
deba@353
   128
      arc._id = (node._id + 1) * _node_num - 1;
deba@353
   129
    }
deba@353
   130
deba@353
   131
    void nextOut(Arc& arc) const {
deba@353
   132
      if (arc._id % _node_num == 0) arc._id = 0;
deba@353
   133
      --arc._id;
deba@353
   134
    }
deba@353
   135
deba@353
   136
    void firstIn(Arc& arc, const Node& node) const {
deba@353
   137
      arc._id = _arc_num + node._id - _node_num;
deba@353
   138
    }
deba@353
   139
deba@353
   140
    void nextIn(Arc& arc) const {
deba@353
   141
      arc._id -= _node_num;
deba@353
   142
      if (arc._id < 0) arc._id = -1;
deba@353
   143
    }
deba@353
   144
deba@353
   145
  };
deba@353
   146
deba@353
   147
  typedef DigraphExtender<FullDigraphBase> ExtendedFullDigraphBase;
deba@353
   148
deba@353
   149
  /// \ingroup graphs
deba@353
   150
  ///
deba@353
   151
  /// \brief A full digraph class.
deba@353
   152
  ///
deba@353
   153
  /// This is a simple and fast directed full graph implementation.
deba@353
   154
  /// From each node go arcs to each node (including the source node),
deba@353
   155
  /// therefore the number of the arcs in the digraph is the square of
kpeter@354
   156
  /// the node number. This digraph type is completely static, so you
kpeter@354
   157
  /// can neither add nor delete either arcs or nodes, and it needs
deba@353
   158
  /// constant space in memory.
deba@353
   159
  ///
kpeter@354
   160
  /// This class conforms to the \ref concepts::Digraph "Digraph" concept
deba@353
   161
  /// and it also has an important extra feature that its maps are
deba@353
   162
  /// real \ref concepts::ReferenceMap "reference map"s.
kpeter@354
   163
  ///
kpeter@354
   164
  /// The \c FullDigraph and \c FullGraph classes are very similar,
kpeter@354
   165
  /// but there are two differences. While this class conforms only
kpeter@354
   166
  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
kpeter@354
   167
  /// class conforms to the \ref concepts::Graph "Graph" concept,
kpeter@354
   168
  /// moreover \c FullGraph does not contain a loop arc for each
kpeter@354
   169
  /// node as \c FullDigraph does.
deba@353
   170
  ///
deba@353
   171
  /// \sa FullGraph
deba@353
   172
  class FullDigraph : public ExtendedFullDigraphBase {
deba@353
   173
  public:
deba@353
   174
deba@353
   175
    typedef ExtendedFullDigraphBase Parent;
deba@353
   176
deba@353
   177
    /// \brief Constructor
deba@353
   178
    FullDigraph() { construct(0); }
deba@353
   179
deba@353
   180
    /// \brief Constructor
deba@353
   181
    ///
kpeter@354
   182
    /// Constructor.
deba@353
   183
    /// \param n The number of the nodes.
deba@353
   184
    FullDigraph(int n) { construct(n); }
deba@353
   185
kpeter@354
   186
    /// \brief Resizes the digraph
deba@353
   187
    ///
kpeter@354
   188
    /// Resizes the digraph. The function will fully destroy and
kpeter@354
   189
    /// rebuild the digraph. This cause that the maps of the digraph will
kpeter@354
   190
    /// reallocated automatically and the previous values will be lost.
deba@353
   191
    void resize(int n) {
deba@353
   192
      Parent::notifier(Arc()).clear();
deba@353
   193
      Parent::notifier(Node()).clear();
deba@353
   194
      construct(n);
deba@353
   195
      Parent::notifier(Node()).build();
deba@353
   196
      Parent::notifier(Arc()).build();
deba@353
   197
    }
deba@353
   198
deba@353
   199
    /// \brief Returns the node with the given index.
deba@353
   200
    ///
kpeter@354
   201
    /// Returns the node with the given index. Since it is a static
kpeter@354
   202
    /// digraph its nodes can be indexed with integers from the range
kpeter@354
   203
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   204
    /// \sa index()
deba@353
   205
    Node operator()(int ix) const { return Parent::operator()(ix); }
deba@353
   206
kpeter@354
   207
    /// \brief Returns the index of the given node.
deba@353
   208
    ///
kpeter@354
   209
    /// Returns the index of the given node. Since it is a static
kpeter@354
   210
    /// digraph its nodes can be indexed with integers from the range
kpeter@354
   211
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   212
    /// \sa operator()
deba@353
   213
    int index(const Node& node) const { return Parent::index(node); }
deba@353
   214
kpeter@354
   215
    /// \brief Returns the arc connecting the given nodes.
deba@353
   216
    ///
kpeter@354
   217
    /// Returns the arc connecting the given nodes.
deba@353
   218
    Arc arc(const Node& u, const Node& v) const {
deba@353
   219
      return Parent::arc(u, v);
deba@353
   220
    }
deba@353
   221
deba@353
   222
    /// \brief Number of nodes.
deba@353
   223
    int nodeNum() const { return Parent::nodeNum(); }
deba@353
   224
    /// \brief Number of arcs.
deba@353
   225
    int arcNum() const { return Parent::arcNum(); }
deba@353
   226
  };
deba@353
   227
deba@353
   228
deba@353
   229
  class FullGraphBase {
deba@353
   230
    int _node_num;
deba@353
   231
    int _edge_num;
deba@353
   232
  public:
deba@353
   233
deba@353
   234
    typedef FullGraphBase Graph;
deba@353
   235
deba@353
   236
    class Node;
deba@353
   237
    class Arc;
deba@353
   238
    class Edge;
deba@353
   239
deba@353
   240
  protected:
deba@353
   241
deba@353
   242
    FullGraphBase() {}
deba@353
   243
deba@353
   244
    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
deba@353
   245
deba@353
   246
    int _uid(int e) const {
deba@353
   247
      int u = e / _node_num;
deba@353
   248
      int v = e % _node_num;
deba@353
   249
      return u < v ? u : _node_num - 2 - u;
deba@353
   250
    }
deba@353
   251
deba@353
   252
    int _vid(int e) const {
deba@353
   253
      int u = e / _node_num;
deba@353
   254
      int v = e % _node_num;
deba@353
   255
      return u < v ? v : _node_num - 1 - v;
deba@353
   256
    }
deba@353
   257
deba@353
   258
    void _uvid(int e, int& u, int& v) const {
deba@353
   259
      u = e / _node_num;
deba@353
   260
      v = e % _node_num;
deba@353
   261
      if  (u >= v) {
deba@353
   262
        u = _node_num - 2 - u;
deba@353
   263
        v = _node_num - 1 - v;
deba@353
   264
      }
deba@353
   265
    }
deba@353
   266
deba@353
   267
    void _stid(int a, int& s, int& t) const {
deba@353
   268
      if ((a & 1) == 1) {
deba@353
   269
        _uvid(a >> 1, s, t);
deba@353
   270
      } else {
deba@353
   271
        _uvid(a >> 1, t, s);
deba@353
   272
      }
deba@353
   273
    }
deba@353
   274
deba@353
   275
    int _eid(int u, int v) const {
deba@353
   276
      if (u < (_node_num - 1) / 2) {
deba@353
   277
        return u * _node_num + v;
deba@353
   278
      } else {
deba@353
   279
        return (_node_num - 1 - u) * _node_num - v - 1;
deba@353
   280
      }
deba@353
   281
    }
deba@353
   282
deba@353
   283
  public:
deba@353
   284
deba@353
   285
    Node operator()(int ix) const { return Node(ix); }
deba@353
   286
    int index(const Node& node) const { return node._id; }
deba@353
   287
deba@353
   288
    Edge edge(const Node& u, const Node& v) const {
deba@353
   289
      if (u._id < v._id) {
deba@353
   290
        return Edge(_eid(u._id, v._id));
deba@353
   291
      } else if (u._id != v._id) {
deba@353
   292
        return Edge(_eid(v._id, u._id));
deba@353
   293
      } else {
deba@353
   294
        return INVALID;
deba@353
   295
      }
deba@353
   296
    }
deba@353
   297
deba@353
   298
    Arc arc(const Node& s, const Node& t) const {
deba@353
   299
      if (s._id < t._id) {
deba@353
   300
        return Arc((_eid(s._id, t._id) << 1) | 1);
deba@353
   301
      } else if (s._id != t._id) {
deba@353
   302
        return Arc(_eid(t._id, s._id) << 1);
deba@353
   303
      } else {
deba@353
   304
        return INVALID;
deba@353
   305
      }
deba@353
   306
    }
deba@353
   307
deba@353
   308
    typedef True NodeNumTag;
kpeter@360
   309
    typedef True ArcNumTag;
deba@353
   310
    typedef True EdgeNumTag;
deba@353
   311
deba@353
   312
    int nodeNum() const { return _node_num; }
deba@353
   313
    int arcNum() const { return 2 * _edge_num; }
deba@353
   314
    int edgeNum() const { return _edge_num; }
deba@353
   315
deba@353
   316
    static int id(Node node) { return node._id; }
deba@353
   317
    static int id(Arc arc) { return arc._id; }
deba@353
   318
    static int id(Edge edge) { return edge._id; }
deba@353
   319
deba@353
   320
    int maxNodeId() const { return _node_num-1; }
deba@353
   321
    int maxArcId() const { return 2 * _edge_num-1; }
deba@353
   322
    int maxEdgeId() const { return _edge_num-1; }
deba@353
   323
deba@353
   324
    static Node nodeFromId(int id) { return Node(id);}
deba@353
   325
    static Arc arcFromId(int id) { return Arc(id);}
deba@353
   326
    static Edge edgeFromId(int id) { return Edge(id);}
deba@353
   327
deba@353
   328
    Node u(Edge edge) const {
deba@353
   329
      return Node(_uid(edge._id));
deba@353
   330
    }
deba@353
   331
deba@353
   332
    Node v(Edge edge) const {
deba@353
   333
      return Node(_vid(edge._id));
deba@353
   334
    }
deba@353
   335
deba@353
   336
    Node source(Arc arc) const {
deba@353
   337
      return Node((arc._id & 1) == 1 ?
deba@353
   338
                  _uid(arc._id >> 1) : _vid(arc._id >> 1));
deba@353
   339
    }
deba@353
   340
deba@353
   341
    Node target(Arc arc) const {
deba@353
   342
      return Node((arc._id & 1) == 1 ?
deba@353
   343
                  _vid(arc._id >> 1) : _uid(arc._id >> 1));
deba@353
   344
    }
deba@353
   345
deba@353
   346
    typedef True FindEdgeTag;
kpeter@360
   347
    typedef True FindArcTag;
deba@353
   348
deba@353
   349
    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
deba@353
   350
      return prev != INVALID ? INVALID : edge(u, v);
deba@353
   351
    }
deba@353
   352
deba@353
   353
    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
deba@353
   354
      return prev != INVALID ? INVALID : arc(s, t);
deba@353
   355
    }
deba@353
   356
deba@353
   357
    class Node {
deba@353
   358
      friend class FullGraphBase;
deba@353
   359
deba@353
   360
    protected:
deba@353
   361
      int _id;
deba@353
   362
      Node(int id) : _id(id) {}
deba@353
   363
    public:
deba@353
   364
      Node() {}
deba@353
   365
      Node (Invalid) { _id = -1; }
deba@353
   366
      bool operator==(const Node node) const {return _id == node._id;}
deba@353
   367
      bool operator!=(const Node node) const {return _id != node._id;}
deba@353
   368
      bool operator<(const Node node) const {return _id < node._id;}
deba@353
   369
    };
deba@353
   370
deba@353
   371
    class Edge {
deba@353
   372
      friend class FullGraphBase;
kpeter@354
   373
      friend class Arc;
deba@353
   374
deba@353
   375
    protected:
deba@353
   376
      int _id;
deba@353
   377
deba@353
   378
      Edge(int id) : _id(id) {}
deba@353
   379
deba@353
   380
    public:
deba@353
   381
      Edge() { }
deba@353
   382
      Edge (Invalid) { _id = -1; }
deba@353
   383
deba@353
   384
      bool operator==(const Edge edge) const {return _id == edge._id;}
deba@353
   385
      bool operator!=(const Edge edge) const {return _id != edge._id;}
deba@353
   386
      bool operator<(const Edge edge) const {return _id < edge._id;}
deba@353
   387
    };
deba@353
   388
deba@353
   389
    class Arc {
deba@353
   390
      friend class FullGraphBase;
deba@353
   391
deba@353
   392
    protected:
deba@353
   393
      int _id;
deba@353
   394
deba@353
   395
      Arc(int id) : _id(id) {}
deba@353
   396
deba@353
   397
    public:
deba@353
   398
      Arc() { }
deba@353
   399
      Arc (Invalid) { _id = -1; }
deba@353
   400
deba@353
   401
      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
deba@353
   402
deba@353
   403
      bool operator==(const Arc arc) const {return _id == arc._id;}
deba@353
   404
      bool operator!=(const Arc arc) const {return _id != arc._id;}
deba@353
   405
      bool operator<(const Arc arc) const {return _id < arc._id;}
deba@353
   406
    };
deba@353
   407
deba@353
   408
    static bool direction(Arc arc) {
deba@353
   409
      return (arc._id & 1) == 1;
deba@353
   410
    }
deba@353
   411
deba@353
   412
    static Arc direct(Edge edge, bool dir) {
deba@353
   413
      return Arc((edge._id << 1) | (dir ? 1 : 0));
deba@353
   414
    }
deba@353
   415
deba@353
   416
    void first(Node& node) const {
deba@353
   417
      node._id = _node_num - 1;
deba@353
   418
    }
deba@353
   419
deba@353
   420
    static void next(Node& node) {
deba@353
   421
      --node._id;
deba@353
   422
    }
deba@353
   423
deba@353
   424
    void first(Arc& arc) const {
deba@353
   425
      arc._id = (_edge_num << 1) - 1;
deba@353
   426
    }
deba@353
   427
deba@353
   428
    static void next(Arc& arc) {
deba@353
   429
      --arc._id;
deba@353
   430
    }
deba@353
   431
deba@353
   432
    void first(Edge& edge) const {
deba@353
   433
      edge._id = _edge_num - 1;
deba@353
   434
    }
deba@353
   435
deba@353
   436
    static void next(Edge& edge) {
deba@353
   437
      --edge._id;
deba@353
   438
    }
deba@353
   439
deba@353
   440
    void firstOut(Arc& arc, const Node& node) const {
deba@353
   441
      int s = node._id, t = _node_num - 1;
deba@353
   442
      if (s < t) {
deba@353
   443
        arc._id = (_eid(s, t) << 1) | 1;
deba@353
   444
      } else {
deba@353
   445
        --t;
deba@353
   446
        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
deba@353
   447
      }
deba@353
   448
    }
deba@353
   449
deba@353
   450
    void nextOut(Arc& arc) const {
deba@353
   451
      int s, t;
deba@353
   452
      _stid(arc._id, s, t);
deba@353
   453
      --t;
deba@353
   454
      if (s < t) {
deba@353
   455
        arc._id = (_eid(s, t) << 1) | 1;
deba@353
   456
      } else {
deba@353
   457
        if (s == t) --t;
deba@353
   458
        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
deba@353
   459
      }
deba@353
   460
    }
deba@353
   461
deba@353
   462
    void firstIn(Arc& arc, const Node& node) const {
deba@353
   463
      int s = _node_num - 1, t = node._id;
deba@353
   464
      if (s > t) {
deba@353
   465
        arc._id = (_eid(t, s) << 1);
deba@353
   466
      } else {
deba@353
   467
        --s;
deba@353
   468
        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
deba@353
   469
      }
deba@353
   470
    }
deba@353
   471
deba@353
   472
    void nextIn(Arc& arc) const {
deba@353
   473
      int s, t;
deba@353
   474
      _stid(arc._id, s, t);
deba@353
   475
      --s;
deba@353
   476
      if (s > t) {
deba@353
   477
        arc._id = (_eid(t, s) << 1);
deba@353
   478
      } else {
deba@353
   479
        if (s == t) --s;
deba@353
   480
        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
deba@353
   481
      }
deba@353
   482
    }
deba@353
   483
deba@353
   484
    void firstInc(Edge& edge, bool& dir, const Node& node) const {
deba@353
   485
      int u = node._id, v = _node_num - 1;
deba@353
   486
      if (u < v) {
deba@353
   487
        edge._id = _eid(u, v);
deba@353
   488
        dir = true;
deba@353
   489
      } else {
deba@353
   490
        --v;
deba@353
   491
        edge._id = (v != -1 ? _eid(v, u) : -1);
deba@353
   492
        dir = false;
deba@353
   493
      }
deba@353
   494
    }
deba@353
   495
deba@353
   496
    void nextInc(Edge& edge, bool& dir) const {
deba@353
   497
      int u, v;
deba@353
   498
      if (dir) {
deba@353
   499
        _uvid(edge._id, u, v);
deba@353
   500
        --v;
deba@353
   501
        if (u < v) {
deba@353
   502
          edge._id = _eid(u, v);
deba@353
   503
        } else {
deba@353
   504
          --v;
deba@353
   505
          edge._id = (v != -1 ? _eid(v, u) : -1);
deba@353
   506
          dir = false;
deba@353
   507
        }
deba@353
   508
      } else {
deba@353
   509
        _uvid(edge._id, v, u);
deba@353
   510
        --v;
deba@353
   511
        edge._id = (v != -1 ? _eid(v, u) : -1);
deba@353
   512
      }
deba@353
   513
    }
deba@353
   514
deba@353
   515
  };
deba@353
   516
deba@353
   517
  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
deba@353
   518
deba@353
   519
  /// \ingroup graphs
deba@353
   520
  ///
deba@353
   521
  /// \brief An undirected full graph class.
deba@353
   522
  ///
deba@353
   523
  /// This is a simple and fast undirected full graph
deba@353
   524
  /// implementation. From each node go edge to each other node,
kpeter@354
   525
  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
kpeter@354
   526
  /// This graph type is completely static, so you can neither
kpeter@354
   527
  /// add nor delete either edges or nodes, and it needs constant
deba@353
   528
  /// space in memory.
deba@353
   529
  ///
kpeter@354
   530
  /// This class conforms to the \ref concepts::Graph "Graph" concept
kpeter@354
   531
  /// and it also has an important extra feature that its maps are
kpeter@354
   532
  /// real \ref concepts::ReferenceMap "reference map"s.
deba@353
   533
  ///
kpeter@354
   534
  /// The \c FullGraph and \c FullDigraph classes are very similar,
kpeter@354
   535
  /// but there are two differences. While the \c FullDigraph class
kpeter@354
   536
  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
kpeter@354
   537
  /// this class conforms to the \ref concepts::Graph "Graph" concept,
kpeter@354
   538
  /// moreover \c FullGraph does not contain a loop arc for each
kpeter@354
   539
  /// node as \c FullDigraph does.
deba@353
   540
  ///
deba@353
   541
  /// \sa FullDigraph
deba@353
   542
  class FullGraph : public ExtendedFullGraphBase {
deba@353
   543
  public:
deba@353
   544
deba@353
   545
    typedef ExtendedFullGraphBase Parent;
deba@353
   546
deba@353
   547
    /// \brief Constructor
deba@353
   548
    FullGraph() { construct(0); }
deba@353
   549
deba@353
   550
    /// \brief Constructor
deba@353
   551
    ///
kpeter@354
   552
    /// Constructor.
deba@353
   553
    /// \param n The number of the nodes.
deba@353
   554
    FullGraph(int n) { construct(n); }
deba@353
   555
kpeter@354
   556
    /// \brief Resizes the graph
deba@353
   557
    ///
kpeter@354
   558
    /// Resizes the graph. The function will fully destroy and
kpeter@354
   559
    /// rebuild the graph. This cause that the maps of the graph will
kpeter@354
   560
    /// reallocated automatically and the previous values will be lost.
deba@353
   561
    void resize(int n) {
deba@353
   562
      Parent::notifier(Arc()).clear();
deba@353
   563
      Parent::notifier(Edge()).clear();
deba@353
   564
      Parent::notifier(Node()).clear();
deba@353
   565
      construct(n);
deba@353
   566
      Parent::notifier(Node()).build();
deba@353
   567
      Parent::notifier(Edge()).build();
deba@353
   568
      Parent::notifier(Arc()).build();
deba@353
   569
    }
deba@353
   570
deba@353
   571
    /// \brief Returns the node with the given index.
deba@353
   572
    ///
kpeter@354
   573
    /// Returns the node with the given index. Since it is a static
kpeter@354
   574
    /// graph its nodes can be indexed with integers from the range
kpeter@354
   575
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   576
    /// \sa index()
deba@353
   577
    Node operator()(int ix) const { return Parent::operator()(ix); }
deba@353
   578
kpeter@354
   579
    /// \brief Returns the index of the given node.
deba@353
   580
    ///
kpeter@354
   581
    /// Returns the index of the given node. Since it is a static
kpeter@354
   582
    /// graph its nodes can be indexed with integers from the range
kpeter@354
   583
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   584
    /// \sa operator()
deba@353
   585
    int index(const Node& node) const { return Parent::index(node); }
deba@353
   586
kpeter@354
   587
    /// \brief Returns the arc connecting the given nodes.
deba@353
   588
    ///
kpeter@354
   589
    /// Returns the arc connecting the given nodes.
deba@353
   590
    Arc arc(const Node& s, const Node& t) const {
deba@353
   591
      return Parent::arc(s, t);
deba@353
   592
    }
deba@353
   593
deba@353
   594
    /// \brief Returns the edge connects the given nodes.
deba@353
   595
    ///
deba@353
   596
    /// Returns the edge connects the given nodes.
deba@353
   597
    Edge edge(const Node& u, const Node& v) const {
deba@353
   598
      return Parent::edge(u, v);
deba@353
   599
    }
kpeter@354
   600
kpeter@354
   601
    /// \brief Number of nodes.
kpeter@354
   602
    int nodeNum() const { return Parent::nodeNum(); }
kpeter@354
   603
    /// \brief Number of arcs.
kpeter@354
   604
    int arcNum() const { return Parent::arcNum(); }
kpeter@354
   605
    /// \brief Number of edges.
kpeter@354
   606
    int edgeNum() const { return Parent::edgeNum(); }
kpeter@354
   607
deba@353
   608
  };
deba@353
   609
deba@353
   610
deba@353
   611
} //namespace lemon
deba@353
   612
deba@353
   613
deba@353
   614
#endif //LEMON_FULL_GRAPH_H