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