lemon/grid_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 04 Nov 2008 10:21:22 +0000
changeset 356 99f1bdf8f7db
parent 336 052cecabcb71
child 360 75cf49ce5390
permissions -rw-r--r--
Merge
kpeter@334
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@334
     2
 *
kpeter@334
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@334
     4
 *
kpeter@334
     5
 * Copyright (C) 2003-2008
kpeter@334
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@334
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@334
     8
 *
kpeter@334
     9
 * Permission to use, modify and distribute this software is granted
kpeter@334
    10
 * provided that this copyright notice appears in all copies. For
kpeter@334
    11
 * precise terms see the accompanying LICENSE file.
kpeter@334
    12
 *
kpeter@334
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@334
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@334
    15
 * purpose.
kpeter@334
    16
 *
kpeter@334
    17
 */
kpeter@334
    18
kpeter@334
    19
#ifndef GRID_GRAPH_H
kpeter@334
    20
#define GRID_GRAPH_H
kpeter@334
    21
kpeter@334
    22
#include <lemon/core.h>
deba@335
    23
#include <lemon/bits/graph_extender.h>
deba@335
    24
#include <lemon/dim2.h>
kpeter@334
    25
#include <lemon/assert.h>
kpeter@334
    26
kpeter@334
    27
///\ingroup graphs
kpeter@334
    28
///\file
kpeter@334
    29
///\brief GridGraph class.
kpeter@334
    30
kpeter@334
    31
