r349:560e4b6d020d
Wed, 22 Oct 2008 23:14:00
[Not Reviewed]
0 comments (0 inline)
0
4
2
| 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 |
| 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
| 2 |
* |
|
| 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
|
| 4 |
* |
|
| 5 |
* Copyright (C) 2003-2008 |
|
| 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
| 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
| 8 |
* |
|
| 9 |
* Permission to use, modify and distribute this software is granted |
|
| 10 |
* provided that this copyright notice appears in all copies. For |
|
| 11 |
* precise terms see the accompanying LICENSE file. |
|
| 12 |
* |
|
| 13 |
* This software is provided "AS IS" with no warranty of any kind, |
|
| 14 |
* express or implied, and with no claim as to its suitability for any |
|
| 15 |
* purpose. |
|
| 16 |
* |
|
| 17 |
*/ |
|
| 18 |
|
|
| 19 |
#ifndef GRID_GRAPH_H |
|
| 20 |
#define GRID_GRAPH_H |
|
| 21 |
|
|
| 22 |
#include <lemon/core.h> |
|
| 23 |
#include <lemon/bits/graph_extender.h> |
|
| 24 |
#include <lemon/dim2.h> |
|
| 25 |
#include <lemon/assert.h> |
|
| 26 |
|
|
| 27 |
///\ingroup graphs |
|
| 28 |
///\file |
|
| 29 |
///\brief GridGraph class. |
|
| 30 |
|
|
| 31 |
namespace lemon {
|
|
| 32 |
|
|
| 33 |
class GridGraphBase {
|
|
| 34 |
|
|
| 35 |
public: |
|
| 36 |
|
|
| 37 |
typedef GridGraphBase Graph; |
|
| 38 |
|
|
| 39 |
class Node; |
|
| 40 |
class Edge; |
|
| 41 |
class Arc; |
|
| 42 |
|
|
| 43 |
public: |
|
| 44 |
|
|
| 45 |
GridGraphBase() {}
|
|
| 46 |
|
|
| 47 |
protected: |
|
| 48 |
|
|
| 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; |
|
| 54 |
} |
|
| 55 |
|
|
| 56 |
public: |
|
| 57 |
|
|
| 58 |
Node operator()(int i, int j) const {
|
|
| 59 |
LEMON_DEBUG(0 <= i && i < _width && |
|
| 60 |
0 <= j && j < _height, "Index out of range"); |
|
| 61 |
return Node(i + j * _width); |
|
| 62 |
} |
|
| 63 |
|
|
| 64 |
int col(Node n) const {
|
|
| 65 |
return n._id % _width; |
|
| 66 |
} |
|
| 67 |
|
|
| 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)); |
|
| 74 |
} |
|
| 75 |
|
|
| 76 |
int width() const {
|
|
| 77 |
return _width; |
|
| 78 |
} |
|
| 79 |
|
|
| 80 |
int height() const {
|
|
| 81 |
return _height; |
|
| 82 |
} |
|
| 83 |
|
|
| 84 |
typedef True NodeNumTag; |
|
| 85 |
typedef True ArcNumTag; |
|
| 86 |
|
|
| 87 |
int nodeNum() const { return _node_num; }
|
|
| 88 |
int edgeNum() const { return _edge_num; }
|
|
| 89 |
int arcNum() const { return 2 * _edge_num; }
|
|
| 90 |
|
|
| 91 |
Node u(Edge edge) const {
|
|
| 92 |
if (edge._id < _edge_limit) {
|
|
| 93 |
return edge._id; |
|
| 94 |
} else {
|
|
| 95 |
return (edge._id - _edge_limit) % (_width - 1) + |
|
| 96 |
(edge._id - _edge_limit) / (_width - 1) * _width; |
|
| 97 |
} |
|
| 98 |
} |
|
| 99 |
|
|
| 100 |
Node v(Edge edge) const {
|
|
| 101 |
if (edge._id < _edge_limit) {
|
|
| 102 |
return edge._id + _width; |
|
| 103 |
} else {
|
|
| 104 |
return (edge._id - _edge_limit) % (_width - 1) + |
|
| 105 |
(edge._id - _edge_limit) / (_width - 1) * _width + 1; |
|
| 106 |
} |
|
| 107 |
} |
|
| 108 |
|
|
| 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; }
|
|
| 124 |
|
|
| 125 |
static Node nodeFromId(int id) { return Node(id);}
|
|
| 126 |
static Edge edgeFromId(int id) { return Edge(id);}
|
|
| 127 |
static Arc arcFromId(int id) { return Arc(id);}
|
|
| 128 |
|
|
| 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 |
} |
|
| 150 |
|
|
| 151 |
Arc findArc(Node u, Node v, Arc prev = INVALID) const {
|
|
| 152 |
if (prev != INVALID) return INVALID; |
|
| 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 |
} |
|
| 167 |
} |
|
| 168 |
return INVALID; |
|
| 169 |
} |
|
| 170 |
|
|
| 171 |
class Node {
|
|
| 172 |
friend class GridGraphBase; |
|
| 173 |
|
|
| 174 |
protected: |
|
| 175 |
int _id; |
|
| 176 |
Node(int id) : _id(id) {}
|
|
| 177 |
public: |
|
| 178 |
Node() {}
|
|
| 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 |
friend class Arc; |
|
| 188 |
|
|
| 189 |
protected: |
|
| 190 |
int _id; |
|
| 191 |
|
|
| 192 |
Edge(int id) : _id(id) {}
|
|
| 193 |
|
|
| 194 |
public: |
|
| 195 |
Edge() {}
|
|
| 196 |
Edge (Invalid) : _id(-1) {}
|
|
| 197 |
bool operator==(const Edge edge) const {return _id == edge._id;}
|
|
| 198 |
bool operator!=(const Edge edge) const {return _id != edge._id;}
|
|
| 199 |
bool operator<(const Edge edge) const {return _id < edge._id;}
|
|
| 200 |
}; |
|
| 201 |
|
|
| 202 |
class Arc {
|
|
| 203 |
friend class GridGraphBase; |
|
| 204 |
|
|
| 205 |
protected: |
|
| 206 |
int _id; |
|
| 207 |
|
|
| 208 |
Arc(int id) : _id(id) {}
|
|
| 209 |
|
|
| 210 |
public: |
|
| 211 |
Arc() {}
|
|
| 212 |
Arc (Invalid) : _id(-1) {}
|
|
| 213 |
operator Edge() const { return _id != -1 ? Edge(_id >> 1) : INVALID; }
|
|
| 214 |
bool operator==(const Arc arc) const {return _id == arc._id;}
|
|
| 215 |
bool operator!=(const Arc arc) const {return _id != arc._id;}
|
|
| 216 |
bool operator<(const Arc arc) const {return _id < arc._id;}
|
|
| 217 |
}; |
|
| 218 |
|
|
| 219 |
static bool direction(Arc arc) {
|
|
| 220 |
return (arc._id & 1) == 1; |
|
| 221 |
} |
|
| 222 |
|
|
| 223 |
static Arc direct(Edge edge, bool dir) {
|
|
| 224 |
return Arc((edge._id << 1) | (dir ? 1 : 0)); |
|
| 225 |
} |
|
| 226 |
|
|
| 227 |
void first(Node& node) const {
|
|
| 228 |
node._id = _node_num - 1; |
|
| 229 |
} |
|
| 230 |
|
|
| 231 |
static void next(Node& node) {
|
|
| 232 |
--node._id; |
|
| 233 |
} |
|
| 234 |
|
|
| 235 |
void first(Edge& edge) const {
|
|
| 236 |
edge._id = _edge_num - 1; |
|
| 237 |
} |
|
| 238 |
|
|
| 239 |
static void next(Edge& edge) {
|
|
| 240 |
--edge._id; |
|
| 241 |
} |
|
| 242 |
|
|
| 243 |
void first(Arc& arc) const {
|
|
| 244 |
arc._id = 2 * _edge_num - 1; |
|
| 245 |
} |
|
| 246 |
|
|
| 247 |
static void next(Arc& arc) {
|
|
| 248 |
--arc._id; |
|
| 249 |
} |
|
| 250 |
|
|
| 251 |
void firstOut(Arc& arc, const Node& node) const {
|
|
| 252 |
if (node._id % _width < _width - 1) {
|
|
| 253 |
arc._id = (_edge_limit + node._id % _width + |
|
| 254 |
(node._id / _width) * (_width - 1)) << 1 | 1; |
|
| 255 |
return; |
|
| 256 |
} |
|
| 257 |
if (node._id < _node_num - _width) {
|
|
| 258 |
arc._id = node._id << 1 | 1; |
|
| 259 |
return; |
|
| 260 |
} |
|
| 261 |
if (node._id % _width > 0) {
|
|
| 262 |
arc._id = (_edge_limit + node._id % _width + |
|
| 263 |
(node._id / _width) * (_width - 1) - 1) << 1; |
|
| 264 |
return; |
|
| 265 |
} |
|
| 266 |
if (node._id >= _width) {
|
|
| 267 |
arc._id = (node._id - _width) << 1; |
|
| 268 |
return; |
|
| 269 |
} |
|
| 270 |
arc._id = -1; |
|
| 271 |
} |
|
| 272 |
|
|
| 273 |
void nextOut(Arc& arc) const {
|
|
| 274 |
int nid = arc._id >> 1; |
|
| 275 |
if ((arc._id & 1) == 1) {
|
|
| 276 |
if (nid >= _edge_limit) {
|
|
| 277 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 278 |
(nid - _edge_limit) / (_width - 1) * _width; |
|
| 279 |
if (nid < _node_num - _width) {
|
|
| 280 |
arc._id = nid << 1 | 1; |
|
| 281 |
return; |
|
| 282 |
} |
|
| 283 |
} |
|
| 284 |
if (nid % _width > 0) {
|
|
| 285 |
arc._id = (_edge_limit + nid % _width + |
|
| 286 |
(nid / _width) * (_width - 1) - 1) << 1; |
|
| 287 |
return; |
|
| 288 |
} |
|
| 289 |
if (nid >= _width) {
|
|
| 290 |
arc._id = (nid - _width) << 1; |
|
| 291 |
return; |
|
| 292 |
} |
|
| 293 |
} else {
|
|
| 294 |
if (nid >= _edge_limit) {
|
|
| 295 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 296 |
(nid - _edge_limit) / (_width - 1) * _width + 1; |
|
| 297 |
if (nid >= _width) {
|
|
| 298 |
arc._id = (nid - _width) << 1; |
|
| 299 |
return; |
|
| 300 |
} |
|
| 301 |
} |
|
| 302 |
} |
|
| 303 |
arc._id = -1; |
|
| 304 |
} |
|
| 305 |
|
|
| 306 |
void firstIn(Arc& arc, const Node& node) const {
|
|
| 307 |
if (node._id % _width < _width - 1) {
|
|
| 308 |
arc._id = (_edge_limit + node._id % _width + |
|
| 309 |
(node._id / _width) * (_width - 1)) << 1; |
|
| 310 |
return; |
|
| 311 |
} |
|
| 312 |
if (node._id < _node_num - _width) {
|
|
| 313 |
arc._id = node._id << 1; |
|
| 314 |
return; |
|
| 315 |
} |
|
| 316 |
if (node._id % _width > 0) {
|
|
| 317 |
arc._id = (_edge_limit + node._id % _width + |
|
| 318 |
(node._id / _width) * (_width - 1) - 1) << 1 | 1; |
|
| 319 |
return; |
|
| 320 |
} |
|
| 321 |
if (node._id >= _width) {
|
|
| 322 |
arc._id = (node._id - _width) << 1 | 1; |
|
| 323 |
return; |
|
| 324 |
} |
|
| 325 |
arc._id = -1; |
|
| 326 |
} |
|
| 327 |
|
|
| 328 |
void nextIn(Arc& arc) const {
|
|
| 329 |
int nid = arc._id >> 1; |
|
| 330 |
if ((arc._id & 1) == 0) {
|
|
| 331 |
if (nid >= _edge_limit) {
|
|
| 332 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 333 |
(nid - _edge_limit) / (_width - 1) * _width; |
|
| 334 |
if (nid < _node_num - _width) {
|
|
| 335 |
arc._id = nid << 1; |
|
| 336 |
return; |
|
| 337 |
} |
|
| 338 |
} |
|
| 339 |
if (nid % _width > 0) {
|
|
| 340 |
arc._id = (_edge_limit + nid % _width + |
|
| 341 |
(nid / _width) * (_width - 1) - 1) << 1 | 1; |
|
| 342 |
return; |
|
| 343 |
} |
|
| 344 |
if (nid >= _width) {
|
|
| 345 |
arc._id = (nid - _width) << 1 | 1; |
|
| 346 |
return; |
|
| 347 |
} |
|
| 348 |
} else {
|
|
| 349 |
if (nid >= _edge_limit) {
|
|
| 350 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 351 |
(nid - _edge_limit) / (_width - 1) * _width + 1; |
|
| 352 |
if (nid >= _width) {
|
|
| 353 |
arc._id = (nid - _width) << 1 | 1; |
|
| 354 |
return; |
|
| 355 |
} |
|
| 356 |
} |
|
| 357 |
} |
|
| 358 |
arc._id = -1; |
|
| 359 |
} |
|
| 360 |
|
|
| 361 |
void firstInc(Edge& edge, bool& dir, const Node& node) const {
|
|
| 362 |
if (node._id % _width < _width - 1) {
|
|
| 363 |
edge._id = _edge_limit + node._id % _width + |
|
| 364 |
(node._id / _width) * (_width - 1); |
|
| 365 |
dir = true; |
|
| 366 |
return; |
|
| 367 |
} |
|
| 368 |
if (node._id < _node_num - _width) {
|
|
| 369 |
edge._id = node._id; |
|
| 370 |
dir = true; |
|
| 371 |
return; |
|
| 372 |
} |
|
| 373 |
if (node._id % _width > 0) {
|
|
| 374 |
edge._id = _edge_limit + node._id % _width + |
|
| 375 |
(node._id / _width) * (_width - 1) - 1; |
|
| 376 |
dir = false; |
|
| 377 |
return; |
|
| 378 |
} |
|
| 379 |
if (node._id >= _width) {
|
|
| 380 |
edge._id = node._id - _width; |
|
| 381 |
dir = false; |
|
| 382 |
return; |
|
| 383 |
} |
|
| 384 |
edge._id = -1; |
|
| 385 |
dir = true; |
|
| 386 |
} |
|
| 387 |
|
|
| 388 |
void nextInc(Edge& edge, bool& dir) const {
|
|
| 389 |
int nid = edge._id; |
|
| 390 |
if (dir) {
|
|
| 391 |
if (nid >= _edge_limit) {
|
|
| 392 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 393 |
(nid - _edge_limit) / (_width - 1) * _width; |
|
| 394 |
if (nid < _node_num - _width) {
|
|
| 395 |
edge._id = nid; |
|
| 396 |
return; |
|
| 397 |
} |
|
| 398 |
} |
|
| 399 |
if (nid % _width > 0) {
|
|
| 400 |
edge._id = _edge_limit + nid % _width + |
|
| 401 |
(nid / _width) * (_width - 1) - 1; |
|
| 402 |
dir = false; |
|
| 403 |
return; |
|
| 404 |
} |
|
| 405 |
if (nid >= _width) {
|
|
| 406 |
edge._id = nid - _width; |
|
| 407 |
dir = false; |
|
| 408 |
return; |
|
| 409 |
} |
|
| 410 |
} else {
|
|
| 411 |
if (nid >= _edge_limit) {
|
|
| 412 |
nid = (nid - _edge_limit) % (_width - 1) + |
|
| 413 |
(nid - _edge_limit) / (_width - 1) * _width + 1; |
|
| 414 |
if (nid >= _width) {
|
|
| 415 |
edge._id = nid - _width; |
|
| 416 |
return; |
|
| 417 |
} |
|
| 418 |
} |
|
| 419 |
} |
|
| 420 |
edge._id = -1; |
|
| 421 |
dir = true; |
|
| 422 |
} |
|
| 423 |
|
|
| 424 |
Arc right(Node n) const {
|
|
| 425 |
if (n._id % _width < _width - 1) {
|
|
| 426 |
return Arc(((_edge_limit + n._id % _width + |
|
| 427 |
(n._id / _width) * (_width - 1)) << 1) | 1); |
|
| 428 |
} else {
|
|
| 429 |
return INVALID; |
|
| 430 |
} |
|
| 431 |
} |
|
| 432 |
|
|
| 433 |
Arc left(Node n) const {
|
|
| 434 |
if (n._id % _width > 0) {
|
|
| 435 |
return Arc((_edge_limit + n._id % _width + |
|
| 436 |
(n._id / _width) * (_width - 1) - 1) << 1); |
|
| 437 |
} else {
|
|
| 438 |
return INVALID; |
|
| 439 |
} |
|
| 440 |
} |
|
| 441 |
|
|
| 442 |
Arc up(Node n) const {
|
|
| 443 |
if (n._id < _edge_limit) {
|
|
| 444 |
return Arc((n._id << 1) | 1); |
|
| 445 |
} else {
|
|
| 446 |
return INVALID; |
|
| 447 |
} |
|
| 448 |
} |
|
| 449 |
|
|
| 450 |
Arc down(Node n) const {
|
|
| 451 |
if (n._id >= _width) {
|
|
| 452 |
return Arc((n._id - _width) << 1); |
|
| 453 |
} else {
|
|
| 454 |
return INVALID; |
|
| 455 |
} |
|
| 456 |
} |
|
| 457 |
|
|
| 458 |
private: |
|
| 459 |
int _width, _height; |
|
| 460 |
int _node_num, _edge_num; |
|
| 461 |
int _edge_limit; |
|
| 462 |
}; |
|
| 463 |
|
|
| 464 |
|
|
| 465 |
typedef GraphExtender<GridGraphBase> ExtendedGridGraphBase; |
|
| 466 |
|
|
| 467 |
/// \ingroup graphs |
|
| 468 |
/// |
|
| 469 |
/// \brief Grid graph class |
|
| 470 |
/// |
|
| 471 |
/// This class implements a special graph type. The nodes of the |
|
| 472 |
/// graph can be indexed by two integer \c (i,j) value where \c i is |
|
| 473 |
/// in the \c [0..width()-1] range and j is in the \c |
|
| 474 |
/// [0..height()-1] range. Two nodes are connected in the graph if |
|
| 475 |
/// the indexes differ exactly on one position and exactly one is |
|
| 476 |
/// the difference. The nodes of the graph can be indexed by position |
|
| 477 |
/// with the \c operator()() function. The positions of the nodes can be |
|
| 478 |
/// get with \c pos(), \c col() and \c row() members. The outgoing |
|
| 479 |
/// arcs can be retrieved with the \c right(), \c up(), \c left() |
|
| 480 |
/// and \c down() functions, where the bottom-left corner is the |
|
| 481 |
/// origin. |
|
| 482 |
/// |
|
| 483 |
/// \image html grid_graph.png |
|
| 484 |
/// \image latex grid_graph.eps "Grid graph" row_num=\textrow_num |
|
| 485 |
/// |
|
| 486 |
/// A short example about the basic usage: |
|
| 487 |
///\code |
|
| 488 |
/// GridGraph graph(rows, cols); |
|
| 489 |
/// GridGraph::NodeMap<int> val(graph); |
|
| 490 |
/// for (int i = 0; i < graph.width(); ++i) {
|
|
| 491 |
/// for (int j = 0; j < graph.height(); ++j) {
|
|
| 492 |
/// val[graph(i, j)] = i + j; |
|
| 493 |
/// } |
|
| 494 |
/// } |
|
| 495 |
///\endcode |
|
| 496 |
/// |
|
| 497 |
/// This graph type is fully conform to the \ref concepts::Graph |
|
| 498 |
/// "Graph" concept, and it also has an important extra feature |
|
| 499 |
/// that its maps are real \ref concepts::ReferenceMap |
|
| 500 |
/// "reference map"s. |
|
| 501 |
class GridGraph : public ExtendedGridGraphBase {
|
|
| 502 |
public: |
|
| 503 |
|
|
| 504 |
typedef ExtendedGridGraphBase Parent; |
|
| 505 |
|
|
| 506 |
/// \brief Map to get the indices of the nodes as dim2::Point<int>. |
|
| 507 |
/// |
|
| 508 |
/// Map to get the indices of the nodes as dim2::Point<int>. |
|
| 509 |
class IndexMap {
|
|
| 510 |
public: |
|
| 511 |
/// \brief The key type of the map |
|
| 512 |
typedef GridGraph::Node Key; |
|
| 513 |
/// \brief The value type of the map |
|
| 514 |
typedef dim2::Point<int> Value; |
|
| 515 |
|
|
| 516 |
/// \brief Constructor |
|
| 517 |
/// |
|
| 518 |
/// Constructor |
|
| 519 |
IndexMap(const GridGraph& graph) : _graph(graph) {}
|
|
| 520 |
|
|
| 521 |
/// \brief The subscript operator |
|
| 522 |
/// |
|
| 523 |
/// The subscript operator. |
|
| 524 |
Value operator[](Key key) const {
|
|
| 525 |
return _graph.pos(key); |
|
| 526 |
} |
|
| 527 |
|
|
| 528 |
private: |
|
| 529 |
const GridGraph& _graph; |
|
| 530 |
}; |
|
| 531 |
|
|
| 532 |
/// \brief Map to get the column of the nodes. |
|
| 533 |
/// |
|
| 534 |
/// Map to get the column of the nodes. |
|
| 535 |
class ColMap {
|
|
| 536 |
public: |
|
| 537 |
/// \brief The key type of the map |
|
| 538 |
typedef GridGraph::Node Key; |
|
| 539 |
/// \brief The value type of the map |
|
| 540 |
typedef int Value; |
|
| 541 |
|
|
| 542 |
/// \brief Constructor |
|
| 543 |
/// |
|
| 544 |
/// Constructor |
|
| 545 |
ColMap(const GridGraph& graph) : _graph(graph) {}
|
|
| 546 |
|
|
| 547 |
/// \brief The subscript operator |
|
| 548 |
/// |
|
| 549 |
/// The subscript operator. |
|
| 550 |
Value operator[](Key key) const {
|
|
| 551 |
return _graph.col(key); |
|
| 552 |
} |
|
| 553 |
|
|
| 554 |
private: |
|
| 555 |
const GridGraph& _graph; |
|
| 556 |
}; |
|
| 557 |
|
|
| 558 |
/// \brief Map to get the row of the nodes. |
|
| 559 |
/// |
|
| 560 |
/// Map to get the row of the nodes. |
|
| 561 |
class RowMap {
|
|
| 562 |
public: |
|
| 563 |
/// \brief The key type of the map |
|
| 564 |
typedef GridGraph::Node Key; |
|
| 565 |
/// \brief The value type of the map |
|
| 566 |
typedef int Value; |
|
| 567 |
|
|
| 568 |
/// \brief Constructor |
|
| 569 |
/// |
|
| 570 |
/// Constructor |
|
| 571 |
RowMap(const GridGraph& graph) : _graph(graph) {}
|
|
| 572 |
|
|
| 573 |
/// \brief The subscript operator |
|
| 574 |
/// |
|
| 575 |
/// The subscript operator. |
|
| 576 |
Value operator[](Key key) const {
|
|
| 577 |
return _graph.row(key); |
|
| 578 |
} |
|
| 579 |
|
|
| 580 |
private: |
|
| 581 |
const GridGraph& _graph; |
|
| 582 |
}; |
|
| 583 |
|
|
| 584 |
/// \brief Constructor |
|
| 585 |
/// |
|
| 586 |
/// Construct a grid graph with given size. |
|
| 587 |
GridGraph(int width, int height) { construct(width, height); }
|
|
| 588 |
|
|
| 589 |
/// \brief Resize the graph |
|
| 590 |
/// |
|
| 591 |
/// Resize the graph. The function will fully destroy and rebuild |
|
| 592 |
/// the graph. This cause that the maps of the graph will |
|
| 593 |
/// reallocated automatically and the previous values will be |
|
| 594 |
/// lost. |
|
| 595 |
void resize(int width, int height) {
|
|
| 596 |
Parent::notifier(Arc()).clear(); |
|
| 597 |
Parent::notifier(Edge()).clear(); |
|
| 598 |
Parent::notifier(Node()).clear(); |
|
| 599 |
construct(width, height); |
|
| 600 |
Parent::notifier(Node()).build(); |
|
| 601 |
Parent::notifier(Edge()).build(); |
|
| 602 |
Parent::notifier(Arc()).build(); |
|
| 603 |
} |
|
| 604 |
|
|
| 605 |
/// \brief The node on the given position. |
|
| 606 |
/// |
|
| 607 |
/// Gives back the node on the given position. |
|
| 608 |
Node operator()(int i, int j) const {
|
|
| 609 |
return Parent::operator()(i, j); |
|
| 610 |
} |
|
| 611 |
|
|
| 612 |
/// \brief Gives back the column index of the node. |
|
| 613 |
/// |
|
| 614 |
/// Gives back the column index of the node. |
|
| 615 |
int col(Node n) const {
|
|
| 616 |
return Parent::col(n); |
|
| 617 |
} |
|
| 618 |
|
|
| 619 |
/// \brief Gives back the row index of the node. |
|
| 620 |
/// |
|
| 621 |
/// Gives back the row index of the node. |
|
| 622 |
int row(Node n) const {
|
|
| 623 |
return Parent::row(n); |
|
| 624 |
} |
|
| 625 |
|
|
| 626 |
/// \brief Gives back the position of the node. |
|
| 627 |
/// |
|
| 628 |
/// Gives back the position of the node, ie. the <tt>(col,row)</tt> pair. |
|
| 629 |
dim2::Point<int> pos(Node n) const {
|
|
| 630 |
return Parent::pos(n); |
|
| 631 |
} |
|
| 632 |
|
|
| 633 |
/// \brief Gives back the number of the columns. |
|
| 634 |
/// |
|
| 635 |
/// Gives back the number of the columns. |
|
| 636 |
int width() const {
|
|
| 637 |
return Parent::width(); |
|
| 638 |
} |
|
| 639 |
|
|
| 640 |
/// \brief Gives back the number of the rows. |
|
| 641 |
/// |
|
| 642 |
/// Gives back the number of the rows. |
|
| 643 |
int height() const {
|
|
| 644 |
return Parent::height(); |
|
| 645 |
} |
|
| 646 |
|
|
| 647 |
/// \brief Gives back the arc goes right from the node. |
|
| 648 |
/// |
|
| 649 |
/// Gives back the arc goes right from the node. If there is not |
|
| 650 |
/// outgoing arc then it gives back INVALID. |
|
| 651 |
Arc right(Node n) const {
|
|
| 652 |
return Parent::right(n); |
|
| 653 |
} |
|
| 654 |
|
|
| 655 |
/// \brief Gives back the arc goes left from the node. |
|
| 656 |
/// |
|
| 657 |
/// Gives back the arc goes left from the node. If there is not |
|
| 658 |
/// outgoing arc then it gives back INVALID. |
|
| 659 |
Arc left(Node n) const {
|
|
| 660 |
return Parent::left(n); |
|
| 661 |
} |
|
| 662 |
|
|
| 663 |
/// \brief Gives back the arc goes up from the node. |
|
| 664 |
/// |
|
| 665 |
/// Gives back the arc goes up from the node. If there is not |
|
| 666 |
/// outgoing arc then it gives back INVALID. |
|
| 667 |
Arc up(Node n) const {
|
|
| 668 |
return Parent::up(n); |
|
| 669 |
} |
|
| 670 |
|
|
| 671 |
/// \brief Gives back the arc goes down from the node. |
|
| 672 |
/// |
|
| 673 |
/// Gives back the arc goes down from the node. If there is not |
|
| 674 |
/// outgoing arc then it gives back INVALID. |
|
| 675 |
Arc down(Node n) const {
|
|
| 676 |
return Parent::down(n); |
|
| 677 |
} |
|
| 678 |
|
|
| 679 |
/// \brief Index map of the grid graph |
|
| 680 |
/// |
|
| 681 |
/// Just returns an IndexMap for the grid graph. |
|
| 682 |
IndexMap indexMap() const {
|
|
| 683 |
return IndexMap(*this); |
|
| 684 |
} |
|
| 685 |
|
|
| 686 |
/// \brief Row map of the grid graph |
|
| 687 |
/// |
|
| 688 |
/// Just returns a RowMap for the grid graph. |
|
| 689 |
RowMap rowMap() const {
|
|
| 690 |
return RowMap(*this); |
|
| 691 |
} |
|
| 692 |
|
|
| 693 |
/// \brief Column map of the grid graph |
|
| 694 |
/// |
|
| 695 |
/// Just returns a ColMap for the grid graph. |
|
| 696 |
ColMap colMap() const {
|
|
| 697 |
return ColMap(*this); |
|
| 698 |
} |
|
| 699 |
|
|
| 700 |
}; |
|
| 701 |
|
|
| 702 |
} |
|
| 703 |
#endif |
| ... | ... |
@@ -10,12 +10,13 @@ |
| 10 | 10 |
|
| 11 | 11 |
IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE) |
| 12 | 12 |
IF(UNIX) |
| 13 | 13 |
ADD_CUSTOM_TARGET(html |
| 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
|
| 18 | 19 |
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
|
| 19 | 20 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
|
| 20 | 21 |
COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps
|
| 21 | 22 |
COMMAND rm -rf html |
| ... | ... |
@@ -11,12 +11,13 @@ |
| 11 | 11 |
doc/named-param.dox \ |
| 12 | 12 |
doc/namespaces.dox \ |
| 13 | 13 |
doc/html \ |
| 14 | 14 |
doc/CMakeLists.txt |
| 15 | 15 |
|
| 16 | 16 |
DOC_EPS_IMAGES18 = \ |
| 17 |
grid_graph.eps \ |
|
| 17 | 18 |
nodeshape_0.eps \ |
| 18 | 19 |
nodeshape_1.eps \ |
| 19 | 20 |
nodeshape_2.eps \ |
| 20 | 21 |
nodeshape_3.eps \ |
| 21 | 22 |
nodeshape_4.eps |
| 22 | 23 |
| ... | ... |
@@ -26,12 +26,13 @@ |
| 26 | 26 |
lemon/core.h \ |
| 27 | 27 |
lemon/dfs.h \ |
| 28 | 28 |
lemon/dijkstra.h \ |
| 29 | 29 |
lemon/dim2.h \ |
| 30 | 30 |
lemon/error.h \ |
| 31 | 31 |
lemon/graph_to_eps.h \ |
| 32 |
lemon/grid_graph.h \ |
|
| 32 | 33 |
lemon/kruskal.h \ |
| 33 | 34 |
lemon/lgf_reader.h \ |
| 34 | 35 |
lemon/lgf_writer.h \ |
| 35 | 36 |
lemon/list_graph.h \ |
| 36 | 37 |
lemon/maps.h \ |
| 37 | 38 |
lemon/math.h \ |
| ... | ... |
@@ -17,13 +17,13 @@ |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/concepts/graph.h> |
| 20 | 20 |
#include <lemon/list_graph.h> |
| 21 | 21 |
#include <lemon/smart_graph.h> |
| 22 | 22 |
// #include <lemon/full_graph.h> |
| 23 |
|
|
| 23 |
#include <lemon/grid_graph.h> |
|
| 24 | 24 |
|
| 25 | 25 |
#include "test_tools.h" |
| 26 | 26 |
#include "graph_test.h" |
| 27 | 27 |
|
| 28 | 28 |
using namespace lemon; |
| 29 | 29 |
using namespace lemon::concepts; |
| ... | ... |
@@ -125,16 +125,15 @@ |
| 125 | 125 |
checkConcept<ClearableGraphComponent<>, SmartGraph>(); |
| 126 | 126 |
} |
| 127 | 127 |
// { // Checking FullGraph
|
| 128 | 128 |
// checkConcept<Graph, FullGraph>(); |
| 129 | 129 |
// checkGraphIterators<FullGraph>(); |
| 130 | 130 |
// } |
| 131 |
// { // Checking GridGraph
|
|
| 132 |
// checkConcept<Graph, GridGraph>(); |
|
| 133 |
// checkGraphIterators<GridGraph>(); |
|
| 134 |
// } |
|
| 131 |
{ // Checking GridGraph
|
|
| 132 |
checkConcept<Graph, GridGraph>(); |
|
| 133 |
} |
|
| 135 | 134 |
} |
| 136 | 135 |
|
| 137 | 136 |
template <typename Graph> |
| 138 | 137 |
void checkGraphValidity() {
|
| 139 | 138 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
| 140 | 139 |
Graph g; |
| ... | ... |
@@ -185,55 +184,90 @@ |
| 185 | 184 |
|
| 186 | 185 |
check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
| 187 | 186 |
check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); |
| 188 | 187 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
| 189 | 188 |
} |
| 190 | 189 |
|
| 191 |
// void checkGridGraph(const GridGraph& g, int w, int h) {
|
|
| 192 |
// check(g.width() == w, "Wrong width"); |
|
| 193 |
|
|
| 190 |
void checkGridGraph(int width, int height) {
|
|
| 191 |
typedef GridGraph Graph; |
|
| 192 |
GRAPH_TYPEDEFS(Graph); |
|
| 193 |
Graph G(width, height); |
|
| 194 | 194 |
|
| 195 |
// for (int i = 0; i < w; ++i) {
|
|
| 196 |
// for (int j = 0; j < h; ++j) {
|
|
| 197 |
// check(g.col(g(i, j)) == i, "Wrong col"); |
|
| 198 |
// check(g.row(g(i, j)) == j, "Wrong row"); |
|
| 199 |
// } |
|
| 200 |
// } |
|
| 195 |
check(G.width() == width, "Wrong column number"); |
|
| 196 |
check(G.height() == height, "Wrong row number"); |
|
| 201 | 197 |
|
| 202 |
// for (int i = 0; i < w; ++i) {
|
|
| 203 |
// for (int j = 0; j < h - 1; ++j) {
|
|
| 204 |
// check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down"); |
|
| 205 |
// check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down"); |
|
| 206 |
// } |
|
| 207 |
// check(g.down(g(i, h - 1)) == INVALID, "Wrong down"); |
|
| 208 |
|
|
| 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"); |
|
| 204 |
} |
|
| 205 |
} |
|
| 209 | 206 |
|
| 210 |
// for (int i = 0; i < w; ++i) {
|
|
| 211 |
// for (int j = 1; j < h; ++j) {
|
|
| 212 |
// check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up"); |
|
| 213 |
// check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up"); |
|
| 214 |
// } |
|
| 215 |
// check(g.up(g(i, 0)) == INVALID, "Wrong up"); |
|
| 216 |
|
|
| 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"); |
|
| 211 |
} |
|
| 212 |
check(G.right(G(width - 1, j)) == INVALID, "Wrong right"); |
|
| 213 |
} |
|
| 217 | 214 |
|
| 218 |
// for (int j = 0; j < h; ++j) {
|
|
| 219 |
// for (int i = 0; i < w - 1; ++i) {
|
|
| 220 |
// check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right"); |
|
| 221 |
// check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right"); |
|
| 222 |
// } |
|
| 223 |
// check(g.right(g(w - 1, j)) == INVALID, "Wrong right"); |
|
| 224 |
|
|
| 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"); |
|
| 219 |
} |
|
| 220 |
check(G.left(G(0, j)) == INVALID, "Wrong left"); |
|
| 221 |
} |
|
| 225 | 222 |
|
| 226 |
// for (int j = 0; j < h; ++j) {
|
|
| 227 |
// for (int i = 1; i < w; ++i) {
|
|
| 228 |
// check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left"); |
|
| 229 |
// check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left"); |
|
| 230 |
// } |
|
| 231 |
// check(g.left(g(0, j)) == INVALID, "Wrong left"); |
|
| 232 |
// } |
|
| 233 |
// } |
|
| 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"); |
|
| 227 |
} |
|
| 228 |
check(G.up(G(i, height - 1)) == INVALID, "Wrong up"); |
|
| 229 |
} |
|
| 230 |
|
|
| 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"); |
|
| 235 |
} |
|
| 236 |
check(G.down(G(i, 0)) == INVALID, "Wrong down"); |
|
| 237 |
} |
|
| 238 |
|
|
| 239 |
checkGraphNodeList(G, width * height); |
|
| 240 |
checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height); |
|
| 241 |
checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); |
|
| 242 |
|
|
| 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; |
|
| 249 |
|
|
| 250 |
checkGraphOutArcList(G, n, nb); |
|
| 251 |
checkGraphInArcList(G, n, nb); |
|
| 252 |
checkGraphIncEdgeList(G, n, nb); |
|
| 253 |
} |
|
| 254 |
|
|
| 255 |
checkArcDirections(G); |
|
| 256 |
|
|
| 257 |
checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height)); |
|
| 258 |
checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height); |
|
| 259 |
|
|
| 260 |
checkNodeIds(G); |
|
| 261 |
checkArcIds(G); |
|
| 262 |
checkEdgeIds(G); |
|
| 263 |
checkGraphNodeMap(G); |
|
| 264 |
checkGraphArcMap(G); |
|
| 265 |
checkGraphEdgeMap(G); |
|
| 266 |
|
|
| 267 |
} |
|
| 234 | 268 |
|
| 235 | 269 |
void checkGraphs() {
|
| 236 | 270 |
{ // Checking ListGraph
|
| 237 | 271 |
checkGraph<ListGraph>(); |
| 238 | 272 |
checkGraphValidityErase<ListGraph>(); |
| 239 | 273 |
} |
| ... | ... |
@@ -243,18 +277,19 @@ |
| 243 | 277 |
} |
| 244 | 278 |
// { // Checking FullGraph
|
| 245 | 279 |
// FullGraph g(5); |
| 246 | 280 |
// checkGraphNodeList(g, 5); |
| 247 | 281 |
// checkGraphEdgeList(g, 10); |
| 248 | 282 |
// } |
| 249 |
// { // Checking GridGraph
|
|
| 250 |
// GridGraph g(5, 6); |
|
| 251 |
// checkGraphNodeList(g, 30); |
|
| 252 |
// checkGraphEdgeList(g, 49); |
|
| 253 |
// checkGridGraph(g, 5, 6); |
|
| 254 |
// } |
|
| 283 |
{ // Checking GridGraph
|
|
| 284 |
checkGridGraph(5, 8); |
|
| 285 |
checkGridGraph(8, 5); |
|
| 286 |
checkGridGraph(5, 5); |
|
| 287 |
checkGridGraph(0, 0); |
|
| 288 |
checkGridGraph(1, 1); |
|
| 289 |
} |
|
| 255 | 290 |
} |
| 256 | 291 |
|
| 257 | 292 |
int main() {
|
| 258 | 293 |
checkConcepts(); |
| 259 | 294 |
checkGraphs(); |
| 260 | 295 |
return 0; |
0 comments (0 inline)