1/** \file
2 * \brief Tests for ogdf::GraphCopy and ogdf::GraphCopySimple.
3 *
4 * \author Mirko Wagner
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/basic/GraphCopy.h>
33#include <ogdf/basic/graph_generators.h>
34#include <ogdf/basic/extended_graph_alg.h>
35#include <ogdf/basic/FaceSet.h>
36
37#include <testing.h>
38
39//! Tests if a GraphCopy is initialized correctly
40/**
41 * \param vCopy a List of all the Nodes that should be active
42 * \param eCopy an EdgeArray<edge> of the \p graph there every edge is assigned an edge
43 * from GraphCopy if it is active or \c nullptr if it isn't active
44 * \param graph a pointer to the graph of which graphCopy is a GraphCopy of
45 * \param graphCopy a pointer to the GraphCopy
46 * \param allAdjEdges if all or none of the nodes of a connected component should be active,
47 * every adjacent edge of an active node should be active too
48 * \tparam the kind of graph-copy
49 */
50template<typename GCType>
51void testInitGraph(const Graph &graph, const GCType &graphCopy,
52 bool allAdjEdges,
53 const List<node> &vCopy,
54 const EdgeArray<edge> &eCopy)
55{
56 int numberOfActiveNodes = 0;
57 int numberOfAdjActiveEdges = 0;
58 for(node v : vCopy){
59 numberOfActiveNodes++;
60 AssertThat(graphCopy.copy(v), !IsNull());
61 for(adjEntry adj = v->firstAdj(); adj != nullptr; adj = adj->succ()){
62 if(graphCopy.copy(adj->theEdge()) != nullptr){
63 numberOfAdjActiveEdges++;
64 } else {
65 if(allAdjEdges){
66 AssertThat(graphCopy.copy(adj->theEdge()), !IsNull());
67 }
68 }
69 }
70 }
71 int nodeCounter = 0;
72 for(node v : graph.nodes){
73 if(graphCopy.copy(v) != nullptr){
74 nodeCounter++;
75 }
76 }
77 AssertThat(nodeCounter, Equals(numberOfActiveNodes));
78 int edgeCounter = 0;
79 for(edge e : graph.edges){
80 if(graphCopy.copy(e) != nullptr){
81 AssertThat(eCopy[e], !IsNull());
82 edgeCounter++;
83 }
84 }
85 AssertThat(numberOfAdjActiveEdges/2, Equals(edgeCounter));
86}
87
88template<typename GCType>
89void testInitGraph(const Graph &graph, const GCType &graphCopy, bool allAdjEdges)
90{
91 List<node> vCopy;
92 graph.allNodes<List<node>>(vCopy);
93
94 EdgeArray<edge> eCopy(graph);
95 for(edge e : graph.edges){
96 eCopy[e] = graphCopy.copy(e);
97 }
98
99 testInitGraph(graph, graphCopy, allAdjEdges, vCopy, eCopy);
100}
101
102/**
103 * Tests common functionality of ogdf::GraphCopy and ogdf::GraphCopySimple.
104 */
105template<typename GCType>
106void describeGraphCopySimple(int numberOfNodes)
107{
108 Graph graph;
109 std::unique_ptr<GCType> graphCopy;
110
111 before_each([&](){
112 randomGraph(graph,numberOfNodes,numberOfNodes*4);
113 graphCopy.reset(new GCType(graph));
114 });
115
116 after_each([&] {
117#ifdef OGDF_DEBUG
118 graphCopy->consistencyCheck();
119#endif
120 });
121
122 describe("simple initialization",[&](){
123 it("is initialized with a given Graph",[&](){
124 testInitGraph<GCType>(graph, *graphCopy, true);
125 });
126
127 it("is initialized with a given graph copy",[&](){
128 GCType graphCopyCopy(*graphCopy);
129 testInitGraph<GCType>(graph, graphCopyCopy, true);
130 });
131
132 it("is re-initialized with some other graph", [&](){
133 Graph initialGraph;
134 randomGraph(initialGraph, numberOfNodes/2, numberOfNodes*2);
135 graphCopy.reset(new GCType(initialGraph));
136 graphCopy->init(graph);
137 testInitGraph(graph, *graphCopy, true);
138 });
139
140 it("supports copy-construction", [&](){
141 GCType copy(*graphCopy);
142
143 AssertThat(copy.numberOfNodes(), Equals(graphCopy->numberOfNodes()));
144 AssertThat(copy.numberOfEdges(), Equals(graphCopy->numberOfEdges()));
145
146 testInitGraph(graph, *graphCopy, true);
147 });
148
149 it("supports copy-construction on a modified copy", [&](){
150 // slightly modify the copy to be copied
151 for(int i = 0; i < numberOfNodes/4; i++) {
152 graphCopy->delNode(graphCopy->chooseNode());
153 graphCopy->delEdge(graphCopy->chooseEdge());
154 }
155
156 // create a single dummy (node, edge)
157 node vNew = graphCopy->newNode();
158 edge eNew = graphCopy->newEdge(graphCopy->chooseNode(), vNew);
159 AssertThat(graphCopy->isDummy(vNew), IsTrue());
160 AssertThat(graphCopy->isDummy(eNew), IsTrue());
161
162 GCType copy(*graphCopy);
163
164 AssertThat(copy.numberOfNodes(), Equals(graphCopy->numberOfNodes()));
165 AssertThat(copy.numberOfEdges(), Equals(graphCopy->numberOfEdges()));
166
167 // verify that there is exactly a single dummy (node, edge)
168 bool foundDummy = false;
169 for(edge e : copy.edges) {
170 bool isDummy = copy.isDummy(e);
171 AssertThat(foundDummy && isDummy, IsFalse());
172 foundDummy |= isDummy;
173 }
174 AssertThat(foundDummy, IsTrue());
175 foundDummy = false;
176 for(node v : copy.nodes) {
177 bool isDummy = copy.isDummy(v);
178 AssertThat(foundDummy && isDummy, IsFalse());
179 foundDummy |= isDummy;
180 }
181 AssertThat(foundDummy, IsTrue());
182 });
183
184
185 it("supports assignment", [&](){
186 GCType copy = *graphCopy;
187
188 AssertThat(copy.numberOfNodes(), Equals(graphCopy->numberOfNodes()));
189 AssertThat(copy.numberOfEdges(), Equals(graphCopy->numberOfEdges()));
190
191 testInitGraph(graph, *graphCopy, true);
192 });
193 });
194
195 it("manages copy and original",[&](){
196 node originalNode=graph.chooseNode();
197 AssertThat(graphCopy->original(graphCopy->copy(originalNode)), Equals(originalNode));
198 edge originalEdge = graph.chooseEdge();
199 AssertThat(graphCopy->original(graphCopy->copy(originalEdge)), Equals(originalEdge));
200 });
201
202 it("maps adjacency entries", [&] {
203 for(edge e : graph.edges) {
204 edge f = graphCopy->copy(e);
205
206 adjEntry adjSrc = graphCopy->copy(e->adjSource());
207 adjEntry adjTgt = graphCopy->copy(e->adjTarget());
208
209 AssertThat(adjSrc->isSource(), IsTrue());
210 AssertThat(adjTgt->isSource(), IsFalse());
211 AssertThat(adjSrc->theEdge() == f, IsTrue());
212 AssertThat(adjTgt->theEdge() == f, IsTrue());
213 AssertThat(graphCopy->original(adjSrc) == e->adjSource(), IsTrue());
214 AssertThat(graphCopy->original(adjTgt) == e->adjTarget(), IsTrue());
215 }
216 });
217
218 it("detects dummies",[&](){
219 randomGraph(graph,numberOfNodes,0);
220 graphCopy.reset(new GCType(graph));
221 AssertThat(graphCopy->isDummy(graphCopy->newEdge(graphCopy->chooseNode(),graphCopy->chooseNode())),IsTrue());
222 AssertThat(graphCopy->isDummy(graphCopy->newNode()), IsTrue());
223 });
224
225 describe("edge adding",[&](){
226 it("works using the original edge",[&](){
227 edge origEdge = graph.chooseEdge();
228 graphCopy->delEdge(graphCopy->copy(origEdge));
229 edge copyEdge = graphCopy->newEdge(origEdge);
230 AssertThat(copyEdge, !IsNull());
231 AssertThat(graphCopy->copy(origEdge), Equals(copyEdge));
232 });
233
234 it("works using source and target",[&](){
235 node firstNode = graphCopy->chooseNode();
236 node secondNode = graphCopy->chooseNode();
237 int degreeFirstNode = firstNode->degree();
238 int degreeSecondNode = secondNode->degree();
239 edge e = graphCopy->newEdge(firstNode, secondNode);
240 AssertThat(e,!IsNull());
241 AssertThat(e->source(), Equals(firstNode));
242 AssertThat(e->target(), Equals(secondNode));
243 AssertThat(firstNode->degree(), Equals(degreeFirstNode+1));
244 AssertThat(secondNode->degree(), Equals(degreeSecondNode+1));
245 });
246 });
247
248 it("deletes nodes and edges",[&](){
249 node delANode = graphCopy->chooseNode();
250 node delANodeOrig = graphCopy->original(delANode);
251 AssertThat(delANodeOrig, !Equals(nullptr));
252 graphCopy->delNode(delANode);
253 AssertThat(graphCopy->copy(delANodeOrig), Equals(nullptr));
254
255 edge delAnEdge = graphCopy->chooseEdge();
256 edge delAnEdgeOrig = graphCopy->original(delAnEdge);
257 AssertThat(delAnEdgeOrig, !Equals(nullptr));
258 graphCopy->delEdge(delAnEdge);
259 AssertThat(graphCopy->copy(delAnEdgeOrig), Equals(nullptr));
260 });
261
262 it("adds new nodes",[&](){
263 AssertThat(graphCopy->newNode(),!IsNull());
264 AssertThat(graphCopy->numberOfNodes(),Equals(graph.numberOfNodes()+1));
265 });
266
267 it("un-splits edges",[&](){
268 edge copyEdge = graphCopy->chooseEdge();
269 edge copyCopyEdge = copyEdge;
270 edge splitEdge = graphCopy->split(copyEdge);
271 graphCopy->unsplit(copyEdge, splitEdge);
272 AssertThat(graphCopy->original(copyEdge), Equals(graphCopy->original(copyCopyEdge)));
273 AssertThat(copyEdge->source(), Equals(copyCopyEdge->source()));
274 AssertThat(copyEdge->target(), Equals(copyCopyEdge->target()));
275 });
276}
277
278go_bandit([](){
279 const int numberOfNodes = 42;
280
281 describe("GraphCopySimple", [&](){
282 describeGraphCopySimple<GraphCopySimple>(numberOfNodes);
283 });
284
285 describe("GraphCopy", [&](){
286 Graph graph;
287 std::unique_ptr<GraphCopy> graphCopy;
288
289 before_each([&](){
290 randomGraph(graph,numberOfNodes,numberOfNodes*4);
291 graphCopy.reset(new GraphCopy(graph));
292 });
293
294 describe("basic functionality",[&](){
295 describeGraphCopySimple<GraphCopy>(numberOfNodes);
296 });
297
298 describe("initialization", [&](){
299 EdgeArray<edge> eCopy;
300 List<node> origNodes;
301
302 it("can be assigned a given GraphCopy",[&](){
303 GraphCopy graphCopyCopy;
304 graphCopyCopy=*graphCopy;
305 testInitGraph<GraphCopy>(graph, graphCopyCopy, true);
306 });
307
308 describe("creating empty copies",[&](){
309 it("works with an empty graph",[&](){
310 graphCopy.reset(new GraphCopy());
311 graph.clear();
312 graphCopy->createEmpty(graph);
313 AssertThat(graphCopy->numberOfNodes(),Equals(0));
314 AssertThat(graphCopy->numberOfEdges(),Equals(0));
315 AssertThat(&(graphCopy->original()),Equals(&graph));
316 });
317
318 it("works with a non-empty graph",[&](){
319 graphCopy.reset(new GraphCopy(graph));
320 graphCopy->createEmpty(graph);
321 AssertThat(graphCopy->numberOfNodes(),Equals(numberOfNodes));
322 AssertThat(graphCopy->numberOfEdges(),Equals(numberOfNodes*4));
323 AssertThat(&(graphCopy->original()),Equals(&graph));
324 AssertThat(graphCopy->chooseNode(),!IsNull());
325 AssertThat(graphCopy->chooseEdge(),!IsNull());
326 AssertThat(graphCopy->copy(graph.chooseNode()), IsNull());
327 AssertThat(graphCopy->copy(graph.chooseEdge()), IsNull());
328 AssertThat(graphCopy->original(graphCopy->chooseNode()), IsNull());
329 AssertThat(graphCopy->original(graphCopy->chooseEdge()), IsNull());
330 });
331 });
332
333 it("is initialized by a given connected component",[&](){
334 randomGraph(graph, numberOfNodes*2, numberOfNodes*3);
335 Graph::CCsInfo ccs = Graph::CCsInfo(graph);
336 graphCopy.reset(new GraphCopy());
337 int numberOfCC = ccs.numberOfCCs()-1;
338 graphCopy->createEmpty(graph);
339 graphCopy->initByCC(ccs, numberOfCC, eCopy);
340 origNodes.clear();
341 for(int i = ccs.startNode(numberOfCC); i< ccs.stopNode(numberOfCC); i++){
342 origNodes.pushBack(ccs.v(i));
343 }
344 testInitGraph<GraphCopy>(graph, *graphCopy, false, origNodes, eCopy);
345 });
346
347 it("maps adjacency entries of chains", [&] {
348 edge e = graph.chooseEdge();
349 edge f0 = graphCopy->copy(e);
350 edge f1 = graphCopy->split(f0);
351 edge f2 = graphCopy->split(f1);
352
353 adjEntry adjSrc = graphCopy->copy(e->adjSource());
354 adjEntry adjTgt = graphCopy->copy(e->adjTarget());
355
356 AssertThat(adjSrc == f0->adjSource(), IsTrue());
357 AssertThat(adjTgt == f2->adjTarget(), IsTrue());
358
359 AssertThat(graphCopy->original(adjSrc) == e->adjSource(), IsTrue());
360 AssertThat(graphCopy->original(adjTgt) == e->adjTarget(), IsTrue());
361 });
362
363 it("is initialized by either all or none of the nodes of a component",[&](){
364 origNodes.clear();
365 graphCopy.reset(new GraphCopy());
366 graphCopy->createEmpty(graph);
367 graphCopy->initByNodes(origNodes, eCopy);
368 testInitGraph<GraphCopy>(graph, *graphCopy, true, origNodes, eCopy);
369 graphCopy.reset(new GraphCopy());
370 origNodes.clear();
371 graph.allNodes<List<node>>(origNodes);
372 eCopy = EdgeArray<edge>(graph);
373 graphCopy->createEmpty(graph);
374 graphCopy->initByNodes(origNodes, eCopy);
375 testInitGraph<GraphCopy>(graph, *graphCopy, true, origNodes, eCopy);
376
377#ifdef OGDF_USE_ASSERT_EXCEPTIONS
378 origNodes = List<node>();
379 origNodes.pushBack(graph.firstNode());
380 origNodes.pushBack(graph.lastNode());
381 eCopy = EdgeArray<edge>(graph);
382 graphCopy.reset(new GraphCopy(graph));
383 AssertThrows(AssertionFailed, graphCopy->initByNodes(origNodes, eCopy));
384#endif
385 });
386
387 it("is initialized by arbitrary nodes",[&](){
388 eCopy = EdgeArray<edge>(graph);
389 NodeArray<bool> activeNodes(graph, false);
390 node actNode1 = graph.chooseNode();
391 node actNode2 = actNode1->lastAdj()->twin()->theNode();
392 activeNodes[actNode1] = true;
393 activeNodes[actNode2] = true;
394 origNodes.clear();
395 origNodes.pushBack(actNode1);
396 origNodes.pushBack(actNode2);
397 graphCopy->createEmpty(graph);
398 graphCopy->initByActiveNodes(origNodes, activeNodes, eCopy);
399 List<node> asdf;
400 graphCopy->allNodes<List<node>>(asdf);
401 List<edge> asdfgh;
402 graphCopy->allEdges(asdfgh);
403 testInitGraph<GraphCopy>(graph, *graphCopy, false, origNodes, eCopy);
404 });
405 });
406
407#ifdef OGDF_USE_ASSERT_EXCEPTIONS
408 it_skip("doesn't add a copied edge twice", [&]{
409 AssertThrows(AssertionFailed, graphCopy->newEdge(graph.chooseEdge()));
410 });
411#endif
412
413 it("adds copied nodes",[&](){
414 int n = graph.numberOfNodes();
415 AssertThat(graphCopy->newNode(graph.newNode()),!IsNull());
416 AssertThat(graphCopy->numberOfNodes(),Equals(n+1));
417 });
418
419 it("returns the chain",[&](){
420 edge originalEdge = graph.chooseEdge();
421 List<edge> givenChain;
422 givenChain.pushFront(graphCopy->split(graphCopy->copy(originalEdge)));
423 givenChain.pushFront(graphCopy->split(graphCopy->copy(originalEdge)));
424 givenChain.pushFront(graphCopy->copy(originalEdge));
425 List<edge> returnedChain = graphCopy->chain(originalEdge);
426 AssertThat(returnedChain.size(),Equals(3));
427 AssertThat(returnedChain,Equals(givenChain));
428 });
429
430 it("detects reversed edges",[&](){
431 edge reversedEdge = graphCopy->chooseEdge([](edge e) { return !e->isSelfLoop(); });
432 AssertThat(graphCopy->isReversed(graphCopy->original(reversedEdge)),IsFalse());
433 graphCopy->reverseEdge(reversedEdge);
434 AssertThat(graphCopy->isReversed(graphCopy->original(reversedEdge)),IsTrue());
435 });
436
437 it("does not return cleared elements", [&]() {
438 graphCopy->clear();
439
440 for(node v : graph.nodes) {
441 AssertThat(graphCopy->copy(v), Equals(nullptr));
442 }
443
444 for(edge e : graph.edges) {
445 AssertThat(graphCopy->copy(e), Equals(nullptr));
446 }
447 });
448
449 describe("original embedding",[&](){
450 before_each([&](){
451 randomPlanarBiconnectedGraph(graph, numberOfNodes, static_cast<int>(min(numberOfNodes*2.5, numberOfNodes*3.0-6)));
452 // shuffle adjacency order
453 for(node v : graph.nodes) {
454 for(adjEntry adj : v->adjEntries) {
455 graph.swapAdjEdges(adj, randomNumber(0, 1) ? v->firstAdj() : v->lastAdj());
456 }
457 }
458 graphCopy.reset(new GraphCopy(graph));
459 });
460
461 it("works if the GraphCopy wasn't modified",[&](){
462 planarEmbed(*graphCopy);
463 AssertThat(graphCopy->representsCombEmbedding(), IsTrue());
464 graphCopy->setOriginalEmbedding();
465 AssertThat(graphCopy->genus(), Equals(graph.genus()));
466 });
467
468#ifdef OGDF_USE_ASSERT_EXCEPTIONS
469 it("doesn't embed split edges",[&](){
470 graphCopy->split(graphCopy->chooseEdge());
471 AssertThrows(AssertionFailed, graphCopy->setOriginalEmbedding());
472 });
473
474 it("doesn't embed dummies",[&](){
475 graphCopy->newNode();
476 AssertThrows(AssertionFailed, graphCopy->setOriginalEmbedding());
477 });
478
479 it("doesn't embed added edges",[&](){
480 graphCopy->newEdge(graphCopy->chooseNode(),graphCopy->chooseNode());
481 AssertThrows(AssertionFailed, graphCopy->setOriginalEmbedding());
482 });
483#endif
484 });
485
486 describe("edge path",[&](){
487 node t, u, v, w;
488 edge tu, uv, vw, tw;
489
490 before_each([&](){
491 graph.clear();
492 t = graph.newNode();
493 u = graph.newNode();
494 v = graph.newNode();
495 w = graph.newNode();
496 graph.newEdge(v, t);
497 tu = graph.newEdge(t, u);
498 uv = graph.newEdge(u, v);
499 graph.newEdge(u, w);
500 vw = graph.newEdge(v, w);
501 tw = graph.newEdge(t, w);
502 planarEmbed(graph);
503
504 graphCopy.reset(new GraphCopy(graph));
505 });
506
507 describe("non-embedded variant",[&](){
508 before_each([&](){
509 SList<adjEntry> crossedEdges;
510 crossedEdges.pushBack(graphCopy->copy(uv)->adjTarget());
511 graphCopy->insertEdgePath(tw, crossedEdges);
512 });
513
514 it("inserts a path",[&](){
515 AssertThat(graphCopy->chain(tw).size(), Equals(2));
516 AssertThat(graphCopy->chain(uv).size(), Equals(2));
517 node newNode = graphCopy->lastNode();
518 AssertThat(newNode->degree(), Equals(4));
519 adjEntry adj = newNode->firstAdj();
520 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(u));
521 adj = adj->succ();
522 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(v));
523 adj = adj->succ();
524 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(t));
525 adj = adj->succ();
526 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(w));
527 adj = adj->succ();
528 });
529
530 it("removes a path",[&](){
531 graphCopy->removeEdgePath(tw);
532 AssertThat(graphCopy->chain(tw).size(), Equals(0));
533 AssertThat(graphCopy->chain(uv).size(), Equals(1));
534 AssertThat(graphCopy->copy(uv)->target(), Equals(graphCopy->copy(v)));
535 AssertThat(graphCopy->copy(uv)->source(), Equals(graphCopy->copy(u)));
536 AssertThat(graphCopy->numberOfNodes(), Equals(graph.numberOfNodes()));
537 AssertThat(graphCopy->numberOfEdges(), Equals(graph.numberOfEdges() - 1));
538 });
539 });
540
541 describe("embedded variant",[&](){
542 CombinatorialEmbedding combEmb;
543 SList<adjEntry> crossedEdges;
544
545 before_each([&](){
546 combEmb.init(*graphCopy);
547 crossedEdges.clear();
548 crossedEdges.pushBack(graphCopy->copy(tu)->adjSource());
549 crossedEdges.pushBack(graphCopy->copy(uv)->adjTarget());
550 crossedEdges.pushBack(graphCopy->copy(vw)->adjTarget());
551 graphCopy->insertEdgePathEmbedded(tw, combEmb, crossedEdges);
552 });
553
554 it("inserts a path",[&](){
555 AssertThat(graphCopy->chain(tw).size(), Equals(2));
556 AssertThat(graphCopy->chain(uv).size(), Equals(2));
557 AssertThat(graphCopy->numberOfEdges(), Equals(8));
558 AssertThat(graphCopy->numberOfNodes(), Equals(5));
559 node newNode = graphCopy->lastNode();
560 AssertThat(newNode->degree(), Equals(4));
561 adjEntry adj = newNode->firstAdj();
562 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(u));
563 adj = adj->succ();
564 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(w));
565 adj = adj->succ();
566 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(v));
567 adj = adj->succ();
568 AssertThat(graphCopy->original(adj->twin()->theNode()), Equals(t));
569 adj = adj->succ();
570 AssertThat(combEmb.numberOfFaces(), Equals(5));
571 });
572
573 it("removes a path",[&](){
574 FaceSet<false> newFaces(combEmb);
575 graphCopy->removeEdgePathEmbedded(combEmb, tw, newFaces);
576 AssertThat(graphCopy->chain(tw).size(), Equals(0));
577 edge newOldEdge = graphCopy->copy(tw);
578 AssertThat(newOldEdge, IsNull());
579 AssertThat(graphCopy->chain(uv).size(), Equals(1));
580 AssertThat(graphCopy->numberOfEdges(), Equals(5));
581 AssertThat(combEmb.rightFace(graphCopy->copy(tu)->adjSource())->size(), Equals(3));
582 AssertThat(combEmb.leftFace(graphCopy->copy(tu)->adjSource())->size(), Equals(4));
583 AssertThat(graphCopy->numberOfNodes(), Equals(4));
584 AssertThat(combEmb.numberOfFaces(), Equals(3));
585 });
586 });
587 });
588
589 it("sets a copy edge and an original edge to be corresponding",[&](){
590 completeGraph(graph, 2);
591 graphCopy.reset(new GraphCopy(graph));
592 edge copyEdge = graphCopy->chooseEdge();
593 edge origEdge = graphCopy->original(copyEdge);
594 graphCopy->delEdge(copyEdge);
595 copyEdge = graphCopy->newEdge(graphCopy->copy(origEdge->source()), graphCopy->copy(origEdge->target()));
596 graphCopy->setEdge(origEdge, copyEdge);
597 AssertThat(graphCopy->original(copyEdge), Equals(origEdge));
598 AssertThat(graphCopy->copy(origEdge), Equals(copyEdge));
599 });
600
601 for(int caseCounter = 0; caseCounter < 8; caseCounter++) {
602 bool crossingEdgeIsDummy = caseCounter / 4;
603 bool crossedEdgeIsDummy = (caseCounter / 2) % 2;
604 bool rightToLeft = caseCounter % 2;
605
606 auto chooseEdge = [&](bool createDummy, edge other) {
607 edge result;
608
609 if(createDummy) {
610 node u = graphCopy->chooseNode([&](node w) { return other == nullptr || !other->isIncident(w); });
611 node v = graphCopy->chooseNode([&](node w) { return w != u && (other == nullptr || !other->isIncident(w)); });
612 result = graphCopy->newEdge(u, v);
613 } else {
614 result = graphCopy->chooseEdge([&](edge e) {
615 return !graphCopy->isDummy(e) && (other == nullptr || e->commonNode(other) == nullptr);
616 });
617 }
618
619 return result;
620 };
621
622 it("inserts crossings (case #" + to_string(caseCounter) + ")" ,[&] {
623 completeGraph(graph, 10);
624 graphCopy.reset(new GraphCopy(graph));
625
626 edge crossingEdge = chooseEdge(crossingEdgeIsDummy, nullptr);
627 edge crossedEdge = chooseEdge(crossedEdgeIsDummy, crossingEdge);
628
629 // store auxiliary data
630 edge origCrossingEdge = graphCopy->original(crossingEdge);
631 edge origCrossedEdge = graphCopy->original(crossedEdge);
632
633 adjEntry adjSrcCrossing = crossingEdge->adjSource()->cyclicPred();
634 adjEntry adjTgtCrossing = crossingEdge->adjTarget()->cyclicPred();
635 adjEntry adjSrcCrossed = crossedEdge->adjSource()->cyclicPred();
636 adjEntry adjTgtCrossed = crossedEdge->adjTarget()->cyclicPred();
637
638 int n = graphCopy->numberOfNodes();
639 int m = graphCopy->numberOfEdges();
640
641 // actually insert the crossing
642 crossedEdge = graphCopy->insertCrossing(crossingEdge, crossedEdge, rightToLeft);
643
644 // validate graph size
645 AssertThat(graphCopy->numberOfNodes(), Equals(n+1));
646 AssertThat(graphCopy->numberOfEdges(), Equals(m+2));
647
648 // validate degree of dummy node
649 node dummy = crossedEdge->source();
650 AssertThat(graphCopy->isDummy(dummy), IsTrue());
651 AssertThat(dummy->outdeg(), Equals(2));
652 AssertThat(dummy->indeg(), Equals(2));
653
654 AssertThat(graphCopy->isDummy(crossingEdge), Equals(crossingEdgeIsDummy));
655 AssertThat(graphCopy->isDummy(crossedEdge), Equals(crossedEdgeIsDummy));
656
657 AssertThat(adjTgtCrossing->cyclicSucc(), Equals(crossingEdge->adjTarget()));
658 AssertThat(adjTgtCrossed->cyclicSucc(), Equals(crossedEdge->adjTarget()));
659
660 // validate chains and adjacency order at the dummy node
661 auto validateChains = [&](edge e, edge other, edge formerOrig, adjEntry adjSrcPred, bool isCrossingEdge) {
662 List<edge> chain = graphCopy->chain(graphCopy->original(e));
663
664 AssertThat(chain.size(), Equals(2));
665
666 AssertThat(chain.back(), Equals(e));
667
668 AssertThat(graphCopy->original(chain.front()), Equals(formerOrig));
669 AssertThat(graphCopy->original(chain.back()), Equals(formerOrig));
670
671 AssertThat(adjSrcPred->cyclicSucc(), Equals(chain.front()->adjSource()));
672
673 AssertThat(e->adjSource()->cyclicSucc()->cyclicSucc(), Equals(chain.front()->adjTarget()));
674
675 adjEntry adj = other->adjSource();
676
677 if (rightToLeft == isCrossingEdge) {
678 AssertThat(adj->cyclicPred(), Equals(chain.back()->adjSource()));
679 AssertThat(adj->cyclicSucc(), Equals(chain.front()->adjTarget()));
680 } else {
681 AssertThat(adj->cyclicPred(), Equals(chain.front()->adjTarget()));
682 AssertThat(adj->cyclicSucc(), Equals(chain.back()->adjSource()));
683 }
684 };
685
686 if(!crossingEdgeIsDummy) {
687 validateChains(crossingEdge, crossedEdge, origCrossingEdge, adjSrcCrossing, true);
688 }
689
690 if(!crossedEdgeIsDummy) {
691 validateChains(crossedEdge, crossingEdge, origCrossedEdge, adjSrcCrossed, false);
692 }
693 });
694 }
695
696 it("removes pseudo crossings, where two edges merely touch",[&](){
697 graph.clear();
698 graph.newEdge(graph.newNode(), graph.newNode());
699 graph.newEdge(graph.newNode(), graph.newNode());
700 graphCopy.reset(new GraphCopy(graph));
701 edge eCopy = graphCopy->firstEdge();
702 edge fCopy = graphCopy->lastEdge();
703 edge eSplit = graphCopy->split(eCopy);
704 edge fSplit = graphCopy->split(fCopy);
705 graphCopy->contract(graphCopy->newEdge(eSplit->source(), fSplit->source()));
706 graphCopy->removePseudoCrossings();
707 AssertThat(graphCopy->chain(graphCopy->original(eCopy)).size(), Equals(1));
708 AssertThat(graphCopy->chain(graphCopy->original(fCopy)).size(), Equals(1));
709 });
710
711#ifdef OGDF_USE_ASSERT_EXCEPTIONS
712 it("won't delete a split edge",[&](){
713 edge splittedEdge=graphCopy->split(graphCopy->chooseEdge());
714 AssertThrows(AssertionFailed, graphCopy->delEdge(splittedEdge));
715 });
716#endif
717 it("splits a reinserted edge", [&](){
718 edge eOrig = graph.chooseEdge();
719 graphCopy->delEdge(graphCopy->copy(eOrig));
720 edge eCopy = graphCopy->newEdge(eOrig);
721 graphCopy->split(eCopy);
722 });
723
724 it("knows if a copy edge is reversed w.r.t. the original edge", [&](){
725 edge eOrig = graph.chooseEdge();
726 edge eCopy = graphCopy->copy(eOrig);
727 AssertThat(graphCopy->isReversedCopyEdge(eCopy), IsFalse());
728 graphCopy->split(eCopy);
729 eCopy = graphCopy->split(eCopy);
730 AssertThat(graphCopy->isReversedCopyEdge(eCopy), IsFalse());
731 graphCopy->reverseEdge(eCopy);
732 AssertThat(graphCopy->isReversedCopyEdge(eCopy), IsTrue());
733 });
734 });
735});
736