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