lemon/grid_graph.h
author Alpar Juttner <alpar@cs.elte.hu>
Thu, 05 Nov 2009 10:01:02 +0100
changeset 779 c160bf9f18ef
parent 582 7a28e215f715
child 735 853fcddcf282
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
 *
alpar@440
     5
 * Copyright (C) 2003-2009
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@360
    85
    typedef True EdgeNumTag;
kpeter@334
    86
    typedef True ArcNumTag;
kpeter@334
    87
deba@335
    88
    int nodeNum() const { return _node_num; }
deba@335
    89
    int edgeNum() const { return _edge_num; }
deba@335
    90
    int arcNum() const { return 2 * _edge_num; }
kpeter@334
    91
deba@335
    92
    Node u(Edge edge) const {
deba@335
    93
      if (edge._id < _edge_limit) {
deba@335
    94
        return edge._id;
kpeter@334
    95
      } else {
deba@335
    96
        return (edge._id - _edge_limit) % (_width - 1) +
deba@335
    97
          (edge._id - _edge_limit) / (_width - 1) * _width;
kpeter@334
    98
      }
kpeter@334
    99
    }
kpeter@334
   100
deba@335
   101
    Node v(Edge edge) const {
deba@335
   102
      if (edge._id < _edge_limit) {
deba@335
   103
        return edge._id + _width;
kpeter@334
   104
      } else {
deba@335
   105
        return (edge._id - _edge_limit) % (_width - 1) +
deba@335
   106
          (edge._id - _edge_limit) / (_width - 1) * _width + 1;
kpeter@334
   107
      }
kpeter@334
   108
    }
kpeter@334
   109
deba@335
   110
    Node source(Arc arc) const {
deba@335
   111
      return (arc._id & 1) == 1 ? u(arc) : v(arc);
deba@335
   112
    }
deba@335
   113
deba@335
   114
    Node target(Arc arc) const {
deba@335
   115
      return (arc._id & 1) == 1 ? v(arc) : u(arc);
deba@335
   116
    }
deba@335
   117
deba@335
   118
    static int id(Node node) { return node._id; }
deba@335
   119
    static int id(Edge edge) { return edge._id; }
deba@335
   120
    static int id(Arc arc) { return arc._id; }
deba@335
   121
deba@335
   122
    int maxNodeId() const { return _node_num - 1; }
deba@335
   123
    int maxEdgeId() const { return _edge_num - 1; }
deba@335
   124
    int maxArcId() const { return 2 * _edge_num - 1; }
kpeter@334
   125
kpeter@334
   126
    static Node nodeFromId(int id) { return Node(id);}
deba@335
   127
    static Edge edgeFromId(int id) { return Edge(id);}
kpeter@334
   128
    static Arc arcFromId(int id) { return Arc(id);}
kpeter@334
   129
deba@335
   130
    typedef True FindEdgeTag;
kpeter@360
   131
    typedef True FindArcTag;
deba@335
   132
deba@335
   133
    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
deba@335
   134
      if (prev != INVALID) return INVALID;
deba@335
   135
      if (v._id > u._id) {
deba@335
   136
        if (v._id - u._id == _width)
deba@335
   137
          return Edge(u._id);
deba@335
   138
        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
deba@335
   139
          return Edge(u._id / _width * (_width - 1) +
deba@335
   140
                      u._id % _width + _edge_limit);
deba@335
   141
        }
deba@335
   142
      } else {
deba@335
   143
        if (u._id - v._id == _width)
deba@335
   144
          return Edge(v._id);
deba@335
   145
        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
deba@335
   146
          return Edge(v._id / _width * (_width - 1) +
deba@335
   147
                      v._id % _width + _edge_limit);
deba@335
   148
        }
deba@335
   149
      }
deba@335
   150
      return INVALID;
deba@335
   151
    }
kpeter@334
   152
kpeter@334
   153
    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
kpeter@334
   154
      if (prev != INVALID) return INVALID;
