Improvement on grid graphs
authorBalazs Dezso <deba@inf.elte.hu>
Mon, 20 Oct 2008 12:36:02 +0200
changeset 347160bf92c7cdc
parent 346 ada5f74d1c9e
child 348 052cecabcb71
Improvement on grid graphs

- The indexing of matrix is changed according to integer points of the plane.
- The graph type does not depend on the UndirGraphExtender.
- Improving documentation.
- Improved image generation.
doc/CMakeLists.txt
doc/Makefile.am
doc/images/grid_graph.eps
lemon/grid_graph.h
test/graph_test.cc
     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