Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 22 Oct 2008 22:14:00 +0100 (2008-10-22)
changeset 337560e4b6d020d
parent 333 9c2a532aa5ef
parent 336 052cecabcb71
child 338 b77fb8c32707
Merge
doc/Makefile.am
lemon/Makefile.am
     1.1 --- a/doc/CMakeLists.txt	Wed Oct 22 14:41:18 2008 +0100
     1.2 +++ b/doc/CMakeLists.txt	Wed Oct 22 22:14:00 2008 +0100
     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	Wed Oct 22 14:41:18 2008 +0100
     2.2 +++ b/doc/Makefile.am	Wed Oct 22 22:14:00 2008 +0100
     2.3 @@ -14,6 +14,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	Wed Oct 22 22:14:00 2008 +0100
     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/Makefile.am	Wed Oct 22 14:41:18 2008 +0100
     4.2 +++ b/lemon/Makefile.am	Wed Oct 22 22:14:00 2008 +0100
     4.3 @@ -29,6 +29,7 @@
     4.4          lemon/dim2.h \
     4.5  	lemon/error.h \
     4.6          lemon/graph_to_eps.h \
     4.7 +        lemon/grid_graph.h \
     4.8  	lemon/kruskal.h \
     4.9  	lemon/lgf_reader.h \
    4.10  	lemon/lgf_writer.h \
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/lemon/grid_graph.h	Wed Oct 22 22:14:00 2008 +0100
     5.3 @@ -0,0 +1,703 @@
     5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
     5.5 + *
     5.6 + * This file is a part of LEMON, a generic C++ optimization library.
     5.7 + *
     5.8 + * Copyright (C) 2003-2008
     5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    5.11 + *
    5.12 + * Permission to use, modify and distribute this software is granted
    5.13 + * provided that this copyright notice appears in all copies. For
    5.14 + * precise terms see the accompanying LICENSE file.
    5.15 + *
    5.16 + * This software is provided "AS IS" with no warranty of any kind,
    5.17 + * express or implied, and with no claim as to its suitability for any
    5.18 + * purpose.
    5.19 + *
    5.20 + */
    5.21 +
    5.22 +#ifndef GRID_GRAPH_H
    5.23 +#define GRID_GRAPH_H
    5.24 +
    5.25 +#include <lemon/core.h>
    5.26 +#include <lemon/bits/graph_extender.h>
    5.27 +#include <lemon/dim2.h>
    5.28 +#include <lemon/assert.h>
    5.29 +
    5.30 +///\ingroup graphs
    5.31 +///\file
    5.32 +///\brief GridGraph class.
    5.33 +
    5.34 +namespace lemon {
    5.35 +
    5.36 +  class GridGraphBase {
    5.37 +
    5.38 +  public:
    5.39 +
    5.40 +    typedef GridGraphBase Graph;
    5.41 +
    5.42 +    class Node;
    5.43 +    class Edge;
    5.44 +    class Arc;
    5.45 +
    5.46 +  public:
    5.47 +
    5.48 +    GridGraphBase() {}
    5.49 +
    5.50 +  protected:
    5.51 +
    5.52 +    void construct(int width, int height) {
    5.53 +       _width = width; _height = height;
    5.54 +      _node_num = width * height;
    5.55 +      _edge_num = 2 * _node_num - width - height;
    5.56 +      _edge_limit = _node_num - _width;
    5.57 +    }
    5.58 +
    5.59 +  public:
    5.60 +
    5.61 +    Node operator()(int i, int j) const {
    5.62 +      LEMON_DEBUG(0 <= i && i < _width &&
    5.63 +                  0 <= j  && j < _height, "Index out of range");
    5.64 +      return Node(i + j * _width);
    5.65 +    }
    5.66 +
    5.67 +    int col(Node n) const {
    5.68 +      return n._id % _width;
    5.69 +    }
    5.70 +
    5.71 +    int row(Node n) const {
    5.72 +      return n._id / _width;
    5.73 +    }
    5.74 +
    5.75 +    dim2::Point<int> pos(Node n) const {
    5.76 +      return dim2::Point<int>(col(n), row(n));
    5.77 +    }
    5.78 +
    5.79 +    int width() const {
    5.80 +      return _width;
    5.81 +    }
    5.82 +
    5.83 +    int height() const {
    5.84 +      return _height;
    5.85 +    }
    5.86 +
    5.87 +    typedef True NodeNumTag;
    5.88 +    typedef True ArcNumTag;
    5.89 +
    5.90 +    int nodeNum() const { return _node_num; }
    5.91 +    int edgeNum() const { return _edge_num; }
    5.92 +    int arcNum() const { return 2 * _edge_num; }
    5.93 +
    5.94 +    Node u(Edge edge) const {
    5.95 +      if (edge._id < _edge_limit) {
    5.96 +        return edge._id;
    5.97 +      } else {
    5.98 +        return (edge._id - _edge_limit) % (_width - 1) +
    5.99 +          (edge._id - _edge_limit) / (_width - 1) * _width;
   5.100 +      }
   5.101 +    }
   5.102 +
   5.103 +    Node v(Edge edge) const {
   5.104 +      if (edge._id < _edge_limit) {
   5.105 +        return edge._id + _width;
   5.106 +      } else {
   5.107 +        return (edge._id - _edge_limit) % (_width - 1) +
   5.108 +          (edge._id - _edge_limit) / (_width - 1) * _width + 1;
   5.109 +      }
   5.110 +    }
   5.111 +
   5.112 +    Node source(Arc arc) const {
   5.113 +      return (arc._id & 1) == 1 ? u(arc) : v(arc);
   5.114 +    }
   5.115 +
   5.116 +    Node target(Arc arc) const {
   5.117 +      return (arc._id & 1) == 1 ? v(arc) : u(arc);
   5.118 +    }
   5.119 +
   5.120 +    static int id(Node node) { return node._id; }
   5.121 +    static int id(Edge edge) { return edge._id; }
   5.122 +    static int id(Arc arc) { return arc._id; }
   5.123 +
   5.124 +    int maxNodeId() const { return _node_num - 1; }
   5.125 +    int maxEdgeId() const { return _edge_num - 1; }
   5.126 +    int maxArcId() const { return 2 * _edge_num - 1; }
   5.127 +
   5.128 +    static Node nodeFromId(int id) { return Node(id);}
   5.129 +    static Edge edgeFromId(int id) { return Edge(id);}
   5.130 +    static Arc arcFromId(int id) { return Arc(id);}
   5.131 +
   5.132 +    typedef True FindEdgeTag;
   5.133 +
   5.134 +    Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
   5.135 +      if (prev != INVALID) return INVALID;
   5.136 +      if (v._id > u._id) {
   5.137 +        if (v._id - u._id == _width)
   5.138 +          return Edge(u._id);
   5.139 +        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
   5.140 +          return Edge(u._id / _width * (_width - 1) +
   5.141 +                      u._id % _width + _edge_limit);
   5.142 +        }
   5.143 +      } else {
   5.144 +        if (u._id - v._id == _width)
   5.145 +          return Edge(v._id);
   5.146 +        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
   5.147 +          return Edge(v._id / _width * (_width - 1) +
   5.148 +                      v._id % _width + _edge_limit);
   5.149 +        }
   5.150 +      }
   5.151 +      return INVALID;
   5.152 +    }
   5.153 +
   5.154 +    Arc findArc(Node u, Node v, Arc prev = INVALID) const {
   5.155 +      if (prev != INVALID) return INVALID;
   5.156 +      if (v._id > u._id) {
   5.157 +        if (v._id - u._id == _width)
   5.158 +          return Arc((u._id << 1) | 1);
   5.159 +        if (v._id - u._id == 1 && u._id % _width < _width - 1) {
   5.160 +          return Arc(((u._id / _width * (_width - 1) +
   5.161 +                       u._id % _width + _edge_limit) << 1) | 1);
   5.162 +        }
   5.163 +      } else {
   5.164 +        if (u._id - v._id == _width)
   5.165 +          return Arc(v._id << 1);
   5.166 +        if (u._id - v._id == 1 && v._id % _width < _width - 1) {
   5.167 +          return Arc((v._id / _width * (_width - 1) +
   5.168 +                       v._id % _width + _edge_limit) << 1);
   5.169 +        }
   5.170 +      }
   5.171 +      return INVALID;
   5.172 +    }
   5.173 +
   5.174 +    class Node {
   5.175 +      friend class GridGraphBase;
   5.176 +
   5.177 +    protected:
   5.178 +      int _id;
   5.179 +      Node(int id) : _id(id) {}
   5.180 +    public:
   5.181 +      Node() {}
   5.182 +      Node (Invalid) : _id(-1) {}
   5.183 +      bool operator==(const Node node) const {return _id == node._id;}
   5.184 +      bool operator!=(const Node node) const {return _id != node._id;}
   5.185 +      bool operator<(const Node node) const {return _id < node._id;}
   5.186 +    };
   5.187 +
   5.188 +    class Edge {
   5.189 +      friend class GridGraphBase;
   5.190 +      friend class Arc;
   5.191 +
   5.192 +    protected:
   5.193 +      int _id;
   5.194 +
   5.195 +      Edge(int id) : _id(id) {}
   5.196 +
   5.197 +    public:
   5.198 +      Edge() {}
   5.199 +      Edge (Invalid) : _id(-1) {}
   5.200 +      bool operator==(const Edge edge) const {return _id == edge._id;}
   5.201 +      bool operator!=(const Edge edge) const {return _id != edge._id;}
   5.202 +      bool operator<(const Edge edge) const {return _id < edge._id;}
   5.203 +    };
   5.204 +
   5.205 +    class Arc {
   5.206 +      friend class GridGraphBase;
   5.207 +
   5.208 +    protected:
   5.209 +      int _id;
   5.210 +
   5.211 +      Arc(int id) : _id(id) {}
   5.212 +
   5.213 +    public:
   5.214 +      Arc() {}
   5.215 +      Arc (Invalid) : _id(-1) {}
   5.216 +      operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
   5.217 +      bool operator==(const Arc arc) const {return _id == arc._id;}
   5.218 +      bool operator!=(const Arc arc) const {return _id != arc._id;}
   5.219 +      bool operator<(const Arc arc) const {return _id < arc._id;}
   5.220 +    };
   5.221 +
   5.222 +    static bool direction(Arc arc) {
   5.223 +      return (arc._id & 1) == 1;
   5.224 +    }
   5.225 +
   5.226 +    static Arc direct(Edge edge, bool dir) {
   5.227 +      return Arc((edge._id << 1) | (dir ? 1 : 0));
   5.228 +    }
   5.229 +
   5.230 +    void first(Node& node) const {
   5.231 +      node._id = _node_num - 1;
   5.232 +    }
   5.233 +
   5.234 +    static void next(Node& node) {
   5.235 +      --node._id;
   5.236 +    }
   5.237 +
   5.238 +    void first(Edge& edge) const {
   5.239 +      edge._id = _edge_num - 1;
   5.240 +    }
   5.241 +
   5.242 +    static void next(Edge& edge) {
   5.243 +      --edge._id;
   5.244 +    }
   5.245 +
   5.246 +    void first(Arc& arc) const {
   5.247 +      arc._id = 2 * _edge_num - 1;
   5.248 +    }
   5.249 +
   5.250 +    static void next(Arc& arc) {
   5.251 +      --arc._id;
   5.252 +    }
   5.253 +
   5.254 +    void firstOut(Arc& arc, const Node& node) const {
   5.255 +      if (node._id % _width < _width - 1) {
   5.256 +        arc._id = (_edge_limit + node._id % _width +
   5.257 +                   (node._id / _width) * (_width - 1)) << 1 | 1;
   5.258 +        return;
   5.259 +      }
   5.260 +      if (node._id < _node_num - _width) {
   5.261 +        arc._id = node._id << 1 | 1;
   5.262 +        return;
   5.263 +      }
   5.264 +      if (node._id % _width > 0) {
   5.265 +        arc._id = (_edge_limit + node._id % _width +
   5.266 +                   (node._id / _width) * (_width - 1) - 1) << 1;
   5.267 +        return;
   5.268 +      }
   5.269 +      if (node._id >= _width) {
   5.270 +        arc._id = (node._id - _width) << 1;
   5.271 +        return;
   5.272 +      }
   5.273 +      arc._id = -1;
   5.274 +    }
   5.275 +
   5.276 +    void nextOut(Arc& arc) const {
   5.277 +      int nid = arc._id >> 1;
   5.278 +      if ((arc._id & 1) == 1) {
   5.279 +        if (nid >= _edge_limit) {
   5.280 +          nid = (nid - _edge_limit) % (_width - 1) +
   5.281 +            (nid - _edge_limit) / (_width - 1) * _width;
   5.282 +          if (nid < _node_num - _width) {
   5.283 +            arc._id = nid << 1 | 1;
   5.284 +            return;
   5.285 +          }
   5.286 +        }
   5.287 +        if (nid % _width > 0) {
   5.288 +          arc._id = (_edge_limit + nid % _width +
   5.289 +                     (nid / _width) * (_width - 1) - 1) << 1;
   5.290 +          return;
   5.291 +        }
   5.292 +        if (nid >= _width) {
   5.293 +          arc._id = (nid - _width) << 1;
   5.294 +          return;
   5.295 +        }
   5.296 +      } else {
   5.297 +        if (nid >= _edge_limit) {
   5.298 +          nid = (nid - _edge_limit) % (_width - 1) +
   5.299 +            (nid - _edge_limit) / (_width - 1) * _width + 1;
   5.300 +          if (nid >= _width) {
   5.301 +            arc._id = (nid - _width) << 1;
   5.302 +            return;
   5.303 +          }
   5.304 +        }
   5.305 +      }
   5.306 +      arc._id = -1;
   5.307 +    }
   5.308 +
   5.309 +    void firstIn(Arc& arc, const Node& node) const {
   5.310 +      if (node._id % _width < _width - 1) {
   5.311 +        arc._id = (_edge_limit + node._id % _width +
   5.312 +                   (node._id / _width) * (_width - 1)) << 1;
   5.313 +        return;
   5.314 +      }
   5.315 +      if (node._id < _node_num - _width) {
   5.316 +        arc._id = node._id << 1;
   5.317 +        return;
   5.318 +      }
   5.319 +      if (node._id % _width > 0) {
   5.320 +        arc._id = (_edge_limit + node._id % _width +
   5.321 +                   (node._id / _width) * (_width - 1) - 1) << 1 | 1;
   5.322 +        return;
   5.323 +      }
   5.324 +      if (node._id >= _width) {
   5.325 +        arc._id = (node._id - _width) << 1 | 1;
   5.326 +        return;
   5.327 +      }
   5.328 +      arc._id = -1;
   5.329 +    }
   5.330 +
   5.331 +    void nextIn(Arc& arc) const {
   5.332 +      int nid = arc._id >> 1;
   5.333 +      if ((arc._id & 1) == 0) {
   5.334 +        if (nid >= _edge_limit) {
   5.335 +          nid = (nid - _edge_limit) % (_width - 1) +
   5.336 +            (nid - _edge_limit) / (_width - 1) * _width;
   5.337 +          if (nid < _node_num - _width) {
   5.338 +            arc._id = nid << 1;
   5.339 +            return;
   5.340 +          }
   5.341 +        }
   5.342 +        if (nid % _width > 0) {
   5.343 +          arc._id = (_edge_limit + nid % _width +
   5.344 +                     (nid / _width) * (_width - 1) - 1) << 1 | 1;
   5.345 +          return;
   5.346 +        }
   5.347 +        if (nid >= _width) {
   5.348 +          arc._id = (nid - _width) << 1 | 1;
   5.349 +          return;
   5.350 +        }
   5.351 +      } else {
   5.352 +        if (nid >= _edge_limit) {
   5.353 +          nid = (nid - _edge_limit) % (_width - 1) +
   5.354 +            (nid - _edge_limit) / (_width - 1) * _width + 1;
   5.355 +          if (nid >= _width) {
   5.356 +            arc._id = (nid - _width) << 1 | 1;
   5.357 +            return;
   5.358 +          }
   5.359 +        }
   5.360 +      }
   5.361 +      arc._id = -1;
   5.362 +    }
   5.363 +
   5.364 +    void firstInc(Edge& edge, bool& dir, const Node& node) const {
   5.365 +      if (node._id % _width < _width - 1) {
   5.366 +        edge._id = _edge_limit + node._id % _width +
   5.367 +          (node._id / _width) * (_width - 1);
   5.368 +        dir = true;
   5.369 +        return;
   5.370 +      }
   5.371 +      if (node._id < _node_num - _width) {
   5.372 +        edge._id = node._id;
   5.373 +        dir = true;
   5.374 +        return;
   5.375 +      }
   5.376 +      if (node._id % _width > 0) {
   5.377 +        edge._id = _edge_limit + node._id % _width +
   5.378 +          (node._id / _width) * (_width - 1) - 1;
   5.379 +        dir = false;
   5.380 +        return;
   5.381 +      }
   5.382 +      if (node._id >= _width) {
   5.383 +        edge._id = node._id - _width;
   5.384 +        dir = false;
   5.385 +        return;
   5.386 +      }
   5.387 +      edge._id = -1;
   5.388 +      dir = true;
   5.389 +    }
   5.390 +
   5.391 +    void nextInc(Edge& edge, bool& dir) const {
   5.392 +      int nid = edge._id;
   5.393 +      if (dir) {
   5.394 +        if (nid >= _edge_limit) {
   5.395 +          nid = (nid - _edge_limit) % (_width - 1) +
   5.396 +            (nid - _edge_limit) / (_width - 1) * _width;
   5.397 +          if (nid < _node_num - _width) {
   5.398 +            edge._id = nid;
   5.399 +            return;
   5.400 +          }
   5.401 +        }
   5.402 +        if (nid % _width > 0) {
   5.403 +          edge._id = _edge_limit + nid % _width +
   5.404 +            (nid / _width) * (_width - 1) - 1;
   5.405 +          dir = false;
   5.406 +          return;
   5.407 +        }
   5.408 +        if (nid >= _width) {
   5.409 +          edge._id = nid - _width;
   5.410 +          dir = false;
   5.411 +          return;
   5.412 +        }
   5.413 +      } else {
   5.414 +        if (nid >= _edge_limit) {
   5.415 +          nid = (nid - _edge_limit) % (_width - 1) +
   5.416 +            (nid - _edge_limit) / (_width - 1) * _width + 1;
   5.417 +          if (nid >= _width) {
   5.418 +            edge._id = nid - _width;
   5.419 +            return;
   5.420 +          }
   5.421 +        }
   5.422 +      }
   5.423 +      edge._id = -1;
   5.424 +      dir = true;
   5.425 +    }
   5.426 +
   5.427 +    Arc right(Node n) const {
   5.428 +      if (n._id % _width < _width - 1) {
   5.429 +        return Arc(((_edge_limit + n._id % _width +
   5.430 +                    (n._id / _width) * (_width - 1)) << 1) | 1);
   5.431 +      } else {
   5.432 +        return INVALID;
   5.433 +      }
   5.434 +    }
   5.435 +
   5.436 +    Arc left(Node n) const {
   5.437 +      if (n._id % _width > 0) {
   5.438 +        return Arc((_edge_limit + n._id % _width +
   5.439 +                     (n._id / _width) * (_width - 1) - 1) << 1);
   5.440 +      } else {
   5.441 +        return INVALID;
   5.442 +      }
   5.443 +    }
   5.444 +
   5.445 +    Arc up(Node n) const {
   5.446 +      if (n._id < _edge_limit) {
   5.447 +        return Arc((n._id << 1) | 1);
   5.448 +      } else {
   5.449 +        return INVALID;
   5.450 +      }
   5.451 +    }
   5.452 +
   5.453 +    Arc down(Node n) const {
   5.454 +      if (n._id >= _width) {
   5.455 +        return Arc((n._id - _width) << 1);
   5.456 +      } else {
   5.457 +        return INVALID;
   5.458 +      }
   5.459 +    }
   5.460 +
   5.461 +  private:
   5.462 +    int _width, _height;
   5.463 +    int _node_num, _edge_num;
   5.464 +    int _edge_limit;
   5.465 +  };
   5.466 +
   5.467 +
   5.468 +  typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase;
   5.469 +
   5.470 +  /// \ingroup graphs
   5.471 +  ///
   5.472 +  /// \brief Grid graph class
   5.473 +  ///
   5.474 +  /// This class implements a special graph type. The nodes of the
   5.475 +  /// graph can be indexed by two integer \c (i,j) value where \c i is
   5.476 +  /// in the \c [0..width()-1] range and j is in the \c
   5.477 +  /// [0..height()-1] range.  Two nodes are connected in the graph if
   5.478 +  /// the indexes differ exactly on one position and exactly one is
   5.479 +  /// the difference. The nodes of the graph can be indexed by position
   5.480 +  /// with the \c operator()() function. The positions of the nodes can be
   5.481 +  /// get with \c pos(), \c col() and \c row() members. The outgoing
   5.482 +  /// arcs can be retrieved with the \c right(), \c up(), \c left()
   5.483 +  /// and \c down() functions, where the bottom-left corner is the
   5.484 +  /// origin.
   5.485 +  ///
   5.486 +  /// \image html grid_graph.png
   5.487 +  /// \image latex grid_graph.eps "Grid graph" row_num=\textrow_num
   5.488 +  ///
   5.489 +  /// A short example about the basic usage:
   5.490 +  ///\code
   5.491 +  /// GridGraph graph(rows, cols);
   5.492 +  /// GridGraph::NodeMap<int> val(graph);
   5.493 +  /// for (int i = 0; i < graph.width(); ++i) {
   5.494 +  ///   for (int j = 0; j < graph.height(); ++j) {
   5.495 +  ///     val[graph(i, j)] = i + j;
   5.496 +  ///   }
   5.497 +  /// }
   5.498 +  ///\endcode
   5.499 +  ///
   5.500 +  /// This graph type is fully conform to the \ref concepts::Graph
   5.501 +  /// "Graph" concept, and it also has an important extra feature
   5.502 +  /// that its maps are real \ref concepts::ReferenceMap
   5.503 +  /// "reference map"s.
   5.504 +  class GridGraph : public ExtendedGridGraphBase {
   5.505 +  public:
   5.506 +
   5.507 +    typedef ExtendedGridGraphBase Parent;
   5.508 +
   5.509 +    /// \brief Map to get the indices of the nodes as dim2::Point<int>.
   5.510 +    ///
   5.511 +    /// Map to get the indices of the nodes as dim2::Point<int>.
   5.512 +    class IndexMap {
   5.513 +    public:
   5.514 +      /// \brief The key type of the map
   5.515 +      typedef GridGraph::Node Key;
   5.516 +      /// \brief The value type of the map
   5.517 +      typedef dim2::Point<int> Value;
   5.518 +
   5.519 +      /// \brief Constructor
   5.520 +      ///
   5.521 +      /// Constructor
   5.522 +      IndexMap(const GridGraph& graph) : _graph(graph) {}
   5.523 +
   5.524 +      /// \brief The subscript operator
   5.525 +      ///
   5.526 +      /// The subscript operator.
   5.527 +      Value operator[](Key key) const {
   5.528 +        return _graph.pos(key);
   5.529 +      }
   5.530 +
   5.531 +    private:
   5.532 +      const GridGraph& _graph;
   5.533 +    };
   5.534 +
   5.535 +    /// \brief Map to get the column of the nodes.
   5.536 +    ///
   5.537 +    /// Map to get the column of the nodes.
   5.538 +    class ColMap {
   5.539 +    public:
   5.540 +      /// \brief The key type of the map
   5.541 +      typedef GridGraph::Node Key;
   5.542 +      /// \brief The value type of the map
   5.543 +      typedef int Value;
   5.544 +
   5.545 +      /// \brief Constructor
   5.546 +      ///
   5.547 +      /// Constructor
   5.548 +      ColMap(const GridGraph& graph) : _graph(graph) {}
   5.549 +
   5.550 +      /// \brief The subscript operator
   5.551 +      ///
   5.552 +      /// The subscript operator.
   5.553 +      Value operator[](Key key) const {
   5.554 +        return _graph.col(key);
   5.555 +      }
   5.556 +
   5.557 +    private:
   5.558 +      const GridGraph& _graph;
   5.559 +    };
   5.560 +
   5.561 +    /// \brief Map to get the row of the nodes.
   5.562 +    ///
   5.563 +    /// Map to get the row of the nodes.
   5.564 +    class RowMap {
   5.565 +    public:
   5.566 +      /// \brief The key type of the map
   5.567 +      typedef GridGraph::Node Key;
   5.568 +      /// \brief The value type of the map
   5.569 +      typedef int Value;
   5.570 +
   5.571 +      /// \brief Constructor
   5.572 +      ///
   5.573 +      /// Constructor
   5.574 +      RowMap(const GridGraph& graph) : _graph(graph) {}
   5.575 +
   5.576 +      /// \brief The subscript operator
   5.577 +      ///
   5.578 +      /// The subscript operator.
   5.579 +      Value operator[](Key key) const {
   5.580 +        return _graph.row(key);
   5.581 +      }
   5.582 +
   5.583 +    private:
   5.584 +      const GridGraph& _graph;
   5.585 +    };
   5.586 +
   5.587 +    /// \brief Constructor
   5.588 +    ///
   5.589 +    /// Construct a grid graph with given size.
   5.590 +    GridGraph(int width, int height) { construct(width, height); }
   5.591 +
   5.592 +    /// \brief Resize the graph
   5.593 +    ///
   5.594 +    /// Resize the graph. The function will fully destroy and rebuild
   5.595 +    /// the graph.  This cause that the maps of the graph will
   5.596 +    /// reallocated automatically and the previous values will be
   5.597 +    /// lost.
   5.598 +    void resize(int width, int height) {
   5.599 +      Parent::notifier(Arc()).clear();
   5.600 +      Parent::notifier(Edge()).clear();
   5.601 +      Parent::notifier(Node()).clear();
   5.602 +      construct(width, height);
   5.603 +      Parent::notifier(Node()).build();
   5.604 +      Parent::notifier(Edge()).build();
   5.605 +      Parent::notifier(Arc()).build();
   5.606 +    }
   5.607 +
   5.608 +    /// \brief The node on the given position.
   5.609 +    ///
   5.610 +    /// Gives back the node on the given position.
   5.611 +    Node operator()(int i, int j) const {
   5.612 +      return Parent::operator()(i, j);
   5.613 +    }
   5.614 +
   5.615 +    /// \brief Gives back the column index of the node.
   5.616 +    ///
   5.617 +    /// Gives back the column index of the node.
   5.618 +    int col(Node n) const {
   5.619 +      return Parent::col(n);
   5.620 +    }
   5.621 +
   5.622 +    /// \brief Gives back the row index of the node.
   5.623 +    ///
   5.624 +    /// Gives back the row index of the node.
   5.625 +    int row(Node n) const {
   5.626 +      return Parent::row(n);
   5.627 +    }
   5.628 +
   5.629 +    /// \brief Gives back the position of the node.
   5.630 +    ///
   5.631 +    /// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair.
   5.632 +    dim2::Point<int> pos(Node n) const {
   5.633 +      return Parent::pos(n);
   5.634 +    }
   5.635 +
   5.636 +    /// \brief Gives back the number of the columns.
   5.637 +    ///
   5.638 +    /// Gives back the number of the columns.
   5.639 +    int width() const {
   5.640 +      return Parent::width();
   5.641 +    }
   5.642 +
   5.643 +    /// \brief Gives back the number of the rows.
   5.644 +    ///
   5.645 +    /// Gives back the number of the rows.
   5.646 +    int height() const {
   5.647 +      return Parent::height();
   5.648 +    }
   5.649 +
   5.650 +    /// \brief Gives back the arc goes right from the node.
   5.651 +    ///
   5.652 +    /// Gives back the arc goes right from the node. If there is not
   5.653 +    /// outgoing arc then it gives back INVALID.
   5.654 +    Arc right(Node n) const {
   5.655 +      return Parent::right(n);
   5.656 +    }
   5.657 +
   5.658 +    /// \brief Gives back the arc goes left from the node.
   5.659 +    ///
   5.660 +    /// Gives back the arc goes left from the node. If there is not
   5.661 +    /// outgoing arc then it gives back INVALID.
   5.662 +    Arc left(Node n) const {
   5.663 +      return Parent::left(n);
   5.664 +    }
   5.665 +
   5.666 +    /// \brief Gives back the arc goes up from the node.
   5.667 +    ///
   5.668 +    /// Gives back the arc goes up from the node. If there is not
   5.669 +    /// outgoing arc then it gives back INVALID.
   5.670 +    Arc up(Node n) const {
   5.671 +      return Parent::up(n);
   5.672 +    }
   5.673 +
   5.674 +    /// \brief Gives back the arc goes down from the node.
   5.675 +    ///
   5.676 +    /// Gives back the arc goes down from the node. If there is not
   5.677 +    /// outgoing arc then it gives back INVALID.
   5.678 +    Arc down(Node n) const {
   5.679 +      return Parent::down(n);
   5.680 +    }
   5.681 +
   5.682 +    /// \brief Index map of the grid graph
   5.683 +    ///
   5.684 +    /// Just returns an IndexMap for the grid graph.
   5.685 +    IndexMap indexMap() const {
   5.686 +      return IndexMap(*this);
   5.687 +    }
   5.688 +
   5.689 +    /// \brief Row map of the grid graph
   5.690 +    ///
   5.691 +    /// Just returns a RowMap for the grid graph.
   5.692 +    RowMap rowMap() const {
   5.693 +      return RowMap(*this);
   5.694 +    }
   5.695 +
   5.696 +    /// \brief Column map of the grid graph
   5.697 +    ///
   5.698 +    /// Just returns a ColMap for the grid graph.
   5.699 +    ColMap colMap() const {
   5.700 +      return ColMap(*this);
   5.701 +    }
   5.702 +
   5.703 +  };
   5.704 +
   5.705 +}
   5.706 +#endif
     6.1 --- a/test/graph_test.cc	Wed Oct 22 14:41:18 2008 +0100
     6.2 +++ b/test/graph_test.cc	Wed Oct 22 22:14:00 2008 +0100
     6.3 @@ -20,7 +20,7 @@
     6.4  #include <lemon/list_graph.h>
     6.5  #include <lemon/smart_graph.h>
     6.6  // #include <lemon/full_graph.h>
     6.7 -// #include <lemon/grid_graph.h>
     6.8 +#include <lemon/grid_graph.h>
     6.9  
    6.10  #include "test_tools.h"
    6.11  #include "graph_test.h"
    6.12 @@ -128,10 +128,9 @@
    6.13  //    checkConcept<Graph, FullGraph>();
    6.14  //    checkGraphIterators<FullGraph>();
    6.15  //  }
    6.16 -//  { // Checking GridGraph
    6.17 -//    checkConcept<Graph, GridGraph>();
    6.18 -//    checkGraphIterators<GridGraph>();
    6.19 -//  }
    6.20 +  { // Checking GridGraph
    6.21 +    checkConcept<Graph, GridGraph>();
    6.22 +  }
    6.23  }
    6.24  
    6.25  template <typename Graph>
    6.26 @@ -188,49 +187,84 @@
    6.27    check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    6.28  }
    6.29  
    6.30 -// void checkGridGraph(const GridGraph& g, int w, int h) {
    6.31 -//   check(g.width() == w, "Wrong width");
    6.32 -//   check(g.height() == h, "Wrong height");
    6.33 +void checkGridGraph(int width, int height) {
    6.34 +  typedef GridGraph Graph;
    6.35 +  GRAPH_TYPEDEFS(Graph);
    6.36 +  Graph G(width, height);
    6.37  
    6.38 -//   for (int i = 0; i < w; ++i) {
    6.39 -//     for (int j = 0; j < h; ++j) {
    6.40 -//       check(g.col(g(i, j)) == i, "Wrong col");
    6.41 -//       check(g.row(g(i, j)) == j, "Wrong row");
    6.42 -//     }
    6.43 -//   }
    6.44 +  check(G.width() == width, "Wrong column number");
    6.45 +  check(G.height() == height, "Wrong row number");
    6.46  
    6.47 -//   for (int i = 0; i < w; ++i) {
    6.48 -//     for (int j = 0; j < h - 1; ++j) {
    6.49 -//       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    6.50 -//       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    6.51 -//     }
    6.52 -//     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    6.53 -//   }
    6.54 +  for (int i = 0; i < width; ++i) {
    6.55 +    for (int j = 0; j < height; ++j) {
    6.56 +      check(G.col(G(i, j)) == i, "Wrong column");
    6.57 +      check(G.row(G(i, j)) == j, "Wrong row");
    6.58 +      check(G.pos(G(i, j)).x == i, "Wrong column");
    6.59 +      check(G.pos(G(i, j)).y == j, "Wrong row");
    6.60 +    }
    6.61 +  }
    6.62  
    6.63 -//   for (int i = 0; i < w; ++i) {
    6.64 -//     for (int j = 1; j < h; ++j) {
    6.65 -//       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    6.66 -//       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    6.67 -//     }
    6.68 -//     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    6.69 -//   }
    6.70 +  for (int j = 0; j < height; ++j) {
    6.71 +    for (int i = 0; i < width - 1; ++i) {
    6.72 +      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
    6.73 +      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
    6.74 +    }
    6.75 +    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
    6.76 +  }
    6.77  
    6.78 -//   for (int j = 0; j < h; ++j) {
    6.79 -//     for (int i = 0; i < w - 1; ++i) {
    6.80 -//       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    6.81 -//       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    6.82 -//     }
    6.83 -//     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    6.84 -//   }
    6.85 +  for (int j = 0; j < height; ++j) {
    6.86 +    for (int i = 1; i < width; ++i) {
    6.87 +      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
    6.88 +      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
    6.89 +    }
    6.90 +    check(G.left(G(0, j)) == INVALID, "Wrong left");
    6.91 +  }
    6.92  
    6.93 -//   for (int j = 0; j < h; ++j) {
    6.94 -//     for (int i = 1; i < w; ++i) {
    6.95 -//       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
    6.96 -//       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
    6.97 -//     }
    6.98 -//     check(g.left(g(0, j)) == INVALID, "Wrong left");
    6.99 -//   }
   6.100 -// }
   6.101 +  for (int i = 0; i < width; ++i) {
   6.102 +    for (int j = 0; j < height - 1; ++j) {
   6.103 +      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
   6.104 +      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
   6.105 +    }
   6.106 +    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
   6.107 +  }
   6.108 +
   6.109 +  for (int i = 0; i < width; ++i) {
   6.110 +    for (int j = 1; j < height; ++j) {
   6.111 +      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
   6.112 +      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
   6.113 +    }
   6.114 +    check(G.down(G(i, 0)) == INVALID, "Wrong down");
   6.115 +  }
   6.116 +
   6.117 +  checkGraphNodeList(G, width * height);
   6.118 +  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
   6.119 +  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   6.120 +
   6.121 +  for (NodeIt n(G); n != INVALID; ++n) {
   6.122 +    int nb = 4;
   6.123 +    if (G.col(n) == 0) --nb;
   6.124 +    if (G.col(n) == width - 1) --nb;
   6.125 +    if (G.row(n) == 0) --nb;
   6.126 +    if (G.row(n) == height - 1) --nb;
   6.127 +
   6.128 +    checkGraphOutArcList(G, n, nb);
   6.129 +    checkGraphInArcList(G, n, nb);
   6.130 +    checkGraphIncEdgeList(G, n, nb);
   6.131 +  }
   6.132 +
   6.133 +  checkArcDirections(G);
   6.134 +
   6.135 +  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
   6.136 +  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
   6.137 +
   6.138 +  checkNodeIds(G);
   6.139 +  checkArcIds(G);
   6.140 +  checkEdgeIds(G);
   6.141 +  checkGraphNodeMap(G);
   6.142 +  checkGraphArcMap(G);
   6.143 +  checkGraphEdgeMap(G);
   6.144 +
   6.145 +}
   6.146  
   6.147  void checkGraphs() {
   6.148    { // Checking ListGraph
   6.149 @@ -246,12 +280,13 @@
   6.150  //     checkGraphNodeList(g, 5);
   6.151  //     checkGraphEdgeList(g, 10);
   6.152  //   }
   6.153 -//   { // Checking GridGraph
   6.154 -//     GridGraph g(5, 6);
   6.155 -//     checkGraphNodeList(g, 30);
   6.156 -//     checkGraphEdgeList(g, 49);
   6.157 -//     checkGridGraph(g, 5, 6);
   6.158 -//   }
   6.159 +  { // Checking GridGraph
   6.160 +    checkGridGraph(5, 8);
   6.161 +    checkGridGraph(8, 5);
   6.162 +    checkGridGraph(5, 5);
   6.163 +    checkGridGraph(0, 0);
   6.164 +    checkGridGraph(1, 1);
   6.165 +  }
   6.166  }
   6.167  
   6.168  int main() {