deba@335
   155
      if (v._id > u._id) {
deba@335
   156
        if (v._id - u._id == _width)
deba@335
   157
          return Arc((u._id << 1) | 1);
deba@335
   158
        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
deba@335
   159
          return Arc(((u._id / _width * (_width - 1) +
deba@335
   160
                       u._id % _width + _edge_limit) << 1) | 1);
deba@335
   161
        }
deba@335
   162
      } else {
deba@335
   163
        if (u._id - v._id == _width)
deba@335
   164
          return Arc(v._id << 1);
deba@335
   165
        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
deba@335
   166
          return Arc((v._id / _width * (_width - 1) +
deba@335
   167
                       v._id % _width + _edge_limit) << 1);
deba@335
   168
        }
kpeter@334
   169
      }
kpeter@334
   170
      return INVALID;
kpeter@334
   171
    }
kpeter@334
   172
kpeter@334
   173
    class Node {
kpeter@334
   174
      friend class GridGraphBase;
kpeter@334
   175
kpeter@334
   176
    protected:
deba@335
   177
      int _id;
deba@335
   178
      Node(int id) : _id(id) {}
kpeter@334
   179
    public:
kpeter@334
   180
      Node() {}
deba@335
   181
      Node (Invalid) : _id(-1) {}
deba@335
   182
      bool operator==(const Node node) const {return _id == node._id;}
deba@335
   183
      bool operator!=(const Node node) const {return _id != node._id;}
deba@335
   184
      bool operator<(const Node node) const {return _id < node._id;}
deba@335
   185
    };
deba@335
   186
deba@335
   187
    class Edge {
deba@335
   188
      friend class GridGraphBase;
kpeter@336
   189
      friend class Arc;
deba@335
   190
deba@335
   191
    protected:
deba@335
   192
      int _id;
deba@335
   193
deba@335
   194
      Edge(int id) : _id(id) {}
deba@335
   195
deba@335
   196
    public:
deba@335
   197
      Edge() {}
deba@335
   198
      Edge (Invalid) : _id(-1) {}
deba@335
   199
      bool operator==(const Edge edge) const {return _id == edge._id;}
deba@335
   200
      bool operator!=(const Edge edge) const {return _id != edge._id;}
deba@335
   201
      bool operator<(const Edge edge) const {return _id < edge._id;}
kpeter@334
   202
    };
kpeter@334
   203
kpeter@334
   204
    class Arc {
kpeter@334
   205
      friend class GridGraphBase;
kpeter@334
   206
kpeter@334
   207
    protected:
deba@335
   208
      int _id;
deba@335
   209
deba@335
   210
      Arc(int id) : _id(id) {}
deba@335
   211
kpeter@334
   212
    public:
kpeter@334
   213
      Arc() {}
deba@335
   214
      Arc (Invalid) : _id(-1) {}
deba@335
   215
      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
deba@335
   216
      bool operator==(const Arc arc) const {return _id == arc._id;}
deba@335
   217
      bool operator!=(const Arc arc) const {return _id != arc._id;}
deba@335
   218
      bool operator<(const Arc arc) const {return _id < arc._id;}
kpeter@334
   219
    };
kpeter@334
   220
deba@335
   221
    static bool direction(Arc arc) {
deba@335
   222
      return (arc._id & 1) == 1;
deba@335
   223
    }
deba@335
   224
deba@335
   225
    static Arc direct(Edge edge, bool dir) {
deba@335
   226
      return Arc((edge._id << 1) | (dir ? 1 : 0));
deba@335
   227
    }
deba@335
   228
kpeter@334
   229
    void first(Node& node) const {
deba@335
   230
      node._id = _node_num - 1;
kpeter@334
   231
    }
kpeter@334
   232
kpeter@334
   233
    static void next(Node& node) {
deba@335
   234
      --node._id;
deba@335
   235
    }
deba@335
   236
deba@335
   237
    void first(Edge& edge) const {
deba@335
   238
      edge._id = _edge_num - 1;
deba@335
   239
    }
deba@335
   240
deba@335
   241
    static void next(Edge& edge) {
deba@335
   242
      --edge._id;
kpeter@334
   243
    }
kpeter@334
   244
kpeter@334
   245
    void first(Arc& arc) const {
deba@335
   246
      arc._id = 2 * _edge_num - 1;
kpeter@334
   247
    }
