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() {