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 |
... | ... |
@@ -4,24 +4,25 @@ |
4 | 4 |
SET(abs_top_builddir ${CMAKE_BINARY_DIR}) |
5 | 5 |
|
6 | 6 |
CONFIGURE_FILE( |
7 | 7 |
${CMAKE_SOURCE_DIR}/doc/Doxyfile.in |
8 | 8 |
${CMAKE_BINARY_DIR}/doc/Doxyfile |
9 | 9 |
@ONLY) |
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 |
22 | 23 |
COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile |
23 | 24 |
WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) |
24 | 25 |
ELSEIF(WIN32) |
25 | 26 |
ADD_CUSTOM_TARGET(html |
26 | 27 |
COMMAND if exist gen-images rmdir /s /q gen-images |
27 | 28 |
COMMAND mkdir gen-images |
... | ... |
@@ -2,24 +2,25 @@ |
2 | 2 |
doc/Doxyfile.in \ |
3 | 3 |
doc/coding_style.dox \ |
4 | 4 |
doc/dirs.dox \ |
5 | 5 |
doc/groups.dox \ |
6 | 6 |
doc/lgf.dox \ |
7 | 7 |
doc/license.dox \ |
8 | 8 |
doc/mainpage.dox \ |
9 | 9 |
doc/namespaces.dox \ |
10 | 10 |
doc/html \ |
11 | 11 |
doc/CMakeLists.txt |
12 | 12 |
|
13 | 13 |
DOC_EPS_IMAGES18 = \ |
14 |
grid_graph.eps \ |
|
14 | 15 |
nodeshape_0.eps \ |
15 | 16 |
nodeshape_1.eps \ |
16 | 17 |
nodeshape_2.eps \ |
17 | 18 |
nodeshape_3.eps \ |
18 | 19 |
nodeshape_4.eps |
19 | 20 |
|
20 | 21 |
DOC_EPS_IMAGES = \ |
21 | 22 |
$(DOC_EPS_IMAGES18) |
22 | 23 |
|
23 | 24 |
DOC_PNG_IMAGES = \ |
24 | 25 |
$(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png) |
25 | 26 |
... | ... |
@@ -10,462 +10,693 @@ |
10 | 10 |
* provided that this copyright notice appears in all copies. For |
11 | 11 |
* precise terms see the accompanying LICENSE file. |
12 | 12 |
* |
13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
14 | 14 |
* express or implied, and with no claim as to its suitability for any |
15 | 15 |
* purpose. |
16 | 16 |
* |
17 | 17 |
*/ |
18 | 18 |
|
19 | 19 |
#ifndef GRID_GRAPH_H |
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 |
33 | 29 |
///\brief GridGraph class. |
34 | 30 |
|
35 | 31 |
namespace lemon { |
36 | 32 |
|
37 | 33 |
class GridGraphBase { |
38 | 34 |
|
39 | 35 |
public: |
40 | 36 |
|
41 | 37 |
typedef GridGraphBase Graph; |
42 | 38 |
|
43 | 39 |
class Node; |
40 |
class Edge; |
|
44 | 41 |
class Arc; |
45 | 42 |
|
46 | 43 |
public: |
47 | 44 |
|
48 | 45 |
GridGraphBase() {} |
49 | 46 |
|
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 |
|
90 | 56 |
public: |
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 |
|
106 | 76 |
int width() const { |
107 | 77 |
return _width; |
108 | 78 |
} |
109 | 79 |
|
110 | 80 |
int height() const { |
111 | 81 |
return _height; |
112 | 82 |
} |
113 | 83 |
|
114 | 84 |
typedef True NodeNumTag; |
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; |
158 | 169 |
} |
159 | 170 |
|
160 | 171 |
class Node { |
161 | 172 |
friend class GridGraphBase; |
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 |
|
174 | 201 |
class Arc { |
175 | 202 |
friend class GridGraphBase; |
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 |
} |
247 | 456 |
|
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 |
258 | 467 |
/// |
259 | 468 |
/// \brief Grid graph class |
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: |
287 | 502 |
|
288 | 503 |
typedef ExtendedGridGraphBase Parent; |
289 | 504 |
|
290 | 505 |
/// \brief Map to get the indices of the nodes as dim2::Point<int>. |
291 | 506 |
/// |
292 | 507 |
/// Map to get the indices of the nodes as dim2::Point<int>. |
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 |
|
308 | 553 |
private: |
309 | 554 |
const GridGraph& _graph; |
310 | 555 |
}; |
311 | 556 |
|
312 | 557 |
/// \brief Map to get the row of the nodes. |
313 | 558 |
/// |
314 | 559 |
/// Map to get the row of the nodes. |
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 |
} |
329 | 578 |
|
330 | 579 |
private: |
331 | 580 |
const GridGraph& _graph; |
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(); |
368 | 596 |
Parent::notifier(Edge()).clear(); |
369 | 597 |
Parent::notifier(Node()).clear(); |
370 | 598 |
construct(width, height); |
371 | 599 |
Parent::notifier(Node()).build(); |
372 | 600 |
Parent::notifier(Edge()).build(); |
373 | 601 |
Parent::notifier(Arc()).build(); |
374 | 602 |
} |
375 | 603 |
|
376 | 604 |
/// \brief The node on the given position. |
377 | 605 |
/// |
378 | 606 |
/// Gives back the node on the given position. |
379 | 607 |
Node operator()(int i, int j) const { |
380 | 608 |
return Parent::operator()(i, j); |
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 |
/// |
385 | 620 |
/// Gives back the row index of the node. |
386 | 621 |
int row(Node n) const { |
387 | 622 |
return Parent::row(n); |
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 |
... | ... |
@@ -117,24 +117,25 @@ |
117 | 117 |
checkConcept<ExtendableGraphComponent<>, ListGraph>(); |
118 | 118 |
checkConcept<ClearableGraphComponent<>, ListGraph>(); |
119 | 119 |
checkConcept<ErasableGraphComponent<>, ListGraph>(); |
120 | 120 |
} |
121 | 121 |
{ // Checking SmartGraph |
122 | 122 |
checkConcept<Graph, SmartGraph>(); |
123 | 123 |
checkConcept<AlterableGraphComponent<>, SmartGraph>(); |
124 | 124 |
checkConcept<ExtendableGraphComponent<>, SmartGraph>(); |
125 | 125 |
checkConcept<ClearableGraphComponent<>, SmartGraph>(); |
126 | 126 |
} |
127 | 127 |
// { // Checking FullGraph |
128 | 128 |
// checkConcept<Graph, FullGraph>(); |
129 |
// checkGraphIterators<FullGraph>(); |
|
129 | 130 |
// } |
130 | 131 |
{ // Checking GridGraph |
131 | 132 |
checkConcept<Graph, GridGraph>(); |
132 | 133 |
} |
133 | 134 |
} |
134 | 135 |
|
135 | 136 |
template <typename Graph> |
136 | 137 |
void checkGraphValidity() { |
137 | 138 |
TEMPLATE_GRAPH_TYPEDEFS(Graph); |
138 | 139 |
Graph g; |
139 | 140 |
|
140 | 141 |
Node |
... | ... |
@@ -177,109 +178,119 @@ |
177 | 178 |
|
178 | 179 |
check(!g.valid(n1), "Wrong validity check"); |
179 | 180 |
check(g.valid(n2), "Wrong validity check"); |
180 | 181 |
check(g.valid(n3), "Wrong validity check"); |
181 | 182 |
check(!g.valid(e1), "Wrong validity check"); |
182 | 183 |
check(g.valid(e2), "Wrong validity check"); |
183 | 184 |
|
184 | 185 |
check(!g.valid(g.nodeFromId(-1)), "Wrong validity check"); |
185 | 186 |
check(!g.valid(g.edgeFromId(-1)), "Wrong validity check"); |
186 | 187 |
check(!g.valid(g.arcFromId(-1)), "Wrong validity check"); |
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 |
|
261 | 269 |
void checkGraphs() { |
262 | 270 |
{ // Checking ListGraph |
263 | 271 |
checkGraph<ListGraph>(); |
264 | 272 |
checkGraphValidityErase<ListGraph>(); |
265 | 273 |
} |
266 | 274 |
{ // Checking SmartGraph |
267 | 275 |
checkGraph<SmartGraph>(); |
268 | 276 |
checkGraphValidity<SmartGraph>(); |
269 | 277 |
} |
270 | 278 |
// { // Checking FullGraph |
271 | 279 |
// FullGraph g(5); |
272 | 280 |
// checkGraphNodeList(g, 5); |
273 | 281 |
// checkGraphEdgeList(g, 10); |
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 |
} |
280 | 291 |
|
281 | 292 |
int main() { |
282 | 293 |
checkConcepts(); |
283 | 294 |
checkGraphs(); |
284 | 295 |
return 0; |
285 | 296 |
} |
0 comments (0 inline)