lemon/full_graph.h
author Akos Ladanyi <ladanyi@tmit.bme.hu>
Thu, 23 Apr 2009 07:30:40 +0100
changeset 621 b536eaacb39b
parent 440 88ed40ad0d4f
child 617 4137ef9aacc6
permissions -rw-r--r--
FindCOIN for CMake (#256)
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
 *
alpar@440
     5
 * Copyright (C) 2003-2009
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@582
   160
  /// This class fully conforms to the \ref concepts::Digraph
kpeter@582
   161
  /// "Digraph concept".
kpeter@354
   162
  ///
kpeter@354
   163
  /// The \c FullDigraph and \c FullGraph classes are very similar,
kpeter@354
   164
  /// but there are two differences. While this class conforms only
kpeter@354
   165
  /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph
kpeter@354
   166
  /// class conforms to the \ref concepts::Graph "Graph" concept,
kpeter@354
   167
  /// moreover \c FullGraph does not contain a loop arc for each
kpeter@354
   168
  /// node as \c FullDigraph does.
deba@353
   169
  ///
deba@353
   170
  /// \sa FullGraph
deba@353
   171
  class FullDigraph : public ExtendedFullDigraphBase {
deba@353
   172
  public:
deba@353
   173
deba@353
   174
    typedef ExtendedFullDigraphBase Parent;
deba@353
   175
deba@353
   176
    /// \brief Constructor
deba@353
   177
    FullDigraph() { construct(0); }
deba@353
   178
deba@353
   179
    /// \brief Constructor
deba@353
   180
    ///
kpeter@354
   181
    /// Constructor.
deba@353
   182
    /// \param n The number of the nodes.
deba@353
   183
    FullDigraph(int n) { construct(n); }
deba@353
   184
kpeter@354
   185
    /// \brief Resizes the digraph
deba@353
   186
    ///
kpeter@354
   187
    /// Resizes the digraph. The function will fully destroy and
kpeter@354
   188
    /// rebuild the digraph. This cause that the maps of the digraph will
kpeter@354
   189
    /// reallocated automatically and the previous values will be lost.
deba@353
   190
    void resize(int n) {
deba@353
   191
      Parent::notifier(Arc()).clear();
deba@353
   192
      Parent::notifier(Node()).clear();
deba@353
   193
      construct(n);
deba@353
   194
      Parent::notifier(Node()).build();
deba@353
   195
      Parent::notifier(Arc()).build();
deba@353
   196
    }
deba@353
   197
deba@353
   198
    /// \brief Returns the node with the given index.
deba@353
   199
    ///
kpeter@354
   200
    /// Returns the node with the given index. Since it is a static
kpeter@354
   201
    /// digraph its nodes can be indexed with integers from the range
kpeter@354
   202
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   203
    /// \sa index()
deba@353
   204
    Node operator()(int ix) const { return Parent::operator()(ix); }
deba@353
   205
kpeter@354
   206
    /// \brief Returns the index of the given node.
deba@353
   207
    ///
kpeter@354
   208
    /// Returns the index of the given node. Since it is a static
kpeter@354
   209
    /// digraph its nodes can be indexed with integers from the range
kpeter@354
   210
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   211
    /// \sa operator()
deba@353
   212
    int index(const Node& node) const { return Parent::index(node); }
deba@353
   213
kpeter@354
   214
    /// \brief Returns the arc connecting the given nodes.
deba@353
   215
    ///
kpeter@354
   216
    /// Returns the arc connecting the given nodes.
deba@353
   217
    Arc arc(const Node& u, const Node& v) const {
deba@353
   218
      return Parent::arc(u, v);
deba@353
   219
    }
deba@353
   220
deba@353
   221
    /// \brief Number of nodes.
deba@353
   222
    int nodeNum() const { return Parent::nodeNum(); }
deba@353
   223
    /// \brief Number of arcs.
deba@353
   224
    int arcNum() const { return Parent::arcNum(); }
deba@353
   225
  };
deba@353
   226
deba@353
   227
deba@353
   228
  class FullGraphBase {
deba@353
   229
    int _node_num;
deba@353
   230
    int _edge_num;
deba@353
   231
  public:
deba@353
   232
deba@353
   233
    typedef FullGraphBase Graph;
deba@353
   234
deba@353
   235
    class Node;
deba@353
   236
    class Arc;
deba@353
   237
    class Edge;
deba@353
   238
deba@353
   239
  protected:
deba@353
   240
deba@353
   241
    FullGraphBase() {}
deba@353
   242
deba@353
   243
    void construct(int n) { _node_num = n; _edge_num = n * (n - 1) / 2; }
deba@353
   244
deba@353
   245
    int _uid(int e) const {
deba@353
   246
      int u = e / _node_num;
deba@353
   247
      int v = e % _node_num;
deba@353
   248
      return u < v ? u : _node_num - 2 - u;
deba@353
   249
    }
deba@353
   250
deba@353
   251
    int _vid(int e) const {
deba@353
   252
      int u = e / _node_num;
deba@353
   253
      int v = e % _node_num;
deba@353
   254
      return u < v ? v : _node_num - 1 - v;
deba@353
   255
    }
deba@353
   256
deba@353
   257
    void _uvid(int e, int& u, int& v) const {
deba@353
   258
      u = e / _node_num;
deba@353
   259
      v = e % _node_num;
deba@353
   260
      if  (u >= v) {
deba@353
   261
        u = _node_num - 2 - u;
deba@353
   262
        v = _node_num - 1 - v;
deba@353
   263
      }
deba@353
   264
    }
deba@353
   265
deba@353
   266
    void _stid(int a, int& s, int& t) const {
deba@353
   267
      if ((a & 1) == 1) {
deba@353
   268
        _uvid(a >> 1, s, t);
deba@353
   269
      } else {
deba@353
   270
        _uvid(a >> 1, t, s);
deba@353
   271
      }
deba@353
   272
    }
deba@353
   273
deba@353
   274
    int _eid(int u, int v) const {
deba@353
   275
      if (u < (_node_num - 1) / 2) {
deba@353
   276
        return u * _node_num + v;
deba@353
   277
      } else {
deba@353
   278
        return (_node_num - 1 - u) * _node_num - v - 1;
deba@353
   279
      }
deba@353
   280
    }
deba@353
   281
deba@353
   282
  public:
deba@353
   283
deba@353
   284
    Node operator()(int ix) const { return Node(ix); }
deba@353
   285
    int index(const Node& node) const { return node._id; }
deba@353
   286
deba@353
   287
    Edge edge(const Node& u, const Node& v) const {
deba@353
   288
      if (u._id < v._id) {
deba@353
   289
        return Edge(_eid(u._id, v._id));
deba@353
   290
      } else if (u._id != v._id) {
deba@353
   291
        return Edge(_eid(v._id, u._id));
deba@353
   292
      } else {
deba@353
   293
        return INVALID;
deba@353
   294
      }
deba@353
   295
    }
deba@353
   296
deba@353
   297
    Arc arc(const Node& s, const Node& t) const {
deba@353
   298
      if (s._id < t._id) {
deba@353
   299
        return Arc((_eid(s._id, t._id) << 1) | 1);
deba@353
   300
      } else if (s._id != t._id) {
deba@353
   301
        return Arc(_eid(t._id, s._id) << 1);
deba@353
   302
      } else {
deba@353
   303
        return INVALID;
deba@353
   304
      }
deba@353
   305
    }
deba@353
   306
deba@353
   307
    typedef True NodeNumTag;
kpeter@360
   308
    typedef True ArcNumTag;
deba@353
   309
    typedef True EdgeNumTag;
deba@353
   310
deba@353
   311
    int nodeNum() const { return _node_num; }
deba@353
   312
    int arcNum() const { return 2 * _edge_num; }
deba@353
   313
    int edgeNum() const { return _edge_num; }
deba@353
   314
deba@353
   315
    static int id(Node node) { return node._id; }
deba@353
   316
    static int id(Arc arc) { return arc._id; }
deba@353
   317
    static int id(Edge edge) { return edge._id; }
deba@353
   318
deba@353
   319
    int maxNodeId() const { return _node_num-1; }
deba@353
   320
    int maxArcId() const { return 2 * _edge_num-1; }
deba@353
   321
    int maxEdgeId() const { return _edge_num-1; }
deba@353
   322
deba@353
   323
    static Node nodeFromId(int id) { return Node(id);}
deba@353
   324
    static Arc arcFromId(int id) { return Arc(id);}
deba@353
   325
    static Edge edgeFromId(int id) { return Edge(id);}
deba@353
   326
deba@353
   327
    Node u(Edge edge) const {
deba@353
   328
      return Node(_uid(edge._id));
deba@353
   329
    }
deba@353
   330
deba@353
   331
    Node v(Edge edge) const {
deba@353
   332
      return Node(_vid(edge._id));
deba@353
   333
    }
deba@353
   334
deba@353
   335
    Node source(Arc arc) const {
deba@353
   336
      return Node((arc._id & 1) == 1 ?
deba@353
   337
                  _uid(arc._id >> 1) : _vid(arc._id >> 1));
deba@353
   338
    }
deba@353
   339
deba@353
   340
    Node target(Arc arc) const {
deba@353
   341
      return Node((arc._id & 1) == 1 ?
deba@353
   342
                  _vid(arc._id >> 1) : _uid(arc._id >> 1));
deba@353
   343
    }
deba@353
   344
deba@353
   345
    typedef True FindEdgeTag;
kpeter@360
   346
    typedef True FindArcTag;
deba@353
   347
deba@353
   348
    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
deba@353
   349
      return prev != INVALID ? INVALID : edge(u, v);
deba@353
   350
    }
deba@353
   351
deba@353
   352
    Arc findArc(Node s, Node t, Arc prev = INVALID) const {
deba@353
   353
      return prev != INVALID ? INVALID : arc(s, t);
deba@353
   354
    }
deba@353
   355
deba@353
   356
    class Node {
deba@353
   357
      friend class FullGraphBase;
deba@353
   358
deba@353
   359
    protected:
deba@353
   360
      int _id;
deba@353
   361
      Node(int id) : _id(id) {}
deba@353
   362
    public:
deba@353
   363
      Node() {}
deba@353
   364
      Node (Invalid) { _id = -1; }
deba@353
   365
      bool operator==(const Node node) const {return _id == node._id;}
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
    };
deba@353
   369
deba@353
   370
    class Edge {
deba@353
   371
      friend class FullGraphBase;
kpeter@354
   372
      friend class Arc;
deba@353
   373
deba@353
   374
    protected:
deba@353
   375
      int _id;
deba@353
   376
deba@353
   377
      Edge(int id) : _id(id) {}
deba@353
   378
deba@353
   379
    public:
deba@353
   380
      Edge() { }
deba@353
   381
      Edge (Invalid) { _id = -1; }
deba@353
   382
deba@353
   383
      bool operator==(const Edge edge) const {return _id == edge._id;}
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
    };
deba@353
   387
deba@353
   388
    class Arc {
deba@353
   389
      friend class FullGraphBase;
deba@353
   390
deba@353
   391
    protected:
deba@353
   392
      int _id;
deba@353
   393
deba@353
   394
      Arc(int id) : _id(id) {}
deba@353
   395
deba@353
   396
    public:
deba@353
   397
      Arc() { }
deba@353
   398
      Arc (Invalid) { _id = -1; }
deba@353
   399
deba@353
   400
      operator Edge() const { return Edge(_id != -1 ? (_id >> 1) : -1); }
deba@353
   401
deba@353
   402
      bool operator==(const Arc arc) const {return _id == arc._id;}
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
    };
deba@353
   406
deba@353
   407
    static bool direction(Arc arc) {
deba@353
   408
      return (arc._id & 1) == 1;
deba@353
   409
    }
deba@353
   410
deba@353
   411
    static Arc direct(Edge edge, bool dir) {
deba@353
   412
      return Arc((edge._id << 1) | (dir ? 1 : 0));
deba@353
   413
    }
deba@353
   414
deba@353
   415
    void first(Node& node) const {
deba@353
   416
      node._id = _node_num - 1;
deba@353
   417
    }
deba@353
   418
deba@353
   419
    static void next(Node& node) {
deba@353
   420
      --node._id;
deba@353
   421
    }
deba@353
   422
deba@353
   423
    void first(Arc& arc) const {
deba@353
   424
      arc._id = (_edge_num << 1) - 1;
deba@353
   425
    }
deba@353
   426
deba@353
   427
    static void next(Arc& arc) {
deba@353
   428
      --arc._id;
deba@353
   429
    }
deba@353
   430
deba@353
   431
    void first(Edge& edge) const {
deba@353
   432
      edge._id = _edge_num - 1;
deba@353
   433
    }
deba@353
   434
deba@353
   435
    static void next(Edge& edge) {
deba@353
   436
      --edge._id;
deba@353
   437
    }
deba@353
   438
deba@353
   439
    void firstOut(Arc& arc, const Node& node) const {
deba@353
   440
      int s = node._id, t = _node_num - 1;
deba@353
   441
      if (s < t) {
deba@353
   442
        arc._id = (_eid(s, t) << 1) | 1;
deba@353
   443
      } else {
deba@353
   444
        --t;
deba@353
   445
        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
deba@353
   446
      }
deba@353
   447
    }
deba@353
   448
deba@353
   449
    void nextOut(Arc& arc) const {
deba@353
   450
      int s, t;
deba@353
   451
      _stid(arc._id, s, t);
deba@353
   452
      --t;
deba@353
   453
      if (s < t) {
deba@353
   454
        arc._id = (_eid(s, t) << 1) | 1;
deba@353
   455
      } else {
deba@353
   456
        if (s == t) --t;
deba@353
   457
        arc._id = (t != -1 ? (_eid(t, s) << 1) : -1);
deba@353
   458
      }
deba@353
   459
    }
deba@353
   460
deba@353
   461
    void firstIn(Arc& arc, const Node& node) const {
deba@353
   462
      int s = _node_num - 1, t = node._id;
deba@353
   463
      if (s > t) {
deba@353
   464
        arc._id = (_eid(t, s) << 1);
deba@353
   465
      } else {
deba@353
   466
        --s;
deba@353
   467
        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
deba@353
   468
      }
deba@353
   469
    }
deba@353
   470
deba@353
   471
    void nextIn(Arc& arc) const {
deba@353
   472
      int s, t;
deba@353
   473
      _stid(arc._id, s, t);
deba@353
   474
      --s;
deba@353
   475
      if (s > t) {
deba@353
   476
        arc._id = (_eid(t, s) << 1);
deba@353
   477
      } else {
deba@353
   478
        if (s == t) --s;
deba@353
   479
        arc._id = (s != -1 ? (_eid(s, t) << 1) | 1 : -1);
deba@353
   480
      }
deba@353
   481
    }
deba@353
   482
deba@353
   483
    void firstInc(Edge& edge, bool& dir, const Node& node) const {
deba@353
   484
      int u = node._id, v = _node_num - 1;
deba@353
   485
      if (u < v) {
deba@353
   486
        edge._id = _eid(u, v);
deba@353
   487
        dir = true;
deba@353
   488
      } else {
deba@353
   489
        --v;
deba@353
   490
        edge._id = (v != -1 ? _eid(v, u) : -1);
deba@353
   491
        dir = false;
deba@353
   492
      }
deba@353
   493
    }
deba@353
   494
deba@353
   495
    void nextInc(Edge& edge, bool& dir) const {
deba@353
   496
      int u, v;
deba@353
   497
      if (dir) {
deba@353
   498
        _uvid(edge._id, u, v);
deba@353
   499
        --v;
deba@353
   500
        if (u < v) {
deba@353
   501
          edge._id = _eid(u, v);
deba@353
   502
        } else {
deba@353
   503
          --v;
deba@353
   504
          edge._id = (v != -1 ? _eid(v, u) : -1);
deba@353
   505
          dir = false;
deba@353
   506
        }
deba@353
   507
      } else {
deba@353
   508
        _uvid(edge._id, v, u);
deba@353
   509
        --v;
deba@353
   510
        edge._id = (v != -1 ? _eid(v, u) : -1);
deba@353
   511
      }
deba@353
   512
    }
deba@353
   513
deba@353
   514
  };
