1 /** \file
2 * \brief implementation of MMFixedEmbeddingInserter class
3 *
4 * \author Carsten Gutwenger
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/planarity/embedding_inserter/CrossingsBucket.h>
33 #include <ogdf/planarity/MMFixedEmbeddingInserter.h>
34 #include <ogdf/planarlayout/PlanarStraightLayout.h>
35 #include <ogdf/fileformats/GraphIO.h>
36
37 namespace ogdf {
38
39 static int globalCounter = 0;
40
41 // constructor
42 // sets default values for options
MMFixedEmbeddingInserter()43 MMFixedEmbeddingInserter::MMFixedEmbeddingInserter()
44 {
45 m_rrOption = RemoveReinsertType::None;
46 m_percentMostCrossed = 25;
47 }
48
49 #if 0
50 static void draw(
51 const PlanRepExpansion &PG,
52 const EdgeArray<bool> *forbiddenEdgeOrig)
53 {
54 static int num = 1;
55
56 GraphAttributes GA(PG,
57 GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics | GraphAttributes::nodeLabel | GraphAttributes::edgeStyle | GraphAttributes::nodeStyle);
58
59 for(node v : PG.nodes) {
60 node vOrig = PG.original(v);
61 if(vOrig != 0) {
62 GA.label(v) = to_string(v->index()) + " | " + to_string(vOrig->index());
63 GA.fillColor(v) = "#ffffff";
64 } else {
65 GA.label(v) = to_string(v->index());
66 GA.fillColor(v) = "#22ff22";
67 }
68 GA.width(v) = 60;
69 GA.height(v) = 20;
70 }
71
72 if(forbiddenEdgeOrig) {
73 for(edge e : PG.edges) {
74 edge eOrig = PG.originalEdge(e);
75 if (eOrig && (*forbiddenEdgeOrig)[eOrig])
76 GA.strokeColor(e) = "#ff0000";
77 }
78 }
79
80 PlanarStraightLayout pl;
81 pl.separation(40);
82 pl.callFixEmbed(GA, PG.firstEdge()->adjSource());
83
84 string fileName = string("layout-") + to_string(num++) + ".gml";
85 GraphIO::writeGML(GA, fileName);
86 }
87 #endif
88
drawDual(const PlanRepExpansion & PG,const EdgeArray<bool> * forbiddenEdgeOrig)89 void MMFixedEmbeddingInserter::drawDual(
90 const PlanRepExpansion &PG,
91 const EdgeArray<bool> *forbiddenEdgeOrig)
92 {
93 GraphAttributes GA(m_dual,
94 GraphAttributes::nodeGraphics | GraphAttributes::edgeGraphics | GraphAttributes::nodeLabel | GraphAttributes::edgeStyle | GraphAttributes::nodeStyle);
95
96 for(node v : m_dual.nodes) {
97 if(m_primalNode[v]) {
98 GA.label(v) = string("v") + to_string(m_primalNode[v]->index()) + ": " + to_string(v->index());
99 GA.fillColor(v) = Color::Name::White;
100 } else {
101 GA.label(v) = string("f: ") + to_string(v->index());
102 GA.fillColor(v) = Color(0x22,0xff,0x22);
103 }
104 GA.width(v) = 50;
105 GA.height(v) = 20;
106 }
107
108 for(edge e : m_dual.edges) {
109 if(origOfDualForbidden(e, PG, forbiddenEdgeOrig))
110 GA.strokeColor(e) = Color::Name::Red;
111 else
112 GA.strokeColor(e) = Color::Name::Black;
113 }
114
115 GraphIO::write(GA, "dual.gml", GraphIO::writeGML);
116 }
117
118
119 // actual call (called by all variations of call)
120 // crossing of generalizations is forbidden if forbidCrossingGens = true
121 // edge costs are obeyed if costOrig != 0
doCall(PlanRepExpansion & PG,const List<edge> & origEdges,const EdgeArray<bool> * forbiddenEdgeOrig)122 Module::ReturnType MMFixedEmbeddingInserter::doCall(
123 PlanRepExpansion &PG,
124 const List<edge> &origEdges,
125 const EdgeArray<bool> *forbiddenEdgeOrig)
126 {
127 ReturnType retValue = ReturnType::Feasible;
128
129 #if 0
130 std::cout << "orig edges: ";
131 ListConstIterator<edge> itE;
132 for(itE = origEdges.begin(); itE.valid(); ++itE)
133 std::cout << *itE << " ";
134 std::cout << std::endl;
135 #endif
136
137 PG.embed();
138 OGDF_ASSERT(PG.representsCombEmbedding());
139
140 if (origEdges.size() == 0)
141 return ReturnType::Optimal; // nothing to do
142
143 // initialization
144 CombinatorialEmbedding E(PG); // embedding of PG
145
146 // construct dual graph
147 m_primalAdj.init(m_dual);
148 m_dualEdge.init(PG,nullptr);
149 m_dualOfFace.init(E);
150 m_dualOfNode.init(PG,nullptr);
151 m_primalNode.init(m_dual,nullptr);
152 m_dualCost.init(m_dual,0);
153
154 constructDual(PG,E);
155 OGDF_ASSERT(checkDualGraph(PG,E));
156
157 #if 0
158 draw(PG, forbiddenEdgeOrig);
159
160 if(forbiddenEdgeOrig) {
161 std::cout << "forbidden edges: ";
162 for(edge e : PG.original().edges)
163 if((*forbiddenEdgeOrig)[e]) std::cout << e << " ";
164 std::cout << std::endl;
165 }
166 #endif
167
168 m_delFaces = new FaceSet<false>(E);
169
170 // m_newFaces and m_mergedNodes are used by removeEdge()
171 m_newFaces = nullptr;
172 m_mergedNodes = nullptr;
173 if (removeReinsert() != RemoveReinsertType::None) {
174 m_newFaces = new FaceSet<false>(E);
175 m_mergedNodes = new NodeSet<false>(PG);
176 }
177
178 SListPure<edge> currentOrigEdges;
179 if(removeReinsert() == RemoveReinsertType::Incremental) {
180 for(edge e : PG.edges)
181 currentOrigEdges.pushBack(PG.originalEdge(e));
182 }
183
184 NodeSet<> sources(PG), targets(PG);
185
186 // insertion of edges
187 for(edge eOrig: origEdges)
188 {
189 node srcOrig = eOrig->source();
190 node tgtOrig = eOrig->target();
191
192 node oldSrc = (PG.splittableOrig(srcOrig) && PG.expansion(srcOrig).size() == 1) ?
193 PG.expansion(srcOrig).front() : nullptr;
194 node oldTgt = (PG.splittableOrig(tgtOrig) && PG.expansion(tgtOrig).size() == 1) ?
195 PG.expansion(tgtOrig).front() : nullptr;
196
197 anchorNodes(eOrig->source(), sources, PG);
198 anchorNodes(eOrig->target(), targets, PG);
199
200 List<Tuple2<adjEntry,adjEntry> > crossed;
201 findShortestPath(PG, E, sources.nodes(), targets.nodes(), crossed, forbiddenEdgeOrig);
202 sources.clear(); targets.clear();
203
204 insertEdge(PG,E,eOrig,eOrig->source(),eOrig->target(),nullptr,crossed);
205
206 if(oldSrc != nullptr && PG.expansion(srcOrig).size() > 1)
207 contractSplitIfReq(PG,E,oldSrc);
208 if(oldTgt != nullptr && PG.expansion(tgtOrig).size() > 1)
209 contractSplitIfReq(PG,E,oldTgt);
210
211 //draw(PG, forbiddenEdgeOrig);
212
213 // THIS OPTION IS NOT YET IMPLEMENTED!
214 if(removeReinsert() == RemoveReinsertType::Incremental)
215 {
216 currentOrigEdges.pushBack(eOrig);
217
218 bool improved;
219 do {
220 improved = false;
221
222 SListConstIterator<edge> itRR;
223 for(itRR = currentOrigEdges.begin(); itRR.valid(); ++itRR)
224 {
225 edge eOrigRR = *itRR;
226
227 int pathLength = PG.chain(eOrigRR).size() - 1;
228 if (pathLength == 0) continue; // cannot improve
229
230 node oldSource, oldTarget;
231 removeEdge(PG,E,eOrigRR,nullptr,oldSource,oldTarget);
232
233 // try to find a better insertion path
234 List<Tuple2<adjEntry,adjEntry> > crossedTuple;
235 findShortestPath(PG, E,
236 PG.expansion(eOrigRR->source()), PG.expansion(eOrigRR->target()),
237 crossedTuple, forbiddenEdgeOrig);
238
239 // re-insert edge (insertion path cannot be longer)
240 insertEdge(PG,E,eOrigRR,eOrigRR->source(),eOrigRR->target(),nullptr,crossedTuple);
241
242 int newPathLength = PG.chain(eOrigRR).size() - 1;
243 OGDF_ASSERT(newPathLength <= pathLength);
244
245 if(newPathLength < pathLength)
246 improved = true;
247 }
248 } while (improved);
249 }
250 OGDF_ASSERT(checkSplitDeg(PG));
251 }
252
253 #ifdef OGDF_DEBUG
254 E.consistencyCheck();
255 PG.consistencyCheck();
256 #endif
257 OGDF_ASSERT(checkDualGraph(PG,E));
258 OGDF_ASSERT(checkSplitDeg(PG));
259
260 const Graph &G = PG.original();
261 if(removeReinsert() != RemoveReinsertType::Incremental) {
262 // postprocessing (remove-reinsert heuristc)
263 SListPure<edge> rrEdges;
264
265 switch(removeReinsert())
266 {
267 case RemoveReinsertType::All:
268 case RemoveReinsertType::MostCrossed:
269 {
270 const List<node> &origInCC = PG.nodesInCC();
271 ListConstIterator<node> itV;
272
273 for(itV = origInCC.begin(); itV.valid(); ++itV) {
274 node vG = *itV;
275 for(adjEntry adj : vG->adjEntries) {
276 if ((adj->index() & 1) == 0) continue;
277 edge eG = adj->theEdge();
278 rrEdges.pushBack(eG);
279 }
280 }
281 }
282 break;
283
284 case RemoveReinsertType::Inserted:
285 for(edge e: origEdges) {
286 rrEdges.pushBack(e);
287 }
288 break;
289
290 case RemoveReinsertType::None:
291 case RemoveReinsertType::Incremental:
292 break;
293 case RemoveReinsertType::IncInserted:
294 OGDF_ASSERT(false);
295 break;
296 }
297
298 // marks the end of the interval of rrEdges over which we iterate
299 // initially set to invalid iterator which means all edges
300 SListConstIterator<edge> itStop;
301
302 bool improved;
303 do {
304 improved = false;
305
306 if(removeReinsert() == RemoveReinsertType::MostCrossed)
307 {
308 embedding_inserter::CrossingsBucket<PlanRepExpansion> bucket(&PG);
309 rrEdges.bucketSort(bucket);
310
311 const int num = int(0.01 * percentMostCrossed() * G.numberOfEdges());
312 itStop = rrEdges.get(num);
313 }
314
315 for(SListConstIterator<edge> it = rrEdges.begin(); it != itStop; ++it)
316 {
317 edge eOrig = *it;
318
319 int pathLength;
320 pathLength = PG.chain(eOrig).size() - 1;
321 if (pathLength == 0) continue; // cannot improve
322
323 node oldSrc = nullptr, oldTgt = nullptr;
324 removeEdge(PG,E,eOrig,nullptr,oldSrc,oldTgt);
325 //draw(PG, forbiddenEdgeOrig);
326
327 // try to find a better insertion path
328 anchorNodes(eOrig->source(), sources, PG);
329 anchorNodes(eOrig->target(), targets, PG);
330
331 List<Tuple2<adjEntry,adjEntry> > crossed;
332 findShortestPath(PG, E, sources.nodes(), targets.nodes(), crossed, forbiddenEdgeOrig);
333 sources.clear(); targets.clear();
334
335 // re-insert edge (insertion path cannot be longer)
336 insertEdge(PG,E,eOrig,eOrig->source(),eOrig->target(),nullptr,crossed);
337
338 if(PG.splittable(oldSrc))
339 contractSplitIfReq(PG,E,oldSrc);
340 if(PG.splittable(oldTgt))
341 contractSplitIfReq(PG,E,oldTgt);
342
343 int newPathLength = PG.chain(eOrig).size() - 1;
344 int saved = pathLength - newPathLength;
345 OGDF_ASSERT(saved >= 0);
346
347 if(saved > 0)
348 improved = true;
349 }
350
351 if(removeReinsert() == RemoveReinsertType::All)
352 {
353 // process all node splits
354 int nsCount = PG.nodeSplits().size();
355 ListIterator<PlanRepExpansion::NodeSplit> itS, itSNext;
356 for(itS = PG.nodeSplits().begin(); itS.valid() && nsCount > 0; itS = itSNext, --nsCount)
357 {
358 ++globalCounter;
359 PlanRepExpansion::NodeSplit *ns = &(*itS);
360
361 int pathLength;
362 pathLength = ns->m_path.size() - 1;
363 if (pathLength == 0) continue; // cannot improve
364
365 node vOrig = PG.original(ns->source());
366
367 node oldSrc = nullptr, oldTgt = nullptr;
368 removeEdge(PG,E,nullptr,ns,oldSrc,oldTgt);
369
370 // try to find a better insertion path
371 findSourcesAndTargets(oldSrc,oldTgt,sources,targets,PG);
372
373 List<Tuple2<adjEntry,adjEntry> > crossed;
374 findShortestPath(PG, E, sources.nodes(), targets.nodes(), crossed, forbiddenEdgeOrig);
375
376 node vCommon = commonDummy(sources,targets);
377 sources.clear(); targets.clear();
378
379 if(vCommon == nullptr)
380 {
381 // re-insert edge (insertion path cannot be longer)
382 insertEdge(PG,E,nullptr,vOrig,vOrig,ns,crossed);
383
384 if(PG.splittable(oldSrc))
385 contractSplitIfReq(PG,E,oldSrc,ns);
386 if(PG.splittable(oldTgt))
387 contractSplitIfReq(PG,E,oldTgt,ns);
388
389 int newPathLength = ns->m_path.size() - 1;
390 int saved = pathLength - newPathLength;
391 OGDF_ASSERT(saved >= 0);
392
393 if(saved > 0)
394 improved = true;
395
396 itSNext = itS.succ();
397 if(newPathLength == 0)
398 contractSplit(PG,E,ns);
399
400 } else {
401 improved = true;
402 itSNext = itS.succ();
403
404 convertDummy(PG,E,vCommon,vOrig,ns);
405 }
406
407 }
408 }
409
410 #ifdef OGDF_DEBUG
411 PG.consistencyCheck();
412 E.consistencyCheck();
413 #endif
414 OGDF_ASSERT(checkDualGraph(PG,E));
415 OGDF_ASSERT(checkSplitDeg(PG));
416
417 } while(improved); // iterate as long as we improve
418 }
419
420
421 // free resources
422 delete m_newFaces;
423 delete m_delFaces;
424 delete m_mergedNodes;
425
426 m_dualOfFace.init();
427 m_dualOfNode.init();
428 m_primalNode.init();
429 m_primalAdj.init();
430 m_dualEdge.init();
431 m_dualCost.init();
432 m_dual.clear();
433
434 return retValue;
435 }
436
437
438 // construct dual graph
constructDual(const PlanRepExpansion & PG,const CombinatorialEmbedding & E)439 void MMFixedEmbeddingInserter::constructDual(
440 const PlanRepExpansion &PG,
441 const CombinatorialEmbedding &E)
442 {
443 // insert a node in the dual graph for each face in E
444 for(face f : E.faces) {
445 m_dualOfFace[f] = m_dual.newNode();
446 //std::cout << "dual of face " << f->index() << ": " << m_dualOfFace[f] << std::endl;
447 }
448
449 // insert a node in the dual graph for each splittable node in PG
450 for(node v : PG.nodes) {
451 if(PG.splittable(v) && v->degree() >= 4) {
452 m_primalNode[m_dualOfNode[v] = m_dual.newNode()] = v;
453 //std::cout << "dual of node " << v << " :" << m_dualOfNode[v] << std::endl;
454 }
455 }
456
457 // Insert an edge into the dual graph for each adjacency entry in E.
458 // The edges are directed from the left face to the right face.
459 for(node v : PG.nodes)
460 {
461 node vDual = m_dualOfNode[v];
462
463 for(adjEntry adj : v->adjEntries)
464 {
465 node vLeft = m_dualOfFace[E.leftFace (adj)];
466 node vRight = m_dualOfFace[E.rightFace(adj)];
467
468 if(vLeft != vRight) {
469 edge e = m_dual.newEdge(vLeft,vRight);
470 //std::cout << "dual edge " << e << std::endl;
471 m_dualEdge[m_primalAdj[e] = adj] = e;
472 m_dualCost[e] = 1;
473 }
474
475 if(vDual) {
476 edge eOut = m_dual.newEdge(vDual,vLeft);
477 //std::cout << "dual edge " << eOut << std::endl;
478 m_primalAdj[eOut] = adj;
479 m_dualCost[eOut] = 0;
480
481 edge eIn = m_dual.newEdge(vLeft,vDual);
482 //std::cout << "dual edge " << eIn << std::endl;
483 m_primalAdj[eIn] = adj;
484 m_dualCost[eIn] = 1;
485 }
486 }
487 }
488
489 // Augment the dual graph by two new vertices. These are used temporarily
490 // when searching for a shortest path in the dual graph.
491 m_vS = m_dual.newNode();
492 m_vT = m_dual.newNode();
493
494 m_maxCost = 2; // we just have 0/1 edge costs at the moment; maximum has
495 // to be adjusted when we have more general costs
496 }
497
498
499 // finds a weighted shortest path in the dual graph augmented by s and t
500 // (represented by m_vS and m_vT) using edges weights given by costOrig;
501 // returns list of crossed adjacency entries (corresponding
502 // to used edges in the dual) in crossed.
503 //
504 // running time: O(|dual| + L + C),
505 // where L ist the weighted length of the insertion path and C the
506 // maximum cost of an edge
findShortestPath(const PlanRepExpansion & PG,const CombinatorialEmbedding & E,const List<node> & sources,const List<node> & targets,List<Tuple2<adjEntry,adjEntry>> & crossed,const EdgeArray<bool> * forbiddenEdgeOrig)507 void MMFixedEmbeddingInserter::findShortestPath(
508 const PlanRepExpansion &PG,
509 const CombinatorialEmbedding &E,
510 const List<node> &sources,
511 const List<node> &targets,
512 List<Tuple2<adjEntry,adjEntry> > &crossed,
513 const EdgeArray<bool> *forbiddenEdgeOrig)
514 {
515 #if 0
516 static int count = 1;
517 std::cout << "==> " << count++ << std::endl;
518 std::cout << "Insert:" << std::endl;
519 std::cout << " sources: ";
520 ListConstIterator<node> itV;
521 for(itV = sources.begin(); itV.valid(); ++itV)
522 std::cout << *itV << " ";
523 std::cout << "\n targets: ";
524 for(itV = targets.begin(); itV.valid(); ++itV)
525 std::cout << *itV << " ";
526 std::cout << std::endl;
527 drawDual(PG, forbiddenEdgeOrig);
528
529 std::cout << "forbidden dual edges: ";
530 for(edge ed : m_dual.edges) {
531 if(origOfDualForbidden(ed,PG,forbiddenEdgeOrig))
532 std::cout << ed << " ";
533 }
534 std::cout << std::endl;
535 #endif
536 Array<SListPure<edge> > nodesAtDist(m_maxCost);
537 NodeArray<edge> spPred(m_dual,nullptr);
538
539 int oldIdCount = m_dual.maxEdgeIndex();
540
541 // augment dual by edges from m_vS to all adjacent faces of sources ...
542 for(node v : sources) {
543 for(adjEntry adj : v->adjEntries) {
544 // starting edges of bfs-search are all edges leaving s
545 edge eDual = m_dual.newEdge(m_vS, m_dualOfFace[E.rightFace(adj)]);
546 m_primalAdj[eDual] = adj;
547 nodesAtDist[0].pushBack(eDual);
548 }
549 }
550
551 // ... and from all adjacent faces of targets to m_vT
552 for(node v : targets) {
553 for(adjEntry adj : v->adjEntries) {
554 edge eDual = m_dual.newEdge(m_dualOfFace[E.rightFace(adj)], m_vT);
555 m_primalAdj[eDual] = adj;
556 }
557 }
558
559
560 // actual search (using extended bfs on directed dual)
561 int currentDist = 0;
562
563 for( ; ; )
564 {
565 // next candidate edge
566 while(nodesAtDist[currentDist % m_maxCost].empty())
567 ++currentDist;
568
569 edge eCand = nodesAtDist[currentDist % m_maxCost].popFrontRet();
570 node v = eCand->target();
571
572 // leads to an unvisited node?
573 if (spPred[v] == nullptr)
574 {
575 // yes, then we set v's predecessor in search tree
576 spPred[v] = eCand;
577
578 // have we reached t ...
579 if (v == m_vT)
580 {
581 // ... then search is done.
582 // constructed list of used edges (translated to crossed
583 // adjacency entries in PG) from t back to s (including first
584 // and last!)
585
586 do {
587 edge eDual = spPred[v];
588 node w = eDual->source();
589
590 if(m_primalNode[w] == nullptr)
591 // w is a face node
592 crossed.pushFront(Tuple2<adjEntry,adjEntry>(m_primalAdj[eDual],nullptr));
593 else {
594 edge eDual2 = spPred[w];
595 w = eDual2->source();
596 crossed.pushFront(Tuple2<adjEntry,adjEntry>(m_primalAdj[eDual2],m_primalAdj[eDual]));
597 }
598
599 v = w;
600 } while(v != m_vS);
601
602 break;
603 }
604
605 // append next candidate edges to queue
606 // (all edges leaving v)
607 for(adjEntry adj : v->adjEntries) {
608 edge e = adj->theEdge();
609 if (v != e->source()) continue;
610 if(origOfDualForbidden(e, PG, forbiddenEdgeOrig)) continue;
611
612 int listPos = (currentDist + m_dualCost[e]) % m_maxCost;
613 nodesAtDist[listPos].pushBack(e);
614 }
615 }
616 }
617
618 // remove augmented edges again
619 adjEntry adj;
620 while ((adj = m_vS->firstAdj()) != nullptr)
621 m_dual.delEdge(adj->theEdge());
622
623 while ((adj = m_vT->firstAdj()) != nullptr)
624 m_dual.delEdge(adj->theEdge());
625
626 m_dual.resetEdgeIdCount(oldIdCount);
627 }
628
629
prepareAnchorNode(PlanRepExpansion & PG,CombinatorialEmbedding & E,adjEntry & adjStart,node srcOrig)630 void MMFixedEmbeddingInserter::prepareAnchorNode(
631 PlanRepExpansion &PG,
632 CombinatorialEmbedding &E,
633 adjEntry &adjStart,
634 node srcOrig)
635 {
636 adjEntry adj = adjStart;
637 face f = E.rightFace(adjStart);
638
639 edge eStraight;
640 PlanRepExpansion::NodeSplit *nsStraight;
641 List<edge> *pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
642
643 node vStraight = pathStraight->front()->source();
644 if(PG.original(vStraight) != srcOrig) {
645 vStraight = pathStraight->back()->target();
646 if(PG.original(vStraight) != srcOrig) {
647 adj = adj->cyclicSucc();
648 pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
649 vStraight = pathStraight->front()->source();
650 if(PG.original(vStraight) != srcOrig) {
651 vStraight = pathStraight->back()->target();
652 }
653 }
654 }
655 OGDF_ASSERT(PG.original(vStraight) == srcOrig);
656
657 if(PG.original(adj->twinNode()) == srcOrig) {
658 // No need for a split; can just directly go to a split node
659 adjStart = (adj == adjStart) ? adj->twin()->cyclicPred() : adj->twin();
660
661 } else {
662 edge eNew, e = adj->theEdge();
663 if(nsStraight == nullptr) {
664 // We split a chain of an original edge
665 eNew = PG.enlargeSplit(vStraight, e, E);
666
667 } else {
668 // We split a node split
669 eNew = PG.splitNodeSplit(e, E);
670 }
671
672 adjEntry adj1 = eNew->adjSource();
673 node vLeft = m_dualOfFace[E.leftFace (adj1)];
674 node vRight = m_dualOfFace[E.rightFace(adj1)];
675
676 edge eDual1 = m_dual.newEdge(vLeft,vRight);
677 m_dualEdge[m_primalAdj[eDual1] = adj1] = eDual1;
678 m_dualCost[eDual1] = 1;
679
680 adjEntry adj2 = e->adjTarget();
681 edge eDual2 = m_dual.newEdge(vRight,vLeft);
682 m_dualEdge[m_primalAdj[eDual2] = adj2] = eDual2;
683 m_dualCost[eDual2] = 1;
684
685 adjStart = (E.rightFace(adj1) == f) ? adj1 : adj2;
686 OGDF_ASSERT(E.rightFace(adjStart) == f);
687 }
688 }
689
690
preprocessInsertionPath(PlanRepExpansion & PG,CombinatorialEmbedding & E,node srcOrig,node tgtOrig,List<Tuple2<adjEntry,adjEntry>> & crossed)691 void MMFixedEmbeddingInserter::preprocessInsertionPath(
692 PlanRepExpansion &PG,
693 CombinatorialEmbedding &E,
694 node srcOrig,
695 node tgtOrig,
696 //PlanRepExpansion::nodeSplit ns,
697 List<Tuple2<adjEntry,adjEntry> > &crossed)
698 {
699 adjEntry &adjStart = (*crossed.begin ()).x1();
700 adjEntry &adjEnd = (*crossed.rbegin()).x1();
701
702 // Warning: Potential multi-edges are not considered here!!!
703
704 if(PG.original(adjStart->theNode()) == nullptr) {
705 prepareAnchorNode(PG, E, adjStart, srcOrig);
706 }
707
708 if(PG.original(adjEnd->theNode()) == nullptr) {
709 prepareAnchorNode(PG, E, adjEnd, tgtOrig);
710 }
711 }
712
713
714 // inserts edge e according to insertion path crossed.
715 // updates embeding and dual graph
insertEdge(PlanRepExpansion & PG,CombinatorialEmbedding & E,edge eOrig,node srcOrig,node tgtOrig,PlanRepExpansion::NodeSplit * nodeSplit,List<Tuple2<adjEntry,adjEntry>> & crossed)716 void MMFixedEmbeddingInserter::insertEdge(
717 PlanRepExpansion &PG,
718 CombinatorialEmbedding &E,
719 edge eOrig,
720 node srcOrig,
721 node tgtOrig,
722 PlanRepExpansion::NodeSplit *nodeSplit,
723 List<Tuple2<adjEntry,adjEntry> > &crossed)
724 {
725 preprocessInsertionPath(PG,E,srcOrig,tgtOrig,/*nodeSplit,*/crossed);
726
727 // remove dual nodes of faces on insertion path
728 ListConstIterator<Tuple2<adjEntry,adjEntry> > it;
729 for(it = crossed.begin(); it.valid() && it.succ().valid(); ++it) {
730 adjEntry adj1 = (*it).x1();
731 adjEntry adj2 = (*it).x2();
732 if(adj2 == nullptr) {
733 m_dual.delNode(m_dualOfFace[E.rightFace(adj1)]);
734 } else {
735 OGDF_ASSERT(adj1->theNode() == adj2->theNode());
736 m_dual.delNode(m_dualOfFace[E.leftFace(adj2)]);
737 }
738 }
739
740 // update primal
741 PG.insertEdgePathEmbedded(eOrig,nodeSplit,E,crossed);
742
743 // remove edges at vertices (to be split) on insertion path
744 // and insert a new vertex in dual for each split node
745 for(it = crossed.begin(); it.succ().valid(); ++it) {
746 adjEntry adj1 = (*it).x1();
747 adjEntry adj2 = (*it).x2();
748 if(adj2 != nullptr) {
749 node v = adj1->theNode();
750 node vDual = m_dualOfNode[v];
751 if(v->degree() >= 4) {
752 while(vDual->firstAdj() != nullptr)
753 m_dual.delEdge(vDual->firstAdj()->theEdge());
754 } else {
755 m_dual.delNode(vDual);
756 m_dualOfNode[v] = nullptr;
757 }
758
759 node w = adj2->theNode();
760 if(w->degree() >= 4)
761 m_primalNode[m_dualOfNode[w] = m_dual.newNode()] = w;
762 }
763 }
764
765 // insert new face nodes into dual
766 OGDF_ASSERT( eOrig != nullptr || nodeSplit != nullptr ); // otherwise the path below is not well defined
767 const List<edge> &path = (eOrig) ? PG.chain(eOrig) : nodeSplit->m_path;
768 ListConstIterator<edge> itEdge;
769 for(itEdge = path.begin(); itEdge.valid(); ++itEdge)
770 {
771 adjEntry adj = (*itEdge)->adjSource();
772 m_dualOfFace[E.leftFace (adj)] = m_dual.newNode();
773 m_dualOfFace[E.rightFace(adj)] = m_dual.newNode();
774 }
775
776 // insert new edges into dual
777 for(itEdge = path.begin(), it = crossed.begin().succ();
778 itEdge.valid(); ++itEdge, ++it)
779 {
780 adjEntry adjSrc = (*itEdge)->adjSource();
781 face f = E.rightFace(adjSrc); // face to the right of adj in loop
782 node vRight = m_dualOfFace[f];
783 m_delFaces->insert(f);
784
785 adjEntry adj1 = f->firstAdj(), adj = adj1;
786 do {
787 face fAdj = E.leftFace(adj);
788 if(!m_delFaces->isMember(fAdj)) // Don't insert edges twice
789 {
790 node vLeft = m_dualOfFace[fAdj];
791
792 edge eLR = m_dual.newEdge(vLeft,vRight);
793 m_dualEdge[m_primalAdj[eLR] = adj] = eLR;
794 m_dualCost [eLR] = 1;
795
796 edge eRL = m_dual.newEdge(vRight,vLeft);
797 m_dualEdge[m_primalAdj[eRL] = adj->twin()] = eRL;
798 m_dualCost [eRL] = 1;
799
800 } else if(f == fAdj)
801 m_dualEdge[adj] = m_dualEdge[adj->twin()] = nullptr;
802
803 node vDual = m_dualOfNode[adj->theNode()];
804 if(vDual != nullptr) {
805 adjEntry adjSucc = adj->cyclicSucc();
806 edge eOut = m_dual.newEdge(vDual,vRight);
807 m_primalAdj[eOut] = adjSucc;
808 m_dualCost[eOut] = 0;
809
810 edge eIn = m_dual.newEdge(vRight,vDual);
811 m_primalAdj[eIn] = adjSucc;
812 m_dualCost[eIn] = 1;
813 }
814 }
815 while((adj = adj->faceCycleSucc()) != adj1);
816
817 // the other face adjacent to *itEdge ...
818 f = E.rightFace(adjSrc->twin());
819 vRight = m_dualOfFace[f];
820 m_delFaces->insert(f);
821
822 adj1 = f->firstAdj();
823 adj = adj1;
824 do {
825 face fAdj = E.leftFace(adj);
826 if(!m_delFaces->isMember(fAdj))
827 {
828 node vLeft = m_dualOfFace[fAdj];
829
830 edge eLR = m_dual.newEdge(vLeft,vRight);
831 m_dualEdge[m_primalAdj[eLR] = adj] = eLR;
832 m_dualCost [eLR] = 1;
833
834 edge eRL = m_dual.newEdge(vRight,vLeft);
835 m_dualEdge[m_primalAdj[eRL] = adj->twin()] = eRL;
836 m_dualCost [eRL] = 1;
837
838 } else if(f == fAdj)
839 m_dualEdge[adj] = m_dualEdge[adj->twin()] = nullptr;
840
841 node vDual = m_dualOfNode[adj->theNode()];
842 if(vDual != nullptr) {
843 adjEntry adjSucc = adj->cyclicSucc();
844 edge eOut = m_dual.newEdge(vDual,vRight);
845 m_primalAdj[eOut] = adjSucc;
846 m_dualCost[eOut] = 0;
847
848 edge eIn = m_dual.newEdge(vRight,vDual);
849 m_primalAdj[eIn] = adjSucc;
850 m_dualCost[eIn] = 1;
851 }
852
853 adjEntry adjS1 = (*it).x1();
854 adjEntry adjS2 = (*it).x2();
855
856 if(adjS2 != nullptr) {
857 node v = adjS1->theNode();
858 node dualV = m_dualOfNode[v];
859 if(dualV) {
860 face f1 = E.leftFace(adjS1);
861 face f2 = E.leftFace(adjS1->cyclicPred());
862
863 for(adjEntry adjE : v->adjEntries) {
864 face fL = E.leftFace(adjE);
865 if(fL == f1 || fL == f2) continue;
866
867 node vL = m_dualOfFace[fL];
868 edge eOut = m_dual.newEdge(dualV,vL);
869 m_primalAdj[eOut] = adjE;
870 m_dualCost[eOut] = 0;
871 edge eIn = m_dual.newEdge(vL,dualV);
872 m_primalAdj[eIn] = adjE;
873 m_dualCost[eIn] = 1;
874 }
875 }
876
877 v = adjS2->theNode();
878 dualV = m_dualOfNode[v];
879 if(dualV) {
880 face f1 = E.leftFace(adjS2);
881 face f2 = E.leftFace(adjS2->cyclicPred());
882
883 for(adjEntry adjE : v->adjEntries) {
884 face fL = E.leftFace(adjE);
885 if(fL == f1 || fL == f2) continue;
886
887 node vL = m_dualOfFace[fL];
888 edge eOut = m_dual.newEdge(dualV,vL);
889 m_primalAdj[eOut] = adjE;
890 m_dualCost[eOut] = 0;
891 edge eIn = m_dual.newEdge(vL,dualV);
892 m_primalAdj[eIn] = adjE;
893 m_dualCost[eIn] = 1;
894 }
895 }
896 }
897 }
898 while((adj = adj->faceCycleSucc()) != adj1);
899 }
900
901 node s = path.front()->source();
902 if(s->degree() == 4 && PG.splittable(s)) {
903 m_primalNode[m_dualOfNode[s] = m_dual.newNode()] = s;
904 insertDualEdges(s,E);
905 }
906
907 node t = path.back()->target();
908 if(t->degree() == 4 && PG.splittable(t)) {
909 m_primalNode[m_dualOfNode[t] = m_dual.newNode()] = t;
910 insertDualEdges(t,E);
911 }
912
913 m_delFaces->clear();
914 }
915
916
insertDualEdge(node vDual,adjEntry adj,const CombinatorialEmbedding & E)917 void MMFixedEmbeddingInserter::insertDualEdge(node vDual, adjEntry adj, const CombinatorialEmbedding &E)
918 {
919 node vLeft = m_dualOfFace[E.leftFace(adj)];
920
921 edge eOut = m_dual.newEdge(vDual,vLeft);
922 m_primalAdj[eOut] = adj;
923 m_dualCost[eOut] = 0;
924
925 edge eIn = m_dual.newEdge(vLeft,vDual);
926 m_primalAdj[eIn] = adj;
927 m_dualCost[eIn] = 1;
928 }
929
930
insertDualEdges(node v,const CombinatorialEmbedding & E)931 void MMFixedEmbeddingInserter::insertDualEdges(node v, const CombinatorialEmbedding &E)
932 {
933 node vDual = m_dualOfNode[v];
934 if (vDual) {
935 for (adjEntry adj : v->adjEntries)
936 insertDualEdge(vDual, adj, E);
937 }
938 }
939
940
941 // removes edge eOrig; updates embedding and dual graph
removeEdge(PlanRepExpansion & PG,CombinatorialEmbedding & E,edge eOrig,PlanRepExpansion::NodeSplit * nodeSplit,node & oldSrc,node & oldTgt)942 void MMFixedEmbeddingInserter::removeEdge(
943 PlanRepExpansion &PG,
944 CombinatorialEmbedding &E,
945 edge eOrig,
946 PlanRepExpansion::NodeSplit *nodeSplit,
947 node &oldSrc, node &oldTgt)
948 {
949 OGDF_ASSERT( eOrig != nullptr || nodeSplit != nullptr ); // otherwise the path below is not well defined
950 const List<edge> &path = (eOrig) ? PG.chain(eOrig) : nodeSplit->m_path;
951
952 ListConstIterator<edge> itEdge;
953 for(itEdge = path.begin(); itEdge.valid(); ++itEdge)
954 {
955 adjEntry adj = (*itEdge)->adjSource();
956 m_delFaces->insert(E.leftFace (adj));
957 m_delFaces->insert(E.rightFace (adj));
958
959 // remove dual of nodes that get merged
960 if(itEdge != path.begin()) {
961 node xl = adj->cyclicSucc()->twinNode();
962 node xlDual = m_dualOfNode[xl];
963 node xlOrig = PG.original(xl);
964 node xr = adj->cyclicPred()->twinNode();
965 node xrDual = m_dualOfNode[xr];
966 node xrOrig = PG.original(xr);
967
968 if(xlOrig != nullptr && xlOrig == xrOrig) {
969 if(xlDual) m_dual.delNode(xlDual);
970 if(xrDual) m_dual.delNode(xrDual);
971 m_dualOfNode[xl] = m_dualOfNode[xr] = nullptr;
972 }
973 }
974 }
975
976 node vSrc = path.front()->source();
977 if(m_dualOfNode[vSrc] != nullptr && vSrc->degree() == 4) {
978 m_dual.delNode(m_dualOfNode[vSrc]);
979 m_dualOfNode[vSrc] = nullptr;
980 }
981 node vTgt = path.back()->target();
982 if(m_dualOfNode[vTgt] != nullptr && vTgt->degree() == 4) {
983 m_dual.delNode(m_dualOfNode[vTgt]);
984 m_dualOfNode[vTgt] = nullptr;
985 }
986
987 // delete all corresponding nodes in dual
988 ListConstIterator<face> itsF;
989 for(itsF = m_delFaces->faces().begin(); itsF.valid(); ++itsF)
990 m_dual.delNode(m_dualOfFace[*itsF]);
991
992 m_delFaces->clear();
993
994 // remove edge path from PG
995 PG.removeEdgePathEmbedded(E,eOrig,nodeSplit,*m_newFaces,*m_mergedNodes, oldSrc, oldTgt);
996
997 // insert dual nodes for merged nodes
998 ListConstIterator<node> itV;
999 for(itV = m_mergedNodes->nodes().begin(); itV.valid(); ++itV) {
1000 node v = *itV;
1001 if(PG.splittable(v) && v->degree() >= 4) {
1002 node vDual = m_dualOfNode[v] = m_dual.newNode();
1003 m_primalNode[vDual] = v;
1004
1005 for(adjEntry adj : v->adjEntries) {
1006 if(!m_newFaces->isMember(E.leftFace(adj))) // other edges are inserted below!
1007 insertDualEdge(vDual,adj,E);
1008 }
1009 }
1010 }
1011 m_mergedNodes->clear();
1012
1013 // insert new nodes for new faces
1014 ListConstIterator<face> itF;
1015 for(itF = m_newFaces->faces().begin(); itF.valid(); ++itF) {
1016 m_dualOfFace[*itF] = m_dual.newNode();
1017 }
1018
1019 // insert new edges into dual
1020 for(itF = m_newFaces->faces().begin(); itF.valid(); ++itF)
1021 {
1022 face f = *itF; // face to the right of adj in loop
1023 node vRight = m_dualOfFace[f];
1024
1025 adjEntry adj1 = f->firstAdj(), adj = adj1;
1026 do {
1027 face fAdj = E.leftFace(adj);
1028
1029 if(!m_newFaces->isMember(fAdj) || f->index() < fAdj->index())
1030 {
1031 node vLeft = m_dualOfFace[E.leftFace(adj)];
1032
1033 edge eLR = m_dual.newEdge(vLeft,vRight);
1034 m_dualEdge[m_primalAdj[eLR] = adj] = eLR;
1035 m_dualCost [eLR] = 1;
1036
1037 edge eRL = m_dual.newEdge(vRight,vLeft);
1038 m_dualEdge[m_primalAdj[eRL] = adj->twin()] = eRL;
1039 m_dualCost [eRL] = 1;
1040
1041 } else if(f == fAdj)
1042 m_dualEdge[adj] = m_dualEdge[adj->twin()] = nullptr;
1043
1044 node vDual = m_dualOfNode[adj->theNode()];
1045 if(vDual != nullptr) {
1046 adjEntry adjSucc = adj->cyclicSucc();
1047 edge eOut = m_dual.newEdge(vDual,vRight);
1048 m_primalAdj[eOut] = adjSucc;
1049 m_dualCost[eOut] = 0;
1050
1051 edge eIn = m_dual.newEdge(vRight,vDual);
1052 m_primalAdj[eIn] = adjSucc;
1053 m_dualCost[eIn] = 1;
1054 }
1055 }
1056 while((adj = adj->faceCycleSucc()) != adj1);
1057 }
1058
1059 m_newFaces->clear();
1060
1061 }
1062
1063
contractSplit(PlanRepExpansion & PG,CombinatorialEmbedding & E,PlanRepExpansion::NodeSplit * nodeSplit)1064 void MMFixedEmbeddingInserter::contractSplit(
1065 PlanRepExpansion &PG,
1066 CombinatorialEmbedding &E,
1067 PlanRepExpansion::NodeSplit *nodeSplit)
1068 {
1069 edge e = nodeSplit->m_path.front();
1070 node u = e->source();
1071 node v = e->target();
1072
1073 if(m_dualOfNode[u]) m_dual.delNode(m_dualOfNode[u]);
1074 if(m_dualOfNode[v]) m_dual.delNode(m_dualOfNode[v]);
1075
1076 // remove dual edges connecting dual node of left face of e
1077 // with dual node of right face of e
1078 node vl = m_dualOfFace[E.leftFace(e->adjSource())];
1079 adjEntry adj, adjNext;
1080 for(adj = vl->firstAdj(); adj != nullptr; adj = adjNext) {
1081 adjNext = adj->succ();
1082
1083 adjEntry padj = m_primalAdj[adj->theEdge()];
1084 if(padj == e->adjSource() || padj == e->adjTarget())
1085 m_dual.delEdge(adj->theEdge());
1086 }
1087
1088 PG.contractSplit(nodeSplit,E);
1089 OGDF_ASSERT(u->degree() >= 4);
1090
1091 m_primalNode[m_dualOfNode[u] = m_dual.newNode()] = u;
1092 insertDualEdges(u,E);
1093 }
1094
1095
contractSplitIfReq(PlanRepExpansion & PG,CombinatorialEmbedding & E,node u,const PlanRepExpansion::nodeSplit nsCurrent)1096 void MMFixedEmbeddingInserter::contractSplitIfReq(
1097 PlanRepExpansion &PG,
1098 CombinatorialEmbedding &E,
1099 node u,
1100 const PlanRepExpansion::nodeSplit nsCurrent)
1101 {
1102 edge eContract = u->firstAdj()->theEdge();
1103 edge eExpand = u->lastAdj ()->theEdge();
1104 if(PG.nodeSplitOf(eContract) == nullptr)
1105 std::swap(eContract, eExpand);
1106
1107 if(u->degree() == 2 && PG.nodeSplitOf(eContract) != nullptr && PG.nodeSplitOf(eContract) != nsCurrent) {
1108 edge eDCS = m_dualEdge[eContract->adjSource()];
1109 if(eDCS) m_dual.delEdge(eDCS);
1110 edge eDCT = m_dualEdge[eContract->adjTarget()];
1111 if(eDCT) m_dual.delEdge(eDCT);
1112 edge eDES = m_dualEdge[eExpand ->adjSource()];
1113 if(eDES) m_dual.delEdge(eDES);
1114 edge eDET = m_dualEdge[eExpand ->adjTarget()];
1115 if(eDET) m_dual.delEdge(eDET);
1116
1117 edge e = PG.unsplitExpandNode(u,eContract,eExpand,E);
1118
1119 if(e->isSelfLoop()) {
1120 for(adjEntry adj : e->source()->adjEntries) {
1121 if(e == adj->theEdge()) continue;
1122 edge eDual = m_dualEdge[adj];
1123 if(eDual) m_dual.delEdge(eDual);
1124 }
1125
1126 PG.removeSelfLoop(e,E);
1127
1128 } else {
1129 adjEntry adj = e->adjSource();
1130 node vLeft = m_dualOfFace[E.leftFace (adj)];
1131 node vRight = m_dualOfFace[E.rightFace(adj)];
1132
1133 if(vLeft != vRight)
1134 {
1135 edge eLR = m_dual.newEdge(vLeft,vRight);
1136 m_dualEdge[m_primalAdj[eLR] = adj] = eLR;
1137 m_dualCost [eLR] = 1;
1138
1139 edge eRL = m_dual.newEdge(vRight,vLeft);
1140 m_dualEdge[m_primalAdj[eRL] = adj->twin()] = eRL;
1141 m_dualCost [eRL] = 1;
1142 }
1143 }
1144 }
1145 }
1146
1147
collectAnchorNodes(node v,NodeSet<> & nodes,const PlanRepExpansion::NodeSplit * nsParent,const PlanRepExpansion & PG) const1148 void MMFixedEmbeddingInserter::collectAnchorNodes(
1149 node v,
1150 NodeSet<> &nodes,
1151 const PlanRepExpansion::NodeSplit *nsParent,
1152 const PlanRepExpansion &PG) const
1153 {
1154 if(PG.original(v) != nullptr)
1155 nodes.insert(v);
1156
1157 for(adjEntry adj : v->adjEntries) {
1158 edge e = adj->theEdge();
1159 const PlanRepExpansion::NodeSplit *ns = PG.nodeSplitOf(e);
1160 if(ns == nullptr) {
1161 // add dummy nodes of non-node-split edge
1162 ListConstIterator<edge> it = PG.chain(PG.originalEdge(e)).begin();
1163 for(++it; it.valid(); ++it)
1164 nodes.insert((*it)->source());
1165
1166 } else if(ns != nsParent) {
1167 // add dummy nodes of node-split edge
1168 ListConstIterator<edge> it = ns->m_path.begin();
1169 for(++it; it.valid(); ++it)
1170 nodes.insert((*it)->source());
1171
1172 node w = (v == e->source()) ? ns->target() : ns->source();
1173 collectAnchorNodes(w, nodes, ns, PG);
1174 }
1175 }
1176 }
1177
1178
findSourcesAndTargets(node src,node tgt,NodeSet<> & sources,NodeSet<> & targets,const PlanRepExpansion & PG) const1179 void MMFixedEmbeddingInserter::findSourcesAndTargets(
1180 node src, node tgt,
1181 NodeSet<> &sources,
1182 NodeSet<> &targets,
1183 const PlanRepExpansion &PG) const
1184 {
1185 collectAnchorNodes(src, sources, nullptr, PG);
1186 collectAnchorNodes(tgt, targets, nullptr, PG);
1187 }
1188
anchorNodes(node vOrig,NodeSet<> & nodes,const PlanRepExpansion & PG) const1189 void MMFixedEmbeddingInserter::anchorNodes(
1190 node vOrig,
1191 NodeSet<> &nodes,
1192 const PlanRepExpansion &PG) const
1193 {
1194 node vFirst = PG.expansion(vOrig).front();
1195 if(PG.splittableOrig(vOrig))
1196 collectAnchorNodes(vFirst, nodes, nullptr, PG);
1197 else
1198 nodes.insert(vFirst);
1199 }
1200
1201
commonDummy(NodeSet<> & sources,NodeSet<> & targets)1202 node MMFixedEmbeddingInserter::commonDummy(
1203 NodeSet<> &sources,
1204 NodeSet<> &targets)
1205 {
1206 ListConstIterator<node> it;
1207 for(it = sources.nodes().begin(); it.valid(); ++it)
1208 if(targets.isMember(*it))
1209 return *it;
1210
1211 return nullptr;
1212 }
1213
1214
convertDummy(PlanRepExpansion & PG,CombinatorialEmbedding & E,node u,node vOrig,PlanRepExpansion::nodeSplit ns_0)1215 void MMFixedEmbeddingInserter::convertDummy(
1216 PlanRepExpansion &PG,
1217 CombinatorialEmbedding &E,
1218 node u,
1219 node vOrig,
1220 PlanRepExpansion::nodeSplit ns_0)
1221 {
1222 PlanRepExpansion::nodeSplit ns_1 = PG.convertDummy(u,vOrig,ns_0);
1223
1224 m_primalNode[m_dualOfNode[u] = m_dual.newNode()] = u;
1225 insertDualEdges(u,E);
1226
1227 if(ns_0->m_path.size() == 1)
1228 contractSplit(PG,E,ns_0);
1229 if(ns_1->m_path.size() == 1)
1230 contractSplit(PG,E,ns_1);
1231 }
1232
1233
checkSplitDeg(PlanRepExpansion & PG) const1234 bool MMFixedEmbeddingInserter::checkSplitDeg(
1235 PlanRepExpansion &PG) const
1236 {
1237 ListConstIterator<PlanRepExpansion::NodeSplit> it;
1238 for(it = PG.nodeSplits().begin(); it.valid(); ++it) {
1239 node src = (*it).source();
1240 if(src->degree() <= 2)
1241 return false;
1242 node tgt = (*it).target();
1243 if(tgt->degree() <= 2)
1244 return false;
1245 }
1246
1247 return true;
1248 }
1249
1250
checkDualGraph(PlanRepExpansion & PG,const CombinatorialEmbedding & E) const1251 bool MMFixedEmbeddingInserter::checkDualGraph(
1252 PlanRepExpansion &PG,
1253 const CombinatorialEmbedding &E) const
1254 {
1255 NodeArray<face> af(m_dual,nullptr);
1256 NodeArray<node> av(m_dual,nullptr);
1257
1258 for(face f : E.faces) {
1259 node u = m_dualOfFace[f];
1260 if(u == nullptr)
1261 return false;
1262 if(af[u] != nullptr || av[u] != nullptr)
1263 return false;
1264 af[u] = f;
1265 }
1266
1267 for(node v : PG.nodes) {
1268 if(PG.splittable(v) && v->degree() >= 4) {
1269 node u = m_dualOfNode[v];
1270 if(u == nullptr)
1271 return false;
1272 if(af[u] != nullptr || av[u] != nullptr)
1273 return false;
1274 av[u] = v;
1275 } else {
1276 if(m_dualOfNode[v] != nullptr)
1277 return false;
1278 }
1279 }
1280
1281 Array<bool> exists(0,m_dual.maxEdgeIndex(),false);
1282
1283 for(edge e : m_dual.edges)
1284 {
1285 exists[e->index()] = true;
1286
1287 node v = e->source();
1288 node w = e->target();
1289 adjEntry adj = m_primalAdj[e];
1290
1291 if(af[v] != nullptr && af[w] != nullptr) {
1292 if(af[v] != E.leftFace(adj))
1293 return false;
1294 if(af[w] != E.rightFace(adj))
1295 return false;
1296 if(m_dualEdge[adj] != e)
1297 return false;
1298
1299 } else if(af[v] != nullptr) {
1300 if(adj->theNode() != av[w])
1301 return false;
1302 if(af[v] != E.leftFace(adj))
1303 return false;
1304
1305 } else if(af[w] != nullptr) {
1306 if(adj->theNode() != av[v])
1307 return false;
1308 if(af[w] != E.leftFace(adj))
1309 return false;
1310 } else
1311 return false;
1312 }
1313
1314 for(edge e : PG.edges)
1315 {
1316 if(E.leftFace(e->adjSource()) == E.rightFace(e->adjSource())) {
1317 if(m_dualEdge[e->adjSource()] != nullptr)
1318 return false;
1319 if(m_dualEdge[e->adjTarget()] != nullptr)
1320 return false;
1321 continue;
1322 }
1323
1324 edge eDual = m_dualEdge[e->adjSource()];
1325 node srcDual = eDual->source();
1326 node tgtDual = eDual->target();
1327
1328 if(af[srcDual] == nullptr)
1329 return false;
1330 if(af[tgtDual] == nullptr)
1331 return false;
1332
1333 if(E.leftFace(e->adjSource()) != af[srcDual])
1334 return false;
1335 if(E.rightFace(e->adjSource()) != af[tgtDual])
1336 return false;
1337
1338 if(!exists[eDual->index()])
1339 return false;
1340 #ifdef OGDF_DEBUG
1341 if(eDual->graphOf() != &m_dual)
1342 return false;
1343
1344 eDual = m_dualEdge[e->adjTarget()];
1345 if(eDual->graphOf() != &m_dual)
1346 return false;
1347 #endif
1348 }
1349
1350 return true;
1351 }
1352
1353 }
1354