1.1 --- a/doc/CMakeLists.txt Tue Sep 02 22:32:04 2008 +0200
1.2 +++ b/doc/CMakeLists.txt Mon Oct 20 12:36:02 2008 +0200
1.3 @@ -13,6 +13,7 @@
1.4 ADD_CUSTOM_TARGET(html
1.5 COMMAND rm -rf gen-images
1.6 COMMAND mkdir gen-images
1.7 + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
1.8 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
1.9 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps
1.10 COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps
2.1 --- a/doc/Makefile.am Tue Sep 02 22:32:04 2008 +0200
2.2 +++ b/doc/Makefile.am Mon Oct 20 12:36:02 2008 +0200
2.3 @@ -11,6 +11,7 @@
2.4 doc/CMakeLists.txt
2.5
2.6 DOC_EPS_IMAGES18 = \
2.7 + grid_graph.eps \
2.8 nodeshape_0.eps \
2.9 nodeshape_1.eps \
2.10 nodeshape_2.eps \
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/doc/images/grid_graph.eps Mon Oct 20 12:36:02 2008 +0200
3.3 @@ -0,0 +1,286 @@
3.4 +%!PS-Adobe-2.0 EPSF-2.0
3.5 +%%Title: Grid undirected graph
3.6 +%%Copyright: (C) 2006 LEMON Project
3.7 +%%Creator: LEMON, graphToEps()
3.8 +%%CreationDate: Fri Sep 29 11:55:56 2006
3.9 +%%BoundingBox: 0 0 985 1144
3.10 +%%EndComments
3.11 +/lb { setlinewidth setrgbcolor newpath moveto
3.12 + 4 2 roll 1 index 1 index curveto stroke } bind def
3.13 +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
3.14 +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
3.15 +/sq { newpath 2 index 1 index add 2 index 2 index add moveto
3.16 + 2 index 1 index sub 2 index 2 index add lineto
3.17 + 2 index 1 index sub 2 index 2 index sub lineto
3.18 + 2 index 1 index add 2 index 2 index sub lineto
3.19 + closepath pop pop pop} bind def
3.20 +/di { newpath 2 index 1 index add 2 index moveto
3.21 + 2 index 2 index 2 index add lineto
3.22 + 2 index 1 index sub 2 index lineto
3.23 + 2 index 2 index 2 index sub lineto
3.24 + closepath pop pop pop} bind def
3.25 +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
3.26 + setrgbcolor 1.1 div c fill
3.27 + } bind def
3.28 +/arrl 1 def
3.29 +/arrw 0.3 def
3.30 +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
3.31 +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
3.32 + /w exch def /len exch def
3.33 + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto
3.34 + len w sub arrl sub dx dy lrl
3.35 + arrw dy dx neg lrl
3.36 + dx arrl w add mul dy w 2 div arrw add mul sub
3.37 + dy arrl w add mul dx w 2 div arrw add mul add rlineto
3.38 + dx arrl w add mul neg dy w 2 div arrw add mul sub
3.39 + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto
3.40 + arrw dy dx neg lrl
3.41 + len w sub arrl sub neg dx dy lrl
3.42 + closepath fill } bind def
3.43 +/cshow { 2 index 2 index moveto dup stringwidth pop
3.44 + neg 2 div fosi .35 mul neg rmoveto show pop pop} def
3.45 +
3.46 +gsave
3.47 +2 2 scale
3.48 +50 40 translate
3.49 +5.5000 5.5000 scale
3.50 +% 1.14018 1.14018 translate
3.51 +%Edges:
3.52 +gsave
3.53 +70 80 70 90 0 0 0 0.5000 l
3.54 +70 70 70 80 0 0 0 0.5000 l
3.55 +70 60 70 70 0 0 0 0.5000 l
3.56 +70 50 70 60 0 0 0 0.5000 l
3.57 +70 40 70 50 0 0 0 0.5000 l
3.58 +70 30 70 40 0 0 0 0.5000 l
3.59 +70 20 70 30 0 0 0 0.5000 l
3.60 +70 10 70 20 0 0 0 0.5000 l
3.61 +70 0 70 10 0 0 0 0.5000 l
3.62 +60 80 60 90 0 0 0 0.5000 l
3.63 +60 70 60 80 0 0 0 0.5000 l
3.64 +60 60 60 70 0 0 0 0.5000 l
3.65 +60 50 60 60 0 0 0 0.5000 l
3.66 +60 40 60 50 0 0 0 0.5000 l
3.67 +60 30 60 40 0 0 0 0.5000 l
3.68 +60 20 60 30 0 0 0 0.5000 l
3.69 +60 10 60 20 0 0 0 0.5000 l
3.70 +60 0 60 10 0 0 0 0.5000 l
3.71 +50 80 50 90 0 0 0 0.5000 l
3.72 +50 70 50 80 0 0 0 0.5000 l
3.73 +50 60 50 70 0 0 0 0.5000 l
3.74 +50 50 50 60 0 0 0 0.5000 l
3.75 +50 40 50 50 0 0 0 0.5000 l
3.76 +50 30 50 40 0 0 0 0.5000 l
3.77 +50 20 50 30 0 0 0 0.5000 l
3.78 +50 10 50 20 0 0 0 0.5000 l
3.79 +50 0 50 10 0 0 0 0.5000 l
3.80 +40 80 40 90 0 0 0 0.5000 l
3.81 +40 70 40 80 0 0 0 0.5000 l
3.82 +40 60 40 70 0 0 0 0.5000 l
3.83 +40 50 40 60 0 0 0 0.5000 l
3.84 +40 40 40 50 0 0 0 0.5000 l
3.85 +40 30 40 40 0 0 0 0.5000 l
3.86 +40 20 40 30 0 0 0 0.5000 l
3.87 +40 10 40 20 0 0 0 0.5000 l
3.88 +40 0 40 10 0 0 0 0.5000 l
3.89 +30 80 30 90 0 0 0 0.5000 l
3.90 +30 70 30 80 0 0 0 0.5000 l
3.91 +30 60 30 70 0 0 0 0.5000 l
3.92 +30 50 30 60 0 0 0 0.5000 l
3.93 +30 40 30 50 0 0 0 0.5000 l
3.94 +30 30 30 40 0 0 0 0.5000 l
3.95 +30 20 30 30 0 0 0 0.5000 l
3.96 +30 10 30 20 0 0 0 0.5000 l
3.97 +30 0 30 10 0 0 0 0.5000 l
3.98 +20 80 20 90 0 0 0 0.5000 l
3.99 +20 70 20 80 0 0 0 0.5000 l
3.100 +20 60 20 70 0 0 0 0.5000 l
3.101 +20 50 20 60 0 0 0 0.5000 l
3.102 +20 40 20 50 0 0 0 0.5000 l
3.103 +20 30 20 40 0 0 0 0.5000 l
3.104 +20 20 20 30 0 0 0 0.5000 l
3.105 +20 10 20 20 0 0 0 0.5000 l
3.106 +20 0 20 10 0 0 0 0.5000 l
3.107 +10 80 10 90 0 0 0 0.5000 l
3.108 +10 70 10 80 0 0 0 0.5000 l
3.109 +10 60 10 70 0 0 0 0.5000 l
3.110 +10 50 10 60 0 0 0 0.5000 l
3.111 +10 40 10 50 0 0 0 0.5000 l
3.112 +10 30 10 40 0 0 0 0.5000 l
3.113 +10 20 10 30 0 0 0 0.5000 l
3.114 +10 10 10 20 0 0 0 0.5000 l
3.115 +10 0 10 10 0 0 0 0.5000 l
3.116 +0 80 0 90 0 0 0 0.5000 l
3.117 +0 70 0 80 0 0 0 0.5000 l
3.118 +0 60 0 70 0 0 0 0.5000 l
3.119 +0 50 0 60 0 0 0 0.5000 l
3.120 +0 40 0 50 0 0 0 0.5000 l
3.121 +0 30 0 40 0 0 0 0.5000 l
3.122 +0 20 0 30 0 0 0 0.5000 l
3.123 +0 10 0 20 0 0 0 0.5000 l
3.124 +0 0 0 10 0 0 0 0.5000 l
3.125 +60 90 70 90 0 0 0 0.5000 l
3.126 +60 80 70 80 0 0 0 0.5000 l
3.127 +60 70 70 70 0 0 0 0.5000 l
3.128 +60 60 70 60 0 0 0 0.5000 l
3.129 +60 50 70 50 0 0 0 0.5000 l
3.130 +60 40 70 40 0 0 0 0.5000 l
3.131 +60 30 70 30 0 0 0 0.5000 l
3.132 +60 20 70 20 0 0 0 0.5000 l
3.133 +60 10 70 10 0 0 0 0.5000 l
3.134 +60 0 70 0 0 0 0 0.5000 l
3.135 +50 90 60 90 0 0 0 0.5000 l
3.136 +50 80 60 80 0 0 0 0.5000 l
3.137 +50 70 60 70 0 0 0 0.5000 l
3.138 +50 60 60 60 0 0 0 0.5000 l
3.139 +50 50 60 50 0 0 0 0.5000 l
3.140 +50 40 60 40 0 0 0 0.5000 l
3.141 +50 30 60 30 0 0 0 0.5000 l
3.142 +50 20 60 20 0 0 0 0.5000 l
3.143 +50 10 60 10 0 0 0 0.5000 l
3.144 +50 0 60 0 0 0 0 0.5000 l
3.145 +40 90 50 90 0 0 0 0.5000 l
3.146 +40 80 50 80 0 0 0 0.5000 l
3.147 +40 70 50 70 0 0 0 0.5000 l
3.148 +40 60 50 60 0 0 0 0.5000 l
3.149 +40 50 50 50 0 0 0 0.5000 l
3.150 +40 40 50 40 0 0 0 0.5000 l
3.151 +40 30 50 30 0 0 0 0.5000 l
3.152 +40 20 50 20 0 0 0 0.5000 l
3.153 +40 10 50 10 0 0 0 0.5000 l
3.154 +40 0 50 0 0 0 0 0.5000 l
3.155 +30 90 40 90 0 0 0 0.5000 l
3.156 +30 80 40 80 0 0 0 0.5000 l
3.157 +30 70 40 70 0 0 0 0.5000 l
3.158 +30 60 40 60 0 0 0 0.5000 l
3.159 +30 50 40 50 0 0 0 0.5000 l
3.160 +30 40 40 40 0 0 0 0.5000 l
3.161 +30 30 40 30 0 0 0 0.5000 l
3.162 +30 20 40 20 0 0 0 0.5000 l
3.163 +30 10 40 10 0 0 0 0.5000 l
3.164 +30 0 40 0 0 0 0 0.5000 l
3.165 +20 90 30 90 0 0 0 0.5000 l
3.166 +20 80 30 80 0 0 0 0.5000 l
3.167 +20 70 30 70 0 0 0 0.5000 l
3.168 +20 60 30 60 0 0 0 0.5000 l
3.169 +20 50 30 50 0 0 0 0.5000 l
3.170 +20 40 30 40 0 0 0 0.5000 l
3.171 +20 30 30 30 0 0 0 0.5000 l
3.172 +20 20 30 20 0 0 0 0.5000 l
3.173 +20 10 30 10 0 0 0 0.5000 l
3.174 +20 0 30 0 0 0 0 0.5000 l
3.175 +10 90 20 90 0 0 0 0.5000 l
3.176 +10 80 20 80 0 0 0 0.5000 l
3.177 +10 70 20 70 0 0 0 0.5000 l
3.178 +10 60 20 60 0 0 0 0.5000 l
3.179 +10 50 20 50 0 0 0 0.5000 l
3.180 +10 40 20 40 0 0 0 0.5000 l
3.181 +10 30 20 30 0 0 0 0.5000 l
3.182 +10 20 20 20 0 0 0 0.5000 l
3.183 +10 10 20 10 0 0 0 0.5000 l
3.184 +10 0 20 0 0 0 0 0.5000 l
3.185 +0 90 10 90 0 0 0 0.5000 l
3.186 +0 80 10 80 0 0 0 0.5000 l
3.187 +0 70 10 70 0 0 0 0.5000 l
3.188 +0 60 10 60 0 0 0 0.5000 l
3.189 +0 50 10 50 0 0 0 0.5000 l
3.190 +0 40 10 40 0 0 0 0.5000 l
3.191 +0 30 10 30 0 0 0 0.5000 l
3.192 +0 20 10 20 0 0 0 0.5000 l
3.193 +0 10 10 10 0 0 0 0.5000 l
3.194 +0 0 10 0 0 0 0 0.5000 l
3.195 +grestore
3.196 +%Nodes:
3.197 +gsave
3.198 +70 90 1.4000 0 0 0 nc
3.199 +70 80 1.4000 1 1 1 nc
3.200 +70 70 1.4000 1 1 1 nc
3.201 +70 60 1.4000 1 1 1 nc
3.202 +70 50 1.4000 1 1 1 nc
3.203 +70 40 1.4000 1 1 1 nc
3.204 +70 30 1.4000 1 1 1 nc
3.205 +70 20 1.4000 1 1 1 nc
3.206 +70 10 1.4000 1 1 1 nc
3.207 +70 0 1.4000 0 0 0 nc
3.208 +60 90 1.4000 1 1 1 nc
3.209 +60 80 1.4000 1 1 1 nc
3.210 +60 70 1.4000 1 1 1 nc
3.211 +60 60 1.4000 1 1 1 nc
3.212 +60 50 1.4000 1 1 1 nc
3.213 +60 40 1.4000 1 1 1 nc
3.214 +60 30 1.4000 1 1 1 nc
3.215 +60 20 1.4000 1 1 1 nc
3.216 +60 10 1.4000 1 1 1 nc
3.217 +60 0 1.4000 1 1 1 nc
3.218 +50 90 1.4000 1 1 1 nc
3.219 +50 80 1.4000 1 1 1 nc
3.220 +50 70 1.4000 1 1 1 nc
3.221 +50 60 1.4000 1 1 1 nc
3.222 +50 50 1.4000 1 1 1 nc
3.223 +50 40 1.4000 1 1 1 nc
3.224 +50 30 1.4000 1 1 1 nc
3.225 +50 20 1.4000 1 1 1 nc
3.226 +50 10 1.4000 1 1 1 nc
3.227 +50 0 1.4000 1 1 1 nc
3.228 +40 90 1.4000 1 1 1 nc
3.229 +40 80 1.4000 1 1 1 nc
3.230 +40 70 1.4000 1 1 1 nc
3.231 +40 60 1.4000 1 1 1 nc
3.232 +40 50 1.4000 1 1 1 nc
3.233 +40 40 1.4000 1 1 1 nc
3.234 +40 30 1.4000 1 1 1 nc
3.235 +40 20 1.4000 1 1 1 nc
3.236 +40 10 1.4000 1 1 1 nc
3.237 +40 0 1.4000 1 1 1 nc
3.238 +30 90 1.4000 1 1 1 nc
3.239 +30 80 1.4000 1 1 1 nc
3.240 +30 70 1.4000 1 1 1 nc
3.241 +30 60 1.4000 1 1 1 nc
3.242 +30 50 1.4000 1 1 1 nc
3.243 +30 40 1.4000 1 1 1 nc
3.244 +30 30 1.4000 1 1 1 nc
3.245 +30 20 1.4000 1 1 1 nc
3.246 +30 10 1.4000 1 1 1 nc
3.247 +30 0 1.4000 1 1 1 nc
3.248 +20 90 1.4000 1 1 1 nc
3.249 +20 80 1.4000 1 1 1 nc
3.250 +20 70 1.4000 1 1 1 nc
3.251 +20 60 1.4000 1 1 1 nc
3.252 +20 50 1.4000 1 1 1 nc
3.253 +20 40 1.4000 1 1 1 nc
3.254 +20 30 1.4000 1 1 1 nc
3.255 +20 20 1.4000 1 1 1 nc
3.256 +20 10 1.4000 1 1 1 nc
3.257 +20 0 1.4000 1 1 1 nc
3.258 +10 90 1.4000 1 1 1 nc
3.259 +10 80 1.4000 1 1 1 nc
3.260 +10 70 1.4000 1 1 1 nc
3.261 +10 60 1.4000 1 1 1 nc
3.262 +10 50 1.4000 1 1 1 nc
3.263 +10 40 1.4000 1 1 1 nc
3.264 +10 30 1.4000 1 1 1 nc
3.265 +10 20 1.4000 1 1 1 nc
3.266 +10 10 1.4000 1 1 1 nc
3.267 +10 0 1.4000 1 1 1 nc
3.268 +0 90 1.4000 0 0 0 nc
3.269 +0 80 1.4000 1 1 1 nc
3.270 +0 70 1.4000 1 1 1 nc
3.271 +0 60 1.4000 1 1 1 nc
3.272 +0 50 1.4000 1 1 1 nc
3.273 +0 40 1.4000 1 1 1 nc
3.274 +0 30 1.4000 1 1 1 nc
3.275 +0 20 1.4000 1 1 1 nc
3.276 +0 10 1.4000 1 1 1 nc
3.277 +0 0 1.4000 0 0 0 nc
3.278 +grestore
3.279 +gsave
3.280 +/fosi 3.5 def
3.281 +(Helvetica) findfont fosi scalefont setfont
3.282 +0 0 0 setrgbcolor
3.283 +0 95 ((0,height-1)) cshow
3.284 +67 95 ((width-1,height-1)) cshow
3.285 +0 -5 ((0,0)) cshow
3.286 +70 -5 ((width-1,0)) cshow
3.287 +grestore
3.288 +grestore
3.289 +showpage
4.1 --- a/lemon/grid_graph.h Tue Sep 02 22:32:04 2008 +0200
4.2 +++ b/lemon/grid_graph.h Mon Oct 20 12:36:02 2008 +0200
4.3 @@ -19,15 +19,11 @@
4.4 #ifndef GRID_GRAPH_H
4.5 #define GRID_GRAPH_H
4.6
4.7 -#include <iostream>
4.8 #include <lemon/core.h>
4.9 +#include <lemon/bits/graph_extender.h>
4.10 +#include <lemon/dim2.h>
4.11 #include <lemon/assert.h>
4.12
4.13 -#include <lemon/bits/base_extender.h>
4.14 -#include <lemon/bits/graph_extender.h>
4.15 -
4.16 -#include <lemon/dim2.h>
4.17 -
4.18 ///\ingroup graphs
4.19 ///\file
4.20 ///\brief GridGraph class.
4.21 @@ -41,6 +37,7 @@
4.22 typedef GridGraphBase Graph;
4.23
4.24 class Node;
4.25 + class Edge;
4.26 class Arc;
4.27
4.28 public:
4.29 @@ -49,58 +46,31 @@
4.30
4.31 protected:
4.32
4.33 - void construct(int w, int h) {
4.34 - _height = h; _width = w;
4.35 - _nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h;
4.36 - _arcLimit = _nodeNum - w;
4.37 - }
4.38 -
4.39 - Arc _down(Node n) const {
4.40 - if (n.id < _nodeNum - _width) {
4.41 - return Arc(n.id);
4.42 - } else {
4.43 - return INVALID;
4.44 - }
4.45 - }
4.46 -
4.47 - Arc _up(Node n) const {
4.48 - if (n.id >= _width) {
4.49 - return Arc(n.id - _width);
4.50 - } else {
4.51 - return INVALID;
4.52 - }
4.53 - }
4.54 -
4.55 - Arc _right(Node n) const {
4.56 - if (n.id % _width < _width - 1) {
4.57 - return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1);
4.58 - } else {
4.59 - return INVALID;
4.60 - }
4.61 - }
4.62 -
4.63 - Arc _left(Node n) const {
4.64 - if (n.id % _width > 0) {
4.65 - return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1;
4.66 - } else {
4.67 - return INVALID;
4.68 - }
4.69 + void construct(int width, int height) {
4.70 + _width = width; _height = height;
4.71 + _node_num = width * height;
4.72 + _edge_num = 2 * _node_num - width - height;
4.73 + _edge_limit = _node_num - _width;
4.74 }
4.75
4.76 public:
4.77
4.78 Node operator()(int i, int j) const {
4.79 - LEMON_ASSERT(0 <= i && i < width() &&
4.80 - 0 <= j && j < height(), "lemon::GridGraph::IndexError");
4.81 + LEMON_DEBUG(0 <= i && i < _width &&
4.82 + 0 <= j && j < _height, "Index out of range");
4.83 return Node(i + j * _width);
4.84 }
4.85
4.86 - int row(Node n) const {
4.87 - return n.id / _width;
4.88 + int col(Node n) const {
4.89 + return n._id % _width;
4.90 }
4.91
4.92 - int col(Node n) const {
4.93 - return n.id % _width;
4.94 + int row(Node n) const {
4.95 + return n._id / _width;
4.96 + }
4.97 +
4.98 + dim2::Point<int> pos(Node n) const {
4.99 + return dim2::Point<int>(col(n), row(n));
4.100 }
4.101
4.102 int width() const {
4.103 @@ -114,45 +84,86 @@
4.104 typedef True NodeNumTag;
4.105 typedef True ArcNumTag;
4.106
4.107 - int nodeNum() const { return _nodeNum; }
4.108 - int arcNum() const { return _arcNum; }
4.109 + int nodeNum() const { return _node_num; }
4.110 + int edgeNum() const { return _edge_num; }
4.111 + int arcNum() const { return 2 * _edge_num; }
4.112
4.113 - int maxNodeId() const { return nodeNum() - 1; }
4.114 - int maxArcId() const { return arcNum() - 1; }
4.115 -
4.116 - Node source(Arc e) const {
4.117 - if (e.id < _arcLimit) {
4.118 - return e.id;
4.119 + Node u(Edge edge) const {
4.120 + if (edge._id < _edge_limit) {
4.121 + return edge._id;
4.122 } else {
4.123 - return (e.id - _arcLimit) % (_width - 1) +
4.124 - (e.id - _arcLimit) / (_width - 1) * _width;
4.125 + return (edge._id - _edge_limit) % (_width - 1) +
4.126 + (edge._id - _edge_limit) / (_width - 1) * _width;
4.127 }
4.128 }
4.129
4.130 - Node target(Arc e) const {
4.131 - if (e.id < _arcLimit) {
4.132 - return e.id + _width;
4.133 + Node v(Edge edge) const {
4.134 + if (edge._id < _edge_limit) {
4.135 + return edge._id + _width;
4.136 } else {
4.137 - return (e.id - _arcLimit) % (_width - 1) +
4.138 - (e.id - _arcLimit) / (_width - 1) * _width + 1;
4.139 + return (edge._id - _edge_limit) % (_width - 1) +
4.140 + (edge._id - _edge_limit) / (_width - 1) * _width + 1;
4.141 }
4.142 }
4.143
4.144 - static int id(Node v) { return v.id; }
4.145 - static int id(Arc e) { return e.id; }
4.146 + Node source(Arc arc) const {
4.147 + return (arc._id & 1) == 1 ? u(arc) : v(arc);
4.148 + }
4.149 +
4.150 + Node target(Arc arc) const {
4.151 + return (arc._id & 1) == 1 ? v(arc) : u(arc);
4.152 + }
4.153 +
4.154 + static int id(Node node) { return node._id; }
4.155 + static int id(Edge edge) { return edge._id; }
4.156 + static int id(Arc arc) { return arc._id; }
4.157 +
4.158 + int maxNodeId() const { return _node_num - 1; }
4.159 + int maxEdgeId() const { return _edge_num - 1; }
4.160 + int maxArcId() const { return 2 * _edge_num - 1; }
4.161
4.162 static Node nodeFromId(int id) { return Node(id);}
4.163 -
4.164 + static Edge edgeFromId(int id) { return Edge(id);}
4.165 static Arc arcFromId(int id) { return Arc(id);}
4.166
4.167 - typedef True FindArcTag;
4.168 + typedef True FindEdgeTag;
4.169 +
4.170 + Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
4.171 + if (prev != INVALID) return INVALID;
4.172 + if (v._id > u._id) {
4.173 + if (v._id - u._id == _width)
4.174 + return Edge(u._id);
4.175 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
4.176 + return Edge(u._id / _width * (_width - 1) +
4.177 + u._id % _width + _edge_limit);
4.178 + }
4.179 + } else {
4.180 + if (u._id - v._id == _width)
4.181 + return Edge(v._id);
4.182 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
4.183 + return Edge(v._id / _width * (_width - 1) +
4.184 + v._id % _width + _edge_limit);
4.185 + }
4.186 + }
4.187 + return INVALID;
4.188 + }
4.189
4.190 Arc findArc(Node u, Node v, Arc prev = INVALID) const {
4.191 if (prev != INVALID) return INVALID;
4.192 - if (v.id - u.id == _width) return Arc(u.id);
4.193 - if (v.id - u.id == 1 && u.id % _width < _width - 1) {
4.194 - return Arc(u.id / _width * (_width - 1) +
4.195 - u.id % _width + _arcLimit);
4.196 + if (v._id > u._id) {
4.197 + if (v._id - u._id == _width)
4.198 + return Arc((u._id << 1) | 1);
4.199 + if (v._id - u._id == 1 && u._id % _width < _width - 1) {
4.200 + return Arc(((u._id / _width * (_width - 1) +
4.201 + u._id % _width + _edge_limit) << 1) | 1);
4.202 + }
4.203 + } else {
4.204 + if (u._id - v._id == _width)
4.205 + return Arc(v._id << 1);
4.206 + if (u._id - v._id == 1 && v._id % _width < _width - 1) {
4.207 + return Arc((v._id / _width * (_width - 1) +
4.208 + v._id % _width + _edge_limit) << 1);
4.209 + }
4.210 }
4.211 return INVALID;
4.212 }
4.213 @@ -161,127 +172,331 @@
4.214 friend class GridGraphBase;
4.215
4.216 protected:
4.217 - int id;
4.218 - Node(int _id) : id(_id) {}
4.219 + int _id;
4.220 + Node(int id) : _id(id) {}
4.221 public:
4.222 Node() {}
4.223 - Node (Invalid) { id = -1; }
4.224 - bool operator==(const Node node) const { return id == node.id; }
4.225 - bool operator!=(const Node node) const { return id != node.id; }
4.226 - bool operator<(const Node node) const { return id < node.id; }
4.227 + Node (Invalid) : _id(-1) {}
4.228 + bool operator==(const Node node) const {return _id == node._id;}
4.229 + bool operator!=(const Node node) const {return _id != node._id;}
4.230 + bool operator<(const Node node) const {return _id < node._id;}
4.231 + };
4.232 +
4.233 + class Edge {
4.234 + friend class GridGraphBase;
4.235 +
4.236 + protected:
4.237 + int _id;
4.238 +
4.239 + Edge(int id) : _id(id) {}
4.240 +
4.241 + public:
4.242 + Edge() {}
4.243 + Edge (Invalid) : _id(-1) {}
4.244 + bool operator==(const Edge edge) const {return _id == edge._id;}
4.245 + bool operator!=(const Edge edge) const {return _id != edge._id;}
4.246 + bool operator<(const Edge edge) const {return _id < edge._id;}
4.247 };
4.248
4.249 class Arc {
4.250 friend class GridGraphBase;
4.251
4.252 protected:
4.253 - int id;
4.254 - Arc(int _id) : id(_id) {}
4.255 + int _id;
4.256 +
4.257 + Arc(int id) : _id(id) {}
4.258 +
4.259 public:
4.260 Arc() {}
4.261 - Arc (Invalid) { id = -1; }
4.262 - bool operator==(const Arc arc) const { return id == arc.id; }
4.263 - bool operator!=(const Arc arc) const { return id != arc.id; }
4.264 - bool operator<(const Arc arc) const { return id < arc.id; }
4.265 + Arc (Invalid) : _id(-1) {}
4.266 + operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
4.267 + bool operator==(const Arc arc) const {return _id == arc._id;}
4.268 + bool operator!=(const Arc arc) const {return _id != arc._id;}
4.269 + bool operator<(const Arc arc) const {return _id < arc._id;}
4.270 };
4.271
4.272 + static bool direction(Arc arc) {
4.273 + return (arc._id & 1) == 1;
4.274 + }
4.275 +
4.276 + static Arc direct(Edge edge, bool dir) {
4.277 + return Arc((edge._id << 1) | (dir ? 1 : 0));
4.278 + }
4.279 +
4.280 void first(Node& node) const {
4.281 - node.id = nodeNum() - 1;
4.282 + node._id = _node_num - 1;
4.283 }
4.284
4.285 static void next(Node& node) {
4.286 - --node.id;
4.287 + --node._id;
4.288 + }
4.289 +
4.290 + void first(Edge& edge) const {
4.291 + edge._id = _edge_num - 1;
4.292 + }
4.293 +
4.294 + static void next(Edge& edge) {
4.295 + --edge._id;
4.296 }
4.297
4.298 void first(Arc& arc) const {
4.299 - arc.id = arcNum() - 1;
4.300 + arc._id = 2 * _edge_num - 1;
4.301 }
4.302
4.303 static void next(Arc& arc) {
4.304 - --arc.id;
4.305 + --arc._id;
4.306 }
4.307
4.308 void firstOut(Arc& arc, const Node& node) const {
4.309 - if (node.id < _nodeNum - _width) {
4.310 - arc.id = node.id;
4.311 - } else if (node.id % _width < _width - 1) {
4.312 - arc.id = _arcLimit + node.id % _width +
4.313 - (node.id / _width) * (_width - 1);
4.314 + if (node._id % _width < _width - 1) {
4.315 + arc._id = (_edge_limit + node._id % _width +
4.316 + (node._id / _width) * (_width - 1)) << 1 | 1;
4.317 + return;
4.318 + }
4.319 + if (node._id < _node_num - _width) {
4.320 + arc._id = node._id << 1 | 1;
4.321 + return;
4.322 + }
4.323 + if (node._id % _width > 0) {
4.324 + arc._id = (_edge_limit + node._id % _width +
4.325 + (node._id / _width) * (_width - 1) - 1) << 1;
4.326 + return;
4.327 + }
4.328 + if (node._id >= _width) {
4.329 + arc._id = (node._id - _width) << 1;
4.330 + return;
4.331 + }
4.332 + arc._id = -1;
4.333 + }
4.334 +
4.335 + void nextOut(Arc& arc) const {
4.336 + int nid = arc._id >> 1;
4.337 + if ((arc._id & 1) == 1) {
4.338 + if (nid >= _edge_limit) {
4.339 + nid = (nid - _edge_limit) % (_width - 1) +
4.340 + (nid - _edge_limit) / (_width - 1) * _width;
4.341 + if (nid < _node_num - _width) {
4.342 + arc._id = nid << 1 | 1;
4.343 + return;
4.344 + }
4.345 + }
4.346 + if (nid % _width > 0) {
4.347 + arc._id = (_edge_limit + nid % _width +
4.348 + (nid / _width) * (_width - 1) - 1) << 1;
4.349 + return;
4.350 + }
4.351 + if (nid >= _width) {
4.352 + arc._id = (nid - _width) << 1;
4.353 + return;
4.354 + }
4.355 } else {
4.356 - arc.id = -1;
4.357 + if (nid >= _edge_limit) {
4.358 + nid = (nid - _edge_limit) % (_width - 1) +
4.359 + (nid - _edge_limit) / (_width - 1) * _width + 1;
4.360 + if (nid >= _width) {
4.361 + arc._id = (nid - _width) << 1;
4.362 + return;
4.363 + }
4.364 + }
4.365 + }
4.366 + arc._id = -1;
4.367 + }
4.368 +
4.369 + void firstIn(Arc& arc, const Node& node) const {
4.370 + if (node._id % _width < _width - 1) {
4.371 + arc._id = (_edge_limit + node._id % _width +
4.372 + (node._id / _width) * (_width - 1)) << 1;
4.373 + return;
4.374 + }
4.375 + if (node._id < _node_num - _width) {
4.376 + arc._id = node._id << 1;
4.377 + return;
4.378 + }
4.379 + if (node._id % _width > 0) {
4.380 + arc._id = (_edge_limit + node._id % _width +
4.381 + (node._id / _width) * (_width - 1) - 1) << 1 | 1;
4.382 + return;
4.383 + }
4.384 + if (node._id >= _width) {
4.385 + arc._id = (node._id - _width) << 1 | 1;
4.386 + return;
4.387 + }
4.388 + arc._id = -1;
4.389 + }
4.390 +
4.391 + void nextIn(Arc& arc) const {
4.392 + int nid = arc._id >> 1;
4.393 + if ((arc._id & 1) == 0) {
4.394 + if (nid >= _edge_limit) {
4.395 + nid = (nid - _edge_limit) % (_width - 1) +
4.396 + (nid - _edge_limit) / (_width - 1) * _width;
4.397 + if (nid < _node_num - _width) {
4.398 + arc._id = nid << 1;
4.399 + return;
4.400 + }
4.401 + }
4.402 + if (nid % _width > 0) {
4.403 + arc._id = (_edge_limit + nid % _width +
4.404 + (nid / _width) * (_width - 1) - 1) << 1 | 1;
4.405 + return;
4.406 + }
4.407 + if (nid >= _width) {
4.408 + arc._id = (nid - _width) << 1 | 1;
4.409 + return;
4.410 + }
4.411 + } else {
4.412 + if (nid >= _edge_limit) {
4.413 + nid = (nid - _edge_limit) % (_width - 1) +
4.414 + (nid - _edge_limit) / (_width - 1) * _width + 1;
4.415 + if (nid >= _width) {
4.416 + arc._id = (nid - _width) << 1 | 1;
4.417 + return;
4.418 + }
4.419 + }
4.420 + }
4.421 + arc._id = -1;
4.422 + }
4.423 +
4.424 + void firstInc(Edge& edge, bool& dir, const Node& node) const {
4.425 + if (node._id % _width < _width - 1) {
4.426 + edge._id = _edge_limit + node._id % _width +
4.427 + (node._id / _width) * (_width - 1);
4.428 + dir = true;
4.429 + return;
4.430 + }
4.431 + if (node._id < _node_num - _width) {
4.432 + edge._id = node._id;
4.433 + dir = true;
4.434 + return;
4.435 + }
4.436 + if (node._id % _width > 0) {
4.437 + edge._id = _edge_limit + node._id % _width +
4.438 + (node._id / _width) * (_width - 1) - 1;
4.439 + dir = false;
4.440 + return;
4.441 + }
4.442 + if (node._id >= _width) {
4.443 + edge._id = node._id - _width;
4.444 + dir = false;
4.445 + return;
4.446 + }
4.447 + edge._id = -1;
4.448 + dir = true;
4.449 + }
4.450 +
4.451 + void nextInc(Edge& edge, bool& dir) const {
4.452 + int nid = edge._id;
4.453 + if (dir) {
4.454 + if (nid >= _edge_limit) {
4.455 + nid = (nid - _edge_limit) % (_width - 1) +
4.456 + (nid - _edge_limit) / (_width - 1) * _width;
4.457 + if (nid < _node_num - _width) {
4.458 + edge._id = nid;
4.459 + return;
4.460 + }
4.461 + }
4.462 + if (nid % _width > 0) {
4.463 + edge._id = _edge_limit + nid % _width +
4.464 + (nid / _width) * (_width - 1) - 1;
4.465 + dir = false;
4.466 + return;
4.467 + }
4.468 + if (nid >= _width) {
4.469 + edge._id = nid - _width;
4.470 + dir = false;
4.471 + return;
4.472 + }
4.473 + } else {
4.474 + if (nid >= _edge_limit) {
4.475 + nid = (nid - _edge_limit) % (_width - 1) +
4.476 + (nid - _edge_limit) / (_width - 1) * _width + 1;
4.477 + if (nid >= _width) {
4.478 + edge._id = nid - _width;
4.479 + return;
4.480 + }
4.481 + }
4.482 + }
4.483 + edge._id = -1;
4.484 + dir = true;
4.485 + }
4.486 +
4.487 + Arc right(Node n) const {
4.488 + if (n._id % _width < _width - 1) {
4.489 + return Arc(((_edge_limit + n._id % _width +
4.490 + (n._id / _width) * (_width - 1)) << 1) | 1);
4.491 + } else {
4.492 + return INVALID;
4.493 }
4.494 }
4.495
4.496 - void nextOut(Arc& arc) const {
4.497 - if (arc.id >= _arcLimit) {
4.498 - arc.id = -1;
4.499 - } else if (arc.id % _width < _width - 1) {
4.500 - arc.id = _arcLimit + arc.id % _width +
4.501 - (arc.id / _width) * (_width - 1);
4.502 + Arc left(Node n) const {
4.503 + if (n._id % _width > 0) {
4.504 + return Arc((_edge_limit + n._id % _width +
4.505 + (n._id / _width) * (_width - 1) - 1) << 1);
4.506 } else {
4.507 - arc.id = -1;
4.508 + return INVALID;
4.509 }
4.510 }
4.511
4.512 - void firstIn(Arc& arc, const Node& node) const {
4.513 - if (node.id >= _width) {
4.514 - arc.id = node.id - _width;
4.515 - } else if (node.id % _width > 0) {
4.516 - arc.id = _arcLimit + node.id % _width +
4.517 - (node.id / _width) * (_width - 1) - 1;
4.518 + Arc up(Node n) const {
4.519 + if (n._id < _edge_limit) {
4.520 + return Arc((n._id << 1) | 1);
4.521 } else {
4.522 - arc.id = -1;
4.523 + return INVALID;
4.524 }
4.525 }
4.526
4.527 - void nextIn(Arc& arc) const {
4.528 - if (arc.id >= _arcLimit) {
4.529 - arc.id = -1;
4.530 - } else if (arc.id % _width > 0) {
4.531 - arc.id = _arcLimit + arc.id % _width +
4.532 - (arc.id / _width + 1) * (_width - 1) - 1;
4.533 + Arc down(Node n) const {
4.534 + if (n._id >= _width) {
4.535 + return Arc((n._id - _width) << 1);
4.536 } else {
4.537 - arc.id = -1;
4.538 + return INVALID;
4.539 }
4.540 }
4.541
4.542 private:
4.543 int _width, _height;
4.544 - int _nodeNum, _arcNum;
4.545 - int _arcLimit;
4.546 + int _node_num, _edge_num;
4.547 + int _edge_limit;
4.548 };
4.549
4.550 - typedef GraphExtender<UndirDigraphExtender<GridGraphBase> >
4.551 - ExtendedGridGraphBase;
4.552 +
4.553 + typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
4.554
4.555 /// \ingroup graphs
4.556 ///
4.557 /// \brief Grid graph class
4.558 ///
4.559 /// This class implements a special graph type. The nodes of the
4.560 - /// graph can be indiced by two integer \c (i,j) value where \c i
4.561 - /// is in the \c [0,width) range and j is in the [0, height) range.
4.562 - /// Two nodes are connected in the graph if the indices differ only
4.563 - /// on one position and only one is the difference.
4.564 + /// graph can be indexed by two integer \c (i,j) value where \c i is
4.565 + /// in the \c [0..width()-1] range and j is in the \c
4.566 + /// [0..height()-1] range. Two nodes are connected in the graph if
4.567 + /// the indexes differ exactly on one position and exactly one is
4.568 + /// the difference. The nodes of the graph be indexed by position
4.569 + /// with \c operator()() function. The positions of the nodes can be
4.570 + /// get with \c pos(), \c col() and \c row() members. The outgoing
4.571 + /// arcs can be retrieved with the \c right(), \c up(), \c left()
4.572 + /// and \c down() functions, where the bottom-left corner is the
4.573 + /// origin.
4.574 ///
4.575 /// \image html grid_graph.png
4.576 - /// \image latex grid_graph.eps "Grid graph" width=\textwidth
4.577 + /// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num
4.578 ///
4.579 - /// The graph can be indiced in the following way:
4.580 + /// A short example about the basic usage:
4.581 ///\code
4.582 - /// GridGraph gr(w, h);
4.583 - /// GridGraph::NodeMap<int> val(gr);
4.584 - /// for (int i = 0; i < gr.width(); ++i) {
4.585 - /// for (int j = 0; j < gr.height(); ++j) {
4.586 - /// val[gr(i, j)] = i + j;
4.587 + /// GridGraph graph(rows, cols);
4.588 + /// GridGraph::NodeMap<int> val(graph);
4.589 + /// for (int i = 0; i < graph.width(); ++i) {
4.590 + /// for (int j = 0; j < graph.height(); ++j) {
4.591 + /// val[graph(i, j)] = i + j;
4.592 /// }
4.593 /// }
4.594 ///\endcode
4.595 ///
4.596 - /// This graph type is fully conform to the \ref concepts::Graph
4.597 - /// "Undirected Graph" concept, and it also has an important extra
4.598 - /// feature that its maps are real \ref concepts::ReferenceMap
4.599 - /// "reference map"s.
4.600 + /// The graph type is fully conform to the \ref concepts::Graph
4.601 + /// "Graph" concept, and it also has an important extra feature
4.602 + /// that its maps are real \ref concepts::ReferenceMap "reference
4.603 + /// map"s.
4.604 class GridGraph : public ExtendedGridGraphBase {
4.605 public:
4.606
4.607 @@ -292,17 +507,47 @@
4.608 /// Map to get the indices of the nodes as dim2::Point<int>.
4.609 class IndexMap {
4.610 public:
4.611 - /// The key type of the map
4.612 + /// \brief The key type of the map
4.613 typedef GridGraph::Node Key;
4.614 - /// The value type of the map
4.615 + /// \brief The value type of the map
4.616 typedef dim2::Point<int> Value;
4.617
4.618 + /// \brief Constructor
4.619 + ///
4.620 /// Constructor
4.621 IndexMap(const GridGraph& graph) : _graph(graph) {}
4.622
4.623 - /// The subscript operator
4.624 - Value operator[](const Key& key) const {
4.625 - return dim2::Point<int>(_graph.row(key), _graph.col(key));
4.626 + /// \brief The subscript operator
4.627 + ///
4.628 + /// The subscript operator.
4.629 + Value operator[](Key key) const {
4.630 + return _graph.pos(key);
4.631 + }
4.632 +
4.633 + private:
4.634 + const GridGraph& _graph;
4.635 + };
4.636 +
4.637 + /// \brief Map to get the column of the nodes.
4.638 + ///
4.639 + /// Map to get the column of the nodes.
4.640 + class ColMap {
4.641 + public:
4.642 + /// \brief The key type of the map
4.643 + typedef GridGraph::Node Key;
4.644 + /// \brief The value type of the map
4.645 + typedef int Value;
4.646 +
4.647 + /// \brief Constructor
4.648 + ///
4.649 + /// Constructor
4.650 + ColMap(const GridGraph& graph) : _graph(graph) {}
4.651 +
4.652 + /// \brief The subscript operator
4.653 + ///
4.654 + /// The subscript operator.
4.655 + Value operator[](Key key) const {
4.656 + return _graph.col(key);
4.657 }
4.658
4.659 private:
4.660 @@ -314,16 +559,20 @@
4.661 /// Map to get the row of the nodes.
4.662 class RowMap {
4.663 public:
4.664 - /// The key type of the map
4.665 + /// \brief The key type of the map
4.666 typedef GridGraph::Node Key;
4.667 - /// The value type of the map
4.668 + /// \brief The value type of the map
4.669 typedef int Value;
4.670
4.671 + /// \brief Constructor
4.672 + ///
4.673 /// Constructor
4.674 RowMap(const GridGraph& graph) : _graph(graph) {}
4.675
4.676 - /// The subscript operator
4.677 - Value operator[](const Key& key) const {
4.678 + /// \brief The subscript operator
4.679 + ///
4.680 + /// The subscript operator.
4.681 + Value operator[](Key key) const {
4.682 return _graph.row(key);
4.683 }
4.684
4.685 @@ -331,38 +580,17 @@
4.686 const GridGraph& _graph;
4.687 };
4.688
4.689 - /// \brief Map to get the column of the nodes.
4.690 - ///
4.691 - /// Map to get the column of the nodes.
4.692 - class ColMap {
4.693 - public:
4.694 - /// The key type of the map
4.695 - typedef GridGraph::Node Key;
4.696 - /// The value type of the map
4.697 - typedef int Value;
4.698 -
4.699 - /// Constructor
4.700 - ColMap(const GridGraph& graph) : _graph(graph) {}
4.701 -
4.702 - /// The subscript operator
4.703 - Value operator[](const Key& key) const {
4.704 - return _graph.col(key);
4.705 - }
4.706 -
4.707 - private:
4.708 - const GridGraph& _graph;
4.709 - };
4.710 -
4.711 /// \brief Constructor
4.712 ///
4.713 - /// Constructor.
4.714 - /// \param width The width of the grid.
4.715 - /// \param height The height of the grid.
4.716 + /// Construct a grid graph with given size.
4.717 GridGraph(int width, int height) { construct(width, height); }
4.718
4.719 /// \brief Resize the graph
4.720 ///
4.721 - /// Resize the grid.
4.722 + /// Resize the graph. The function will fully destroy and rebuild
4.723 + /// the graph. This cause that the maps of the graph will
4.724 + /// reallocated automatically and the previous values will be
4.725 + /// lost.
4.726 void resize(int width, int height) {
4.727 Parent::notifier(Arc()).clear();
4.728 Parent::notifier(Edge()).clear();
4.729 @@ -380,6 +608,13 @@
4.730 return Parent::operator()(i, j);
4.731 }
4.732
4.733 + /// \brief Gives back the column index of the node.
4.734 + ///
4.735 + /// Gives back the column index of the node.
4.736 + int col(Node n) const {
4.737 + return Parent::col(n);
4.738 + }
4.739 +
4.740 /// \brief Gives back the row index of the node.
4.741 ///
4.742 /// Gives back the row index of the node.
4.743 @@ -387,85 +622,81 @@
4.744 return Parent::row(n);
4.745 }
4.746
4.747 - /// \brief Gives back the column index of the node.
4.748 + /// \brief Gives back the position of the node.
4.749 ///
4.750 - /// Gives back the column index of the node.
4.751 - int col(Node n) const {
4.752 - return Parent::col(n);
4.753 + /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
4.754 + dim2::Point<int> pos(Node n) const {
4.755 + return Parent::pos(n);
4.756 }
4.757
4.758 - /// \brief Gives back the width of the grid.
4.759 + /// \brief Gives back the number of the columns.
4.760 ///
4.761 - /// Gives back the width of the grid.
4.762 + /// Gives back the number of the columns.
4.763 int width() const {
4.764 return Parent::width();
4.765 }
4.766
4.767 - /// \brief Gives back the height of the grid.
4.768 + /// \brief Gives back the number of the rows.
4.769 ///
4.770 - /// Gives back the height of the grid.
4.771 + /// Gives back the number of the rows.
4.772 int height() const {
4.773 return Parent::height();
4.774 }
4.775
4.776 + /// \brief Gives back the arc goes right from the node.
4.777 + ///
4.778 + /// Gives back the arc goes right from the node. If there is not
4.779 + /// outgoing arc then it gives back INVALID.
4.780 + Arc right(Node n) const {
4.781 + return Parent::right(n);
4.782 + }
4.783 +
4.784 + /// \brief Gives back the arc goes left from the node.
4.785 + ///
4.786 + /// Gives back the arc goes left from the node. If there is not
4.787 + /// outgoing arc then it gives back INVALID.
4.788 + Arc left(Node n) const {
4.789 + return Parent::left(n);
4.790 + }
4.791 +
4.792 + /// \brief Gives back the arc goes up from the node.
4.793 + ///
4.794 + /// Gives back the arc goes up from the node. If there is not
4.795 + /// outgoing arc then it gives back INVALID.
4.796 + Arc up(Node n) const {
4.797 + return Parent::up(n);
4.798 + }
4.799 +
4.800 /// \brief Gives back the arc goes down from the node.
4.801 ///
4.802 /// Gives back the arc goes down from the node. If there is not
4.803 - /// outgoing arc then it gives back \c INVALID.
4.804 + /// outgoing arc then it gives back INVALID.
4.805 Arc down(Node n) const {
4.806 - Edge e = _down(n);
4.807 - return e != INVALID ? direct(e, true) : INVALID;
4.808 + return Parent::down(n);
4.809 }
4.810
4.811 - /// \brief Gives back the arc goes up from the node.
4.812 + /// \brief Index map of the grid graph
4.813 ///
4.814 - /// Gives back the arc goes up from the node. If there is not
4.815 - /// outgoing arc then it gives back \c INVALID.
4.816 - Arc up(Node n) const {
4.817 - Edge e = _up(n);
4.818 - return e != INVALID ? direct(e, false) : INVALID;
4.819 + /// Just returns an IndexMap for the grid graph.
4.820 + IndexMap indexMap() const {
4.821 + return IndexMap(*this);
4.822 }
4.823
4.824 - /// \brief Gives back the arc goes right from the node.
4.825 + /// \brief Row map of the grid graph
4.826 ///
4.827 - /// Gives back the arc goes right from the node. If there is not
4.828 - /// outgoing arc then it gives back \c INVALID.
4.829 - Arc right(Node n) const {
4.830 - Edge e = _right(n);
4.831 - return e != INVALID ? direct(e, true) : INVALID;
4.832 + /// Just returns a RowMap for the grid graph.
4.833 + RowMap rowMap() const {
4.834 + return RowMap(*this);
4.835 }
4.836
4.837 - /// \brief Gives back the arc goes left from the node.
4.838 + /// \brief Column map of the grid graph
4.839 ///
4.840 - /// Gives back the arc goes left from the node. If there is not
4.841 - /// outgoing arc then it gives back \c INVALID.
4.842 - Arc left(Node n) const {
4.843 - Edge e = _left(n);
4.844 - return e != INVALID ? direct(e, false) : INVALID;
4.845 + /// Just returns a ColMap for the grid graph.
4.846 + ColMap colMap() const {
4.847 + return ColMap(*this);
4.848 }
4.849
4.850 - }; // class GridGraph
4.851 + };
4.852
4.853 - /// \brief Index map of the grid graph
4.854 - ///
4.855 - /// Just returns an IndexMap for the grid graph.
4.856 - inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
4.857 - return GridGraph::IndexMap(graph);
4.858 - }
4.859 -
4.860 - /// \brief Row map of the grid graph
4.861 - ///
4.862 - /// Just returns a RowMap for the grid graph.
4.863 - inline GridGraph::RowMap rowMap(const GridGraph& graph) {
4.864 - return GridGraph::RowMap(graph);
4.865 - }
4.866 -
4.867 - /// \brief Column map of the grid graph
4.868 - ///
4.869 - /// Just returns a ColMap for the grid graph.
4.870 - inline GridGraph::ColMap colMap(const GridGraph& graph) {
4.871 - return GridGraph::ColMap(graph);
4.872 - }
4.873 }
4.874 -
4.875 -#endif // GRID_GRAPH_H
4.876 +#endif
5.1 --- a/test/graph_test.cc Tue Sep 02 22:32:04 2008 +0200
5.2 +++ b/test/graph_test.cc Mon Oct 20 12:36:02 2008 +0200
5.3 @@ -126,6 +126,7 @@
5.4 }
5.5 // { // Checking FullGraph
5.6 // checkConcept<Graph, FullGraph>();
5.7 +// checkGraphIterators<FullGraph>();
5.8 // }
5.9 { // Checking GridGraph
5.10 checkConcept<Graph, GridGraph>();
5.11 @@ -186,76 +187,83 @@
5.12 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
5.13 }
5.14
5.15 -void checkGridGraph(const GridGraph& g, int w, int h) {
5.16 - check(g.width() == w, "Wrong width");
5.17 - check(g.height() == h, "Wrong height");
5.18 +void checkGridGraph(int width, int height) {
5.19 + typedef GridGraph Graph;
5.20 + GRAPH_TYPEDEFS(Graph);
5.21 + Graph G(width, height);
5.22
5.23 - for (int i = 0; i < w; ++i) {
5.24 - for (int j = 0; j < h; ++j) {
5.25 - check(g.col(g(i, j)) == i, "Wrong col");
5.26 - check(g.row(g(i, j)) == j, "Wrong row");
5.27 + check(G.width() == width, "Wrong row number");
5.28 + check(G.height() == height, "Wrong column number");
5.29 +
5.30 + for (int i = 0; i < width; ++i) {
5.31 + for (int j = 0; j < height; ++j) {
5.32 + check(G.col(G(i, j)) == i, "Wrong column");
5.33 + check(G.row(G(i, j)) == j, "Wrong row");
5.34 + check(G.pos(G(i, j)).x == i, "Wrong column");
5.35 + check(G.pos(G(i, j)).y == j, "Wrong row");
5.36 }
5.37 }
5.38
5.39 - for (int i = 0; i < w; ++i) {
5.40 - for (int j = 0; j < h - 1; ++j) {
5.41 - check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
5.42 - check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
5.43 + for (int j = 0; j < height; ++j) {
5.44 + for (int i = 0; i < width - 1; ++i) {
5.45 + check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
5.46 + check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
5.47 }
5.48 - check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
5.49 + check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
5.50 }
5.51
5.52 - for (int i = 0; i < w; ++i) {
5.53 - for (int j = 1; j < h; ++j) {
5.54 - check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
5.55 - check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
5.56 + for (int j = 0; j < height; ++j) {
5.57 + for (int i = 1; i < width; ++i) {
5.58 + check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
5.59 + check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
5.60 }
5.61 - check(g.up(g(i, 0)) == INVALID, "Wrong up");
5.62 + check(G.left(G(0, j)) == INVALID, "Wrong left");
5.63 }
5.64
5.65 - for (int j = 0; j < h; ++j) {
5.66 - for (int i = 0; i < w - 1; ++i) {
5.67 - check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
5.68 - check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
5.69 + for (int i = 0; i < width; ++i) {
5.70 + for (int j = 0; j < height - 1; ++j) {
5.71 + check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
5.72 + check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
5.73 }
5.74 - check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
5.75 + check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
5.76 }
5.77
5.78 - for (int j = 0; j < h; ++j) {
5.79 - for (int i = 1; i < w; ++i) {
5.80 - check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
5.81 - check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
5.82 + for (int i = 0; i < width; ++i) {
5.83 + for (int j = 1; j < height; ++j) {
5.84 + check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
5.85 + check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
5.86 }
5.87 - check(g.left(g(0, j)) == INVALID, "Wrong left");
5.88 + check(G.down(G(i, 0)) == INVALID, "Wrong down");
5.89 }
5.90
5.91 - checkGraphNodeList(g, w*h);
5.92 - checkGraphArcList(g, 2*(2*w*h-w-h));
5.93 - checkGraphEdgeList(g, 2*w*h-w-h);
5.94 + checkGraphNodeList(G, width * height);
5.95 + checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
5.96 + checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
5.97
5.98 - checkGraphOutArcList(g, g(0,0), 2);
5.99 - checkGraphOutArcList(g, g(0,1), 3);
5.100 - checkGraphOutArcList(g, g(w-2,h-2), 4);
5.101 + for (NodeIt n(G); n != INVALID; ++n) {
5.102 + int nb = 4;
5.103 + if (G.col(n) == 0) --nb;
5.104 + if (G.col(n) == width - 1) --nb;
5.105 + if (G.row(n) == 0) --nb;
5.106 + if (G.row(n) == height - 1) --nb;
5.107
5.108 - checkGraphInArcList(g, g(0,0), 2);
5.109 - checkGraphInArcList(g, g(0,1), 3);
5.110 - checkGraphInArcList(g, g(w-2,h-2), 4);
5.111 + checkGraphOutArcList(G, n, nb);
5.112 + checkGraphInArcList(G, n, nb);
5.113 + checkGraphIncEdgeList(G, n, nb);
5.114 + }
5.115
5.116 - checkGraphIncEdgeList(g, g(0,0), 2);
5.117 - checkGraphIncEdgeList(g, g(0,1), 3);
5.118 - checkGraphIncEdgeList(g, g(w-2,h-2), 4);
5.119 + checkArcDirections(G);
5.120
5.121 - checkGraphConArcList(g, 2*(2*w*h-w-h));
5.122 - checkGraphConEdgeList(g, 2*w*h-w-h);
5.123 + checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
5.124 + checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
5.125
5.126 - checkArcDirections(g);
5.127 + checkNodeIds(G);
5.128 + checkArcIds(G);
5.129 + checkEdgeIds(G);
5.130 + checkGraphNodeMap(G);
5.131 + checkGraphArcMap(G);
5.132 + checkGraphEdgeMap(G);
5.133
5.134 - checkNodeIds(g);
5.135 - checkArcIds(g);
5.136 - checkEdgeIds(g);
5.137 - checkGraphNodeMap(g);
5.138 - checkGraphArcMap(g);
5.139 - checkGraphEdgeMap(g);
5.140 }
5.141
5.142 void checkGraphs() {
5.143 @@ -273,8 +281,11 @@
5.144 // checkGraphEdgeList(g, 10);
5.145 // }
5.146 { // Checking GridGraph
5.147 - GridGraph g(5, 6);
5.148 - checkGridGraph(g, 5, 6);
5.149 + checkGridGraph(5, 8);
5.150 + checkGridGraph(8, 5);
5.151 + checkGridGraph(5, 5);
5.152 + checkGridGraph(0, 0);
5.153 + checkGridGraph(1, 1);
5.154 }
5.155 }
5.156