deba@353
   515
deba@353
   516
  typedef GraphExtender<FullGraphBase> ExtendedFullGraphBase;
deba@353
   517
deba@353
   518
  /// \ingroup graphs
deba@353
   519
  ///
deba@353
   520
  /// \brief An undirected full graph class.
deba@353
   521
  ///
deba@353
   522
  /// This is a simple and fast undirected full graph
deba@353
   523
  /// implementation. From each node go edge to each other node,
kpeter@354
   524
  /// therefore the number of edges in the graph is \f$n(n-1)/2\f$.
kpeter@354
   525
  /// This graph type is completely static, so you can neither
kpeter@354
   526
  /// add nor delete either edges or nodes, and it needs constant
deba@353
   527
  /// space in memory.
deba@353
   528
  ///
kpeter@582
   529
  /// This class fully conforms to the \ref concepts::Graph "Graph concept".
deba@353
   530
  ///
kpeter@354
   531
  /// The \c FullGraph and \c FullDigraph classes are very similar,
kpeter@354
   532
  /// but there are two differences. While the \c FullDigraph class
kpeter@354
   533
  /// conforms only to the \ref concepts::Digraph "Digraph" concept,
kpeter@354
   534
  /// this class conforms to the \ref concepts::Graph "Graph" concept,
kpeter@354
   535
  /// moreover \c FullGraph does not contain a loop arc for each
