r335:160bf92c7cdc
Mon, 20 Oct 2008 12:36:02
[Not Reviewed]
0 comments (0 inline)
0
4
1
451
220
61
50
| 1 |
%!PS-Adobe-2.0 EPSF-2.0 |
|
| 2 |
%%Title: Grid undirected graph |
|
| 3 |
%%Copyright: (C) 2006 LEMON Project |
|
| 4 |
%%Creator: LEMON, graphToEps() |
|
| 5 |
%%CreationDate: Fri Sep 29 11:55:56 2006 |
|
| 6 |
%%BoundingBox: 0 0 985 1144 |
|
| 7 |
%%EndComments |
|
| 8 |
/lb { setlinewidth setrgbcolor newpath moveto
|
|
| 9 |
4 2 roll 1 index 1 index curveto stroke } bind def |
|
| 10 |
/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def
|
|
| 11 |
/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def
|
|
| 12 |
/sq { newpath 2 index 1 index add 2 index 2 index add moveto
|
|
| 13 |
2 index 1 index sub 2 index 2 index add lineto |
|
| 14 |
2 index 1 index sub 2 index 2 index sub lineto |
|
| 15 |
2 index 1 index add 2 index 2 index sub lineto |
|
| 16 |
closepath pop pop pop} bind def |
|
| 17 |
/di { newpath 2 index 1 index add 2 index moveto
|
|
| 18 |
2 index 2 index 2 index add lineto |
|
| 19 |
2 index 1 index sub 2 index lineto |
|
| 20 |
2 index 2 index 2 index sub lineto |
|
| 21 |
closepath pop pop pop} bind def |
|
| 22 |
/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill
|
|
| 23 |
setrgbcolor 1.1 div c fill |
|
| 24 |
} bind def |
|
| 25 |
/arrl 1 def |
|
| 26 |
/arrw 0.3 def |
|
| 27 |
/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def
|
|
| 28 |
/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def
|
|
| 29 |
/w exch def /len exch def |
|
| 30 |
newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto |
|
| 31 |
len w sub arrl sub dx dy lrl |
|
| 32 |
arrw dy dx neg lrl |
|
| 33 |
dx arrl w add mul dy w 2 div arrw add mul sub |
|
| 34 |
dy arrl w add mul dx w 2 div arrw add mul add rlineto |
|
| 35 |
dx arrl w add mul neg dy w 2 div arrw add mul sub |
|
| 36 |
dy arrl w add mul neg dx w 2 div arrw add mul add rlineto |
|
| 37 |
arrw dy dx neg lrl |
|
| 38 |
len w sub arrl sub neg dx dy lrl |
|
| 39 |
closepath fill } bind def |
|
| 40 |
/cshow { 2 index 2 index moveto dup stringwidth pop
|
|
| 41 |
neg 2 div fosi .35 mul neg rmoveto show pop pop} def |
|
| 42 |
|
|
| 43 |
gsave |
|
| 44 |
2 2 scale |
|
| 45 |
50 40 translate |
|
| 46 |
5.5000 5.5000 scale |
|
| 47 |
% 1.14018 1.14018 translate |
|
| 48 |
%Edges: |
|
| 49 |
gsave |
|
| 50 |
70 80 70 90 0 0 0 0.5000 l |
|
| 51 |
70 70 70 80 0 0 0 0.5000 l |
|
| 52 |
70 60 70 70 0 0 0 0.5000 l |
|
| 53 |
70 50 70 60 0 0 0 0.5000 l |
|
| 54 |
70 40 70 50 0 0 0 0.5000 l |
|
| 55 |
70 30 70 40 0 0 0 0.5000 l |
|
| 56 |
70 20 70 30 0 0 0 0.5000 l |
|
| 57 |
70 10 70 20 0 0 0 0.5000 l |
|
| 58 |
70 0 70 10 0 0 0 0.5000 l |
|
| 59 |
60 80 60 90 0 0 0 0.5000 l |
|
| 60 |
60 70 60 80 0 0 0 0.5000 l |
|
| 61 |
60 60 60 70 0 0 0 0.5000 l |
|
| 62 |
60 50 60 60 0 0 0 0.5000 l |
|
| 63 |
60 40 60 50 0 0 0 0.5000 l |
|
| 64 |
60 30 60 40 0 0 0 0.5000 l |
|
| 65 |
60 20 60 30 0 0 0 0.5000 l |
|
| 66 |
60 10 60 20 0 0 0 0.5000 l |
|
| 67 |
60 0 60 10 0 0 0 0.5000 l |
|
| 68 |
50 80 50 90 0 0 0 0.5000 l |
|
| 69 |
50 70 50 80 0 0 0 0.5000 l |
|
| 70 |
50 60 50 70 0 0 0 0.5000 l |
|
| 71 |
50 50 50 60 0 0 0 0.5000 l |
|
| 72 |
50 40 50 50 0 0 0 0.5000 l |
|
| 73 |
50 30 50 40 0 0 0 0.5000 l |
|
| 74 |
50 20 50 30 0 0 0 0.5000 l |
|
| 75 |
50 10 50 20 0 0 0 0.5000 l |
|
| 76 |
50 0 50 10 0 0 0 0.5000 l |
|
| 77 |
40 80 40 90 0 0 0 0.5000 l |
|
| 78 |
40 70 40 80 0 0 0 0.5000 l |
|
| 79 |
40 60 40 70 0 0 0 0.5000 l |
|
| 80 |
40 50 40 60 0 0 0 0.5000 l |
|
| 81 |
40 40 40 50 0 0 0 0.5000 l |
|
| 82 |
40 30 40 40 0 0 0 0.5000 l |
|
| 83 |
40 20 40 30 0 0 0 0.5000 l |
|
| 84 |
40 10 40 20 0 0 0 0.5000 l |
|
| 85 |
40 0 40 10 0 0 0 0.5000 l |
|
| 86 |
30 80 30 90 0 0 0 0.5000 l |
|
| 87 |
30 70 30 80 0 0 0 0.5000 l |
|
| 88 |
30 60 30 70 0 0 0 0.5000 l |
|
| 89 |
30 50 30 60 0 0 0 0.5000 l |
|
| 90 |
30 40 30 50 0 0 0 0.5000 l |
|
| 91 |
30 30 30 40 0 0 0 0.5000 l |
|
| 92 |
30 20 30 30 0 0 0 0.5000 l |
|
| 93 |
30 10 30 20 0 0 0 0.5000 l |
|
| 94 |
30 0 30 10 0 0 0 0.5000 l |
|
| 95 |
20 80 20 90 0 0 0 0.5000 l |
|
| 96 |
20 70 20 80 0 0 0 0.5000 l |
|
| 97 |
20 60 20 70 0 0 0 0.5000 l |
|
| 98 |
20 50 20 60 0 0 0 0.5000 l |
|
| 99 |
20 40 20 50 0 0 0 0.5000 l |
|
| 100 |
20 30 20 40 0 0 0 0.5000 l |
|
| 101 |
20 20 20 30 0 0 0 0.5000 l |
|
| 102 |
20 10 20 20 0 0 0 0.5000 l |
|
| 103 |
20 0 20 10 0 0 0 0.5000 l |
|
| 104 |
10 80 10 90 0 0 0 0.5000 l |
|
| 105 |
10 70 10 80 0 0 0 0.5000 l |
|
| 106 |
10 60 10 70 0 0 0 0.5000 l |
|
| 107 |
10 50 10 60 0 0 0 0.5000 l |
|
| 108 |
10 40 10 50 0 0 0 0.5000 l |
|
| 109 |
10 30 10 40 0 0 0 0.5000 l |
|
| 110 |
10 20 10 30 0 0 0 0.5000 l |
|
| 111 |
10 10 10 20 0 0 0 0.5000 l |
|
| 112 |
10 0 10 10 0 0 0 0.5000 l |
|
| 113 |
0 80 0 90 0 0 0 0.5000 l |
|
| 114 |
0 70 0 80 0 0 0 0.5000 l |
|
| 115 |
0 60 0 70 0 0 0 0.5000 l |
|
| 116 |
0 50 0 60 0 0 0 0.5000 l |
|
| 117 |
0 40 0 50 0 0 0 0.5000 l |
|
| 118 |
0 30 0 40 0 0 0 0.5000 l |
|
| 119 |
0 20 0 30 0 0 0 0.5000 l |
|
| 120 |
0 10 0 20 0 0 0 0.5000 l |
|
| 121 |
0 0 0 10 0 0 0 0.5000 l |
|
| 122 |
60 90 70 90 0 0 0 0.5000 l |
|
| 123 |
60 80 70 80 0 0 0 0.5000 l |
|
| 124 |
60 70 70 70 0 0 0 0.5000 l |
|
| 125 |
60 60 70 60 0 0 0 0.5000 l |
|
| 126 |
60 50 70 50 0 0 0 0.5000 l |
|
| 127 |
60 40 70 40 0 0 0 0.5000 l |
|
| 128 |
60 30 70 30 0 0 0 0.5000 l |
|
| 129 |
60 20 70 20 0 0 0 0.5000 l |
|
| 130 |
60 10 70 10 0 0 0 0.5000 l |
|
| 131 |
60 0 70 0 0 0 0 0.5000 l |
|
| 132 |
50 90 60 90 0 0 0 0.5000 l |
|
| 133 |
50 80 60 80 0 0 0 0.5000 l |
|
| 134 |
50 70 60 70 0 0 0 0.5000 l |
|
| 135 |
50 60 60 60 0 0 0 0.5000 l |
|
| 136 |
50 50 60 50 0 0 0 0.5000 l |
|
| 137 |
50 40 60 40 0 0 0 0.5000 l |
|
| 138 |
50 30 60 30 0 0 0 0.5000 l |
|
| 139 |
50 20 60 20 0 0 0 0.5000 l |
|
| 140 |
50 10 60 10 0 0 0 0.5000 l |
|
| 141 |
50 0 60 0 0 0 0 0.5000 l |
|
| 142 |
40 90 50 90 0 0 0 0.5000 l |
|
| 143 |
40 80 50 80 0 0 0 0.5000 l |
|
| 144 |
40 70 50 70 0 0 0 0.5000 l |
|
| 145 |
40 60 50 60 0 0 0 0.5000 l |
|
| 146 |
40 50 50 50 0 0 0 0.5000 l |
|
| 147 |
40 40 50 40 0 0 0 0.5000 l |
|
| 148 |
40 30 50 30 0 0 0 0.5000 l |
|
| 149 |
40 20 50 20 0 0 0 0.5000 l |
|
| 150 |
40 10 50 10 0 0 0 0.5000 l |
|
| 151 |
40 0 50 0 0 0 0 0.5000 l |
|
| 152 |
30 90 40 90 0 0 0 0.5000 l |
|
| 153 |
30 80 40 80 0 0 0 0.5000 l |
|
| 154 |
30 70 40 70 0 0 0 0.5000 l |
|
| 155 |
30 60 40 60 0 0 0 0.5000 l |
|
| 156 |
30 50 40 50 0 0 0 0.5000 l |
|
| 157 |
30 40 40 40 0 0 0 0.5000 l |
|
| 158 |
30 30 40 30 0 0 0 0.5000 l |
|
| 159 |
30 20 40 20 0 0 0 0.5000 l |
|
| 160 |
30 10 40 10 0 0 0 0.5000 l |
|
| 161 |
30 0 40 0 0 0 0 0.5000 l |
|
| 162 |
20 90 30 90 0 0 0 0.5000 l |
|
| 163 |
20 80 30 80 0 0 0 0.5000 l |
|
| 164 |
20 70 30 70 0 0 0 0.5000 l |
|
| 165 |
20 60 30 60 0 0 0 0.5000 l |
|
| 166 |
20 50 30 50 0 0 0 0.5000 l |
|
| 167 |
20 40 30 40 0 0 0 0.5000 l |
|
| 168 |
20 30 30 30 0 0 0 0.5000 l |
|
| 169 |
20 20 30 20 0 0 0 0.5000 l |
|
| 170 |
20 10 30 10 0 0 0 0.5000 l |
|
| 171 |
20 0 30 0 0 0 0 0.5000 l |
|
| 172 |
10 90 20 90 0 0 0 0.5000 l |
|
| 173 |
10 80 20 80 0 0 0 0.5000 l |
|
| 174 |
10 70 20 70 0 0 0 0.5000 l |
|
| 175 |
10 60 20 60 0 0 0 0.5000 l |
|
| 176 |
10 50 20 50 0 0 0 0.5000 l |
|
| 177 |
10 40 20 40 0 0 0 0.5000 l |
|
| 178 |
10 30 20 30 0 0 0 0.5000 l |
|
| 179 |
10 20 20 20 0 0 0 0.5000 l |
|
| 180 |
10 10 20 10 0 0 0 0.5000 l |
|
| 181 |
10 0 20 0 0 0 0 0.5000 l |
|
| 182 |
0 90 10 90 0 0 0 0.5000 l |
|
| 183 |
0 80 10 80 0 0 0 0.5000 l |
|
| 184 |
0 70 10 70 0 0 0 0.5000 l |
|
| 185 |
0 60 10 60 0 0 0 0.5000 l |
|
| 186 |
0 50 10 50 0 0 0 0.5000 l |
|
| 187 |
0 40 10 40 0 0 0 0.5000 l |
|
| 188 |
0 30 10 30 0 0 0 0.5000 l |
|
| 189 |
0 20 10 20 0 0 0 0.5000 l |
|
| 190 |
0 10 10 10 0 0 0 0.5000 l |
|
| 191 |
0 0 10 0 0 0 0 0.5000 l |
|
| 192 |
grestore |
|
| 193 |
%Nodes: |
|
| 194 |
gsave |
|
| 195 |
70 90 1.4000 0 0 0 nc |
|
| 196 |
70 80 1.4000 1 1 1 nc |
|
| 197 |
70 70 1.4000 1 1 1 nc |
|
| 198 |
70 60 1.4000 1 1 1 nc |
|
| 199 |
70 50 1.4000 1 1 1 nc |
|
| 200 |
70 40 1.4000 1 1 1 nc |
|
| 201 |
70 30 1.4000 1 1 1 nc |
|
| 202 |
70 20 1.4000 1 1 1 nc |
|
| 203 |
70 10 1.4000 1 1 1 nc |
|
| 204 |
70 0 1.4000 0 0 0 nc |
|
| 205 |
60 90 1.4000 1 1 1 nc |
|
| 206 |
60 80 1.4000 1 1 1 nc |
|
| 207 |
60 70 1.4000 1 1 1 nc |
|
| 208 |
60 60 1.4000 1 1 1 nc |
|
| 209 |
60 50 1.4000 1 1 1 nc |
|
| 210 |
60 40 1.4000 1 1 1 nc |
|
| 211 |
60 30 1.4000 1 1 1 nc |
|
| 212 |
60 20 1.4000 1 1 1 nc |
|
| 213 |
60 10 1.4000 1 1 1 nc |
|
| 214 |
60 0 1.4000 1 1 1 nc |
|
| 215 |
50 90 1.4000 1 1 1 nc |
|
| 216 |
50 80 1.4000 1 1 1 nc |
|
| 217 |
50 70 1.4000 1 1 1 nc |
|
| 218 |
50 60 1.4000 1 1 1 nc |
|
| 219 |
50 50 1.4000 1 1 1 nc |
|
| 220 |
50 40 1.4000 1 1 1 nc |
|
| 221 |
50 30 1.4000 1 1 1 nc |
|
| 222 |
50 20 1.4000 1 1 1 nc |
|
| 223 |
50 10 1.4000 1 1 1 nc |
|
| 224 |
50 0 1.4000 1 1 1 nc |
|
| 225 |
40 90 1.4000 1 1 1 nc |
|
| 226 |
40 80 1.4000 1 1 1 nc |
|
| 227 |
40 70 1.4000 1 1 1 nc |
|
| 228 |
40 60 1.4000 1 1 1 nc |
|
| 229 |
40 50 1.4000 1 1 1 nc |
|
| 230 |
40 40 1.4000 1 1 1 nc |
|
| 231 |
40 30 1.4000 1 1 1 nc |
|
| 232 |
40 20 1.4000 1 1 1 nc |
|
| 233 |
40 10 1.4000 1 1 1 nc |
|
| 234 |
40 0 1.4000 1 1 1 nc |
|
| 235 |
30 90 1.4000 1 1 1 nc |
|
| 236 |
30 80 1.4000 1 1 1 nc |
|
| 237 |
30 70 1.4000 1 1 1 nc |
|
| 238 |
30 60 1.4000 1 1 1 nc |
|
| 239 |
30 50 1.4000 1 1 1 nc |
|
| 240 |
30 40 1.4000 1 1 1 nc |
|
| 241 |
30 30 1.4000 1 1 1 nc |
|
| 242 |
30 20 1.4000 1 1 1 nc |
|
| 243 |
30 10 1.4000 1 1 1 nc |
|
| 244 |
30 0 1.4000 1 1 1 nc |
|
| 245 |
20 90 1.4000 1 1 1 nc |
|
| 246 |
20 80 1.4000 1 1 1 nc |
|
| 247 |
20 70 1.4000 1 1 1 nc |
|
| 248 |
20 60 1.4000 1 1 1 nc |
|
| 249 |
20 50 1.4000 1 1 1 nc |
|
| 250 |
20 40 1.4000 1 1 1 nc |
|
| 251 |
20 30 1.4000 1 1 1 nc |
|
| 252 |
20 20 1.4000 1 1 1 nc |
|
| 253 |
20 10 1.4000 1 1 1 nc |
|
| 254 |
20 0 1.4000 1 1 1 nc |
|
| 255 |
10 90 1.4000 1 1 1 nc |
|
| 256 |
10 80 1.4000 1 1 1 nc |
|
| 257 |
10 70 1.4000 1 1 1 nc |
|
| 258 |
10 60 1.4000 1 1 1 nc |
|
| 259 |
10 50 1.4000 1 1 1 nc |
|
| 260 |
10 40 1.4000 1 1 1 nc |
|
| 261 |
10 30 1.4000 1 1 1 nc |
|
| 262 |
10 20 1.4000 1 1 1 nc |
|
| 263 |
10 10 1.4000 1 1 1 nc |
|
| 264 |
10 0 1.4000 1 1 1 nc |
|
| 265 |
0 90 1.4000 0 0 0 nc |
|
| 266 |
0 80 1.4000 1 1 1 nc |
|
| 267 |
0 70 1.4000 1 1 1 nc |
|
| 268 |
0 60 1.4000 1 1 1 nc |
|
| 269 |
0 50 1.4000 1 1 1 nc |
|
| 270 |
0 40 1.4000 1 1 1 nc |
|
| 271 |
0 30 1.4000 1 1 1 nc |
|
| 272 |
0 20 1.4000 1 1 1 nc |
|
| 273 |
0 10 1.4000 1 1 1 nc |
|
| 274 |
0 0 1.4000 0 0 0 nc |
|
| 275 |
grestore |
|
| 276 |
gsave |
|
| 277 |
/fosi 3.5 def |
|
| 278 |
(Helvetica) findfont fosi scalefont setfont |
|
| 279 |
0 0 0 setrgbcolor |
|
| 280 |
0 95 ((0,height-1)) cshow |
|
| 281 |
67 95 ((width-1,height-1)) cshow |
|
| 282 |
0 -5 ((0,0)) cshow |
|
| 283 |
70 -5 ((width-1,0)) cshow |
|
| 284 |
grestore |
|
| 285 |
grestore |
|
| 286 |
showpage |
| ... | ... |
@@ -14,4 +14,5 @@ |
| 14 | 14 |
COMMAND rm -rf gen-images |
| 15 | 15 |
COMMAND mkdir gen-images |
| 16 |
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
|
|
| 16 | 17 |
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
|
| 17 | 18 |
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
|
| ... | ... |
@@ -20,13 +20,9 @@ |
| 20 | 20 |
#define GRID_GRAPH_H |
| 21 | 21 |
|
| 22 |
#include <iostream> |
|
| 23 | 22 |
#include <lemon/core.h> |
| 23 |
#include <lemon/bits/graph_extender.h> |
|
| 24 |
#include <lemon/dim2.h> |
|
| 24 | 25 |
#include <lemon/assert.h> |
| 25 | 26 |
|
| 26 |
#include <lemon/bits/base_extender.h> |
|
| 27 |
#include <lemon/bits/graph_extender.h> |
|
| 28 |
|
|
| 29 |
#include <lemon/dim2.h> |
|
| 30 |
|
|
| 31 | 27 |
///\ingroup graphs |
| 32 | 28 |
///\file |
| ... | ... |
@@ -42,4 +38,5 @@ |
| 42 | 38 |
|
| 43 | 39 |
class Node; |
| 40 |
class Edge; |
|
| 44 | 41 |
class Arc; |
| 45 | 42 |
|
| ... | ... |
@@ -50,40 +47,9 @@ |
| 50 | 47 |
protected: |
| 51 | 48 |
|
| 52 |
void construct(int w, int h) {
|
|
| 53 |
_height = h; _width = w; |
|
| 54 |
_nodeNum = h * w; _arcNum = 2 * _nodeNum - w - h; |
|
| 55 |
_arcLimit = _nodeNum - w; |
|
| 56 |
} |
|
| 57 |
|
|
| 58 |
Arc _down(Node n) const {
|
|
| 59 |
if (n.id < _nodeNum - _width) {
|
|
| 60 |
return Arc(n.id); |
|
| 61 |
} else {
|
|
| 62 |
return INVALID; |
|
| 63 |
} |
|
| 64 |
} |
|
| 65 |
|
|
| 66 |
Arc _up(Node n) const {
|
|
| 67 |
if (n.id >= _width) {
|
|
| 68 |
return Arc(n.id - _width); |
|
| 69 |
} else {
|
|
| 70 |
return INVALID; |
|
| 71 |
} |
|
| 72 |
} |
|
| 73 |
|
|
| 74 |
Arc _right(Node n) const {
|
|
| 75 |
if (n.id % _width < _width - 1) {
|
|
| 76 |
return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1); |
|
| 77 |
} else {
|
|
| 78 |
return INVALID; |
|
| 79 |
} |
|
| 80 |
} |
|
| 81 |
|
|
| 82 |
Arc _left(Node n) const {
|
|
| 83 |
if (n.id % _width > 0) {
|
|
| 84 |
return _arcLimit + n.id % _width + (n.id / _width) * (_width - 1) - 1; |
|
| 85 |
} else {
|
|
| 86 |
return INVALID; |
|
| 87 |
} |
|
| 49 |
void construct(int width, int height) {
|
|
| 50 |
_width = width; _height = height; |
|
| 51 |
_node_num = width * height; |
|
| 52 |
_edge_num = 2 * _node_num - width - height; |
|
| 53 |
_edge_limit = _node_num - _width; |
|
| 88 | 54 |
} |
| 89 | 55 |
|
| ... | ... |
@@ -91,15 +57,19 @@ |
| 91 | 57 |
|
| 92 | 58 |
Node operator()(int i, int j) const {
|
| 93 |
LEMON_ASSERT(0 <= i && i < width() && |
|
| 94 |
0 <= j && j < height(), "lemon::GridGraph::IndexError"); |
|
| 59 |
LEMON_DEBUG(0 <= i && i < _width && |
|
| 60 |
0 <= j && j < _height, "Index out of range"); |
|
| 95 | 61 |
return Node(i + j * _width); |
| 96 | 62 |
} |
| 97 | 63 |
|
| 98 |
int row(Node n) const {
|
|
| 99 |
return n.id / _width; |
|
| 64 |
int col(Node n) const {
|
|
| 65 |
return n._id % _width; |
|
| 100 | 66 |
} |
| 101 | 67 |
|
| 102 |
int col(Node n) const {
|
|
| 103 |
return n.id % _width; |
|
| 68 |
int row(Node n) const {
|
|
| 69 |
return n._id / _width; |
|
| 70 |
} |
|
| 71 |
|
|
| 72 |
dim2::Point<int> pos(Node n) const {
|
|
| 73 |
return dim2::Point<int>(col(n), row(n)); |
|
| 104 | 74 |
} |
| 105 | 75 |
|
| ... | ... |
@@ -115,43 +85,84 @@ |
| 115 | 85 |
typedef True ArcNumTag; |
| 116 | 86 |
|
| 117 |
int nodeNum() const { return _nodeNum; }
|
|
| 118 |
int arcNum() const { return _arcNum; }
|
|
| 87 |
int nodeNum() const { return _node_num; }
|
|
| 88 |
int edgeNum() const { return _edge_num; }
|
|
| 89 |
int arcNum() const { return 2 * _edge_num; }
|
|
| 119 | 90 |
|
| 120 |
int maxNodeId() const { return nodeNum() - 1; }
|
|
| 121 |
int maxArcId() const { return arcNum() - 1; }
|
|
| 122 |
|
|
| 123 |
Node source(Arc e) const {
|
|
| 124 |
if (e.id < _arcLimit) {
|
|
| 125 |
return e.id; |
|
| 91 |
Node u(Edge edge) const {
|
|
| 92 |
if (edge._id < _edge_limit) {
|
|
| 93 |
return edge._id; |
|
| 126 | 94 |
} else {
|
| 127 |
return (e.id - _arcLimit) % (_width - 1) + |
|
| 128 |
(e.id - _arcLimit) / (_width - 1) * _width; |
|
| 95 |
return (edge._id - _edge_limit) % (_width - 1) + |
|
| 96 |
(edge._id - _edge_limit) / (_width - 1) * _width; |
|
| 129 | 97 |
} |
| 130 | 98 |
} |
| 131 | 99 |
|
| 132 |
Node target(Arc e) const {
|
|
| 133 |
if (e.id < _arcLimit) {
|
|
| 134 |
|
|
| 100 |
Node v(Edge edge) const {
|
|
| 101 |
if (edge._id < _edge_limit) {
|
|
| 102 |
return edge._id + _width; |
|
| 135 | 103 |
} else {
|
| 136 |
return (e.id - _arcLimit) % (_width - 1) + |
|
| 137 |
(e.id - _arcLimit) / (_width - 1) * _width + 1; |
|
| 104 |
return (edge._id - _edge_limit) % (_width - 1) + |
|
| 105 |
(edge._id - _edge_limit) / (_width - 1) * _width + 1; |
|
| 138 | 106 |
} |
| 139 | 107 |
} |
| 140 | 108 |
|
| 141 |
static int id(Node v) { return v.id; }
|
|
| 142 |
static int id(Arc e) { return e.id; }
|
|
| 109 |
Node source(Arc arc) const {
|
|
| 110 |
return (arc._id & 1) == 1 ? u(arc) : v(arc); |
|
| 111 |
} |
|
| 112 |
|
|
| 113 |
Node target(Arc arc) const {
|
|
| 114 |
return (arc._id & 1) == 1 ? v(arc) : u(arc); |
|
| 115 |
} |
|
| 116 |
|
|
| 117 |
static int id(Node node) { return node._id; }
|
|
| 118 |
static int id(Edge edge) { return edge._id; }
|
|
| 119 |
static int id(Arc arc) { return arc._id; }
|
|
| 120 |
|
|
| 121 |
int maxNodeId() const { return _node_num - 1; }
|
|
| 122 |
int maxEdgeId() const { return _edge_num - 1; }
|
|
| 123 |
int maxArcId() const { return 2 * _edge_num - 1; }
|
|
| 143 | 124 |
|
| 144 | 125 |
static Node nodeFromId(int id) { return Node(id);}
|
| 145 |
|
|
| 126 |
static Edge edgeFromId(int id) { return Edge(id);}
|
|
| 146 | 127 |
static Arc arcFromId(int id) { return Arc(id);}
|
| 147 | 128 |
|
| 148 |
typedef True |
|
| 129 |
typedef True FindEdgeTag; |
|
| 130 |
|
|
| 131 |
Edge findEdge(Node u, Node v, Edge prev = INVALID) const {
|
|
| 132 |
if (prev != INVALID) return INVALID; |
|
| 133 |
if (v._id > u._id) {
|
|
| 134 |
if (v._id - u._id == _width) |
|
| 135 |
return Edge(u._id); |
|
| 136 |
if (v._id - u._id == 1 && u._id % _width < _width - 1) {
|
|
| 137 |
return Edge(u._id / _width * (_width - 1) + |
|
| 138 |
u._id % _width + _edge_limit); |
|
| 139 |
} |
|
| 140 |
} else {
|
|
| 141 |
if (u._id - v._id == _width) |
|
| 142 |
return Edge(v._id); |
|
| 143 |
if (u._id - v._id == 1 && v._id % _width < _width - 1) {
|
|
| 144 |
return Edge(v._id / _width * (_width - 1) + |
|
| 145 |
v._id % _width + _edge_limit); |
|
| 146 |
} |
|
| 147 |
} |
|
| 148 |
return INVALID; |
|
| 149 |
} |
|
| 149 | 150 |
|
| 150 | 151 |
Arc findArc(Node u, Node v, Arc prev = INVALID) const {
|
| 151 | 152 |
if (prev != INVALID) return INVALID; |
| 152 |
if (v.id - u.id == _width) return Arc(u.id); |
|
| 153 |
if (v.id - u.id == 1 && u.id % _width < _width - 1) {
|
|
| 154 |
return Arc(u.id / _width * (_width - 1) + |
|
| 155 |
u.id % _width + _arcLimit); |
|
| 153 |
if (v._id > u._id) {
|
|
| 154 |
if (v._id - u._id == _width) |
|
| 155 |
return Arc((u._id << 1) | 1); |
|
| 156 |
if (v._id - u._id == 1 && u._id % _width < _width - 1) {
|
|
| 157 |
return Arc(((u._id / _width * (_width - 1) + |
|
| 158 |
u._id % _width + _edge_limit) << 1) | 1); |
|
| 159 |
} |
|
| 160 |
} else {
|
|
| 161 |
if (u._id - v._id == _width) |
|
| 162 |
return Arc(v._id << 1); |
|
| 163 |
if (u._id - v._id == 1 && v._id % _width < _width - 1) {
|
|
| 164 |
return Arc((v._id / _width * (_width - 1) + |
|
| 165 |
v._id % _width + _edge_limit) << 1); |
|
| 166 |
} |
|
| 156 | 167 |
} |
| 157 | 168 |
return INVALID; |
| ... | ... |
@@ -162,12 +173,28 @@ |
| 162 | 173 |
|
| 163 | 174 |
protected: |
| 164 |
int id; |
|
| 165 |
Node(int _id) : id(_id) {}
|
|
| 175 |
int _id; |
|
| 176 |
Node(int id) : _id(id) {}
|
|
| 166 | 177 |
public: |
| 167 | 178 |
Node() {}
|
| 168 |
Node (Invalid) { id = -1; }
|
|
| 169 |
bool operator==(const Node node) const { return id == node.id; }
|
|
| 170 |
bool operator!=(const Node node) const { return id != node.id; }
|
|
| 171 |
bool operator<(const Node node) const { return id < node.id; }
|
|
| 179 |
Node (Invalid) : _id(-1) {}
|
|
| 180 |
bool operator==(const Node node) const {return _id == node._id;}
|
|
| 181 |
bool operator!=(const Node node) const {return _id != node._id;}
|
|
| 182 |
bool operator<(const Node node) const {return _id < node._id;}
|
|
| 183 |
}; |
|
| 184 |
|
|
| 185 |
class Edge {
|
|
| 186 |
friend class GridGraphBase; |
|
| 187 |
|
|
| 188 |
protected: |
|
| 189 |
int _id; |
|
| 190 |
|
|
| 191 |
Edge(int id) : _id(id) {}
|
|
| 192 |
|
|
| 193 |
public: |
|
| 194 |
Edge() {}
|
|
| 195 |
Edge (Invalid) : _id(-1) {}
|
|
| 196 |
bool operator==(const Edge edge) const {return _id == edge._id;}
|
|
| 197 |
bool operator!=(const Edge edge) const {return _id != edge._id;}
|
|
| 198 |
bool operator<(const Edge edge) const {return _id < edge._id;}
|
|
| 172 | 199 |
}; |
| 173 | 200 |
|
| ... | ... |
@@ -176,71 +203,253 @@ |
| 176 | 203 |
|
| 177 | 204 |
protected: |
| 178 |
int id; |
|
| 179 |
Arc(int _id) : id(_id) {}
|
|
| 205 |
int _id; |
|
| 206 |
|
|
| 207 |
Arc(int id) : _id(id) {}
|
|
| 208 |
|
|
| 180 | 209 |
public: |
| 181 | 210 |
Arc() {}
|
| 182 |
Arc (Invalid) { id = -1; }
|
|
| 183 |
bool operator==(const Arc arc) const { return id == arc.id; }
|
|
| 184 |
bool operator!=(const Arc arc) const { return id != arc.id; }
|
|
| 185 |
bool operator<(const Arc arc) const { return id < arc.id; }
|
|
| 211 |
Arc (Invalid) : _id(-1) {}
|
|
| 212 |
operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
|
|
| 213 |
bool operator==(const Arc arc) const {return _id == arc._id;}
|
|
| 214 |
bool operator!=(const Arc arc) const {return _id != arc._id;}
|
|
| 215 |
bool operator<(const Arc arc) const {return _id < arc._id;}
|
|
| 186 | 216 |
}; |
| 187 | 217 |
|
| 218 |
static bool direction(Arc arc) {
|
|
| 219 |
return (arc._id & 1) == 1; |
|
| 220 |
} |
|
| 221 |
|
|
| 222 |
static Arc direct(Edge edge, bool dir) {
|
|
| 223 |
return Arc((edge._id << 1) | (dir ? 1 : 0)); |
|
| 224 |
} |
|
| 225 |
|
|
| 188 | 226 |
void first(Node& node) const {
|
| 189 |
node. |
|
| 227 |
node._id = _node_num - 1; |
|
| 190 | 228 |
} |
| 191 | 229 |
|
| 192 | 230 |
static void next(Node& node) {
|
| 193 |
--node. |
|
| 231 |
--node._id; |
|
| 232 |
} |
|
| 233 |
|
|
| 234 |
void first(Edge& edge) const {
|
|
| 235 |
edge._id = _edge_num - 1; |
|
| 236 |
} |
|
| 237 |
|
|
| 238 |
static void next(Edge& edge) {
|
|
| 239 |
--edge._id; |
|
| 194 | 240 |
} |
| 195 | 241 |
|
| 196 | 242 |
void first(Arc& arc) const {
|
| 197 |
arc. |
|
| 243 |
arc._id = 2 * _edge_num - 1; |
|
| 198 | 244 |
} |
| 199 | 245 |
|
| 200 | 246 |
static void next(Arc& arc) {
|
| 201 |
--arc. |
|
| 247 |
--arc._id; |
|
| 202 | 248 |
} |
| 203 | 249 |
|
| 204 | 250 |
void firstOut(Arc& arc, const Node& node) const {
|
| 205 |
if (node.id < _nodeNum - _width) {
|
|
| 206 |
arc.id = node.id; |
|
| 207 |
} else if (node.id % _width < _width - 1) {
|
|
| 208 |
arc.id = _arcLimit + node.id % _width + |
|
| 209 |
|
|
| 251 |
if (node._id % _width < _width - 1) {
|
|
| 252 |
arc._id = (_edge_limit + node._id % _width + |
|
| 253 |
(node._id / _width) * (_width - 1)) << 1 | 1; |
|
| 254 |
return; |
|
| 255 |
} |
|
| 256 |
if (node._id < _node_num - _width) {
|
|
| 257 |
arc._id = node._id << 1 | 1; |
|
| 258 |
return; |
|
| 259 |
} |
|
| 260 |
if (node._id % _width > 0) {
|
|
| 261 |
arc._id = (_edge_limit + node._id % _width + |
|
| 262 |
(node._id / _width) * (_width - 1) - 1) << 1; |
|
| 263 |
return; |
|
| 264 |
} |
|
| 265 |
if (node._id >= _width) {
|
|
| 266 |
arc._id = (node._id - _width) << 1; |
|
| 267 |
return; |
|
| 268 |
} |
|
| 269 |
arc._id = -1; |
|
| 270 |
} |
|
| 271 |
|
|
| 272 |
void nextOut(Arc& arc) const {
|
|
| 273 |
int nid = arc._id >> 1; |
|
| 274 |
if ((arc._id & 1) == 1) {
|
|
| 275 |
if (nid >= _edge_limit) {
|
|
| 276 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 277 |
(nid - _edge_limit) / (_width - 1) * _width; |
|
| 278 |
if (nid < _node_num - _width) {
|
|
| 279 |
arc._id = nid << 1 | 1; |
|
| 280 |
return; |
|
| 281 |
} |
|
| 282 |
} |
|
| 283 |
if (nid % _width > 0) {
|
|
| 284 |
arc._id = (_edge_limit + nid % _width + |
|
| 285 |
(nid / _width) * (_width - 1) - 1) << 1; |
|
| 286 |
return; |
|
| 287 |
} |
|
| 288 |
if (nid >= _width) {
|
|
| 289 |
arc._id = (nid - _width) << 1; |
|
| 290 |
return; |
|
| 291 |
} |
|
| 210 | 292 |
} else {
|
| 211 |
|
|
| 293 |
if (nid >= _edge_limit) {
|
|
| 294 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 295 |
(nid - _edge_limit) / (_width - 1) * _width + 1; |
|
| 296 |
if (nid >= _width) {
|
|
| 297 |
arc._id = (nid - _width) << 1; |
|
| 298 |
return; |
|
| 299 |
} |
|
| 300 |
} |
|
| 301 |
} |
|
| 302 |
arc._id = -1; |
|
| 303 |
} |
|
| 304 |
|
|
| 305 |
void firstIn(Arc& arc, const Node& node) const {
|
|
| 306 |
if (node._id % _width < _width - 1) {
|
|
| 307 |
arc._id = (_edge_limit + node._id % _width + |
|
| 308 |
(node._id / _width) * (_width - 1)) << 1; |
|
| 309 |
return; |
|
| 310 |
} |
|
| 311 |
if (node._id < _node_num - _width) {
|
|
| 312 |
arc._id = node._id << 1; |
|
| 313 |
return; |
|
| 314 |
} |
|
| 315 |
if (node._id % _width > 0) {
|
|
| 316 |
arc._id = (_edge_limit + node._id % _width + |
|
| 317 |
(node._id / _width) * (_width - 1) - 1) << 1 | 1; |
|
| 318 |
return; |
|
| 319 |
} |
|
| 320 |
if (node._id >= _width) {
|
|
| 321 |
arc._id = (node._id - _width) << 1 | 1; |
|
| 322 |
return; |
|
| 323 |
} |
|
| 324 |
arc._id = -1; |
|
| 325 |
} |
|
| 326 |
|
|
| 327 |
void nextIn(Arc& arc) const {
|
|
| 328 |
int nid = arc._id >> 1; |
|
| 329 |
if ((arc._id & 1) == 0) {
|
|
| 330 |
if (nid >= _edge_limit) {
|
|
| 331 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 332 |
(nid - _edge_limit) / (_width - 1) * _width; |
|
| 333 |
if (nid < _node_num - _width) {
|
|
| 334 |
arc._id = nid << 1; |
|
| 335 |
return; |
|
| 336 |
} |
|
| 337 |
} |
|
| 338 |
if (nid % _width > 0) {
|
|
| 339 |
arc._id = (_edge_limit + nid % _width + |
|
| 340 |
(nid / _width) * (_width - 1) - 1) << 1 | 1; |
|
| 341 |
return; |
|
| 342 |
} |
|
| 343 |
if (nid >= _width) {
|
|
| 344 |
arc._id = (nid - _width) << 1 | 1; |
|
| 345 |
return; |
|
| 346 |
} |
|
| 347 |
} else {
|
|
| 348 |
if (nid >= _edge_limit) {
|
|
| 349 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 350 |
(nid - _edge_limit) / (_width - 1) * _width + 1; |
|
| 351 |
if (nid >= _width) {
|
|
| 352 |
arc._id = (nid - _width) << 1 | 1; |
|
| 353 |
return; |
|
| 354 |
} |
|
| 355 |
} |
|
| 356 |
} |
|
| 357 |
arc._id = -1; |
|
| 358 |
} |
|
| 359 |
|
|
| 360 |
void firstInc(Edge& edge, bool& dir, const Node& node) const {
|
|
| 361 |
if (node._id % _width < _width - 1) {
|
|
| 362 |
edge._id = _edge_limit + node._id % _width + |
|
| 363 |
(node._id / _width) * (_width - 1); |
|
| 364 |
dir = true; |
|
| 365 |
return; |
|
| 366 |
} |
|
| 367 |
if (node._id < _node_num - _width) {
|
|
| 368 |
edge._id = node._id; |
|
| 369 |
dir = true; |
|
| 370 |
return; |
|
| 371 |
} |
|
| 372 |
if (node._id % _width > 0) {
|
|
| 373 |
edge._id = _edge_limit + node._id % _width + |
|
| 374 |
(node._id / _width) * (_width - 1) - 1; |
|
| 375 |
dir = false; |
|
| 376 |
return; |
|
| 377 |
} |
|
| 378 |
if (node._id >= _width) {
|
|
| 379 |
edge._id = node._id - _width; |
|
| 380 |
dir = false; |
|
| 381 |
return; |
|
| 382 |
} |
|
| 383 |
edge._id = -1; |
|
| 384 |
dir = true; |
|
| 385 |
} |
|
| 386 |
|
|
| 387 |
void nextInc(Edge& edge, bool& dir) const {
|
|
| 388 |
int nid = edge._id; |
|
| 389 |
if (dir) {
|
|
| 390 |
if (nid >= _edge_limit) {
|
|
| 391 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 392 |
(nid - _edge_limit) / (_width - 1) * _width; |
|
| 393 |
if (nid < _node_num - _width) {
|
|
| 394 |
edge._id = nid; |
|
| 395 |
return; |
|
| 396 |
} |
|
| 397 |
} |
|
| 398 |
if (nid % _width > 0) {
|
|
| 399 |
edge._id = _edge_limit + nid % _width + |
|
| 400 |
(nid / _width) * (_width - 1) - 1; |
|
| 401 |
dir = false; |
|
| 402 |
return; |
|
| 403 |
} |
|
| 404 |
if (nid >= _width) {
|
|
| 405 |
edge._id = nid - _width; |
|
| 406 |
dir = false; |
|
| 407 |
return; |
|
| 408 |
} |
|
| 409 |
} else {
|
|
| 410 |
if (nid >= _edge_limit) {
|
|
| 411 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 412 |
(nid - _edge_limit) / (_width - 1) * _width + 1; |
|
| 413 |
if (nid >= _width) {
|
|
| 414 |
edge._id = nid - _width; |
|
| 415 |
return; |
|
| 416 |
} |
|
| 417 |
} |
|
| 418 |
} |
|
| 419 |
edge._id = -1; |
|
| 420 |
dir = true; |
|
| 421 |
} |
|
| 422 |
|
|
| 423 |
Arc right(Node n) const {
|
|
| 424 |
if (n._id % _width < _width - 1) {
|
|
| 425 |
return Arc(((_edge_limit + n._id % _width + |
|
| 426 |
(n._id / _width) * (_width - 1)) << 1) | 1); |
|
| 427 |
} else {
|
|
| 428 |
return INVALID; |
|
| 212 | 429 |
} |
| 213 | 430 |
} |
| 214 | 431 |
|
| 215 |
void nextOut(Arc& arc) const {
|
|
| 216 |
if (arc.id >= _arcLimit) {
|
|
| 217 |
arc.id = -1; |
|
| 218 |
} else if (arc.id % _width < _width - 1) {
|
|
| 219 |
arc.id = _arcLimit + arc.id % _width + |
|
| 220 |
(arc.id / _width) * (_width - 1); |
|
| 432 |
Arc left(Node n) const {
|
|
| 433 |
if (n._id % _width > 0) {
|
|
| 434 |
return Arc((_edge_limit + n._id % _width + |
|
| 435 |
(n._id / _width) * (_width - 1) - 1) << 1); |
|
| 221 | 436 |
} else {
|
| 222 |
|
|
| 437 |
return INVALID; |
|
| 223 | 438 |
} |
| 224 | 439 |
} |
| 225 | 440 |
|
| 226 |
void firstIn(Arc& arc, const Node& node) const {
|
|
| 227 |
if (node.id >= _width) {
|
|
| 228 |
arc.id = node.id - _width; |
|
| 229 |
} else if (node.id % _width > 0) {
|
|
| 230 |
arc.id = _arcLimit + node.id % _width + |
|
| 231 |
(node.id / _width) * (_width - 1) - 1; |
|
| 441 |
Arc up(Node n) const {
|
|
| 442 |
if (n._id < _edge_limit) {
|
|
| 443 |
return Arc((n._id << 1) | 1); |
|
| 232 | 444 |
} else {
|
| 233 |
|
|
| 445 |
return INVALID; |
|
| 234 | 446 |
} |
| 235 | 447 |
} |
| 236 | 448 |
|
| 237 |
void nextIn(Arc& arc) const {
|
|
| 238 |
if (arc.id >= _arcLimit) {
|
|
| 239 |
arc.id = -1; |
|
| 240 |
} else if (arc.id % _width > 0) {
|
|
| 241 |
arc.id = _arcLimit + arc.id % _width + |
|
| 242 |
(arc.id / _width + 1) * (_width - 1) - 1; |
|
| 449 |
Arc down(Node n) const {
|
|
| 450 |
if (n._id >= _width) {
|
|
| 451 |
return Arc((n._id - _width) << 1); |
|
| 243 | 452 |
} else {
|
| 244 |
|
|
| 453 |
return INVALID; |
|
| 245 | 454 |
} |
| 246 | 455 |
} |
| ... | ... |
@@ -248,10 +457,10 @@ |
| 248 | 457 |
private: |
| 249 | 458 |
int _width, _height; |
| 250 |
int _nodeNum, _arcNum; |
|
| 251 |
int _arcLimit; |
|
| 459 |
int _node_num, _edge_num; |
|
| 460 |
int _edge_limit; |
|
| 252 | 461 |
}; |
| 253 | 462 |
|
| 254 |
typedef GraphExtender<UndirDigraphExtender<GridGraphBase> > |
|
| 255 |
ExtendedGridGraphBase; |
|
| 463 |
|
|
| 464 |
typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase; |
|
| 256 | 465 |
|
| 257 | 466 |
/// \ingroup graphs |
| ... | ... |
@@ -260,27 +469,33 @@ |
| 260 | 469 |
/// |
| 261 | 470 |
/// This class implements a special graph type. The nodes of the |
| 262 |
/// graph can be indiced by two integer \c (i,j) value where \c i |
|
| 263 |
/// is in the \c [0,width) range and j is in the [0, height) range. |
|
| 264 |
/// Two nodes are connected in the graph if the indices differ only |
|
| 265 |
/// on one position and only one is the difference. |
|
| 471 |
/// graph can be indexed by two integer \c (i,j) value where \c i is |
|
| 472 |
/// in the \c [0..width()-1] range and j is in the \c |
|
| 473 |
/// [0..height()-1] range. Two nodes are connected in the graph if |
|
| 474 |
/// the indexes differ exactly on one position and exactly one is |
|
| 475 |
/// the difference. The nodes of the graph be indexed by position |
|
| 476 |
/// with \c operator()() function. The positions of the nodes can be |
|
| 477 |
/// get with \c pos(), \c col() and \c row() members. The outgoing |
|
| 478 |
/// arcs can be retrieved with the \c right(), \c up(), \c left() |
|
| 479 |
/// and \c down() functions, where the bottom-left corner is the |
|
| 480 |
/// origin. |
|
| 266 | 481 |
/// |
| 267 | 482 |
/// \image html grid_graph.png |
| 268 |
/// \image latex grid_graph.eps "Grid |
|
| 483 |
/// \image latex grid_graph.eps "Grid digraph" row_num=\textrow_num |
|
| 269 | 484 |
/// |
| 270 |
/// |
|
| 485 |
/// A short example about the basic usage: |
|
| 271 | 486 |
///\code |
| 272 |
/// GridGraph gr(w, h); |
|
| 273 |
/// GridGraph::NodeMap<int> val(gr); |
|
| 274 |
/// for (int i = 0; i < gr.width(); ++i) {
|
|
| 275 |
/// for (int j = 0; j < gr.height(); ++j) {
|
|
| 276 |
/// |
|
| 487 |
/// GridGraph graph(rows, cols); |
|
| 488 |
/// GridGraph::NodeMap<int> val(graph); |
|
| 489 |
/// for (int i = 0; i < graph.width(); ++i) {
|
|
| 490 |
/// for (int j = 0; j < graph.height(); ++j) {
|
|
| 491 |
/// val[graph(i, j)] = i + j; |
|
| 277 | 492 |
/// } |
| 278 | 493 |
/// } |
| 279 | 494 |
///\endcode |
| 280 | 495 |
/// |
| 281 |
/// This graph type is fully conform to the \ref concepts::Graph |
|
| 282 |
/// "Undirected Graph" concept, and it also has an important extra |
|
| 283 |
/// feature that its maps are real \ref concepts::ReferenceMap |
|
| 284 |
/// "reference map"s. |
|
| 496 |
/// The graph type is fully conform to the \ref concepts::Graph |
|
| 497 |
/// "Graph" concept, and it also has an important extra feature |
|
| 498 |
/// that its maps are real \ref concepts::ReferenceMap "reference |
|
| 499 |
/// map"s. |
|
| 285 | 500 |
class GridGraph : public ExtendedGridGraphBase {
|
| 286 | 501 |
public: |
| ... | ... |
@@ -293,15 +508,45 @@ |
| 293 | 508 |
class IndexMap {
|
| 294 | 509 |
public: |
| 295 |
/// The key type of the map |
|
| 510 |
/// \brief The key type of the map |
|
| 296 | 511 |
typedef GridGraph::Node Key; |
| 297 |
/// The value type of the map |
|
| 512 |
/// \brief The value type of the map |
|
| 298 | 513 |
typedef dim2::Point<int> Value; |
| 299 | 514 |
|
| 515 |
/// \brief Constructor |
|
| 516 |
/// |
|
| 300 | 517 |
/// Constructor |
| 301 | 518 |
IndexMap(const GridGraph& graph) : _graph(graph) {}
|
| 302 | 519 |
|
| 303 |
/// The subscript operator |
|
| 304 |
Value operator[](const Key& key) const {
|
|
| 305 |
|
|
| 520 |
/// \brief The subscript operator |
|
| 521 |
/// |
|
| 522 |
/// The subscript operator. |
|
| 523 |
Value operator[](Key key) const {
|
|
| 524 |
return _graph.pos(key); |
|
| 525 |
} |
|
| 526 |
|
|
| 527 |
private: |
|
| 528 |
const GridGraph& _graph; |
|
| 529 |
}; |
|
| 530 |
|
|
| 531 |
/// \brief Map to get the column of the nodes. |
|
| 532 |
/// |
|
| 533 |
/// Map to get the column of the nodes. |
|
| 534 |
class ColMap {
|
|
| 535 |
public: |
|
| 536 |
/// \brief The key type of the map |
|
| 537 |
typedef GridGraph::Node Key; |
|
| 538 |
/// \brief The value type of the map |
|
| 539 |
typedef int Value; |
|
| 540 |
|
|
| 541 |
/// \brief Constructor |
|
| 542 |
/// |
|
| 543 |
/// Constructor |
|
| 544 |
ColMap(const GridGraph& graph) : _graph(graph) {}
|
|
| 545 |
|
|
| 546 |
/// \brief The subscript operator |
|
| 547 |
/// |
|
| 548 |
/// The subscript operator. |
|
| 549 |
Value operator[](Key key) const {
|
|
| 550 |
return _graph.col(key); |
|
| 306 | 551 |
} |
| 307 | 552 |
|
| ... | ... |
@@ -315,14 +560,18 @@ |
| 315 | 560 |
class RowMap {
|
| 316 | 561 |
public: |
| 317 |
/// The key type of the map |
|
| 562 |
/// \brief The key type of the map |
|
| 318 | 563 |
typedef GridGraph::Node Key; |
| 319 |
/// The value type of the map |
|
| 564 |
/// \brief The value type of the map |
|
| 320 | 565 |
typedef int Value; |
| 321 | 566 |
|
| 567 |
/// \brief Constructor |
|
| 568 |
/// |
|
| 322 | 569 |
/// Constructor |
| 323 | 570 |
RowMap(const GridGraph& graph) : _graph(graph) {}
|
| 324 | 571 |
|
| 325 |
/// The subscript operator |
|
| 326 |
Value operator[](const Key& key) const {
|
|
| 572 |
/// \brief The subscript operator |
|
| 573 |
/// |
|
| 574 |
/// The subscript operator. |
|
| 575 |
Value operator[](Key key) const {
|
|
| 327 | 576 |
return _graph.row(key); |
| 328 | 577 |
} |
| ... | ... |
@@ -332,36 +581,15 @@ |
| 332 | 581 |
}; |
| 333 | 582 |
|
| 334 |
/// \brief Map to get the column of the nodes. |
|
| 335 |
/// |
|
| 336 |
/// Map to get the column of the nodes. |
|
| 337 |
class ColMap {
|
|
| 338 |
public: |
|
| 339 |
/// The key type of the map |
|
| 340 |
typedef GridGraph::Node Key; |
|
| 341 |
/// The value type of the map |
|
| 342 |
typedef int Value; |
|
| 343 |
|
|
| 344 |
/// Constructor |
|
| 345 |
ColMap(const GridGraph& graph) : _graph(graph) {}
|
|
| 346 |
|
|
| 347 |
/// The subscript operator |
|
| 348 |
Value operator[](const Key& key) const {
|
|
| 349 |
return _graph.col(key); |
|
| 350 |
} |
|
| 351 |
|
|
| 352 |
private: |
|
| 353 |
const GridGraph& _graph; |
|
| 354 |
}; |
|
| 355 |
|
|
| 356 | 583 |
/// \brief Constructor |
| 357 | 584 |
/// |
| 358 |
/// Constructor. |
|
| 359 |
/// \param width The width of the grid. |
|
| 360 |
/// |
|
| 585 |
/// Construct a grid graph with given size. |
|
| 361 | 586 |
GridGraph(int width, int height) { construct(width, height); }
|
| 362 | 587 |
|
| 363 | 588 |
/// \brief Resize the graph |
| 364 | 589 |
/// |
| 365 |
/// Resize the |
|
| 590 |
/// Resize the graph. The function will fully destroy and rebuild |
|
| 591 |
/// the graph. This cause that the maps of the graph will |
|
| 592 |
/// reallocated automatically and the previous values will be |
|
| 593 |
/// lost. |
|
| 366 | 594 |
void resize(int width, int height) {
|
| 367 | 595 |
Parent::notifier(Arc()).clear(); |
| ... | ... |
@@ -381,4 +609,11 @@ |
| 381 | 609 |
} |
| 382 | 610 |
|
| 611 |
/// \brief Gives back the column index of the node. |
|
| 612 |
/// |
|
| 613 |
/// Gives back the column index of the node. |
|
| 614 |
int col(Node n) const {
|
|
| 615 |
return Parent::col(n); |
|
| 616 |
} |
|
| 617 |
|
|
| 383 | 618 |
/// \brief Gives back the row index of the node. |
| 384 | 619 |
/// |
| ... | ... |
@@ -388,84 +623,80 @@ |
| 388 | 623 |
} |
| 389 | 624 |
|
| 390 |
/// \brief Gives back the |
|
| 625 |
/// \brief Gives back the position of the node. |
|
| 391 | 626 |
/// |
| 392 |
/// Gives back the column index of the node. |
|
| 393 |
int col(Node n) const {
|
|
| 394 |
|
|
| 627 |
/// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. |
|
| 628 |
dim2::Point<int> pos(Node n) const {
|
|
| 629 |
return Parent::pos(n); |
|
| 395 | 630 |
} |
| 396 | 631 |
|
| 397 |
/// \brief Gives back the |
|
| 632 |
/// \brief Gives back the number of the columns. |
|
| 398 | 633 |
/// |
| 399 |
/// Gives back the |
|
| 634 |
/// Gives back the number of the columns. |
|
| 400 | 635 |
int width() const {
|
| 401 | 636 |
return Parent::width(); |
| 402 | 637 |
} |
| 403 | 638 |
|
| 404 |
/// \brief Gives back the |
|
| 639 |
/// \brief Gives back the number of the rows. |
|
| 405 | 640 |
/// |
| 406 |
/// Gives back the |
|
| 641 |
/// Gives back the number of the rows. |
|
| 407 | 642 |
int height() const {
|
| 408 | 643 |
return Parent::height(); |
| 409 | 644 |
} |
| 410 | 645 |
|
| 646 |
/// \brief Gives back the arc goes right from the node. |
|
| 647 |
/// |
|
| 648 |
/// Gives back the arc goes right from the node. If there is not |
|
| 649 |
/// outgoing arc then it gives back INVALID. |
|
| 650 |
Arc right(Node n) const {
|
|
| 651 |
return Parent::right(n); |
|
| 652 |
} |
|
| 653 |
|
|
| 654 |
/// \brief Gives back the arc goes left from the node. |
|
| 655 |
/// |
|
| 656 |
/// Gives back the arc goes left from the node. If there is not |
|
| 657 |
/// outgoing arc then it gives back INVALID. |
|
| 658 |
Arc left(Node n) const {
|
|
| 659 |
return Parent::left(n); |
|
| 660 |
} |
|
| 661 |
|
|
| 662 |
/// \brief Gives back the arc goes up from the node. |
|
| 663 |
/// |
|
| 664 |
/// Gives back the arc goes up from the node. If there is not |
|
| 665 |
/// outgoing arc then it gives back INVALID. |
|
| 666 |
Arc up(Node n) const {
|
|
| 667 |
return Parent::up(n); |
|
| 668 |
} |
|
| 669 |
|
|
| 411 | 670 |
/// \brief Gives back the arc goes down from the node. |
| 412 | 671 |
/// |
| 413 | 672 |
/// Gives back the arc goes down from the node. If there is not |
| 414 |
/// outgoing arc then it gives back |
|
| 673 |
/// outgoing arc then it gives back INVALID. |
|
| 415 | 674 |
Arc down(Node n) const {
|
| 416 |
Edge e = _down(n); |
|
| 417 |
return e != INVALID ? direct(e, true) : INVALID; |
|
| 675 |
return Parent::down(n); |
|
| 418 | 676 |
} |
| 419 | 677 |
|
| 420 |
/// \brief |
|
| 678 |
/// \brief Index map of the grid graph |
|
| 421 | 679 |
/// |
| 422 |
/// Gives back the arc goes up from the node. If there is not |
|
| 423 |
/// outgoing arc then it gives back \c INVALID. |
|
| 424 |
Arc up(Node n) const {
|
|
| 425 |
Edge e = _up(n); |
|
| 426 |
|
|
| 680 |
/// Just returns an IndexMap for the grid graph. |
|
| 681 |
IndexMap indexMap() const {
|
|
| 682 |
return IndexMap(*this); |
|
| 427 | 683 |
} |
| 428 | 684 |
|
| 429 |
/// \brief |
|
| 685 |
/// \brief Row map of the grid graph |
|
| 430 | 686 |
/// |
| 431 |
/// Gives back the arc goes right from the node. If there is not |
|
| 432 |
/// outgoing arc then it gives back \c INVALID. |
|
| 433 |
Arc right(Node n) const {
|
|
| 434 |
Edge e = _right(n); |
|
| 435 |
|
|
| 687 |
/// Just returns a RowMap for the grid graph. |
|
| 688 |
RowMap rowMap() const {
|
|
| 689 |
return RowMap(*this); |
|
| 436 | 690 |
} |
| 437 | 691 |
|
| 438 |
/// \brief |
|
| 692 |
/// \brief Column map of the grid graph |
|
| 439 | 693 |
/// |
| 440 |
/// Gives back the arc goes left from the node. If there is not |
|
| 441 |
/// outgoing arc then it gives back \c INVALID. |
|
| 442 |
Arc left(Node n) const {
|
|
| 443 |
Edge e = _left(n); |
|
| 444 |
|
|
| 694 |
/// Just returns a ColMap for the grid graph. |
|
| 695 |
ColMap colMap() const {
|
|
| 696 |
return ColMap(*this); |
|
| 445 | 697 |
} |
| 446 | 698 |
|
| 447 |
}; |
|
| 699 |
}; |
|
| 448 | 700 |
|
| 449 |
/// \brief Index map of the grid graph |
|
| 450 |
/// |
|
| 451 |
/// Just returns an IndexMap for the grid graph. |
|
| 452 |
inline GridGraph::IndexMap indexMap(const GridGraph& graph) {
|
|
| 453 |
return GridGraph::IndexMap(graph); |
|
| 454 |
} |
|
| 455 |
|
|
| 456 |
/// \brief Row map of the grid graph |
|
| 457 |
/// |
|
| 458 |
/// Just returns a RowMap for the grid graph. |
|
| 459 |
inline GridGraph::RowMap rowMap(const GridGraph& graph) {
|
|
| 460 |
return GridGraph::RowMap(graph); |
|
| 461 |
} |
|
| 462 |
|
|
| 463 |
/// \brief Column map of the grid graph |
|
| 464 |
/// |
|
| 465 |
/// Just returns a ColMap for the grid graph. |
|
| 466 |
inline GridGraph::ColMap colMap(const GridGraph& graph) {
|
|
| 467 |
return GridGraph::ColMap(graph); |
|
| 468 |
} |
|
| 469 | 701 |
} |
| 470 |
|
|
| 471 |
#endif // GRID_GRAPH_H |
|
| 702 |
#endif |
| ... | ... |
@@ -127,4 +127,5 @@ |
| 127 | 127 |
// { // Checking FullGraph
|
| 128 | 128 |
// checkConcept<Graph, FullGraph>(); |
| 129 |
// checkGraphIterators<FullGraph>(); |
|
| 129 | 130 |
// } |
| 130 | 131 |
{ // Checking GridGraph
|
| ... | ... |
@@ -187,74 +188,81 @@ |
| 187 | 188 |
} |
| 188 | 189 |
|
| 189 |
void checkGridGraph(const GridGraph& g, int w, int h) {
|
|
| 190 |
check(g.width() == w, "Wrong width"); |
|
| 191 |
|
|
| 190 |
void checkGridGraph(int width, int height) {
|
|
| 191 |
typedef GridGraph Graph; |
|
| 192 |
GRAPH_TYPEDEFS(Graph); |
|
| 193 |
Graph G(width, height); |
|
| 192 | 194 |
|
| 193 |
for (int i = 0; i < w; ++i) {
|
|
| 194 |
for (int j = 0; j < h; ++j) {
|
|
| 195 |
check(g.col(g(i, j)) == i, "Wrong col"); |
|
| 196 |
check(g.row(g(i, j)) == j, "Wrong row"); |
|
| 195 |
check(G.width() == width, "Wrong row number"); |
|
| 196 |
check(G.height() == height, "Wrong column number"); |
|
| 197 |
|
|
| 198 |
for (int i = 0; i < width; ++i) {
|
|
| 199 |
for (int j = 0; j < height; ++j) {
|
|
| 200 |
check(G.col(G(i, j)) == i, "Wrong column"); |
|
| 201 |
check(G.row(G(i, j)) == j, "Wrong row"); |
|
| 202 |
check(G.pos(G(i, j)).x == i, "Wrong column"); |
|
| 203 |
check(G.pos(G(i, j)).y == j, "Wrong row"); |
|
| 197 | 204 |
} |
| 198 | 205 |
} |
| 199 | 206 |
|
| 200 |
for (int i = 0; i < w; ++i) {
|
|
| 201 |
for (int j = 0; j < h - 1; ++j) {
|
|
| 202 |
check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); |
|
| 203 |
check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); |
|
| 207 |
for (int j = 0; j < height; ++j) {
|
|
| 208 |
for (int i = 0; i < width - 1; ++i) {
|
|
| 209 |
check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right"); |
|
| 210 |
check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right"); |
|
| 204 | 211 |
} |
| 205 |
check( |
|
| 212 |
check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); |
|
| 206 | 213 |
} |
| 207 | 214 |
|
| 208 |
for (int i = 0; i < w; ++i) {
|
|
| 209 |
for (int j = 1; j < h; ++j) {
|
|
| 210 |
check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); |
|
| 211 |
check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); |
|
| 215 |
for (int j = 0; j < height; ++j) {
|
|
| 216 |
for (int i = 1; i < width; ++i) {
|
|
| 217 |
check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left"); |
|
| 218 |
check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left"); |
|
| 212 | 219 |
} |
| 213 |
check( |
|
| 220 |
check(G.left(G(0, j)) == INVALID, "Wrong left"); |
|
| 214 | 221 |
} |
| 215 | 222 |
|
| 216 |
for (int j = 0; j < h; ++j) {
|
|
| 217 |
for (int i = 0; i < w - 1; ++i) {
|
|
| 218 |
check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); |
|
| 219 |
check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); |
|
| 223 |
for (int i = 0; i < width; ++i) {
|
|
| 224 |
for (int j = 0; j < height - 1; ++j) {
|
|
| 225 |
check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up"); |
|
| 226 |
check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up"); |
|
| 220 | 227 |
} |
| 221 |
check( |
|
| 228 |
check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); |
|
| 222 | 229 |
} |
| 223 | 230 |
|
| 224 |
for (int j = 0; j < h; ++j) {
|
|
| 225 |
for (int i = 1; i < w; ++i) {
|
|
| 226 |
check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); |
|
| 227 |
check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); |
|
| 231 |
for (int i = 0; i < width; ++i) {
|
|
| 232 |
for (int j = 1; j < height; ++j) {
|
|
| 233 |
check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down"); |
|
| 234 |
check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down"); |
|
| 228 | 235 |
} |
| 229 |
check( |
|
| 236 |
check(G.down(G(i, 0)) == INVALID, "Wrong down"); |
|
| 230 | 237 |
} |
| 231 | 238 |
|
| 232 |
checkGraphNodeList(g, w*h); |
|
| 233 |
checkGraphArcList(g, 2*(2*w*h-w-h)); |
|
| 234 |
|
|
| 239 |
checkGraphNodeList(G, width * height); |
|
| 240 |
checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); |
|
| 241 |
checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); |
|
| 235 | 242 |
|
| 236 |
checkGraphOutArcList(g, g(0,0), 2); |
|
| 237 |
checkGraphOutArcList(g, g(0,1), 3); |
|
| 238 |
|
|
| 243 |
for (NodeIt n(G); n != INVALID; ++n) {
|
|
| 244 |
int nb = 4; |
|
| 245 |
if (G.col(n) == 0) --nb; |
|
| 246 |
if (G.col(n) == width - 1) --nb; |
|
| 247 |
if (G.row(n) == 0) --nb; |
|
| 248 |
if (G.row(n) == height - 1) --nb; |
|
| 239 | 249 |
|
| 240 |
checkGraphInArcList(g, g(0,0), 2); |
|
| 241 |
checkGraphInArcList(g, g(0,1), 3); |
|
| 242 |
|
|
| 250 |
checkGraphOutArcList(G, n, nb); |
|
| 251 |
checkGraphInArcList(G, n, nb); |
|
| 252 |
checkGraphIncEdgeList(G, n, nb); |
|
| 253 |
} |
|
| 243 | 254 |
|
| 244 |
checkGraphIncEdgeList(g, g(0,0), 2); |
|
| 245 |
checkGraphIncEdgeList(g, g(0,1), 3); |
|
| 246 |
|
|
| 255 |
checkArcDirections(G); |
|
| 247 | 256 |
|
| 248 |
checkGraphConArcList(g, 2*(2*w*h-w-h)); |
|
| 249 |
checkGraphConEdgeList(g, 2*w*h-w-h); |
|
| 257 |
checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); |
|
| 258 |
checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); |
|
| 250 | 259 |
|
| 251 |
|
|
| 260 |
checkNodeIds(G); |
|
| 261 |
checkArcIds(G); |
|
| 262 |
checkEdgeIds(G); |
|
| 263 |
checkGraphNodeMap(G); |
|
| 264 |
checkGraphArcMap(G); |
|
| 265 |
checkGraphEdgeMap(G); |
|
| 252 | 266 |
|
| 253 |
checkNodeIds(g); |
|
| 254 |
checkArcIds(g); |
|
| 255 |
checkEdgeIds(g); |
|
| 256 |
checkGraphNodeMap(g); |
|
| 257 |
checkGraphArcMap(g); |
|
| 258 |
checkGraphEdgeMap(g); |
|
| 259 | 267 |
} |
| 260 | 268 |
|
| ... | ... |
@@ -274,6 +282,9 @@ |
| 274 | 282 |
// } |
| 275 | 283 |
{ // Checking GridGraph
|
| 276 |
GridGraph g(5, 6); |
|
| 277 |
checkGridGraph(g, 5, 6); |
|
| 284 |
checkGridGraph(5, 8); |
|
| 285 |
checkGridGraph(8, 5); |
|
| 286 |
checkGridGraph(5, 5); |
|
| 287 |
checkGridGraph(0, 0); |
|
| 288 |
checkGridGraph(1, 1); |
|
| 278 | 289 |
} |
| 279 | 290 |
} |
0 comments (0 inline)