1 /** \file
2 * \brief Offers variety of possible SimDraw creations.
3 *
4 * \author Michael Schulz and Daniel Lueckerath
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32 #include <ogdf/simultaneous/SimDrawCreatorSimple.h>
33 #include <ogdf/basic/Array2D.h>
34
35 namespace ogdf {
36
37 // creates simultaneous graph given by two trees with n^2+n+1 nodes
38 // see Geyer,Kaufmann,Vrto (GD'05) for description of graph
createTrees_GKV05(int n)39 void SimDrawCreatorSimple::createTrees_GKV05(int n)
40 {
41 OGDF_ASSERT( n>=1 );
42
43 node v0 = m_G->newNode();
44 Array<node> v(n);
45 Array2D<node> w(0,n,0,n);
46 edge e;
47
48 for(int i=0; i<n; i++)
49 {
50 v[i] = m_G->newNode();
51 for(int j=0; j<n; j++)
52 if(i!=j)
53 w(i,j) = m_G->newNode();
54 }
55
56 for(int i=0; i<n; i++)
57 {
58 e = m_G->newEdge(v0,v[i]);
59 m_GA->addSubGraph(e,0);
60 m_GA->addSubGraph(e,1);
61 for(int j=0; j<n; j++)
62 if(i!=j)
63 {
64 e = m_G->newEdge(v[i],w(i,j));
65 m_GA->addSubGraph(e,0);
66 e = m_G->newEdge(v[j],w(i,j));
67 m_GA->addSubGraph(e,1);
68 }
69 }
70 }
71
72 // creates simultaneous graph given by a path and a planar graph
73 // see Erten, Kobourov (GD'04) for description of instance
createPathPlanar_EK04()74 void SimDrawCreatorSimple::createPathPlanar_EK04()
75 {
76 node v[10];
77 edge e;
78
79 for(int i= 1; i< 10; i++)
80 v[i] = m_G->newNode();
81
82 e = m_G->newEdge(v[1],v[2]);
83 m_GA->addSubGraph(e,0);
84
85 e = m_G->newEdge(v[1],v[3]);
86 m_GA->addSubGraph(e,0);
87 m_GA->addSubGraph(e,1);
88
89 e = m_G->newEdge(v[1],v[4]);
90 m_GA->addSubGraph(e,0);
91
92 e = m_G->newEdge(v[1],v[5]);
93 m_GA->addSubGraph(e,0);
94
95 e = m_G->newEdge(v[1],v[6]);
96 m_GA->addSubGraph(e,0);
97
98 e = m_G->newEdge(v[2],v[3]);
99 m_GA->addSubGraph(e,0);
100
101 e = m_G->newEdge(v[2],v[4]);
102 m_GA->addSubGraph(e,1);
103
104 e = m_G->newEdge(v[2],v[5]);
105 m_GA->addSubGraph(e,0);
106
107 e = m_G->newEdge(v[2],v[6]);
108 m_GA->addSubGraph(e,0);
109
110 e = m_G->newEdge(v[2],v[7]);
111 m_GA->addSubGraph(e,0);
112 m_GA->addSubGraph(e,1);
113
114 e = m_G->newEdge(v[2],v[8]);
115 m_GA->addSubGraph(e,0);
116
117 e = m_G->newEdge(v[2],v[9]);
118 m_GA->addSubGraph(e,0);
119
120 e = m_G->newEdge(v[3],v[4]);
121 m_GA->addSubGraph(e,0);
122
123 e = m_G->newEdge(v[3],v[5]);
124 m_GA->addSubGraph(e,0);
125 m_GA->addSubGraph(e,1);
126
127 e = m_G->newEdge(v[4],v[5]);
128 m_GA->addSubGraph(e,0);
129 m_GA->addSubGraph(e,1);
130
131 e = m_G->newEdge(v[5],v[6]);
132 m_GA->addSubGraph(e,0);
133
134 e = m_G->newEdge(v[5],v[9]);
135 m_GA->addSubGraph(e,0);
136
137 e = m_G->newEdge(v[6],v[7]);
138 m_GA->addSubGraph(e,0);
139
140 e = m_G->newEdge(v[6],v[9]);
141 m_GA->addSubGraph(e,0);
142
143 e = m_G->newEdge(v[6],v[8]);
144 m_GA->addSubGraph(e,1);
145
146 e = m_G->newEdge(v[7],v[8]);
147 m_GA->addSubGraph(e,0);
148
149 e = m_G->newEdge(v[7],v[9]);
150 m_GA->addSubGraph(e,0);
151 m_GA->addSubGraph(e,1);
152
153 e = m_G->newEdge(v[8],v[9]);
154 m_GA->addSubGraph(e,0);
155 m_GA->addSubGraph(e,1);
156 }
157
158 // creates simultaneous graph given by a colored K5
159 // see Erten, Kobourov (GD'04) for description of instance
createK5_EK04()160 void SimDrawCreatorSimple::createK5_EK04()
161 {
162 int number = 5;
163 Array<node> v(number);
164 edge e;
165
166 for(int i = 0; i < number; i++)
167 v[i] = m_G->newNode();
168
169 for(int i = 0; i < number-1; i++)
170 {
171 for(int j = i+1; j < number; j++)
172 {
173 e = m_G->newEdge(v[i],v[j]);
174 if ((j == i+1) || ((j == number-1) && (i == 0)))
175 m_GA->addSubGraph(e,0);
176 else
177 m_GA->addSubGraph(e,1);
178 }
179 }
180 }
181
182 // creates simultaneous graph given by a colored K5
183 // see Gassner, Juenger, Percan, Schaefer, Schulz (WG'06) for description of instance
createK5_GJPSS06()184 void SimDrawCreatorSimple::createK5_GJPSS06()
185 {
186 int number = 5;
187 Array<node> v(number);
188 edge e;
189
190 for(int i = 0; i < number; i++)
191 v[i] = m_G->newNode();
192
193 for(int i = 0; i < 3; i++)
194 {
195 for(int j = i+1; j <= 2; j++)
196 {
197 e = m_G->newEdge(v[i],v[j]);
198 m_GA->addSubGraph(e,0);
199 m_GA->addSubGraph(e,1);
200 }
201 }
202
203 for(int i = 3; i < number; i++)
204 {
205 for(int j = 0; j < i; j++)
206 {
207 e = m_G->newEdge(v[i],v[j]);
208 if(j == 3)
209 m_GA->addSubGraph(e,0);
210 else
211 m_GA->addSubGraph(e,1);
212 }
213 }
214 }
215
216 // creates simultaneous graph given by two outerplanar graphs
217 // see Brass et al. (WADS '03) for description of instance
createOuterplanar_BCDEEIKLM03()218 void SimDrawCreatorSimple::createOuterplanar_BCDEEIKLM03()
219 {
220 int number = 6;
221 Array<node> v(number);
222 edge e;
223
224 for(int i = 0; i < number; i++)
225 v[i] = m_G->newNode();
226
227 for(int i = 0; i < number-1; i++)
228 {
229 e = m_G->newEdge(v[i],v[i+1]);
230 if(!(i == 2))
231 {
232 m_GA->addSubGraph(e,0);
233 m_GA->addSubGraph(e,1);
234 }
235 else
236 {
237 m_GA->addSubGraph(e,0);
238
239 e = m_G->newEdge(v[i],v[number-1]);
240 m_GA->addSubGraph(e,1);
241 }
242 }
243 e = m_G->newEdge(v[number-1],v[0]);
244 m_GA->addSubGraph(e,0);
245
246 e = m_G->newEdge(v[0],v[3]);
247 m_GA->addSubGraph(e,1);
248
249 e = m_G->newEdge(v[1],v[4]);
250 m_GA->addSubGraph(e,0);
251 m_GA->addSubGraph(e,1);
252 }
253
254 // creates simultaneous graph with crossing number 0 but
255 // with multicrossings of adjacent edges in mincross drawing
256 // see Kratochvil (GD '98) for description of instance
createKrat98(int N,int nodeNumber)257 void SimDrawCreatorSimple::createKrat98(int N, int nodeNumber)
258 {
259 OGDF_ASSERT(N>=1);
260 OGDF_ASSERT(nodeNumber>=1);
261
262 Array<node> p(nodeNumber);
263 Array<node> q(nodeNumber);
264 Array<node> r(nodeNumber);
265 Array<node> outerNodes(4);
266 Array<node> outerOuterNodes(4);
267 node a = m_G->newNode();
268 node b = m_G->newNode();
269 node nodeC = m_G->newNode();
270 edge e;
271
272 for(int i = 0; i < nodeNumber; i++)
273 {
274 p[i] = m_G->newNode();
275 q[i] = m_G->newNode();
276 r[i] = m_G->newNode();
277 }
278
279 for(int i = 0; i < 4; i++)
280 {
281 outerNodes[i] = m_G->newNode();
282 outerOuterNodes[i] = m_G->newNode();
283 }
284
285 if(N > 1)
286 {
287 Array<node> c(N);
288 for(int i = 0; i < N; i++)
289 {
290 c[i] = m_G->newNode();
291
292 e = m_G->newEdge(c[i],nodeC);
293 m_GA->addSubGraph(e,1);
294
295 e = m_G->newEdge(a,c[i]);
296 m_GA->addSubGraph(e,1);
297
298 //eventuell unnoetig?
299 e = m_G->newEdge(outerNodes[1],c[i]);
300 m_GA->addSubGraph(e,1);
301 }
302 }
303 else
304 {
305 e = m_G->newEdge(a,nodeC);
306 m_GA->addSubGraph(e,1);
307 }
308
309 e = m_G->newEdge(a,b);
310 m_GA->addSubGraph(e,0);
311
312 e = m_G->newEdge(b,nodeC);
313 m_GA->addSubGraph(e,0);
314 m_GA->addSubGraph(e,1);
315 m_GA->addSubGraph(e,2);
316
317 for(int i = 0; i < nodeNumber-1; i++)
318 {
319 e = m_G->newEdge(p[i],p[i+1]);
320 m_GA->addSubGraph(e,0);
321 m_GA->addSubGraph(e,1);
322 m_GA->addSubGraph(e,2);
323
324 e = m_G->newEdge(r[i],r[i+1]);
325 m_GA->addSubGraph(e,0);
326 m_GA->addSubGraph(e,1);
327 m_GA->addSubGraph(e,2);
328 }
329
330 for(int i = 0; i < nodeNumber; i++)
331 {
332 e = m_G->newEdge(p[i],q[i]);
333 m_GA->addSubGraph(e,2);
334 if(i%2)
335 m_GA->addSubGraph(e,0);
336 else
337 m_GA->addSubGraph(e,1);
338
339 e = m_G->newEdge(r[i],q[i]);
340 m_GA->addSubGraph(e,2);
341 if(i%2)
342 m_GA->addSubGraph(e,1);
343 else
344 m_GA->addSubGraph(e,0);
345 }
346
347 e = m_G->newEdge(a,p[0]);
348 m_GA->addSubGraph(e,0);
349 m_GA->addSubGraph(e,1);
350 m_GA->addSubGraph(e,2);
351
352 e = m_G->newEdge(a,r[0]);
353 m_GA->addSubGraph(e,0);
354 m_GA->addSubGraph(e,1);
355 m_GA->addSubGraph(e,2);
356
357 e = m_G->newEdge(r[nodeNumber-1],b);
358 m_GA->addSubGraph(e,0);
359 m_GA->addSubGraph(e,1);
360 m_GA->addSubGraph(e,2);
361
362 e = m_G->newEdge(p[nodeNumber-1],nodeC);
363 m_GA->addSubGraph(e,0);
364 m_GA->addSubGraph(e,1);
365 m_GA->addSubGraph(e,2);
366
367 for(int i = 0; i < 4; i++)
368 {
369 e = m_G->newEdge(outerOuterNodes[i],outerNodes[i]);
370 m_GA->addSubGraph(e,0);
371 m_GA->addSubGraph(e,1);
372 m_GA->addSubGraph(e,2);
373
374 if(i < 3)
375 {
376 e = m_G->newEdge(outerOuterNodes[i],outerOuterNodes[i+1]);
377 m_GA->addSubGraph(e,0);
378 m_GA->addSubGraph(e,1);
379 m_GA->addSubGraph(e,2);
380 }
381 }
382
383 e = m_G->newEdge(outerOuterNodes[3],outerOuterNodes[0]);
384 m_GA->addSubGraph(e,0);
385 m_GA->addSubGraph(e,1);
386 m_GA->addSubGraph(e,2);
387
388 e = m_G->newEdge(outerNodes[1],outerNodes[2]);
389 m_GA->addSubGraph(e,0);
390 m_GA->addSubGraph(e,1);
391 m_GA->addSubGraph(e,2);
392
393 e = m_G->newEdge(outerNodes[3],outerNodes[0]);
394 m_GA->addSubGraph(e,0);
395 m_GA->addSubGraph(e,1);
396 m_GA->addSubGraph(e,2);
397
398 e = m_G->newEdge(outerNodes[0],a);
399 m_GA->addSubGraph(e,0);
400 m_GA->addSubGraph(e,1);
401 m_GA->addSubGraph(e,2);
402
403 e = m_G->newEdge(outerNodes[3],a);
404 m_GA->addSubGraph(e,0);
405 m_GA->addSubGraph(e,1);
406 m_GA->addSubGraph(e,2);
407
408 e = m_G->newEdge(outerNodes[1],nodeC);
409 m_GA->addSubGraph(e,0);
410 m_GA->addSubGraph(e,1);
411 m_GA->addSubGraph(e,2);
412
413 e = m_G->newEdge(outerNodes[2],b);
414 m_GA->addSubGraph(e,0);
415 m_GA->addSubGraph(e,1);
416 m_GA->addSubGraph(e,2);
417 }
418
419 // creates Graph with numberofBasic*2 outer, numberOfParallels*numberOfBasic
420 // inner Nodes and one Root.
createWheel(int numberOfParallels,int numberOfBasic)421 void SimDrawCreatorSimple::createWheel(int numberOfParallels, int numberOfBasic )
422 {
423 OGDF_ASSERT(numberOfBasic > 0);
424 OGDF_ASSERT(numberOfParallels >= 0);
425
426 node root = m_G->newNode();
427 Array<node> v(numberOfBasic*2);
428 edge e;
429
430 for(int i = 0; i < numberOfBasic*2; i++)
431 {
432 v[i] = m_G->newNode();
433 e = m_G->newEdge(root,v[i]);
434 for(int j = 0; j < numberOfBasic; j++)
435 m_GA->addSubGraph(e,j);
436 }
437
438 for(int i = 0; i < numberOfBasic*2; i++)
439 {
440 if((i >= 0) && (i < (numberOfBasic*2)-1))
441 {
442 e = m_G->newEdge(v[i],v[i+1]);
443 for(int j = 0; j < numberOfBasic; j++)
444 m_GA->addSubGraph(e,j);
445 }
446 if(i == (numberOfBasic*2)-1)
447 {
448 e = m_G->newEdge(v[i],v[0]);
449 for(int j = 0; j < numberOfBasic; j++)
450 m_GA->addSubGraph(e,j);
451 }
452
453 if((numberOfBasic+i) < (numberOfBasic*2))
454 {
455 for(int j = 0; j < numberOfParallels; j++)
456 {
457 node tmpNOP = m_G->newNode();
458 e = m_G->newEdge(v[i],tmpNOP);
459 m_GA->addSubGraph(e,i);
460 e = m_G->newEdge(v[numberOfBasic+i],tmpNOP);
461 m_GA->addSubGraph(e,i);
462 }
463 }
464 }
465 }
466
467 // creates simultaneously planar simulatenous graph with n+1 basic graphs.
createExpo(int n)468 void SimDrawCreatorSimple::createExpo(int n)
469 {
470 OGDF_ASSERT(n>0);
471 OGDF_ASSERT(n<31);
472
473 Array<node> u(n+1);
474 Array<node> v(n+1);
475 Array<node> twinNodesU(n+1);
476 Array<node> outerNodes(6);
477 edge e;
478
479 for(int i = 0; i < n+1; i++)
480 {
481 u[i] = m_G->newNode();
482 v[i] = m_G->newNode();
483 twinNodesU[i] = m_G->newNode();
484 }
485
486 for(int i = 0; i < 6; i++)
487 outerNodes[i] = m_G->newNode();
488
489 for(int i = 1; i < 3 ; i++)
490 {
491 e = m_G->newEdge(outerNodes[i],outerNodes[i+1]);
492 for(int j = 0; j < 4; j++)
493 m_GA->addSubGraph(e,j);
494 }
495
496 e = m_G->newEdge(outerNodes[4],outerNodes[5]);
497 for(int j = 0; j < 4; j++)
498 m_GA->addSubGraph(e,j);
499
500 e = m_G->newEdge(outerNodes[5],outerNodes[0]);
501 for(int j = 0; j < 4; j++)
502 m_GA->addSubGraph(e,j);
503
504 for(int i = 0; i < n+1; i++)
505 {
506 e = m_G->newEdge(u[i],twinNodesU[i]);
507 for(int j = 0; j < 4; j++)
508 m_GA->addSubGraph(e,j);
509 }
510
511 for(int i = 0; i < n; i++)
512 {
513 e = m_G->newEdge(twinNodesU[i],twinNodesU[i+1]);
514 for(int j = 0; j < 4; j++)
515 m_GA->addSubGraph(e,j);
516
517 if(i == 0)
518 {
519 e = m_G->newEdge(outerNodes[3],twinNodesU[i]);
520 for(int j = 0; j < 4; j++)
521 m_GA->addSubGraph(e,j);
522 }
523 }
524
525 e = m_G->newEdge(outerNodes[4],twinNodesU[n]);
526 for(int j = 0; j < 4; j++)
527 m_GA->addSubGraph(e,j);
528
529 e = m_G->newEdge(v[0],outerNodes[0]);
530 for(int j = 0; j < 4; j++)
531 m_GA->addSubGraph(e,j);
532
533 e = m_G->newEdge(v[0],outerNodes[1]);
534 for(int j = 0; j < 4; j++)
535 m_GA->addSubGraph(e,j);
536
537 for(int i = 0; i < n+1; i++)
538 {
539 e = m_G->newEdge(u[i],v[i]);
540 if(i == 0)
541 m_GA->addSubGraph(e,0);
542 else
543 {
544 m_GA->addSubGraph(e,1);
545 if(i == 1)
546 m_GA->addSubGraph(e,2);
547 if(i == 2)
548 m_GA->addSubGraph(e,3);
549 }
550 }
551
552 e = m_G->newEdge(outerNodes[5],u[n]);
553 m_GA->addSubGraph(e,0);
554 m_GA->addSubGraph(e,2);
555 m_GA->addSubGraph(e,3);
556
557 e = m_G->newEdge(outerNodes[2],v[1]);
558 m_GA->addSubGraph(e,0);
559
560 for(int i = 1; i < n+1; i++)
561 {
562 e = m_G->newEdge(v[i],u[i-1]);
563 m_GA->addSubGraph(e,0);
564 if(i == 3)
565 m_GA->addSubGraph(e,2);
566 }
567
568 for(int i = 0; i < 2; i++)
569 {
570 e = m_G->newEdge(u[i],v[i+2]);
571 m_GA->addSubGraph(e,0);
572 m_GA->addSubGraph(e,2);
573 if(i == 1)
574 m_GA->addSubGraph(e,3);
575 }
576
577 e = m_G->newEdge(u[n-1],u[n]);
578 for(int j = 0; j < 4; j++)
579 if(j != 1)
580 m_GA->addSubGraph(e,j);
581 }
582
583 }
584