namespace lemon {
kpeter@334
    32
kpeter@334
    33
  class GridGraphBase {
kpeter@334
    34
kpeter@334
    35
  public:
kpeter@334
    36
kpeter@334
    37
    typedef GridGraphBase Graph;
kpeter@334
    38
kpeter@334
    39
    class Node;
deba@335
    40
    class Edge;
kpeter@334
    41
    class Arc;
kpeter@334
    42
kpeter@334
    43
  public:
kpeter@334
    44
kpeter@334
    45
    GridGraphBase() {}
kpeter@334
    46
kpeter@334
    47
  protected:
kpeter@334
    48
deba@335
    49
    void construct(int width, int height) {
deba@335
    50
       _width = width; _height = height;
deba@335
    51
      _node_num = width * height;
deba@335
    52
      _edge_num = 2 * _node_num - width - height;
deba@335
    53
      _edge_limit = _node_num - _width;
kpeter@334
    54
    }
kpeter@334
    55
kpeter@334
    56
  public:
kpeter@334
    57
kpeter@334
    58
    Node operator()(int i, int j) const {
deba@335
    59
      LEMON_DEBUG(0 <= i && i < _width &&
deba@335
    60
                  0 <= j  && j < _height, "Index out of range");
kpeter@334
    61
      return Node(i + j * _width);
kpeter@334
    62
    }
kpeter@334
    63
deba@335
    64
    int col(Node n) const {
deba@335
    65
      return n._id % _width;
kpeter@334
    66
    }
kpeter@334
    67
deba@335
    68
    int row(Node n) const {
deba@335
    69
      return n._id / _width;
deba@335
    70
    }
deba@335
    71
deba@335
    72
    dim2::Point<int> pos(Node n) const {
deba@335
    73
      return dim2::Point<int>(col(n), row(n));
kpeter@334
    74
    }
kpeter@334
    75
kpeter@334
    76
    int width() const {
kpeter@334
    77
      return _width;
kpeter@334
    78
    }
kpeter@334
    79
kpeter@334
    80
    int height() const {
kpeter@334
    81
      return _height;
kpeter@334
    82
    }
kpeter@334
    83
kpeter@334
    84
    typedef True NodeNumTag;
kpeter@334
    85
    typedef True ArcNumTag;
kpeter@334
    86
deba@335
    87
    int nodeNum() const { return _node_num; }
deba@335
    88
    int edgeNum() const { return _edge_num; }
deba@335
    89
    int arcNum() const { return 2 * _edge_num; }
kpeter@334
    90
deba@335
    91
    Node u(Edge edge) const {
deba@335
    92
      if (edge._id < _edge_limit) {
deba@335
    93
        return edge._id;
kpeter@334
    94
      } else {
deba@335
    95
        return (edge._id - _edge_limit) % (_width - 1) +
deba@335
    96
          (edge._id - _edge_limit) / (_width - 1) * _width;
kpeter@334
    97
      }
kpeter@334
    98
    }
kpeter@334
    99
deba@335
   100
    Node v(Edge edge) const {
deba@335
   101
      if (edge._id < _edge_limit) {
deba@335
   102
        return edge._id + _width;
kpeter@334
   103
      } else {
deba@335
   104
        return (edge._id - _edge_limit) % (_width - 1) +
deba@335
   105
          (edge._id - _edge_limit) / (_width - 1) * _width + 1;
kpeter@334
   106
      }
kpeter@334
   107
    }
kpeter@334
   108
deba@335
   109
    Node source(Arc arc) const {
deba@335
   110
      return (arc._id & 1) == 1 ? u(arc) : v(arc);
deba@335
   111
    }
deba@335
   112
deba@335
   113
    Node target(Arc arc) const {
deba@335
   114
      return (arc._id & 1) == 1 ? v(arc) : u(arc);
deba@335
   115
    }
deba@335
   116
deba@335
   117
    static int id(Node node) { return node._id; }
deba@335
   118
    static int id(Edge edge) { return edge._id; }
deba@335
   119
    static int id(Arc arc) { return arc._id; }
deba@335
   120
deba@335
   121
    int maxNodeId() const { return _node_num - 1; }
deba@335
   122
    int maxEdgeId() const { return _edge_num - 1; }
deba@335
   123
    int maxArcId() const { return 2 * _edge_num - 1; }
kpeter@334
   124
kpeter@334
   125
    static Node nodeFromId(int id) { return Node(id);}
deba@335
   126
    static Edge edgeFromId(int id) { return Edge(id);}
kpeter@334
   127
    static Arc arcFromId(int id) { return Arc(id);}
kpeter@334
   128
deba@335
   129
    typedef True FindEdgeTag;
deba@335
   130
deba@335
   131
    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
deba@335
   132
      if (prev != INVALID) return INVALID;
deba@335
   133
      if (v._id > u._id) {
deba@335
   134
        if (v._id - u._id == _width)
deba@335
   135
          return Edge(u._id);
deba@335
   136
        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
deba@335
   137
          return Edge(u._id / _width * (_width - 1) +
deba@335
   138
                      u._id % _width + _edge_limit);
deba@335
   139
        }
deba@335
   140
      } else {
deba@335
   141
        if (u._id - v._id == _width)
deba@335
   142
          return Edge(v._id);
deba@335
   143
        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
deba@335
   144
          return Edge(v._id / _width * (_width - 1) +
deba@335
   145
                      v._id % _width + _edge_limit);
deba@335
   146
        }
deba@335
   147
      }
deba@335
   148
      return INVALID;
deba@335
   149
    }
kpeter@334
   150
kpeter@334
   151
    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
kpeter@334
   152
      if (prev != INVALID) return INVALID;
deba@335
   153
      if (v._id > u._id) {
deba@335
   154
        if (v._id - u._id == _width)
deba@335
   155
          return Arc((u._id << 1) | 1);
deba@335
   156
        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
deba@335
   157
          return Arc(((u._id / _width * (_width - 1) +
deba@335
   158
                       u._id % _width + _edge_limit) << 1) | 1);
deba@335
   159
        }
deba@335
   160
      } else {
deba@335
   161
        if (u._id - v._id == _width)
deba@335
   162
          return Arc(v._id << 1);
deba@335
   163
        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
deba@335
   164
          return Arc((v._id / _width * (_width - 1) +
deba@335
   165
                       v._id % _width + _edge_limit) << 1);
deba@335
   166
        }
kpeter@334
   167
      }
kpeter@334
   168
      return INVALID;
kpeter@334
   169
    }
kpeter@334
   170