kpeter@354
   536
  /// node as \c FullDigraph does.
deba@353
   537
  ///
deba@353
   538
  /// \sa FullDigraph
deba@353
   539
  class FullGraph : public ExtendedFullGraphBase {
deba@353
   540
  public:
deba@353
   541
deba@353
   542
    typedef ExtendedFullGraphBase Parent;
deba@353
   543
deba@353
   544
    /// \brief Constructor
deba@353
   545
    FullGraph() { construct(0); }
deba@353
   546
deba@353
   547
    /// \brief Constructor
deba@353
   548
    ///
kpeter@354
   549
    /// Constructor.
deba@353
   550
    /// \param n The number of the nodes.
deba@353
   551
    FullGraph(int n) { construct(n); }
deba@353
   552
kpeter@354
   553
    /// \brief Resizes the graph
deba@353
   554
    ///
kpeter@354
   555
    /// Resizes the graph. The function will fully destroy and
kpeter@354
   556
    /// rebuild the graph. This cause that the maps of the graph will
kpeter@354
   557
    /// reallocated automatically and the previous values will be lost.
deba@353
   558
    void resize(int n) {
deba@353
   559
      Parent::notifier(Arc()).clear();
deba@353
   560
      Parent::notifier(Edge()).clear();
deba@353
   561
      Parent::notifier(Node()).clear();
deba@353
   562
      construct(n);
deba@353
   563
      Parent::notifier(Node()).build();
deba@353
   564
      Parent::notifier(Edge()).build();
deba@353
   565
      Parent::notifier(Arc()).build();
deba@353
   566
    }
deba@353
   567
deba@353
   568
    /// \brief Returns the node with the given index.
deba@353
   569
    ///
kpeter@354
   570
    /// Returns the node with the given index. Since it is a static
kpeter@354
   571
    /// graph its nodes can be indexed with integers from the range
kpeter@354
   572
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   573
    /// \sa index()
deba@353
   574
    Node operator()(int ix) const { return Parent::operator()(ix); }
deba@353
   575
kpeter@354
   576
    /// \brief Returns the index of the given node.
deba@353
   577
    ///
kpeter@354
   578
    /// Returns the index of the given node. Since it is a static
kpeter@354
   579
    /// graph its nodes can be indexed with integers from the range
kpeter@354
   580
    /// <tt>[0..nodeNum()-1]</tt>.
kpeter@354
   581
    /// \sa operator()
deba@353
   582
    int index(const Node& node) const { return Parent::index(node); }
deba@353
   583
kpeter@354
   584
    /// \brief Returns the arc connecting the given nodes.
deba@353
   585
    ///
kpeter@354
   586
    /// Returns the arc connecting the given nodes.
deba@353
   587
    Arc arc(const Node& s, const Node& t) const {
deba@353
   588
      return Parent::arc(s, t);
deba@353
   589
    }
deba@353
   590
deba@353
   591
    /// \brief Returns the edge connects the given nodes.
deba@353
   592
    ///
deba@353
   593
    /// Returns the edge connects the given nodes.
deba@353
   594
    Edge edge(const Node& u, const Node& v) const {
deba@353
   595
      return Parent::edge(u, v);
deba@353
   596
    }
kpeter@354
   597
kpeter@354
   598
    /// \brief Number of nodes.
kpeter@354
   599
    int nodeNum() const { return Parent::nodeNum(); }
kpeter@354
   600
    /// \brief Number of arcs.
kpeter@354
   601
    int arcNum() const { return Parent::arcNum(); }
kpeter@354
   602
    /// \brief Number of edges.
kpeter@354
   603
    int edgeNum() const { return Parent::edgeNum(); }
kpeter@354
   604
deba@353
   605
  };
deba@353
   606
deba@353
   607
deba@353
   608
} //namespace lemon
deba@353
   609
deba@353
   610
deba@353
   611
#endif //LEMON_FULL_GRAPH_H