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