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