00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef GRID_GRAPH_H
00020 #define GRID_GRAPH_H
00021
00022 #include <iostream>
00023 #include <lemon/invalid.h>
00024 #include <lemon/utility.h>
00025
00026 #include <lemon/bits/iterable_graph_extender.h>
00027 #include <lemon/bits/alteration_notifier.h>
00028 #include <lemon/bits/static_map.h>
00029 #include <lemon/bits/graph_extender.h>
00030
00031 #include <lemon/xy.h>
00032
00036
00037 namespace lemon {
00038
00046 class GridGraphBase {
00047
00048 public:
00049
00050 typedef GridGraphBase Graph;
00051
00052 class Node;
00053 class Edge;
00054
00055 public:
00056
00057 GridGraphBase() {}
00058
00059 protected:
00060
00064 void construct(int width, int height) {
00065 _height = height; _width = width;
00066 _nodeNum = height * width; _edgeNum = 2 * _nodeNum - width - height;
00067 _edgeLimit = _nodeNum - width;
00068 }
00069
00074 Edge _down(Node n) const {
00075 if (n.id < _nodeNum - _width) {
00076 return Edge(n.id);
00077 } else {
00078 return INVALID;
00079 }
00080 }
00081
00086 Edge _up(Node n) const {
00087 if (n.id >= _width) {
00088 return Edge(n.id - _width);
00089 } else {
00090 return INVALID;
00091 }
00092 }
00093
00098 Edge _right(Node n) const {
00099 if (n.id % _width < _width - 1) {
00100 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1);
00101 } else {
00102 return INVALID;
00103 }
00104 }
00105
00110 Edge _left(Node n) const {
00111 if (n.id % _width > 0) {
00112 return _edgeLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
00113 } else {
00114 return INVALID;
00115 }
00116 }
00117
00118
00119 public:
00120
00124 Node operator()(int i, int j) const {
00125 return Node(i + j * _width);
00126 }
00127
00131 int row(Node n) const {
00132 return n.id / _width;
00133 }
00134
00138 int col(Node n) const {
00139 return n.id % _width;
00140 }
00141
00145 int width() const {
00146 return _width;
00147 }
00148
00152 int height() const {
00153 return _height;
00154 }
00155
00156 typedef True NodeNumTag;
00157 typedef True EdgeNumTag;
00158
00160 int nodeNum() const { return _nodeNum; }
00162 int edgeNum() const { return _edgeNum; }
00163
00165
00168 int maxNodeId() const { return nodeNum() - 1; }
00170
00173 int maxEdgeId() const { return edgeNum() - 1; }
00174
00178 Node source(Edge e) const {
00179 if (e.id < _edgeLimit) {
00180 return e.id;
00181 } else {
00182 return (e.id - _edgeLimit) % (_width - 1) +
00183 (e.id - _edgeLimit) / (_width - 1) * _width;
00184 }
00185 }
00186
00190 Node target(Edge e) const {
00191 if (e.id < _edgeLimit) {
00192 return e.id + _width;
00193 } else {
00194 return (e.id - _edgeLimit) % (_width - 1) +
00195 (e.id - _edgeLimit) / (_width - 1) * _width + 1;
00196 }
00197 }
00198
00200
00207
00208 static int id(Node v) { return v.id; }
00210
00217 static int id(Edge e) { return e.id; }
00218
00219 static Node nodeFromId(int id) { return Node(id);}
00220
00221 static Edge edgeFromId(int id) { return Edge(id);}
00222
00223 typedef True FindEdgeTag;
00224
00226
00233 Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
00234 if (prev != INVALID) return INVALID;
00235 if (v.id - u.id == _width) return Edge(u.id);
00236 if (v.id - u.id == 1 && u.id % _width < _width - 1) {
00237 return Edge(u.id / _width * (_width - 1) +
00238 u.id % _width + _edgeLimit);
00239 }
00240 return INVALID;
00241 }
00242
00243
00244 class Node {
00245 friend class GridGraphBase;
00246
00247 protected:
00248 int id;
00249 Node(int _id) { id = _id;}
00250 public:
00251 Node() {}
00252 Node (Invalid) { id = -1; }
00253 bool operator==(const Node node) const {return id == node.id;}
00254 bool operator!=(const Node node) const {return id != node.id;}
00255 bool operator<(const Node node) const {return id < node.id;}
00256 };
00257
00258
00259
00260 class Edge {
00261 friend class GridGraphBase;
00262
00263 protected:
00264 int id;
00265
00266 Edge(int _id) : id(_id) {}
00267
00268 public:
00269 Edge() { }
00270 Edge (Invalid) { id = -1; }
00271 bool operator==(const Edge edge) const {return id == edge.id;}
00272 bool operator!=(const Edge edge) const {return id != edge.id;}
00273 bool operator<(const Edge edge) const {return id < edge.id;}
00274 };
00275
00276 void first(Node& node) const {
00277 node.id = nodeNum() - 1;
00278 }
00279
00280 static void next(Node& node) {
00281 --node.id;
00282 }
00283
00284 void first(Edge& edge) const {
00285 edge.id = edgeNum() - 1;
00286 }
00287
00288 static void next(Edge& edge) {
00289 --edge.id;
00290 }
00291
00292 void firstOut(Edge& edge, const Node& node) const {
00293 if (node.id < _nodeNum - _width) {
00294 edge.id = node.id;
00295 } else if (node.id % _width < _width - 1) {
00296 edge.id = _edgeLimit + node.id % _width +
00297 (node.id / _width) * (_width - 1);
00298 } else {
00299 edge.id = -1;
00300 }
00301 }
00302
00303 void nextOut(Edge& edge) const {
00304 if (edge.id >= _edgeLimit) {
00305 edge.id = -1;
00306 } else if (edge.id % _width < _width - 1) {
00307 edge.id = _edgeLimit + edge.id % _width +
00308 (edge.id / _width) * (_width - 1);
00309 } else {
00310 edge.id = -1;
00311 }
00312 }
00313
00314 void firstIn(Edge& edge, const Node& node) const {
00315 if (node.id >= _width) {
00316 edge.id = node.id - _width;
00317 } else if (node.id % _width > 0) {
00318 edge.id = _edgeLimit + node.id % _width +
00319 (node.id / _width) * (_width - 1) - 1;
00320 } else {
00321 edge.id = -1;
00322 }
00323 }
00324
00325 void nextIn(Edge& edge) const {
00326 if (edge.id >= _edgeLimit) {
00327 edge.id = -1;
00328 } else if (edge.id % _width > 0) {
00329 edge.id = _edgeLimit + edge.id % _width +
00330 (edge.id / _width + 1) * (_width - 1) - 1;
00331 } else {
00332 edge.id = -1;
00333 }
00334 }
00335
00336 private:
00337 int _width, _height;
00338 int _nodeNum, _edgeNum;
00339 int _edgeLimit;
00340 };
00341
00342
00343 typedef StaticMappableUGraphExtender<
00344 IterableUGraphExtender<
00345 AlterableUGraphExtender<
00346 UGraphExtender<GridGraphBase> > > > ExtendedGridGraphBase;
00347
00374 class GridGraph : public ExtendedGridGraphBase {
00375 public:
00376
00380 class IndexMap {
00381 public:
00382 typedef True NeedCopy;
00384 typedef GridGraph::Node Key;
00386 typedef xy<int> Value;
00387
00391 IndexMap(const GridGraph& _graph) : graph(_graph) {}
00392
00396 Value operator[](Key key) const {
00397 return xy<int>(graph.row(key), graph.col(key));
00398 }
00399
00400 private:
00401 const GridGraph& graph;
00402 };
00403
00407 class RowMap {
00408 public:
00409 typedef True NeedCopy;
00411 typedef GridGraph::Node Key;
00413 typedef int Value;
00414
00418 RowMap(const GridGraph& _graph) : graph(_graph) {}
00419
00423 Value operator[](Key key) const {
00424 return graph.row(key);
00425 }
00426
00427 private:
00428 const GridGraph& graph;
00429 };
00430
00434 class ColMap {
00435 public:
00436 typedef True NeedCopy;
00438 typedef GridGraph::Node Key;
00440 typedef int Value;
00441
00445 ColMap(const GridGraph& _graph) : graph(_graph) {}
00446
00450 Value operator[](Key key) const {
00451 return graph.col(key);
00452 }
00453
00454 private:
00455 const GridGraph& graph;
00456 };
00457
00461 GridGraph(int n, int m) { construct(n, m); }
00462
00467 Edge down(Node n) const {
00468 UEdge ue = _down(n);
00469 return ue != INVALID ? direct(ue, true) : INVALID;
00470 }
00471
00476 Edge up(Node n) const {
00477 UEdge ue = _up(n);
00478 return ue != INVALID ? direct(ue, false) : INVALID;
00479 }
00480
00485 Edge right(Node n) const {
00486 UEdge ue = _right(n);
00487 return ue != INVALID ? direct(ue, true) : INVALID;
00488 }
00489
00494 Edge left(Node n) const {
00495 UEdge ue = _left(n);
00496 return ue != INVALID ? direct(ue, false) : INVALID;
00497 }
00498
00499 };
00500
00504 GridGraph::IndexMap indexMap(const GridGraph& graph) {
00505 return GridGraph::IndexMap(graph);
00506 }
00507
00511 GridGraph::RowMap rowMap(const GridGraph& graph) {
00512 return GridGraph::RowMap(graph);
00513 }
00514
00518 GridGraph::ColMap colMap(const GridGraph& graph) {
00519 return GridGraph::ColMap(graph);
00520 }
00521 }
00522 #endif