kpeter@334
   248
kpeter@334
   249
    static void next(Arc& arc) {
deba@335
   250
      --arc._id;
kpeter@334
   251
    }
kpeter@334
   252
kpeter@334
   253
    void firstOut(Arc& arc, const Node& node) const {
deba@335
   254
      if (node._id % _width < _width - 1) {
deba@335
   255
        arc._id = (_edge_limit + node._id % _width +
deba@335
   256
                   (node._id / _width) * (_width - 1)) << 1 | 1;
deba@335
   257
        return;
deba@335
   258
      }
deba@335
   259
      if (node._id < _node_num - _width) {
deba@335
   260
        arc._id = node._id << 1 | 1;
deba@335
   261
        return;
deba@335
   262
      }
deba@335
   263
      if (node._id % _width > 0) {
deba@335
   264
        arc._id = (_edge_limit + node._id % _width +
deba@335
   265
                   (node._id / _width) * (_width - 1) - 1) << 1;
deba@335
   266
        return;
deba@335
   267
      }
deba@335
   268
      if (node._id >= _width) {
deba@335
   269
        arc._id = (node._id - _width) << 1;
deba@335
   270
        return;
deba@335
   271
      }
deba@335
   272
      arc._id = -1;
deba@335
   273
    }
deba@335
   274
