1 /** \file
2 * \brief Implementation of class PlanRepExpansion.
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
33 #include <ogdf/planarity/PlanRepExpansion.h>
34 #include <ogdf/basic/simple_graph_alg.h>
35 #include <ogdf/basic/extended_graph_alg.h>
36 #include <ogdf/basic/FaceSet.h>
37 #include <ogdf/basic/NodeSet.h>
38
39
40 namespace ogdf {
41
PlanRepExpansion(const Graph & G)42 PlanRepExpansion::PlanRepExpansion(const Graph& G)
43 {
44 List<node> splittableNodes;
45 for(node v : G.nodes) {
46 if(v->degree() >= 4)
47 splittableNodes.pushBack(v);
48 }
49
50 doInit(G,splittableNodes);
51 }
52
PlanRepExpansion(const Graph & G,const List<node> & splittableNodes)53 PlanRepExpansion::PlanRepExpansion(const Graph& G, const List<node> &splittableNodes)
54 {
55 doInit(G,splittableNodes);
56 }
57
doInit(const Graph & G,const List<node> & splittableNodes)58 void PlanRepExpansion::doInit(const Graph &G, const List<node> &splittableNodes)
59 {
60 m_pGraph = &G;
61 m_eAuxCopy.init(G);
62
63 // compute connected component of G
64 NodeArray<int> component(G);
65 m_numCC = connectedComponents(G,component);
66
67 // intialize the array of lists of nodes contained in a CC
68 m_nodesInCC.init(m_numCC);
69
70 for(node v : G.nodes)
71 m_nodesInCC[component[v]].pushBack(v);
72
73 m_currentCC = -1; // not yet initialized
74
75 m_vCopy.init(G);
76 m_eCopy.init(G);
77 m_vOrig.init(*this,nullptr);
78 m_eOrig.init(*this,nullptr);
79 m_vIterator.init(*this,nullptr);
80 m_eIterator.init(*this,nullptr);
81
82 m_splittable.init(*this,false);
83 m_splittableOrig.init(G,false);
84 m_eNodeSplit.init(*this,nullptr);
85
86 ListConstIterator<node> it;
87 for(it = splittableNodes.begin(); it.valid(); ++it)
88 if((*it)->degree() >= 4)
89 m_splittableOrig[*it] = true;
90 }
91
92
initCC(int i)93 void PlanRepExpansion::initCC(int i)
94 {
95 // delete copy / chain fields for originals of nodes in current cc
96 // (since we remove all these copies in initByNodes(...)
97 if (m_currentCC >= 0)
98 {
99 const List<node> &origInCC = nodesInCC(i);
100 ListConstIterator<node> itV;
101
102 for(itV = origInCC.begin(); itV.valid(); ++itV)
103 {
104 node vG = *itV;
105
106 m_vCopy[vG].clear();
107
108 for(adjEntry adj : vG->adjEntries) {
109 if ((adj->index() & 1) == 0) continue;
110 edge eG = adj->theEdge();
111
112 m_eCopy[eG].clear();
113 }
114 }
115 }
116
117 m_currentCC = i;
118
119 NodeArray<node> vCopy(*m_pGraph);
120 Graph::constructInitByNodes(*m_pGraph,m_nodesInCC[i],vCopy,m_eAuxCopy);
121
122 ListConstIterator<node> itV;
123 for(itV = m_nodesInCC[i].begin(); itV.valid(); ++itV)
124 {
125 node vOrig = *itV;
126 node v = vCopy[vOrig];
127
128 m_vOrig[v] = vOrig;
129 m_vIterator[v] = m_vCopy[vOrig].pushBack(v);
130 m_splittable[v] = m_splittableOrig[vOrig];
131
132 for(adjEntry adj : vOrig->adjEntries) {
133 if ((adj->index() & 1) == 0) {
134 edge e = adj->theEdge();
135 m_eIterator[m_eAuxCopy[e]] = m_eCopy[e].pushBack(m_eAuxCopy[e]);
136 m_eOrig[m_eAuxCopy[e]] = e;
137 }
138 }
139 }
140
141 m_nodeSplits.clear();
142 }
143
144
delEdge(edge e)145 void PlanRepExpansion::delEdge(edge e)
146 {
147 edge eOrig = m_eOrig[e];
148 OGDF_ASSERT(m_eCopy[eOrig].size() == 1);
149 Graph::delEdge(e);
150 m_eCopy[eOrig].clear();
151 }
152
153
embed()154 bool PlanRepExpansion::embed()
155 {
156 return planarEmbed(*this);
157 }
158
159
prepareNodeSplit(const SList<adjEntry> & partitionLeft,adjEntry & adjLeft,adjEntry & adjRight)160 void PlanRepExpansion::prepareNodeSplit(
161 const SList<adjEntry> &partitionLeft,
162 adjEntry &adjLeft,
163 adjEntry &adjRight)
164 {
165 OGDF_ASSERT(!partitionLeft.empty());
166 OGDF_ASSERT(partitionLeft.front()->theNode()->degree() > partitionLeft.size());
167
168 SListConstIterator<adjEntry> it = partitionLeft.begin();
169 adjEntry adj = *it;
170 adjLeft = adj;
171
172 for(++it; it.valid(); ++it) {
173 moveAdjAfter(*it,adj);
174 adj = *it;
175 }
176
177 adjRight = adj->cyclicSucc();
178 }
179
180
insertEdgePath(edge eOrig,nodeSplit ns,node vStart,node vEnd,List<Crossing> & eip,edge eSrc,edge eTgt)181 void PlanRepExpansion::insertEdgePath(
182 edge eOrig,
183 nodeSplit ns,
184 node vStart,
185 node vEnd,
186 List<Crossing> &eip,
187 edge eSrc,
188 edge eTgt)
189 {
190 OGDF_ASSERT((eOrig != nullptr && ns == nullptr) || (eOrig == nullptr && ns != nullptr));
191
192 if(eOrig)
193 m_eCopy[eOrig].clear();
194 else
195 ns->m_path.clear();
196
197 if(eSrc != nullptr) {
198 if(eOrig) {
199 m_eIterator[eSrc] = m_eCopy[eOrig].pushBack(eSrc);
200 m_eOrig [eSrc] = eOrig;
201 } else {
202 m_eIterator [eSrc] = ns->m_path.pushBack(eSrc);
203 m_eNodeSplit[eSrc] = ns;
204 }
205 }
206
207 node v = vStart;
208 ListConstIterator<Crossing> it;
209 for(it = eip.begin(); it.valid(); ++it)
210 {
211 adjEntry adj = (*it).m_adj;
212 if(adj == nullptr) {
213 adjEntry adjLeft, adjRight;
214 prepareNodeSplit((*it).m_partitionLeft, adjLeft, adjRight);
215
216 node w = splitNode(adjLeft,adjRight);
217 edge eNew = adjLeft->cyclicPred()->theEdge();
218
219 m_vIterator [w] = m_vCopy[m_vOrig[adjLeft->theNode()]].pushBack(w);
220 m_splittable[w] = true;
221 m_vOrig [w] = m_vOrig[adjLeft->theNode()];
222
223 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
224 (*itNS).m_nsIterator = itNS;
225 m_eIterator[eNew] = (*itNS).m_path.pushBack(eNew);
226 m_eNodeSplit[eNew] = &(*itNS);
227
228 adj = adjRight->cyclicPred();
229 }
230
231 node u = split(adj->theEdge())->source();
232 edge eNew = newEdge(v,u);
233
234 if(eOrig) {
235 m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
236 m_eOrig [eNew] = eOrig;
237 } else {
238 m_eIterator [eNew] = ns->m_path.pushBack(eNew);
239 m_eNodeSplit[eNew] = ns;
240 }
241
242 v = u;
243 }
244
245 edge eNew = newEdge(v,vEnd);
246 if(eOrig) {
247 m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
248 m_eOrig [eNew] = eOrig;
249 } else {
250 m_eIterator [eNew] = ns->m_path.pushBack(eNew);
251 m_eNodeSplit[eNew] = ns;
252 }
253
254 if(eTgt != nullptr) {
255 if(eOrig) {
256 m_eIterator[eTgt] = m_eCopy[eOrig].pushBack(eTgt);
257 m_eOrig [eTgt] = eOrig;
258 } else {
259 m_eIterator [eTgt] = ns->m_path.pushBack(eTgt);
260 m_eNodeSplit[eTgt] = ns;
261 }
262 }
263 }
264
265
insertEdgePathEmbedded(edge eOrig,nodeSplit ns,CombinatorialEmbedding & E,const List<Tuple2<adjEntry,adjEntry>> & crossedEdges)266 void PlanRepExpansion::insertEdgePathEmbedded(
267 edge eOrig,
268 nodeSplit ns,
269 CombinatorialEmbedding &E,
270 const List<Tuple2<adjEntry,adjEntry> > &crossedEdges)
271 {
272 OGDF_ASSERT((eOrig != nullptr && ns == nullptr) || (eOrig == nullptr && ns != nullptr));
273
274 if(eOrig)
275 m_eCopy[eOrig].clear();
276 else
277 ns->m_path.clear();
278
279 adjEntry adjSrc, adjTgt;
280 ListConstIterator<Tuple2<adjEntry,adjEntry> > it = crossedEdges.begin();
281
282 // iterate over all adjacency entries in crossedEdges except for first
283 // and last
284 adjSrc = (*it).x1();
285 for(++it; it.valid() && it.succ().valid(); ++it)
286 {
287 adjEntry adj = (*it).x1();
288 adjEntry adj2 = (*it).x2();
289
290 if(adj2 != nullptr) {
291 OGDF_ASSERT(adj->theNode() == adj2->theNode());
292 OGDF_ASSERT(E.rightFace(adjSrc) == E.rightFace(adj->twin()));
293 node w = E.splitNode(adj,adj2);
294 edge eNew = adj->cyclicPred()->theEdge();
295
296 m_vIterator [w] = m_vCopy[m_vOrig[adj->theNode()]].pushBack(w);
297 m_splittable[w] = true;
298 m_vOrig [w] = m_vOrig[adj->theNode()];
299
300 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
301 (*itNS).m_nsIterator = itNS;
302 m_eIterator[eNew] = (*itNS).m_path.pushBack(eNew);
303 m_eNodeSplit[eNew] = &(*itNS);
304
305 adj = adj2->cyclicPred();
306 }
307
308 // split edge
309 node u = E.split(adj->theEdge())->source();
310
311 // determine target adjacency entry and source adjacency entry
312 // in the next iteration step
313 adjTgt = u->firstAdj();
314 adjEntry adjSrcNext = adjTgt->succ();
315
316 if (adjTgt != adj->twin())
317 std::swap(adjTgt, adjSrcNext);
318
319 OGDF_ASSERT(adjTgt == adj->twin());
320
321 // insert a new edge into the face
322 edge eNew = E.splitFace(adjSrc,adjTgt);
323
324 if(eOrig) {
325 m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
326 m_eOrig [eNew] = eOrig;
327 } else {
328 m_eIterator [eNew] = ns->m_path.pushBack(eNew);
329 m_eNodeSplit[eNew] = ns;
330 }
331
332 adjSrc = adjSrcNext;
333 }
334
335 // insert last edge
336 edge eNew = E.splitFace(adjSrc,(*it).x1());
337
338 if(eOrig) {
339 m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
340 m_eOrig [eNew] = eOrig;
341 } else {
342 m_eIterator [eNew] = ns->m_path.pushBack(eNew);
343 m_eNodeSplit[eNew] = ns;
344 }
345 }
346
347
removeEdgePathEmbedded(CombinatorialEmbedding & E,edge eOrig,nodeSplit ns,FaceSet<false> & newFaces,NodeSet<false> & mergedNodes,node & oldSrc,node & oldTgt)348 void PlanRepExpansion::removeEdgePathEmbedded(
349 CombinatorialEmbedding &E,
350 edge eOrig,
351 nodeSplit ns,
352 FaceSet<false> &newFaces,
353 NodeSet<false> &mergedNodes,
354 node &oldSrc,
355 node &oldTgt)
356 {
357 OGDF_ASSERT((eOrig != nullptr && ns == nullptr) || (eOrig == nullptr && ns != nullptr));
358
359 const List<edge> &path = (eOrig) ? m_eCopy[eOrig] : ns->m_path;
360 ListConstIterator<edge> it = path.begin();
361
362 oldSrc = path.front()->source();
363 oldTgt = path.back()->target();
364
365 newFaces.insert(E.joinFaces(*it));
366
367 for(++it; it.valid(); ++it)
368 {
369 edge e = *it;
370 node u = e->source();
371
372 newFaces.remove(E.rightFace(e->adjSource()));
373 newFaces.remove(E.rightFace(e->adjTarget()));
374
375 newFaces.insert(E.joinFaces(e));
376
377 edge eIn = u->firstAdj()->theEdge();
378 edge eOut = u->lastAdj()->theEdge();
379 if (eIn->target() != u)
380 std::swap(eIn, eOut);
381
382 E.unsplit(eIn,eOut);
383
384 u = eIn->source();
385 node v = eIn->target();
386
387 node vOrig = m_vOrig[v];
388 if(vOrig != nullptr && m_vOrig[u] == vOrig) {
389 m_vCopy[vOrig].del(m_vIterator[v]);
390 ListIterator<NodeSplit> itNS = m_eNodeSplit[eIn]->m_nsIterator;
391 m_nodeSplits.del(itNS);
392
393 E.contract(eIn);
394
395 if(mergedNodes.isMember(v))
396 mergedNodes.remove(v);
397 mergedNodes.insert(u);
398
399 if(oldSrc == v) oldSrc = u;
400 if(oldTgt == v) oldTgt = u;
401 }
402 }
403
404 if(eOrig)
405 m_eCopy[eOrig].clear();
406 else
407 ns->m_path.clear();
408 }
409
410
removeEdgePath(edge eOrig,nodeSplit ns,node & oldSrc,node & oldTgt)411 void PlanRepExpansion::removeEdgePath(
412 edge eOrig,
413 nodeSplit ns,
414 node &oldSrc,
415 node &oldTgt)
416 {
417 OGDF_ASSERT((eOrig != nullptr && ns == nullptr) || (eOrig == nullptr && ns != nullptr));
418
419 const List<edge> &path = (eOrig) ? m_eCopy[eOrig] : ns->m_path;
420 ListConstIterator<edge> it = path.begin();
421
422 oldSrc = path.front()->source();
423 oldTgt = path.back()->target();
424
425 delEdge(*it);
426
427 for(++it; it.valid(); ++it)
428 {
429 edge e = *it;
430 node u = e->source();
431
432 delEdge(e);
433
434 edge eIn = u->firstAdj()->theEdge();
435 edge eOut = u->lastAdj()->theEdge();
436 if (eIn->target() != u)
437 std::swap(eIn, eOut);
438
439 unsplit(eIn,eOut);
440
441 u = eIn->source();
442 node v = eIn->target();
443
444 node vOrig = m_vOrig[v];
445 if(vOrig != nullptr && m_vOrig[u] == vOrig) {
446 m_vCopy[vOrig].del(m_vIterator[v]);
447 ListIterator<NodeSplit> itNS = m_eNodeSplit[eIn]->m_nsIterator;
448 m_nodeSplits.del(itNS);
449
450 contract(eIn);
451
452 if(oldSrc == v) oldSrc = u;
453 if(oldTgt == v) oldTgt = u;
454 }
455 }
456
457 if(eOrig)
458 m_eCopy[eOrig].clear();
459 else
460 ns->m_path.clear();
461 }
462
463
contractSplit(nodeSplit ns,CombinatorialEmbedding & E)464 void PlanRepExpansion::contractSplit(nodeSplit ns, CombinatorialEmbedding &E)
465 {
466 OGDF_ASSERT(ns->m_path.size() == 1);
467
468 edge e = ns->m_path.front();
469 node v = e->target();
470 node vOrig = m_vOrig[v];
471
472 m_vCopy[vOrig].del(m_vIterator[v]);
473 ListIterator<NodeSplit> itNS = ns->m_nsIterator;
474 m_nodeSplits.del(itNS);
475
476 E.contract(e);
477 }
478
479
contractSplit(nodeSplit ns)480 void PlanRepExpansion::contractSplit(nodeSplit ns)
481 {
482 OGDF_ASSERT(ns->m_path.size() == 1);
483
484 edge e = ns->m_path.front();
485 node v = e->target();
486 node vOrig = m_vOrig[v];
487
488 m_vCopy[vOrig].del(m_vIterator[v]);
489 ListIterator<NodeSplit> itNS = ns->m_nsIterator;
490 m_nodeSplits.del(itNS);
491
492 contract(e);
493 }
494
495
computeNumberOfCrossings() const496 int PlanRepExpansion::computeNumberOfCrossings() const
497 {
498 int cr = 0;
499
500 for(node v : nodes)
501 if(m_vOrig[v] == nullptr)
502 ++cr;
503
504 return cr;
505 }
506
507
split(edge e)508 edge PlanRepExpansion::split(edge e)
509 {
510 edge eNew = Graph::split(e);
511 edge eOrig = m_eOrig[e];
512 NodeSplit *ns = m_eNodeSplit[e];
513
514 if ((m_eOrig[eNew] = eOrig) != nullptr) {
515 m_eIterator[eNew] = m_eCopy[eOrig].insert(eNew,m_eIterator[e],Direction::after);
516
517 } else if ((m_eNodeSplit[eNew] = ns) != nullptr) {
518 m_eIterator[eNew] = ns->m_path.insert(eNew,m_eIterator[e],Direction::after);
519 }
520
521 return eNew;
522 }
523
524
unsplit(edge eIn,edge eOut)525 void PlanRepExpansion::unsplit(edge eIn, edge eOut)
526 {
527 edge eOrig = m_eOrig[eOut];
528 NodeSplit *ns = m_eNodeSplit[eOut];
529
530 // update chain of eOrig if eOrig exists
531 if (eOrig != nullptr) {
532 m_eCopy[eOrig].del(m_eIterator[eOut]);
533
534 } else if (ns != nullptr) {
535 ns->m_path.del(m_eIterator[eOut]);
536 }
537
538 Graph::unsplit(eIn,eOut);
539 }
540
541
unsplitExpandNode(node u,edge eContract,edge eExpand,CombinatorialEmbedding & E)542 edge PlanRepExpansion::unsplitExpandNode(
543 node u,
544 edge eContract,
545 edge eExpand,
546 CombinatorialEmbedding &E)
547 {
548 NodeSplit *ns = m_eNodeSplit[eContract];
549 List<edge> &path = ns->m_path;
550
551 NodeSplit *nsExp = m_eNodeSplit[eExpand];
552 edge eOrigExp = m_eOrig[eExpand];
553 List<edge> &pathExp = (nsExp != nullptr) ? nsExp->m_path : m_eCopy[eOrigExp];
554
555 if((eExpand->target() == u && eContract->source() != u) ||
556 (eExpand->source() == u && eContract->target() != u))
557 {
558 // reverse path of eContract
559 ListConstIterator<edge> it;
560 for(it = path.begin(); it.valid(); ++it) {
561 E.reverseEdge(*it);
562 }
563 path.reverse();
564 }
565
566 // remove u from list of copy nodes of its original
567 m_vCopy[m_vOrig[u]].del(m_vIterator[u]);
568
569 // unsplit u and enlarge edge path of eOrigExp
570 edge eRet;
571 if(eExpand->target() == u) {
572 eRet = eExpand;
573 E.unsplit(eExpand,eContract);
574
575 ListConstIterator<edge> it;
576 for(it = path.begin(); it.valid(); ++it) {
577 m_eNodeSplit[*it] = nsExp;
578 m_eOrig [*it] = eOrigExp;
579 }
580
581 pathExp.conc(path);
582
583 } else {
584 eRet = eContract;
585 E.unsplit(eContract,eExpand);
586
587 ListConstIterator<edge> it;
588 for(it = path.begin(); it.valid(); ++it) {
589 m_eNodeSplit[*it] = nsExp;
590 m_eOrig [*it] = eOrigExp;
591 }
592
593 pathExp.concFront(path);
594 }
595
596 m_nodeSplits.del(ns->m_nsIterator);
597 return eRet;
598 }
599
600
unsplitExpandNode(node u,edge eContract,edge eExpand)601 edge PlanRepExpansion::unsplitExpandNode(
602 node u,
603 edge eContract,
604 edge eExpand)
605 {
606 NodeSplit *ns = m_eNodeSplit[eContract];
607 List<edge> &path = ns->m_path;
608
609 NodeSplit *nsExp = m_eNodeSplit[eExpand];
610 edge eOrigExp = m_eOrig[eExpand];
611 List<edge> &pathExp = (nsExp != nullptr) ? nsExp->m_path : m_eCopy[eOrigExp];
612
613 if((eExpand->target() == u && eContract->source() != u) ||
614 (eExpand->source() == u && eContract->target() != u))
615 {
616 // reverse path of eContract
617 ListConstIterator<edge> it;
618 for(it = path.begin(); it.valid(); ++it) {
619 reverseEdge(*it);
620 }
621 path.reverse();
622 }
623
624 // remove u from list of copy nodes of its original
625 m_vCopy[m_vOrig[u]].del(m_vIterator[u]);
626
627 // unsplit u and enlarge edge path of eOrigExp
628 edge eRet;
629 if(eExpand->target() == u) {
630 eRet = eExpand;
631 unsplit(eExpand,eContract);
632
633 ListConstIterator<edge> it;
634 for(it = path.begin(); it.valid(); ++it) {
635 m_eNodeSplit[*it] = nsExp;
636 m_eOrig [*it] = eOrigExp;
637 }
638
639 pathExp.conc(path);
640
641 } else {
642 eRet = eContract;
643 unsplit(eContract,eExpand);
644
645 ListConstIterator<edge> it;
646 for(it = path.begin(); it.valid(); ++it) {
647 m_eNodeSplit[*it] = nsExp;
648 m_eOrig [*it] = eOrigExp;
649 }
650
651 pathExp.concFront(path);
652 }
653
654 m_nodeSplits.del(ns->m_nsIterator);
655 return eRet;
656 }
657
658
enlargeSplit(node v,edge e)659 edge PlanRepExpansion::enlargeSplit(
660 node v,
661 edge e)
662 {
663 node vOrig = m_vOrig[v];
664 edge eOrig = m_eOrig[e];
665
666 edge eNew = split(e);
667 node u = e->target();
668
669 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
670 nodeSplit ns = &(*itNS);
671 ns->m_nsIterator = itNS;
672
673 m_vOrig [u] = vOrig;
674 m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
675 m_splittable[u] = true;
676
677 List<edge> &path = m_eCopy[eOrig];
678 if(v == path.front()->source()) {
679 ListIterator<edge> it, itNext;
680 for(it = path.begin(); *it != eNew; it = itNext) {
681 itNext = it.succ();
682
683 path.moveToBack(it, ns->m_path);
684 m_eOrig[*it] = nullptr;
685 m_eNodeSplit[*it] = ns;
686 }
687
688 } else {
689 ListIterator<edge> it, itNext;
690 for(it = m_eIterator[eNew]; it.valid(); it = itNext) {
691 itNext = it.succ();
692
693 path.moveToBack(it, ns->m_path);
694 m_eOrig[*it] = nullptr;
695 m_eNodeSplit[*it] = ns;
696 }
697 }
698
699 return eNew;
700 }
701
702
enlargeSplit(node v,edge e,CombinatorialEmbedding & E)703 edge PlanRepExpansion::enlargeSplit(
704 node v,
705 edge e,
706 CombinatorialEmbedding &E)
707 {
708 node vOrig = m_vOrig[v];
709 edge eOrig = m_eOrig[e];
710
711 edge eNew = E.split(e);
712 node u = e->target();
713
714 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
715 nodeSplit ns = &(*itNS);
716 ns->m_nsIterator = itNS;
717
718 m_vOrig [u] = vOrig;
719 m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
720 m_splittable[u] = true;
721
722 List<edge> &path = m_eCopy[eOrig];
723 if(v == path.front()->source()) {
724 ListIterator<edge> it, itNext;
725 for(it = path.begin(); *it != eNew; it = itNext) {
726 itNext = it.succ();
727
728 path.moveToBack(it, ns->m_path);
729 m_eOrig[*it] = nullptr;
730 m_eNodeSplit[*it] = ns;
731 }
732
733 } else {
734 ListIterator<edge> it, itNext;
735 for(it = m_eIterator[eNew]; it.valid(); it = itNext) {
736 itNext = it.succ();
737
738 path.moveToBack(it, ns->m_path);
739 m_eOrig[*it] = nullptr;
740 m_eNodeSplit[*it] = ns;
741 }
742 }
743
744 return eNew;
745 }
746
747
splitNodeSplit(edge e)748 edge PlanRepExpansion::splitNodeSplit(edge e)
749 {
750 nodeSplit ns = m_eNodeSplit[e];
751 node vOrig = m_vOrig[ns->source()];
752
753 edge eNew = split(e);
754 node u = e->target();
755
756 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
757 nodeSplit nsNew = &(*itNS);
758 nsNew->m_nsIterator = itNS;
759
760 m_vOrig [u] = vOrig;
761 m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
762 m_splittable[u] = true;
763
764 List<edge> &path = ns->m_path;
765 path.split(m_eIterator[eNew], path, nsNew->m_path);
766
767 ListIterator<edge> it;
768 for(it = nsNew->m_path.begin(); it.valid(); ++it) {
769 m_eNodeSplit[*it] = nsNew;
770 }
771
772 return eNew;
773 }
774
775
splitNodeSplit(edge e,CombinatorialEmbedding & E)776 edge PlanRepExpansion::splitNodeSplit(
777 edge e,
778 CombinatorialEmbedding &E)
779 {
780 nodeSplit ns = m_eNodeSplit[e];
781 node vOrig = m_vOrig[ns->source()];
782
783 edge eNew = E.split(e);
784 node u = e->target();
785
786 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
787 nodeSplit nsNew = &(*itNS);
788 nsNew->m_nsIterator = itNS;
789
790 m_vOrig [u] = vOrig;
791 m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
792 m_splittable[u] = true;
793
794 List<edge> &path = ns->m_path;
795 path.split(m_eIterator[eNew], path, nsNew->m_path);
796
797 ListIterator<edge> it;
798 for(it = nsNew->m_path.begin(); it.valid(); ++it) {
799 m_eNodeSplit[*it] = nsNew;
800 }
801
802 return eNew;
803 }
804
805
removeSelfLoop(edge e,CombinatorialEmbedding & E)806 void PlanRepExpansion::removeSelfLoop(
807 edge e,
808 CombinatorialEmbedding &E)
809 {
810 node u = e->source();
811 nodeSplit ns = m_eNodeSplit[e];
812 edge eOrig = m_eOrig[e];
813
814 List<edge> &path = (eOrig != nullptr) ? m_eCopy[eOrig] : ns->m_path;
815 path.del(m_eIterator[e]);
816
817 E.joinFaces(e);
818
819 edge eIn = u->firstAdj()->theEdge();
820 edge eOut = u->lastAdj ()->theEdge();
821 if(eIn->target() != u) std::swap(eIn, eOut);
822
823 OGDF_ASSERT(ns == m_eNodeSplit[eOut]);
824 OGDF_ASSERT(eOrig == m_eOrig[eOut]);
825
826 E.unsplit(eIn,eOut);
827 }
828
829
removeSelfLoop(edge e)830 void PlanRepExpansion::removeSelfLoop(edge e)
831 {
832 node u = e->source();
833 nodeSplit ns = m_eNodeSplit[e];
834 edge eOrig = m_eOrig[e];
835
836 List<edge> &path = (eOrig != nullptr) ? m_eCopy[eOrig] : ns->m_path;
837 path.del(m_eIterator[e]);
838
839 delEdge(e);
840
841 edge eIn = u->firstAdj()->theEdge();
842 edge eOut = u->lastAdj ()->theEdge();
843 if(eIn->target() != u) std::swap(eIn, eOut);
844
845 OGDF_ASSERT(ns == m_eNodeSplit[eOut]);
846 OGDF_ASSERT(eOrig == m_eOrig[eOut]);
847
848 unsplit(eIn,eOut);
849 }
850
851
852 #ifdef OGDF_DEBUG
consistencyCheck() const853 void PlanRepExpansion::consistencyCheck() const
854 {
855 Graph::consistencyCheck();
856
857 OGDF_ASSERT(isLoopFree(*this));
858
859 for(edge eOrig : m_pGraph->edges) {
860 const List<edge> &path = m_eCopy[eOrig];
861
862 for(ListConstIterator<edge> it = path.begin(); it.valid(); ++it) {
863 edge e = *it;
864
865 if(it != path.begin()) {
866 OGDF_ASSERT(e->source()->degree() == 4);
867 OGDF_ASSERT(e->source() == (*it.pred())->target());
868 }
869 }
870 }
871
872 for(node vOrig : m_pGraph->nodes) {
873 const List<node> &nodeList = m_vCopy[vOrig];
874
875 if (nodeList.size() == 1) {
876 OGDF_ASSERT(m_splittable[nodeList.front()] != m_splittableOrig[vOrig]);
877 }
878
879 if(nodeList.size() > 1) {
880 OGDF_ASSERT(m_splittableOrig[vOrig]);
881
882 for (node v : nodeList) {
883 OGDF_ASSERT(v->degree() >= 2);
884 }
885 }
886 }
887
888 EdgeArray<const NodeSplit*> nso(*this, nullptr);
889
890 for(const NodeSplit &ns : m_nodeSplits) {
891 if(ns.m_path.size() != 0) {
892 node v = ns.source();
893 node w = ns.target();
894 node vOrig = m_vOrig[v];
895
896 OGDF_ASSERT(vOrig != nullptr);
897 OGDF_ASSERT(vOrig == m_vOrig[w]);
898 OGDF_ASSERT(m_splittable[v]);
899 OGDF_ASSERT(m_splittable[w]);
900
901 const List<edge> &path = ns.m_path;
902
903 for(ListConstIterator<edge> itE = path.begin(); itE.valid(); ++itE) {
904 edge e = *itE;
905 nso[e] = &ns;
906
907 if (itE != path.begin()) {
908 OGDF_ASSERT(e->source()->degree() == 4);
909 OGDF_ASSERT(e->source() == (*itE.pred())->target());
910 }
911 }
912 }
913 }
914
915 for(edge e : edges) {
916 OGDF_ASSERT(nso[e] == m_eNodeSplit[e]);
917 }
918 }
919 #endif
920
921
setOrigs(edge e,edge & eOrig,nodeSplit & ns)922 List<edge> &PlanRepExpansion::setOrigs(edge e, edge &eOrig, nodeSplit &ns)
923 {
924 eOrig = m_eOrig[e];
925 ns = m_eNodeSplit[e];
926 return (eOrig != nullptr) ? m_eCopy[eOrig] : ns->m_path;
927 }
928
929
convertDummy(node u,node vOrig,PlanRepExpansion::nodeSplit ns_0)930 PlanRepExpansion::nodeSplit PlanRepExpansion::convertDummy(
931 node u,
932 node vOrig,
933 PlanRepExpansion::nodeSplit ns_0)
934 {
935 OGDF_ASSERT(u->indeg() == 2);
936 OGDF_ASSERT(u->outdeg() == 2);
937 OGDF_ASSERT(m_vOrig[u] == nullptr);
938
939 m_vOrig [u] = vOrig;
940 m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
941 m_splittable[u] = true;
942
943 edge ec[2], eOrig[2];
944 PlanRepExpansion::nodeSplit nsplit[2];
945 int i = 0;
946 for(adjEntry adj : u->adjEntries) {
947 edge e = adj->theEdge();
948 if(e->source() == u) {
949 ec [i] = e;
950 eOrig [i] = m_eOrig[e];
951 nsplit[i] = m_eNodeSplit[e];
952 ++i;
953 }
954 }
955
956 List<edge> &path_0 = (eOrig[0] != nullptr) ? m_eCopy[eOrig[0]] : nsplit[0]->m_path;
957 if(m_vOrig[path_0.front()->source()] == vOrig)
958 path_0.split(m_eIterator[ec[0]], ns_0->m_path, path_0);
959 else
960 path_0.split(m_eIterator[ec[0]], path_0, ns_0->m_path);
961
962 ListConstIterator<edge> itE;
963 for(itE = ns_0->m_path.begin(); itE.valid(); ++itE) {
964 m_eNodeSplit[*itE] = ns_0;
965 m_eOrig [*itE] = nullptr;
966 }
967
968 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
969 nodeSplit ns_1 = &(*itNS);
970 ns_1->m_nsIterator = itNS;
971
972 List<edge> &path_1 = (eOrig[1] != nullptr) ? m_eCopy[eOrig[1]] : nsplit[1]->m_path;
973 if(m_vOrig[path_1.front()->source()] == vOrig)
974 path_1.split(m_eIterator[ec[1]], ns_1->m_path, path_1);
975 else
976 path_1.split(m_eIterator[ec[1]], path_1, ns_1->m_path);
977
978 for(itE = ns_1->m_path.begin(); itE.valid(); ++itE) {
979 m_eNodeSplit[*itE] = ns_1;
980 m_eOrig [*itE] = nullptr;
981 }
982
983 return ns_1;
984 }
985
986
separateDummy(adjEntry adj_1,adjEntry adj_2,node vStraight,bool isSrc)987 edge PlanRepExpansion::separateDummy(
988 adjEntry adj_1, adjEntry adj_2, node vStraight, bool isSrc)
989 {
990 node u = adj_1->theNode();
991 OGDF_ASSERT(m_vOrig[u] == nullptr);
992
993 node vOrig = m_vOrig[vStraight];
994 node v = newNode();
995
996 m_vOrig [v] = vOrig;
997 m_vIterator [v] = m_vCopy[vOrig].pushBack(v);
998 m_splittable[v] = true;
999
1000 if(adj_1->theEdge()->target() == u)
1001 moveTarget(adj_1->theEdge(),v);
1002 else
1003 moveSource(adj_1->theEdge(),v);
1004
1005 if(adj_2->theEdge()->target() == u)
1006 moveTarget(adj_2->theEdge(),v);
1007 else
1008 moveSource(adj_2->theEdge(),v);
1009
1010 edge eNew = (isSrc) ? newEdge(v,u) : newEdge(u,v);
1011
1012 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
1013 nodeSplit nsNew = &(*itNS);
1014 nsNew->m_nsIterator = itNS;
1015
1016 edge eOrig = m_eOrig[adj_1->theEdge()];
1017 NodeSplit *ns = m_eNodeSplit[adj_1->theEdge()];
1018 List<edge> &path = (eOrig != nullptr) ? m_eCopy[eOrig] : ns->m_path;
1019
1020 if(vStraight == path.front()->source()) {
1021 ListIterator<edge> it, itNext;
1022 for(it = path.begin(); (*it)->source() != v; it = itNext) {
1023 itNext = it.succ();
1024 path.moveToBack(it, nsNew->m_path);
1025 m_eOrig [*it] = nullptr;
1026 m_eNodeSplit[*it] = nsNew;
1027 }
1028
1029 } else {
1030 ListReverseIterator<edge> it, itPrev;
1031 for(it = path.rbegin(); (*it)->target() != v; it = itPrev) {
1032 itPrev = it.succ();
1033 path.moveToFront(it, nsNew->m_path);
1034 m_eOrig [*it] = nullptr;
1035 m_eNodeSplit[*it] = nsNew;
1036 }
1037 }
1038
1039 return eNew;
1040
1041 #if 0
1042 edge eOrig = m_eOrig[adjStraight->theEdge()];
1043 NodeSplit *ns = m_eNodeSplit[adjStraight->theEdge()];
1044
1045 Array<adjEntry> adjA(2), adjB(2);
1046 int i = 0, j = 0;
1047
1048 for(adjEntry adj : u->adjEntries) {
1049 edge e = adj->theEdge();
1050 if(m_eOrig[e] == eOrig && m_eNodeSplit[e] == ns)
1051 adjA[i++] = adj;
1052 else
1053 adjB[j++] = adj;
1054 }
1055
1056 OGDF_ASSERT(i == 2);
1057 OGDF_ASSERT(j == 2);
1058
1059 // resolve split on adjB
1060 edge eB = adjB[0]->theEdge();
1061 node vB = adjB[1]->twinNode();
1062
1063 edge eOrigB;
1064 NodeSplit *nsB;
1065 List<edge> &pathB = (m_eOrig[eB] != 0) ? m_eCopy[m_eOrig[eB]] : m_eNodeSplit[eB]->m_path;
1066
1067 if(eB->target() == u)
1068 moveTarget(eB,vB);
1069 else
1070 moveSource(eB,vB);
1071
1072 edge eB2 = adjB[1]->theEdge();
1073 pathB.del(m_eIterator[eB2]);
1074 delEdge(eB2);
1075
1076 // split path at u
1077 node vOrig = m_vOrig[vStraight];
1078
1079 m_vOrig [u] = vOrig;
1080 m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
1081 m_splittable[u] = true;
1082
1083 ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
1084 nodeSplit nsNew = &(*itNS);
1085 nsNew->m_nsIterator = itNS;
1086
1087 List<edge> &pathA = (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
1088 if(vStraight == pathA.front()->source()) {
1089 ListIterator<edge> it, itNext;
1090 for(it = pathA.begin(); (*it)->source() != u; it = itNext) {
1091 itNext = it.succ();
1092 pathA.moveToBack(it, nsNew->m_path);
1093 m_eOrig [*it] = 0;
1094 m_eNodeSplit[*it] = nsNew;
1095 }
1096
1097 } else {
1098 ListReverseIterator<edge> it, itPrev;
1099 for(it = pathA.rbegin(); (*it)->target() != u; it = itPrev) {
1100 itPrev = it.succ();
1101 pathA.moveToFront(it, nsNew->m_path);
1102 m_eOrig [*it] = 0;
1103 m_eNodeSplit[*it] = nsNew;
1104 }
1105 }
1106 #endif
1107 }
1108
1109
numberOfSplittedNodes() const1110 int PlanRepExpansion::numberOfSplittedNodes() const
1111 {
1112 int num = 0;
1113
1114 for(node vOrig : m_pGraph->nodes)
1115 if(m_vCopy[vOrig].size() >= 2)
1116 ++num;
1117
1118 return num;
1119 }
1120
1121
isPseudoCrossing(node v) const1122 bool PlanRepExpansion::isPseudoCrossing(node v) const
1123 {
1124 if(m_vOrig[v] != nullptr)
1125 return false;
1126
1127 adjEntry adj_1 = v->firstAdj();
1128 adjEntry adj_2 = adj_1->succ();
1129 adjEntry adj_3 = adj_2->succ();
1130
1131 edge eOrig = m_eOrig[adj_2->theEdge()];
1132 nodeSplit ns = m_eNodeSplit[adj_2->theEdge()];
1133
1134 if(m_eNodeSplit[adj_1->theEdge()] == ns && m_eOrig[adj_1->theEdge()] == eOrig)
1135 return true;
1136
1137 if(m_eNodeSplit[adj_3->theEdge()] == ns && m_eOrig[adj_3->theEdge()] == eOrig)
1138 return true;
1139
1140 return false;
1141 }
1142
1143
resolvePseudoCrossing(node v)1144 void PlanRepExpansion::resolvePseudoCrossing(node v)
1145 {
1146 OGDF_ASSERT(isPseudoCrossing(v));
1147
1148 edge eIn[2];
1149 int i = 0;
1150 for(adjEntry adj : v->adjEntries) {
1151 edge e = adj->theEdge();
1152 if(e->target() == v)
1153 eIn[i++] = e;
1154 }
1155 OGDF_ASSERT(i == 2);
1156
1157 for(i = 0; i < 2; ++i) {
1158 edge e = eIn[i];
1159
1160 ListIterator<edge> it = m_eIterator[e];
1161 List<edge> &path = (m_eOrig[e] != nullptr) ? m_eCopy[m_eOrig[e]] : m_eNodeSplit[e]->m_path;
1162
1163 edge eNext = *(it.succ());
1164 moveSource(eNext, e->source());
1165 path.del(it);
1166 delEdge(e);
1167 }
1168 }
1169
1170 }
1171