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