deba@335
   275
    void nextOut(Arc& arc) const {
deba@335
   276
      int nid = arc._id >> 1;
deba@335
   277
      if ((arc._id & 1) == 1) {
deba@335
   278
        if (nid >= _edge_limit) {
deba@335
   279
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   280
            (nid - _edge_limit) / (_width - 1) * _width;
deba@335
   281
          if (nid < _node_num - _width) {
deba@335
   282
            arc._id = nid << 1 | 1;
deba@335
   283
            return;
deba@335
   284
          }
deba@335
   285
        }
deba@335
   286
        if (nid % _width > 0) {
deba@335
   287
          arc._id = (_edge_limit + nid % _width +
deba@335
   288
                     (nid / _width) * (_width - 1) - 1) << 1;
deba@335
   289
          return;
deba@335
   290
        }
deba@335
   291
        if (nid >= _width) {
deba@335
   292
          arc._id = (nid - _width) << 1;
deba@335
   293
          return;
deba@335
   294
        }
kpeter@334
   295
      } else {
deba@335
   296
        if (nid >= _edge_limit) {
deba@335
   297
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   298
            (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@335
   299
          if (nid >= _width) {
deba@335
   300
            arc._id = (nid - _width) << 1;
deba@335
   301
            return;
deba@335
   302
          }
deba@335
   303
        }
deba@335
   304
      }
deba@335
   305
      arc._id = -1;
deba@335
   306
    }
deba@335
   307
deba@335
   308
    void firstIn(Arc& arc, const Node& node) const {
deba@335
   309
      if (node._id % _width < _width - 1) {
deba@335
   310
        arc._id = (_edge_limit + node._id % _width +
deba@335
   311
                   (node._id / _width) * (_width - 1)) << 1;
deba@335
   312
        return;
deba@335
   313
      }
deba@335
   314
      if (node._id < _node_num - _width) {
deba@335
   315
        arc._id = node._id << 1;
deba@335
   316
        return;
deba@335
   317
      }
deba@335
   318
      if (node._id % _width > 0) {
deba@335
   319
        arc._id = (_edge_limit + node._id % _width +
deba@335
   320
                   (node._id / _width) * (_width - 1) - 1) << 1 | 1;
deba@335
   321
        return;
deba@335
   322
      }
deba@335
   323
      if (node._id >= _width) {
deba@335
   324
        arc._id = (node._id - _width) << 1 | 1;
deba@335
   325
        return;
deba@335
   326
      }
deba@335
   327
      arc._id = -1;
deba@335
   328
    }
deba@335
   329
deba@335
   330
    void nextIn(Arc& arc) const {
deba@335
   331
      int nid = arc._id >> 1;
deba@335
   332
      if ((arc._id & 1) == 0) {
deba@335
   333
        if (nid >= _edge_limit) {
deba@335
   334
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   335
            (nid - _edge_limit) / (_width - 1) * _width;
deba@335
   336
          if (nid < _node_num - _width) {
deba@335
   337
            arc._id = nid << 1;
deba@335
   338
            return;
deba@335
   339
          }
deba@335
   340
        }
deba@335
   341
        if (nid % _width > 0) {
deba@335
   342
          arc._id = (_edge_limit + nid % _width +
deba@335
   343
                     (nid / _width) * (_width - 1) - 1) << 1 | 1;
deba@335
   344
          return;
deba@335
   345
        }
deba@335
   346
        if (nid >= _width) {
deba@335
   347
          arc._id = (nid - _width) << 1 | 1;
deba@335
   348
          return;
deba@335
   349
        }
deba@335
   350
      } else {
deba@335
   351
        if (nid >= _edge_limit) {
deba@335
   352
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   353
            (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@335
   354
          if (nid >= _width) {
deba@335
   355
            arc._id = (nid - _width) << 1 | 1;
deba@335
   356
            return;
deba@335
   357
          }
deba@335
   358
        }
deba@335
   359
      }
deba@335
   360
      arc._id = -1;
deba@335
   361
    }
deba@335
   362
deba@335
   363
    void firstInc(Edge& edge, bool& dir, const Node& node) const {
deba@335
   364
      if (node._id % _width < _width - 1) {
deba@335
   365
        edge._id = _edge_limit + node._id % _width +
deba@335
   366
          (node._id / _width) * (_width - 1);
deba@335
   367
        dir = true;
deba@335
   368
        return;
deba@335
   369
      }
deba@335
   370
      if (node._id < _node_num - _width) {
deba@335
   371
        edge._id = node._id;
deba@335
   372
        dir = true;
deba@335
   373
        return;
deba@335
   374
      }
deba@335
   375
      if (node._id % _width > 0) {
deba@335
   376
        edge._id = _edge_limit + node._id % _width +
deba@335
   377
          (node._id / _width) * (_width - 1) - 1;
deba@335
   378
        dir = false;
deba@335
   379
        return;
deba@335
   380
      }
deba@335
   381
      if (node._id >= _width) {
deba@335
   382
        edge._id = node._id - _width;
deba@335
   383
        dir = false;
deba@335
   384
        return;
deba@335
   385
      }
deba@335
   386
      edge._id = -1;
deba@335
   387
      dir = true;
deba@335
   388
    }
deba@335
   389
deba@335
   390
    void nextInc(Edge& edge, bool& dir) const {
deba@335
   391
      int nid = edge._id;
deba@335
   392
      if (dir) {
deba@335
   393
        if (nid >= _edge_limit) {
deba@335
   394
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   395
            (nid - _edge_limit) / (_width - 1) * _width;
deba@335
   396
          if (nid < _node_num - _width) {
deba@335
   397
            edge._id = nid;
deba@335
   398
            return;
deba@335
   399
          }
deba@335
   400
        }
deba@335
   401
        if (nid % _width > 0) {
deba@335
   402
          edge._id = _edge_limit + nid % _width +
deba@335
   403
            (nid / _width) * (_width - 1) - 1;
deba@335
   404
          dir = false;
deba@335
   405
          return;
deba@335
   406
        }
deba@335
   407
        if (nid >= _width) {
deba@335
   408
          edge._id = nid - _width;
deba@335
   409
          dir = false;
deba@335
   410
          return;
deba@335
   411
        }
deba@335
   412
      } else {
deba@335
   413
        if (nid >= _edge_limit) {
deba@335
   414
          nid = (nid - _edge_limit) % (_width - 1) +
deba@335
   415
            (nid - _edge_limit) / (_width - 1) * _width + 1;
deba@335
   416
          if (nid >= _width) {
deba@335
   417
            edge._id = nid - _width;
deba@335
   418
            return;
deba@335
   419
          }
deba@335
   420
        }
deba@335
   421
      }
deba@335
   422
      edge._id = -1;
deba@335
   423
      dir = true;
deba@335
   424
    }
deba@335
   425
deba@335
   426
    Arc right(Node n) const {
deba@335
   427
      if (n._id % _width < _width - 1) {
deba@335
   428
        return Arc(((_edge_limit + n._id % _width +
deba@335
   429
                    (n._id / _width) * (_width - 1)) << 1) | 1);
deba@335
   430
      } else {
deba@335
   431
        return INVALID;
kpeter@334
   432
      }
kpeter@334
   433
    }
kpeter@334
   434
deba@335
   435
    Arc left(Node n) const {
deba@335
   436
      if (n._id % _width > 0) {
deba@335
   437
        return Arc((_edge_limit + n._id % _width +
deba@335
   438
                     (n._id / _width) * (_width - 1) - 1) << 1);
kpeter@334
   439
      } else {
deba@335
   440
        return INVALID;
kpeter@334
   441
      }
kpeter@334
   442
    }
kpeter@334
   443
deba@335
   444
    Arc up(Node n) const {
deba@335
   445
      if (n._id < _edge_limit) {
deba@335
   446
        return Arc((n._id << 1) | 1);
kpeter@334
   447
      } else {
deba@335
   448
        return INVALID;
kpeter@334
   449
      }
kpeter@334
   450
    }
kpeter@334
   451
deba@335
   452
    Arc down(Node n) const {
deba@335
   453
      if (n._id >= _width) {
deba@335
   454
        return Arc((n._id - _width) << 1);
kpeter@334
   455
      } else {
deba@335
   456
        return INVALID;
kpeter@334
   457
      }
kpeter@334
   458
    }
kpeter@334
   459
kpeter@334
   460
  private:
kpeter@334
   461
    int _width, _height;
deba@335
   462
    int _node_num, _edge_num;
deba@335
   463
    int _edge_limit;
kpeter@334
   464
  };
kpeter@334
   465
deba@335
   466
deba@335
   467
  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
kpeter@334
   468
kpeter@334
   469
  /// \ingroup graphs
kpeter@334
   470
  ///
kpeter@334
   471
  /// \brief Grid graph class
kpeter@334
   472
  ///
kpeter@334
   473
  /// This class implements a special graph type. The nodes of the
deba@335
   474
  /// graph can be indexed by two integer \c (i,j) value where \c i is
deba@335
   475
  /// in the \c [0..width()-1] range and j is in the \c
deba@335
   476
  /// [0..height()-1] range.  Two nodes are connected in the graph if
deba@335
   477
  /// the indexes differ exactly on one position and exactly one is
kpeter@336
   478
  /// the difference. The nodes of the graph can be indexed by position
kpeter@336
   479
  /// with the \c operator()() function. The positions of the nodes can be
deba@335
   480
  /// get with \c pos(), \c col() and \c row() members. The outgoing
deba@335
   481
  /// arcs can be retrieved with the \c right(), \c up(), \c left()
deba@335
   482
  /// and \c down() functions, where the bottom-left corner is the
deba@335
   483
  /// origin.
kpeter@334
   484
  ///
kpeter@334
   485
  /// \image html grid_graph.png
deba@338
   486
  /// \image latex grid_graph.eps "Grid graph" width=\textwidth
kpeter@334
   487
  ///
deba@335
   488
  /// A short example about the basic usage:
kpeter@334
   489
  ///\code
deba@335
   490
  /// GridGraph graph(rows, cols);
deba@335
   491
  /// GridGraph::NodeMap<int> val(graph);
deba@335
   492
  /// for (int i = 0; i < graph.width(); ++i) {
deba@335
   493
  ///   for (int j = 0; j < graph.height(); ++j) {
deba@335
   494
  ///     val[graph(i, j)] = i + j;
kpeter@334
   495
  ///   }
kpeter@334
   496
  /// }
kpeter@334
   497
  ///\endcode
kpeter@334
   498
  ///
kpeter@559
   499
  /// This graph type fully conforms to the \ref concepts::Graph
kpeter@582
   500
  /// "Graph concept".
kpeter@334
   501
  class GridGraph : public ExtendedGridGraphBase {
kpeter@617
   502
    typedef ExtendedGridGraphBase Parent;
kpeter@617
   503
kpeter@334
   504
  public:
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