kpeter@334
   171
    class Node {
kpeter@334
   172
      friend class GridGraphBase;
kpeter@334
   173
kpeter@334
   174
    protected:
deba@335
   175
      int _id;
deba@335
   176
      Node(int id) : _id(id) {}
kpeter@334
   177
    public:
kpeter@334
   178
      Node() {}
deba@335
   179
      Node (Invalid) : _id(-1) {}
deba@335
   180
      bool operator==(const Node node) const {return _id == node._id;}
deba@335
   181
      bool operator!=(const Node node) const {return _id != node._id;}
deba@335
   182
      bool operator<(const Node node) const {return _id < node._id;}
deba@335
   183
    };
deba@335
   184
deba@335
   185
    class Edge {
deba@335
   186
      friend class GridGraphBase;
kpeter@336
   187
      friend class Arc;
deba@335
   188
deba@335
   189
    protected:
deba@335
   190
      int _id;
deba@335
   191
deba@335
   192
      Edge(int id) : _id(id) {}
deba@335
   193
deba@335
   194
    public:
deba@335
   195
      Edge() {}
deba@335
   196
      Edge (Invalid) : _id(-1) {}
deba@335
   197
      bool operator==(const Edge edge) const {return _id == edge._id;}
deba@335
   198
      bool operator!=(const Edge edge) const {return _id != edge._id;}
deba@335
   199
      bool operator<(const Edge edge) const {return _id < edge._id;}
kpeter@334
   200
    };
kpeter@334
   201
kpeter@334
   202
    class Arc {
kpeter@334
   203
      friend class GridGraphBase;
kpeter@334
   204
kpeter@334
   205
    protected:
deba@335
   206
      int _id;
deba@335
   207
deba@335
   208
      Arc(int id) : _id(id) {}
deba@335
   209
kpeter@334
   210
    public:
kpeter@334
   211
      Arc() {}
deba@335
   212
      Arc (Invalid) : _id(-1) {}
deba@335
   213
      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
deba@335
   214
      bool operator==(const Arc arc) const {return _id == arc._id;}
deba@335
   215
      bool operator!=(const Arc arc) const {return _id != arc._id;}
deba@335
   216
      bool operator<(const Arc arc) const {return _id < arc._id;}
kpeter@334
   217
    };
kpeter@334
   218
deba@335
   219
    static bool direction(Arc arc) {
deba@335
   220
      return (arc._id & 1) == 1;
deba@335
   221
    }
deba@335
   222
deba@335
   223
    static Arc direct(Edge edge, bool dir) {
deba@335
   224
      return Arc((edge._id << 1) | (dir ? 1 : 0));
deba@335
   225
    }
deba@335
   226
kpeter@334
   227
    void first(Node& node) const {
deba@335
   228
      node._id = _node_num - 1;
kpeter@334
   229
    }
kpeter@334
   230
kpeter@334
   231
    static void next(Node& node) {
deba@335
   232
      --node._id;
deba@335
   233
    }
deba@335
   234
deba@335
   235
    void first(Edge& edge) const {
deba@335
   236
      edge._id = _edge_num - 1;
deba@335
   237
    }
deba@335
   238
deba@335
   239
    static void next(Edge& edge) {
deba@335
   240
      --edge._id;
kpeter@334
   241
    }
kpeter@334
   242
kpeter@334
   243
    void first(Arc& arc) const {
deba@335
   244
      arc._id = 2 * _edge_num - 1;
kpeter@334
   245
    }
kpeter@334
   246
kpeter@334
   247
    static void next(Arc& arc) {
deba@335
   248
      --arc._id;
kpeter@334
   249
    }
kpeter@334
   250
kpeter@334
   251
    void firstOut(Arc& arc, const Node& node) const {
deba@335
   252
      if (node._id % _width < _width - 1) {
deba@335
   253
        arc._id = (_edge_limit + node._id % _width +
deba@335
   254
                   (node._id / _width) * (_width - 1)) << 1 | 1;
deba@335
   255
        return;
deba@335
   256
      }
deba@335
   257
      if (node._id < _node_num - _width) {
deba@335
   258
        arc._id = node._id << 1 | 1;
deba@335
   259
        return;
deba@335
   260
      }
deba@335
   261
      if (node._id % _width > 0) {
deba@335
   262
        arc._id = (_edge_limit + node._id % _width +
deba@335
   263
                   (node._id / _width) * (_width - 1) - 1) << 1;
deba@335
   264
        return;
deba@335
   265
      }
deba@335
   266
      if (node._id >= _width) {
deba@335
   267
        arc._id = (node._id - _width) << 1;
deba@335
   268
        return;
deba@335
   269
      }
deba@335
   270
      arc._id = -1;
deba@335
   271
    }
