6 * $Date: 2012-07-06 11:39:38 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
10 * \brief Offers variety of possible SimDraw creations.
12 * \author Michael Schulz and Daniel Lueckerath
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
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
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.
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.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
43 #include <ogdf/simultaneous/SimDrawCreatorSimple.h>
44 #include <ogdf/basic/Array2D.h>
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
)
55 node v0
= m_G
->newNode();
57 Array2D
<node
> w(0,n
,0,n
);
60 for(int i
=0; i
<n
; i
++)
62 v
[i
] = m_G
->newNode();
63 for(int j
=0; j
<n
; j
++)
65 w(i
,j
) = m_G
->newNode();
68 for(int i
=0; i
<n
; i
++)
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
++)
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);
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()
94 for(int i
= 1; i
< 10; i
++)
95 v
[i
] = m_G
->newNode();
97 e
= m_G
->newEdge(v
[1],v
[2]);
98 m_GA
->addSubGraph(e
,0);
100 e
= m_G
->newEdge(v
[1],v
[3]);
101 m_GA
->addSubGraph(e
,0);
102 m_GA
->addSubGraph(e
,1);
104 e
= m_G
->newEdge(v
[1],v
[4]);
105 m_GA
->addSubGraph(e
,0);
107 e
= m_G
->newEdge(v
[1],v
[5]);
108 m_GA
->addSubGraph(e
,0);
110 e
= m_G
->newEdge(v
[1],v
[6]);
111 m_GA
->addSubGraph(e
,0);
113 e
= m_G
->newEdge(v
[2],v
[3]);
114 m_GA
->addSubGraph(e
,0);
116 e
= m_G
->newEdge(v
[2],v
[4]);
117 m_GA
->addSubGraph(e
,1);
119 e
= m_G
->newEdge(v
[2],v
[5]);
120 m_GA
->addSubGraph(e
,0);
122 e
= m_G
->newEdge(v
[2],v
[6]);
123 m_GA
->addSubGraph(e
,0);
125 e
= m_G
->newEdge(v
[2],v
[7]);
126 m_GA
->addSubGraph(e
,0);
127 m_GA
->addSubGraph(e
,1);
129 e
= m_G
->newEdge(v
[2],v
[8]);
130 m_GA
->addSubGraph(e
,0);
132 e
= m_G
->newEdge(v
[2],v
[9]);
133 m_GA
->addSubGraph(e
,0);
135 e
= m_G
->newEdge(v
[3],v
[4]);
136 m_GA
->addSubGraph(e
,0);
138 e
= m_G
->newEdge(v
[3],v
[5]);
139 m_GA
->addSubGraph(e
,0);
140 m_GA
->addSubGraph(e
,1);
142 e
= m_G
->newEdge(v
[4],v
[5]);
143 m_GA
->addSubGraph(e
,0);
144 m_GA
->addSubGraph(e
,1);
146 e
= m_G
->newEdge(v
[5],v
[6]);
147 m_GA
->addSubGraph(e
,0);
149 e
= m_G
->newEdge(v
[5],v
[9]);
150 m_GA
->addSubGraph(e
,0);
152 e
= m_G
->newEdge(v
[6],v
[7]);
153 m_GA
->addSubGraph(e
,0);
155 e
= m_G
->newEdge(v
[6],v
[9]);
156 m_GA
->addSubGraph(e
,0);
158 e
= m_G
->newEdge(v
[6],v
[8]);
159 m_GA
->addSubGraph(e
,1);
161 e
= m_G
->newEdge(v
[7],v
[8]);
162 m_GA
->addSubGraph(e
,0);
164 e
= m_G
->newEdge(v
[7],v
[9]);
165 m_GA
->addSubGraph(e
,0);
166 m_GA
->addSubGraph(e
,1);
168 e
= m_G
->newEdge(v
[8],v
[9]);
169 m_GA
->addSubGraph(e
,0);
170 m_GA
->addSubGraph(e
,1);
172 }//end createPathPlanar_EK04
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()
181 Array
<node
> v(number
);
184 for(int i
= 0; i
< number
; i
++)
185 v
[i
] = m_G
->newNode();
187 for(int i
= 0; i
< number
-1; i
++)
189 for(int j
= i
+1; j
< number
; j
++)
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);
195 m_GA
->addSubGraph(e
,1);
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()
208 Array
<node
> v(number
);
211 for(int i
= 0; i
< number
; i
++)
212 v
[i
] = m_G
->newNode();
214 for(int i
= 0; i
< 3; i
++)
216 for(int j
= i
+1; j
<= 2; j
++)
218 e
= m_G
->newEdge(v
[i
],v
[j
]);
219 m_GA
->addSubGraph(e
,0);
220 m_GA
->addSubGraph(e
,1);
224 for(int i
= 3; i
< number
; i
++)
226 for(int j
= 0; j
< i
; j
++)
228 e
= m_G
->newEdge(v
[i
],v
[j
]);
230 m_GA
->addSubGraph(e
,0);
232 m_GA
->addSubGraph(e
,1);
236 }//end createK5_GJPSS06
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()
245 Array
<node
> v(number
);
248 for(int i
= 0; i
< number
; i
++)
249 v
[i
] = m_G
->newNode();
251 for(int i
= 0; i
< number
-1; i
++)
253 e
= m_G
->newEdge(v
[i
],v
[i
+1]);
256 m_GA
->addSubGraph(e
,0);
257 m_GA
->addSubGraph(e
,1);
261 m_GA
->addSubGraph(e
,0);
263 e
= m_G
->newEdge(v
[i
],v
[number
-1]);
264 m_GA
->addSubGraph(e
,1);
267 e
= m_G
->newEdge(v
[number
-1],v
[0]);
268 m_GA
->addSubGraph(e
,0);
270 e
= m_G
->newEdge(v
[0],v
[3]);
271 m_GA
->addSubGraph(e
,1);
273 e
= m_G
->newEdge(v
[1],v
[4]);
274 m_GA
->addSubGraph(e
,0);
275 m_GA
->addSubGraph(e
,1);
277 }// end createOuterplanar_BCDEEIKLM03
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
)
286 OGDF_ASSERT( N
>=1 && nodeNumber
>=1 );
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();
298 for(int i
= 0; i
< nodeNumber
; i
++)
300 p
[i
] = m_G
->newNode();
301 q
[i
] = m_G
->newNode();
302 r
[i
] = m_G
->newNode();
305 for(int i
= 0; i
< 4; i
++)
307 outerNodes
[i
] = m_G
->newNode();
308 outerOuterNodes
[i
] = m_G
->newNode();
314 for(int i
= 0; i
< N
; i
++)
316 c
[i
] = m_G
->newNode();
318 e
= m_G
->newEdge(c
[i
],nodeC
);
319 m_GA
->addSubGraph(e
,1);
321 e
= m_G
->newEdge(a
,c
[i
]);
322 m_GA
->addSubGraph(e
,1);
324 //eventuell unnoetig?
325 e
= m_G
->newEdge(outerNodes
[1],c
[i
]);
326 m_GA
->addSubGraph(e
,1);
331 e
= m_G
->newEdge(a
,nodeC
);
332 m_GA
->addSubGraph(e
,1);
335 e
= m_G
->newEdge(a
,b
);
336 m_GA
->addSubGraph(e
,0);
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);
343 for(int i
= 0; i
< nodeNumber
-1; i
++)
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);
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);
356 for(int i
= 0; i
< nodeNumber
; i
++)
358 e
= m_G
->newEdge(p
[i
],q
[i
]);
359 m_GA
->addSubGraph(e
,2);
361 m_GA
->addSubGraph(e
,0);
363 m_GA
->addSubGraph(e
,1);
365 e
= m_G
->newEdge(r
[i
],q
[i
]);
366 m_GA
->addSubGraph(e
,2);
368 m_GA
->addSubGraph(e
,1);
370 m_GA
->addSubGraph(e
,0);
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);
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);
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);
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);
393 for(int i
= 0; i
< 4; i
++)
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);
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);
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);
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);
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);
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);
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);
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);
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);
447 //*************************************************************
448 // creates Graph with numberofBasic*2 outer, numberOfParallels*numberOfBasic
449 // inner Nodes and one Root.
450 void SimDrawCreatorSimple::createWheel(int numberOfParallels
, int numberOfBasic
)
452 OGDF_ASSERT(numberOfBasic
> 0 && numberOfParallels
>= 0);
454 node root
= m_G
->newNode();
455 Array
<node
> v(numberOfBasic
*2);
458 for(int i
= 0; i
< numberOfBasic
*2; i
++)
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
);
466 for(int i
= 0; i
< numberOfBasic
*2; i
++)
468 if((i
>= 0) && (i
< (numberOfBasic
*2)-1))
470 e
= m_G
->newEdge(v
[i
],v
[i
+1]);
471 for(int j
= 0; j
< numberOfBasic
; j
++)
472 m_GA
->addSubGraph(e
,j
);
474 if(i
== (numberOfBasic
*2)-1)
476 e
= m_G
->newEdge(v
[i
],v
[0]);
477 for(int j
= 0; j
< numberOfBasic
; j
++)
478 m_GA
->addSubGraph(e
,j
);
481 if((numberOfBasic
+i
) < (numberOfBasic
*2))
483 for(int j
= 0; j
< numberOfParallels
; j
++)
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
);
497 //*************************************************************
498 // creates simultaneously planar simulatenous graph with n+1 basic graphs.
500 void SimDrawCreatorSimple::createExpo(int n
)
503 OGDF_ASSERT(n
>0 && n
<31);
507 Array
<node
> twinNodesU(n
+1);
508 Array
<node
> outerNodes(6);
511 for(int i
= 0; i
< n
+1; i
++)
513 u
[i
] = m_G
->newNode();
514 v
[i
] = m_G
->newNode();
515 twinNodesU
[i
] = m_G
->newNode();
518 for(int i
= 0; i
< 6; i
++)
519 outerNodes
[i
] = m_G
->newNode();
521 for(int i
= 1; i
< 3 ; i
++)
523 e
= m_G
->newEdge(outerNodes
[i
],outerNodes
[i
+1]);
524 for(int j
= 0; j
< 4; j
++)
525 m_GA
->addSubGraph(e
,j
);
528 e
= m_G
->newEdge(outerNodes
[4],outerNodes
[5]);
529 for(int j
= 0; j
< 4; j
++)
530 m_GA
->addSubGraph(e
,j
);
532 e
= m_G
->newEdge(outerNodes
[5],outerNodes
[0]);
533 for(int j
= 0; j
< 4; j
++)
534 m_GA
->addSubGraph(e
,j
);
536 for(int i
= 0; i
< n
+1; i
++)
538 e
= m_G
->newEdge(u
[i
],twinNodesU
[i
]);
539 for(int j
= 0; j
< 4; j
++)
540 m_GA
->addSubGraph(e
,j
);
543 for(int i
= 0; i
< n
; i
++)
545 e
= m_G
->newEdge(twinNodesU
[i
],twinNodesU
[i
+1]);
546 for(int j
= 0; j
< 4; j
++)
547 m_GA
->addSubGraph(e
,j
);
551 e
= m_G
->newEdge(outerNodes
[3],twinNodesU
[i
]);
552 for(int j
= 0; j
< 4; j
++)
553 m_GA
->addSubGraph(e
,j
);
557 e
= m_G
->newEdge(outerNodes
[4],twinNodesU
[n
]);
558 for(int j
= 0; j
< 4; j
++)
559 m_GA
->addSubGraph(e
,j
);
561 e
= m_G
->newEdge(v
[0],outerNodes
[0]);
562 for(int j
= 0; j
< 4; j
++)
563 m_GA
->addSubGraph(e
,j
);
565 e
= m_G
->newEdge(v
[0],outerNodes
[1]);
566 for(int j
= 0; j
< 4; j
++)
567 m_GA
->addSubGraph(e
,j
);
569 for(int i
= 0; i
< n
+1; i
++)
571 e
= m_G
->newEdge(u
[i
],v
[i
]);
573 m_GA
->addSubGraph(e
,0);
576 m_GA
->addSubGraph(e
,1);
578 m_GA
->addSubGraph(e
,2);
580 m_GA
->addSubGraph(e
,3);
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);
589 e
= m_G
->newEdge(outerNodes
[2],v
[1]);
590 m_GA
->addSubGraph(e
,0);
592 for(int i
= 1; i
< n
+1; i
++)
594 e
= m_G
->newEdge(v
[i
],u
[i
-1]);
595 m_GA
->addSubGraph(e
,0);
597 m_GA
->addSubGraph(e
,2);
600 for(int i
= 0; i
< 2; i
++)
602 e
= m_G
->newEdge(u
[i
],v
[i
+2]);
603 m_GA
->addSubGraph(e
,0);
604 m_GA
->addSubGraph(e
,2);
606 m_GA
->addSubGraph(e
,3);
609 e
= m_G
->newEdge(u
[n
-1],u
[n
]);
610 for(int j
= 0; j
< 4; j
++)
612 m_GA
->addSubGraph(e
,j
);
616 } // end namespace ogdf