deba@335
   272
deba@335
   273
    void nextOut(Arc& arc) const {
deba@335
   274
      int nid = arc._id >> 1;
deba@335
   275
      if ((arc._id & 1) == 1) {
deba@335
   276
        if (nid >= _edge_limit) {
deba@335
   277
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   278
            (nid - _edge_limit) / (_width - 1) * _width;
deba@335
   279
          if (nid < _node_num - _width) {
deba@335
   280
            arc._id = nid << 1 | 1;
deba@335
   281
            return;
deba@335
   282
          }
deba@335
   283
        }
deba@335
   284
        if (nid % _width > 0) {
deba@335
   285
          arc._id = (_edge_limit + nid % _width +
deba@335
   286
                     (nid / _width) * (_width - 1) - 1) << 1;
deba@335
   287
          return;
deba@335
   288
        }
deba@335
   289
        if (nid >= _width) {
deba@335
   290
          arc._id = (nid - _width) << 1;
deba@335
   291
          return;
deba@335
   292
        }
kpeter@334
   293
      } else {
deba@335
   294
        if (nid >= _edge_limit) {
deba@335
   295
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   296
            (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@335
   297
          if (nid >= _width) {
deba@335
   298
            arc._id = (nid - _width) << 1;
deba@335
   299
            return;
deba@335
   300
          }
deba@335
   301
        }
deba@335
   302
      }
deba@335
   303
      arc._id = -1;
deba@335
   304
    }
deba@335
   305
deba@335
   306
    void firstIn(Arc& arc, const Node& node) const {
deba@335
   307
      if (node._id % _width < _width - 1) {
deba@335
   308
        arc._id = (_edge_limit + node._id % _width +
deba@335
   309
                   (node._id / _width) * (_width - 1)) << 1;
deba@335
   310
        return;
deba@335
   311
      }
deba@335
   312
      if (node._id < _node_num - _width) {
deba@335
   313
        arc._id = node._id << 1;
deba@335
   314
        return;
deba@335
   315
      }
deba@335
   316
      if (node._id % _width > 0) {
deba@335
   317
        arc._id = (_edge_limit + node._id % _width +
deba@335
   318
                   (node._id / _width) * (_width - 1) - 1) << 1 | 1;
deba@335
   319
        return;
deba@335
   320
      }
deba@335
   321
      if (node._id >= _width) {
deba@335
   322
        arc._id = (node._id - _width) << 1 | 1;
deba@335
   323
        return;
deba@335
   324
      }
deba@335
   325
      arc._id = -1;
deba@335
   326
    }
deba@335
   327
deba@335
   328
    void nextIn(Arc& arc) const {
deba@335
   329
      int nid = arc._id >> 1;
deba@335
   330
      if ((arc._id & 1) == 0) {
deba@335
   331
        if (nid >= _edge_limit) {
deba@335
   332
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   333
            (nid - _edge_limit) / (_width - 1) * _width;
deba@335
   334
          if (nid < _node_num - _width) {
deba@335
   335
            arc._id = nid << 1;
deba@335
   336
            return;
deba@335
   337
          }
deba@335
   338
        }
deba@335
   339
        if (nid % _width > 0) {
deba@335
   340
          arc._id = (_edge_limit + nid % _width +
deba@335
   341
                     (nid / _width) * (_width - 1) - 1) << 1 | 1;
deba@335
   342
          return;
deba@335
   343
        }
deba@335
   344
        if (nid >= _width) {
deba@335
   345
          arc._id = (nid - _width) << 1 | 1;
deba@335
   346
          return;
deba@335
   347
        }
deba@335
   348
      } else {
deba@335
   349
        if (nid >= _edge_limit) {
deba@335
   350
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   351
            (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@335
   352
          if (nid >= _width) {
deba@335
   353
            arc._id = (nid - _width) << 1 | 1;
deba@335
   354
            return;
deba@335
   355
          }
deba@335
   356
        }
deba@335
   357
      }
deba@335
   358
      arc._id = -1;
deba@335
   359
    }
deba@335
   360
deba@335
   361
    void firstInc(Edge& edge, bool& dir, const Node& node) const {
deba@335
   362
      if (node._id % _width < _width - 1) {
deba@335
   363
        edge._id = _edge_limit + node._id % _width +
deba@335
   364
          (node._id / _width) * (_width - 1);
deba@335
   365
        dir = true;
deba@335
   366
        return;
deba@335
   367
      }
deba@335
   368
      if (node._id < _node_num - _width) {
deba@335
   369
        edge._id = node._id;
deba@335
   370
        dir = true;
deba@335
   371
        return;
deba@335
   372
      }
deba@335
   373
      if (node._id % _width > 0) {
deba@335
   374
        edge._id = _edge_limit + node._id % _width +
deba@335
   375
          (node._id / _width) * (_width - 1) - 1;
deba@335
   376
        dir = false;
deba@335
   377
        return;
deba@335
   378
      }
deba@335
   379
      if (node._id >= _width) {
deba@335
   380
        edge._id = node._id - _width;
deba@335
   381
        dir = false;
deba@335
   382
        return;
deba@335
   383
      }
deba@335
   384
      edge._id = -1;
deba@335
   385
      dir = true;
deba@335
   386
    }
deba@335
   387
deba@335
   388
    void nextInc(Edge& edge, bool& dir) const {
deba@335
   389
      int nid = edge._id;
deba@335
   390
      if (dir) {
deba@335
   391
        if (nid >= _edge_limit) {
deba@335
   392
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   393
            (nid - _edge_limit) / (_width - 1) * _width;
deba@335
   394
          if (nid < _node_num - _width) {
deba@335
   395
            edge._id = nid;
deba@335
   396
            return;
deba@335
   397
          }
deba@335
   398
        }
deba@335
   399
        if (nid % _width > 0) {
deba@335
   400
          edge._id = _edge_limit + nid % _width +
deba@335
   401
            (nid / _width) * (_width - 1) - 1;
deba@335
   402
          dir = false;
deba@335
   403
          return;
deba@335
   404
        }
deba@335
   405
        if (nid >= _width) {
deba@335
   406
          edge._id = nid - _width;
deba@335
   407
          dir = false;
deba@335
   408
          return;
deba@335
   409
        }
deba@335
   410
      } else {
deba@335
   411
        if (nid >= _edge_limit) {
deba@335
   412
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   413
            (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@335
   414
          if (nid >= _width) {
deba@335
   415
            edge._id = nid - _width;
deba@335
   416
            return;
deba@335
   417
          }
deba@335
   418
        }
deba@335
   419
      }
deba@335
   420
      edge._id = -1;
deba@335
   421
      dir = true;
deba@335
   422
    }
deba@335
   423
deba@335
   424
    Arc right(Node n) const {
deba@335
   425
      if (n._id % _width < _width - 1) {
deba@335
   426
        return Arc(((_edge_limit + n._id % _width +
deba@335
   427
                    (n._id / _width) * (_width - 1)) << 1) | 1);
deba@335
   428
      } else {
deba@335
   429
        return INVALID;
kpeter@334
   430
      }
kpeter@334
   431
    }
kpeter@334
   432
deba@335
   433
    Arc left(Node n) const {
deba@335
   434
      if (n._id % _width > 0) {
deba@335
   435
        return Arc((_edge_limit + n._id % _width +
deba@335
   436
                     (n._id / _width) * (_width - 1) - 1) << 1);
kpeter@334
   437
      } else {
deba@335
   438
        return INVALID;
kpeter@334
   439
      }
kpeter@334
   440
    }
kpeter@334
   441
deba@335
   442
    Arc up(Node n) const {
deba@335
   443
      if (n._id < _edge_limit) {
deba@335
   444
        return Arc((n._id << 1) | 1);
kpeter@334
   445
      } else {
deba@335
   446
        return INVALID;
kpeter@334
   447
      }
kpeter@334
   448
    }
kpeter@334
   449
deba@335
   450
    Arc down(Node n) const {
deba@335
   451
      if (n._id >= _width) {
deba@335
   452
        return Arc((n._id - _width) << 1);
kpeter@334
   453
      } else {
deba@335
   454
        return INVALID;
kpeter@334
   455
      }
kpeter@334
   456
    }
kpeter@334
   457
kpeter@334
   458
  private:
kpeter@334
   459
    int _width, _height;
deba@335
   460
    int _node_num, _edge_num;
deba@335
   461
    int _edge_limit;
kpeter@334
   462
  };
kpeter@334
   463
deba@335
   464
deba@335
   465
  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
kpeter@334
   466
kpeter@334
   467
  /// \ingroup graphs
kpeter@334
   468
  ///
kpeter@334
   469
  /// \brief Grid graph class
kpeter@334
   470
  ///
kpeter@334
   471
  /// This class implements a special graph type. The nodes of the
deba@335
   472
  /// graph can be indexed by two integer \c (i,j) value where \c i is
deba@335
   473
  /// in the \c [0..width()-1] range and j is in the \c
deba@335
   474
  /// [0..height()-1] range.  Two nodes are connected in the graph if
deba@335
   475
  /// the indexes differ exactly on one position and exactly one is
kpeter@336
   476
  /// the difference. The nodes of the graph can be indexed by position
kpeter@336
   477
  /// with the \c operator()() function. The positions of the nodes can be
deba@335
   478
  /// get with \c pos(), \c col() and \c row() members. The outgoing
deba@335
   479
  /// arcs can be retrieved with the \c right(), \c up(), \c left()
deba@335
   480
  /// and \c down() functions, where the bottom-left corner is the
deba@335
   481
  /// origin.
kpeter@334
   482
  ///
kpeter@334
   483
  /// \image html grid_graph.png
deba@338
   484
  /// \image latex grid_graph.eps "Grid graph" width=\textwidth
kpeter@334
   485
  ///
deba@335
   486
  /// A short example about the basic usage:
kpeter@334
   487
  ///\code
deba@335
   488
  /// GridGraph graph(rows, cols);
deba@335
   489
  /// GridGraph::NodeMap<int> val(graph);
deba@335
   490
  /// for (int i = 0; i < graph.width(); ++i) {
deba@335
   491
  ///   for (int j = 0; j < graph.height(); ++j) {
deba@335
   492
  ///     val[graph(i, j)] = i + j;
kpeter@334
   493
  ///   }
kpeter@334
   494
  /// }
kpeter@334
   495
  ///\endcode
kpeter@334
   496
  ///
kpeter@336
   497
  /// This graph type is fully conform to the \ref concepts::Graph
deba@335
   498
  /// "Graph" concept, and it also has an important extra feature
kpeter@336
   499
  /// that its maps are real \ref concepts::ReferenceMap
kpeter@336
   500
  /// "reference map"s.
kpeter@334
   501
  class GridGraph : public ExtendedGridGraphBase {
kpeter@334
   502
  public:
kpeter@334
   503
kpeter@334
   504
    typedef ExtendedGridGraphBase Parent;
kpeter@334
   505
kpeter@334
   506
    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
kpeter@334
   507
    ///
kpeter@334
   508
    /// Map to get the indices of the nodes as dim2::Point<int>.
kpeter@334
   509
    class IndexMap {
kpeter@334
   510
    public:
deba@335
   511
      /// \brief The key type of the map
kpeter@334
   512
      typedef GridGraph::Node Key;
deba@335
   513
      /// \brief The value type of the map
kpeter@334
   514
      typedef dim2::Point<int> Value;
kpeter@334
   515
deba@335
   516
      /// \brief Constructor
deba@335
   517
      ///
kpeter@334
   518
      /// Constructor
kpeter@334
   519
      IndexMap(const GridGraph& graph) : _graph(graph) {}
kpeter@334
   520
deba@335
   521
      /// \brief The subscript operator
deba@335
   522
      ///
deba@335
   523
      /// The subscript operator.
deba@335
   524
      Value operator[](Key key) const {
deba@335
   525
        return _graph.pos(key);
deba@335
   526
      }
deba@335
   527
deba@335
   528
    private:
deba@335
   529
      const GridGraph& _graph;
deba@335
   530
    };
deba@335
   531
deba@335
   532
    /// \brief Map to get the column of the nodes.
deba@335
   533
    ///
deba@335
   534
    /// Map to get the column of the nodes.
deba@335
   535
    class ColMap {
deba@335
   536
    public:
deba@335
   537
      /// \brief The key type of the map
deba@335
   538
      typedef GridGraph::Node Key;
deba@335
   539
      /// \brief The value type of the map
deba@335
   540
      typedef int Value;
deba@335
   541
deba@335
   542
      /// \brief Constructor
deba@335
   543
      ///
deba@335
   544
      /// Constructor
deba@335
   545
      ColMap(const GridGraph& graph) : _graph(graph) {}
deba@335
   546
deba@335
   547
      /// \brief The subscript operator
deba@335
   548
      ///
deba@335
   549
      /// The subscript operator.
deba@335
   550
      Value operator[](Key key) const {
deba@335
   551
        return _graph.col(key);
kpeter@334
   552
      }
kpeter@334
   553
kpeter@334
   554
    private:
kpeter@334
   555
      const GridGraph& _graph;
kpeter@334
   556
    };
kpeter@334
   557
kpeter@334
   558
    /// \brief Map to get the row of the nodes.
kpeter@334
   559
    ///
kpeter@334
   560
    /// Map to get the row of the nodes.
kpeter@334
   561
    class RowMap {
kpeter@334
   562
    public:
deba@335
   563
      /// \brief The key type of the map
kpeter@334
   564
      typedef GridGraph::Node Key;
deba@335
   565
      /// \brief The value type of the map
kpeter@334
   566
      typedef int Value;
kpeter@334
   567
deba@335
   568
      /// \brief Constructor
deba@335
   569
      ///
kpeter@334
   570
      /// Constructor
kpeter@334
   571
      RowMap(const GridGraph& graph) : _graph(graph) {}
kpeter@334
   572
deba@335
   573
      /// \brief The subscript operator
deba@335
   574
      ///
deba@335
   575
      /// The subscript operator.
deba@335
   576
      Value operator[](Key key) const {
kpeter@334
   577
        return _graph.row(key);
kpeter@334
   578
      }
kpeter@334
   579
kpeter@334
   580
    private:
kpeter@334
   581
      const GridGraph& _graph;
kpeter@334
   582
    };
kpeter@334
   583
kpeter@334
   584
    /// \brief Constructor
kpeter@334
   585
    ///
deba@335
   586
    /// Construct a grid graph with given size.
kpeter@334
   587
    GridGraph(int width, int height) { construct(width, height); }
kpeter@334
   588
kpeter@334
   589
    /// \brief Resize the graph
kpeter@334
   590
    ///
deba@335
   591
    /// Resize the graph. The function will fully destroy and rebuild
deba@335
   592
    /// the graph.  This cause that the maps of the graph will
deba@335
   593
    /// reallocated automatically and the previous values will be
deba@335
   594
    /// lost.
kpeter@334
   595
    void resize(int width, int height) {
kpeter@334
   596
      Parent::notifier(Arc()).clear();
kpeter@334
   597
      Parent::notifier(Edge()).clear();
kpeter@334
   598
      Parent::notifier(Node()).clear();
kpeter@334
   599
      construct(width, height);
kpeter@334
   600
      Parent::notifier(Node()).build();
kpeter@334
   601
      Parent::notifier(Edge()).build();
kpeter@334
   602
      Parent::notifier(Arc()).build();
kpeter@334
   603
    }
kpeter@334
   604
kpeter@334
   605
    /// \brief The node on the given position.
kpeter@334
   606
    ///
kpeter@334
   607
    /// Gives back the node on the given position.
kpeter@334
   608
    Node operator()(int i, int j) const {
kpeter@334
   609
      return Parent::operator()(i, j);
kpeter@334
   610
    }
kpeter@334
   611
deba@335
   612
    /// \brief Gives back the column index of the node.
deba@335
   613
    ///
deba@335
   614
    /// Gives back the column index of the node.
deba@335
   615
    int col(Node n) const {
deba@335
   616
      return Parent::col(n);
deba@335
   617
    }
deba@335
   618
kpeter@334
   619
    /// \brief Gives back the row index of the node.
kpeter@334
   620
    ///
kpeter@334
   621
    /// Gives back the row index of the node.
kpeter@334
   622
    int row(Node n) const {
kpeter@334
   623
      return Parent::row(n);
kpeter@334
   624
    }
kpeter@334
   625
deba@335
   626
    /// \brief Gives back the position of the node.
kpeter@334
   627
    ///
deba@335
   628
    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
deba@335
   629
    dim2::Point<int> pos(Node n) const {
deba@335
   630
      return Parent::pos(n);
kpeter@334
   631
    }
kpeter@334
   632
deba@335
   633
    /// \brief Gives back the number of the columns.
kpeter@334
   634
    ///
deba@335
   635
    /// Gives back the number of the columns.
kpeter@334
   636
    int width() const {
kpeter@334
   637
      return Parent::width();
kpeter@334
   638
    }
kpeter@334
   639
deba@335
   640
    /// \brief Gives back the number of the rows.
kpeter@334
   641
    ///
deba@335
   642
    /// Gives back the number of the rows.
kpeter@334
   643
    int height() const {
kpeter@334
   644
      return Parent::height();
kpeter@334
   645
    }
kpeter@334
   646
deba@335
   647
    /// \brief Gives back the arc goes right from the node.
deba@335
   648
    ///
deba@335
   649
    /// Gives back the arc goes right from the node. If there is not
deba@335
   650
    /// outgoing arc then it gives back INVALID.
deba@335
   651
    Arc right(Node n) const {
deba@335
   652
      return Parent::right(n);
deba@335
   653
    }
deba@335
   654
deba@335
   655
    /// \brief Gives back the arc goes left from the node.
deba@335
   656
    ///
deba@335
   657
    /// Gives back the arc goes left from the node. If there is not
deba@335
   658
    /// outgoing arc then it gives back INVALID.
deba@335
   659
    Arc left(Node n) const {
deba@335
   660
      return Parent::left(n);
deba@335
   661
    }
deba@335
   662
deba@335
   663
    /// \brief Gives back the arc goes up from the node.
deba@335
   664
    ///
deba@335
   665
    /// Gives back the arc goes up from the node. If there is not
deba@335
   666
    /// outgoing arc then it gives back INVALID.
deba@335
   667
    Arc up(Node n) const {
deba@335
   668
      return Parent::up(n);
deba@335
   669
    }
deba@335
   670
kpeter@334
   671
    /// \brief Gives back the arc goes down from the node.
kpeter@334
   672
    ///
kpeter@334
   673
    /// Gives back the arc goes down from the node. If there is not
deba@335
   674
    /// outgoing arc then it gives back INVALID.
kpeter@334
   675
    Arc down(Node n) const {
deba@335
   676
      return Parent::down(n);
kpeter@334
   677
    }
kpeter@334
   678
deba@335
   679
    /// \brief Index map of the grid graph
kpeter@334
   680
    ///
deba@335
   681
    /// Just returns an IndexMap for the grid graph.
deba@335
   682
    IndexMap indexMap() const {
deba@335
   683
      return IndexMap(*this);
kpeter@334
   684
    }
kpeter@334
   685
deba@335
   686
    /// \brief Row map of the grid graph
kpeter@334
   687
    ///
deba@335
   688
    /// Just returns a RowMap for the grid graph.
deba@335
   689
    RowMap rowMap() const {
deba@335
   690
      return RowMap(*this);
kpeter@334
   691
    }
kpeter@334
   692
deba@335
   693
    /// \brief Column map of the grid graph
kpeter@334
   694
    ///
deba@335
   695
    /// Just returns a ColMap for the grid graph.
deba@335
   696
    ColMap colMap() const {
deba@335
   697
      return ColMap(*this);
kpeter@334
   698
    }
kpeter@334
   699
deba@335
   700
  };
kpeter@334
   701
kpeter@334
   702
}
deba@335
   703
#endif