?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Prefer to use VS2013 for compiling and testing on AppVeyor
[TortoiseGit.git] / ext / OGDF / src / planarity / MMVariableEmbeddingInserter.cpp
blobb7320cfc36867cbd271f3719cde009a4ce854ba0
1 /*
2 * $Revision: 2616 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-16 15:34:43 +0200 (Mo, 16. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief implementation of MMVariableEmbeddingInserter class
11 *
12 * \author Carsten Gutwenger
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
42
43
44 #include <ogdf/planarity/MMVariableEmbeddingInserter.h>
45 #include <ogdf/basic/NodeSet.h>
46 #include <ogdf/basic/simple_graph_alg.h>
47 #include <ogdf/decomposition/StaticPlanarSPQRTree.h>
48 #include <ogdf/basic/extended_graph_alg.h>
49 #include <ogdf/basic/String.h>
50 #include <ogdf/basic/GraphAttributes.h>
51
52
53 //#define MMC_OUTPUT
54
55 namespace ogdf {
56
57 static int globalCounter = 0;
58
59 //---------------------------------------------------------
60 // constructor
61 // sets default values for options
62 //
63 MMVariableEmbeddingInserter::MMVariableEmbeddingInserter()
64 {
65 m_rrOption = rrNone;
66 m_percentMostCrossed = 25;
67 }
68
69
70 //---------------------------------------------------------
71 // VEICrossingsBucket
72 // bucket function for sorting edges by decreasing number
73 // of crossings
74 class VEICrossingsBucket : public BucketFunc<edge>
75 {
76 const PlanRepExpansion *m_pPG;
77
78 public:
79 VEICrossingsBucket(const PlanRepExpansion *pPG) :
80 m_pPG(pPG) { }
81
82 int getBucket(const edge &e) {
83 return -m_pPG->chain(e).size();
84 }
85 };
86
87 void outputPG(const PlanRepExpansion &PG, int i)
88 {
89 GraphAttributes AG(PG, GraphAttributes::nodeLabel);
90 String label;
91
92 node v;
93 forall_nodes(v,PG) {
94 label.sprintf("%d",v->index());
95 AG.labelNode(v) = label;
96 }
97
98 String str;
99 str.sprintf("PG_%d.gml", i);
100 AG.writeGML(str);
101 }
102
103 void MMVariableEmbeddingInserter::writeEip(const List<Crossing> &eip)
104 {
105 ListConstIterator<Crossing> it;
106 for(it = eip.begin(); it.valid(); ++it) {
107 const MMVariableEmbeddingInserter::Crossing &cr = *it;
108
109 if(cr.m_adj == 0) {
110 cout << "nil {";
111 cout << cr.m_partitionLeft;
112 cout << "} {";
113 cout << cr.m_partitionRight;
114 cout << "}";
115
116 } else
117 cout << cr.m_adj;
118 cout << endl;
119 }
120 }
121
122 //---------------------------------------------------------
123 // actual call (called by all variations of call)
124 // crossing of generalizations is forbidden if forbidCrossingGens = true
125 // edge costs are obeyed if costOrig != 0
126 //
127 Module::ReturnType MMVariableEmbeddingInserter::doCall(
128 PlanRepExpansion &PG,
129 const List<edge> &origEdges,
130 const EdgeArray<bool> *forbiddenEdgeOrig)
131 {
132 ReturnType retValue = retFeasible;
133
134 if (origEdges.size() == 0)
135 return retOptimal; // nothing to do
136
137 m_pPG = &PG;
138 m_forbiddenEdgeOrig = forbiddenEdgeOrig;
139
140 SListPure<edge> rrEdges;
141 if(removeReinsert() != rrNone) {
142 edge e;
143 forall_edges(e,PG)
144 rrEdges.pushBack(PG.originalEdge(e));
145
146 ListConstIterator<edge> itE;
147 for(itE = origEdges.begin(); itE.valid(); ++itE)
148 rrEdges.pushBack(*itE);
149 }
150
151 m_pSources = new NodeSet(PG);
152 m_pTargets = new NodeSet(PG);
153
154 #ifdef MMC_OUTPUT
155 outputPG(PG,0);
156 int ii = 0;
157 #endif
158
159 // insertion of edges
160 ListConstIterator<edge> it;
161 for(it = origEdges.begin(); it.valid(); ++it)
162 {
163 edge eOrig = *it;
164 node srcOrig = eOrig->source();
165 node tgtOrig = eOrig->target();
166
167 #ifdef MMC_OUTPUT
168 cout << "insert " << srcOrig << " -> " << tgtOrig << endl;
169 #endif
170
171 node oldSrc = (PG.splittableOrig(srcOrig) && PG.expansion(srcOrig).size() == 1) ?
172 PG.expansion(srcOrig).front() : 0;
173 node oldTgt = (PG.splittableOrig(tgtOrig) && PG.expansion(tgtOrig).size() == 1) ?
174 PG.expansion(tgtOrig).front() : 0;
175
176 anchorNodes(eOrig->source(), *m_pSources);
177 anchorNodes(eOrig->target(), *m_pTargets);
178
179 node vDummy = commonDummy(*m_pSources, *m_pTargets);
180 node src, tgt;
181 edge eExtraSrc = 0, eExtraTgt = 0;
182 List<Crossing> eip;
183
184 if(vDummy == 0) {
185 AnchorNodeInfo vStart, vEnd;
186 insert(eip, vStart, vEnd);
187
188 #ifdef MMC_OUTPUT
189 writeEip(eip);
190 #endif
191 preprocessInsertionPath(vStart,vEnd,srcOrig,tgtOrig,src,tgt,eExtraSrc,eExtraTgt);
192
193 #ifdef MMC_OUTPUT
194 cout << "from: " << src << " to: " << tgt << endl;
195 #endif
196
197 } else {
198 insertWithCommonDummy(eOrig, vDummy, src, tgt);
199 #ifdef MMC_OUTPUT
200 cout << "(direct) from: " << src << " to: " << tgt << endl;
201 #endif
202 }
203
204 PG.insertEdgePath(eOrig, 0, src, tgt, eip, eExtraSrc, eExtraTgt);
205
206 #ifdef MMC_OUTPUT
207 ++ii;
208 cout << endl;
209 outputPG(PG,ii);
210 #endif
211
212 m_pSources->clear();
213 m_pTargets->clear();
214
215 if(oldSrc != 0 && PG.expansion(srcOrig).size() > 1)
216 contractSplitIfReq(oldSrc);
217 if(oldTgt != 0 && PG.expansion(tgtOrig).size() > 1)
218 contractSplitIfReq(oldTgt);
219
220 //OGDF_ASSERT(PG.consistencyCheck());
221 //OGDF_ASSERT(isPlanar(PG));
222 }
223
224 if(removeReinsert() != rrNone) {
225 // postprocessing (remove-reinsert heuristc)
226 //SListPure<edge> rrEdges;
227
228 //switch(removeReinsert())
229 //{
230 //case rrAll:
231 //case rrMostCrossed: {
232 // const List<node> &origInCC = PG.nodesInCC();
233 // ListConstIterator<node> itV;
234
235 // for(itV = origInCC.begin(); itV.valid(); ++itV) {
236 // node vG = *itV;
237 // adjEntry adj;
238 // forall_adj(adj,vG) {
239 // if ((adj->index() & 1) == 0) continue;
240 // edge eG = adj->theEdge();
241 // rrEdges.pushBack(eG);
242 // }
243 // }
244 // }
245 // break;
246
247 //case rrInserted: {
248 // ListConstIterator<edge> it;
249 // for(it = origEdges.begin(); it.valid(); ++it)
250 // rrEdges.pushBack(*it);
251 // }
252 // break;
253 //}
254
255 // marks the end of the interval of rrEdges over which we iterate
256 // initially set to invalid iterator which means all edges
257 //SListConstIterator<edge> itStop;
258
259 bool improved;
260 do {
261 improved = false;
262
263 //if(removeReinsert() == rrMostCrossed)
264 //{
265 // VEICrossingsBucket bucket(&PG);
266 // rrEdges.bucketSort(bucket);
267
268 // const int num = int(0.01 * percentMostCrossed() * G.numberOfEdges());
269 // itStop = rrEdges.get(num);
270 //}
271
272 SListConstIterator<edge> it;
273 for(it = rrEdges.begin(); it.valid(); ++it)
274 {
275 globalCounter++;
276 edge eOrig = *it;
277 node srcOrig = eOrig->source();
278 node tgtOrig = eOrig->target();
279
280 int oldCrossings = PG.chain(eOrig).size() - 1;
281 if (oldCrossings == 0) continue; // cannot improve
282
283 node oldSrc = 0, oldTgt = 0;
284 PG.removeEdgePath(eOrig,0,oldSrc,oldTgt);
285 //OGDF_ASSERT(PG.consistencyCheck());
286
287 // try to find a better insertion path
288 anchorNodes(eOrig->source(), *m_pSources);
289 anchorNodes(eOrig->target(), *m_pTargets);
290
291 node vDummy = commonDummy(*m_pSources, *m_pTargets);
292 node src, tgt;
293 edge eExtraSrc = 0, eExtraTgt = 0;
294
295 List<Crossing> eip;
296 if(vDummy == 0) {
297 AnchorNodeInfo vStart, vEnd;
298 insert(eip, vStart, vEnd);
299 preprocessInsertionPath(vStart,vEnd,srcOrig,tgtOrig,src,tgt,eExtraSrc,eExtraTgt);
300
301 } else {
302 insertWithCommonDummy(eOrig, vDummy, src, tgt);
303 }
304
305 int newCrossings = eip.size();
306
307 OGDF_ASSERT(isPlanar(PG));
308 PG.insertEdgePath(eOrig, 0, src, tgt, eip, eExtraSrc, eExtraTgt);
309 OGDF_ASSERT(PG.consistencyCheck());
310 OGDF_ASSERT(isPlanar(PG));
311
312 m_pSources->clear();
313 m_pTargets->clear();
314
315 if(PG.splittable(oldSrc))
316 contractSplitIfReq(oldSrc);
317 if(PG.splittable(oldTgt))
318 contractSplitIfReq(oldTgt);
319
320 OGDF_ASSERT(PG.consistencyCheck());
321 OGDF_ASSERT(isPlanar(PG));
322
323 //int newPathLength = PG.chain(eOrig).size() - 1;
324 int saved = oldCrossings - newCrossings;
325 OGDF_ASSERT(saved >= 0);
326
327 if(saved > 0)
328 improved = true;
329 }
330
331 if(removeReinsert() == rrAll)
332 {
333 // process all node splits
334 int nsCount = PG.nodeSplits().size();
335 ListIterator<PlanRepExpansion::NodeSplit> itS, itSNext;
336 for(itS = PG.nodeSplits().begin(); itS.valid() && nsCount > 0; itS = itSNext, --nsCount)
337 {
338 globalCounter++;
339 PlanRepExpansion::NodeSplit *ns = &(*itS);
340
341 int oldCrossings = ns->m_path.size() - 1;
342 if (oldCrossings == 0) {
343 itSNext = itS.succ();
344 PG.contractSplit(ns);
345 continue; // cannot improve
346 }
347
348 node vOrig = PG.original(ns->source());
349
350 node oldSrc = 0, oldTgt = 0;
351 PG.removeEdgePath(0,ns,oldSrc,oldTgt);
352 OGDF_ASSERT(PG.consistencyCheck());
353
354 // try to find a better insertion path
355 findSourcesAndTargets(oldSrc,oldTgt,*m_pSources,*m_pTargets);
356
357 node vCommon = commonDummy(*m_pSources, *m_pTargets);
358
359 if(vCommon == 0) {
360 node src, tgt;
361 edge eExtraSrc = 0, eExtraTgt = 0;
362
363 List<Crossing> eip;
364 AnchorNodeInfo vStart, vEnd;
365 insert(eip, vStart, vEnd);
366 preprocessInsertionPath(vStart,vEnd,vOrig,vOrig,src,tgt,eExtraSrc,eExtraTgt);
367 PG.insertEdgePath(0, ns, src, tgt, eip, eExtraSrc, eExtraTgt);
368
369 OGDF_ASSERT(PG.consistencyCheck());
370
371 m_pSources->clear();
372 m_pTargets->clear();
373
374 if(PG.splittable(oldSrc))
375 contractSplitIfReq(oldSrc);
376 if(PG.splittable(oldTgt))
377 contractSplitIfReq(oldTgt);
378
379 OGDF_ASSERT(PG.consistencyCheck());
380 OGDF_ASSERT(isPlanar(PG));
381
382 //int newCrossings = ns->m_path.size() - 1;
383 int newCrossings = eip.size();
384 int saved = oldCrossings - newCrossings;
385 OGDF_ASSERT(saved >= 0);
386
387 if(saved > 0)
388 improved = true;
389
390 itSNext = itS.succ();
391 if(ns->m_path.size() == 1)
392 PG.contractSplit(ns);
393
394 } else {
395 m_pSources->clear();
396 m_pTargets->clear();
397
398 improved = true;
399 itSNext = itS.succ();
400
401 convertDummy(vCommon,vOrig,ns);
402 OGDF_ASSERT(PG.consistencyCheck());
403 OGDF_ASSERT(isPlanar(PG));
404 }
405 }
406 }
407
408 } while(improved);
409 }
410
411 delete m_pSources;
412 delete m_pTargets;
413
414 #ifdef OGDF_DEBUG
415 bool isPlanar =
416 #endif
417 PG.embed();
418 OGDF_ASSERT(isPlanar);
419 OGDF_ASSERT(PG.representsCombEmbedding());
420
421 return retValue;
422 }
423
424
425 void MMVariableEmbeddingInserter::insert(
426 List<Crossing> &eip,
427 AnchorNodeInfo &vStart,
428 AnchorNodeInfo &vEnd)
429 {
430 PlanRepExpansion &PG = *m_pPG;
431 eip.clear();
432
433 // compute biconnected components of PG
434 EdgeArray<int> compnum(PG);
435 int c = biconnectedComponents(PG,compnum);
436
437 m_compV.init(PG);
438 m_nodeB.init(c);
439
440 // edgeB[i] = list of edges in component i
441 m_edgeB.init(c);
442 edge e;
443 forall_edges(e,PG)
444 m_edgeB[compnum[e]].pushBack(e);
445
446 // construct arrays compV and nodeB such that
447 // m_compV[v] = list of components containing v
448 // m_nodeB[i] = list of vertices in component i
449 NodeArray<bool> mark(PG,false);
450
451 int i;
452 for(i = 0; i < c; ++i) {
453 SListConstIterator<edge> itEdge;
454 for(itEdge = m_edgeB[i].begin(); itEdge.valid(); ++itEdge)
455 {
456 edge e = *itEdge;
457
458 if (!mark[e->source()]) {
459 mark[e->source()] = true;
460 m_nodeB[i].pushBack(e->source());
461 }
462 if (!mark[e->target()]) {
463 mark[e->target()] = true;
464 m_nodeB[i].pushBack(e->target());
465 }
466 }
467
468 SListConstIterator<node> itNode;
469 for(itNode = m_nodeB[i].begin(); itNode.valid(); ++itNode)
470 {
471 node v = *itNode;
472 m_compV[v].pushBack(i);
473 mark[v] = false;
474 }
475 }
476
477 mark.init();
478 m_GtoBC.init(PG,0);
479
480 m_conFinished = false;
481 dfsVertex(m_pTargets->nodes().front(), -1, eip, vStart, vEnd);
482
483 // deallocate resources used by insert()
484 m_GtoBC.init();
485 m_edgeB.init();
486 m_nodeB.init();
487 m_compV.init();
488 }
489
490
491 node MMVariableEmbeddingInserter::prepareAnchorNode(
492 const AnchorNodeInfo &anchor,
493 node vOrig,
494 bool isSrc,
495 edge &eExtra)
496 {
497 PlanRepExpansion &PG = *m_pPG;
498
499 adjEntry adj = 0;
500 node vStraight = 0;
501
502 edge eStraight;
503 PlanRepExpansion::NodeSplit *nsStraight;
504 if(anchor.m_adj_2 != 0) {
505 adj = anchor.m_adj_1;
506 //if(PG.originalEdge(adj->theEdge()) == PG.originalEdge(anchor.m_adj_2->theEdge()) &&
507 // PG.nodeSplitOf(adj->theEdge()) == PG.nodeSplitOf(anchor.m_adj_2->theEdge()))
508 //{
509 // node u = adj->theNode();
510 // forall_adj(adj,u) {
511 // List<edge> *pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
512 // vStraight = pathStraight->front()->source();
513 // if(PG.original(vStraight) == vOrig)
514 // break;
515 // vStraight = pathStraight->back()->target();
516 // if(PG.original(vStraight)== vOrig)
517 // break;
518 // }
519 //
520 // PG.removeCrossingReuseDummy(adj, vStraight);
521
522 // return u;
523 //}
524
525 List<edge> *pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
526
527 vStraight = pathStraight->front()->source();
528 if(PG.original(vStraight) != vOrig) {
529 vStraight = pathStraight->back()->target();
530 if(PG.original(vStraight) != vOrig) {
531 adj = anchor.m_adj_2;
532 pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
533 vStraight = pathStraight->front()->source();
534 if(PG.original(vStraight) != vOrig) {
535 vStraight = pathStraight->back()->target();
536 }
537 }
538 }
539
540 if(PG.original(vStraight) != vOrig) {
541 node u = adj->theNode();
542 adjEntry adjA[2];
543 int i = 0;
544 adjEntry adj_x;
545 forall_adj(adj_x,u) {
546 if(adj_x != anchor.m_adj_1 && adj_x != anchor.m_adj_2)
547 adjA[i++] = adj_x;
548 }
549
550 List<edge> *pathStraight = &PG.setOrigs(adjA[0]->theEdge(), eStraight, nsStraight);
551 vStraight = pathStraight->front()->source();
552 if(PG.original(vStraight) != vOrig)
553 vStraight = pathStraight->back()->target();
554 OGDF_ASSERT(PG.original(vStraight) == vOrig);
555
556 eExtra = PG.separateDummy(adjA[0], adjA[1], vStraight, isSrc);
557 return u;
558 }
559
560 } else {
561 // Should be the correct adj... (case S-node, dummy)
562 adj = anchor.m_adj_1;
563 List<edge> *pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
564
565 if((eStraight && eStraight->source() != vOrig && eStraight->target() != vOrig) ||
566 (nsStraight && PG.original(nsStraight->source()) != vOrig))
567 {
568 node vDummy = adj->theNode();
569 edge eStraightOld = eStraight;
570 PlanRepExpansion::NodeSplit *nsStraightOld = nsStraight;
571
572 forall_adj(adj,vDummy) {
573 pathStraight = &PG.setOrigs(adj->theEdge(), eStraight, nsStraight);
574 if((eStraightOld && eStraight != eStraightOld) || (nsStraightOld && nsStraight != nsStraightOld))
575 break;
576 }
577 }
578
579 vStraight = pathStraight->front()->source();
580 if(PG.original(vStraight) != vOrig)
581 vStraight = pathStraight->back()->target();
582 }
583
584 OGDF_ASSERT(PG.original(vStraight) == vOrig);
585 eExtra = 0;
586
587 if(PG.original(adj->twinNode()) == vOrig) {
588 // No need for a split; can just directly go to a split node
589 return adj->twinNode();
590
591 } else {
592 edge e = adj->theEdge();
593 if(nsStraight == 0) {
594 // We split a chain of an original edge
595 PG.enlargeSplit(vStraight, e);
596 return e->target();
597
598 } else {
599 // We split a node split
600 PG.splitNodeSplit(e);
601 return e->target();
602 }
603 }
604 }
605
606 void MMVariableEmbeddingInserter::preprocessInsertionPath(
607 const AnchorNodeInfo &srcInfo,
608 const AnchorNodeInfo &tgtInfo,
609 node srcOrig,
610 node tgtOrig,
611 node &src,
612 node &tgt,
613 edge &eSrc,
614 edge &eTgt)
615 {
616 PlanRepExpansion &PG = *m_pPG;
617
618 src = srcInfo.m_adj_1->theNode();
619 if(PG.original(src) == 0)
620 src = prepareAnchorNode(srcInfo,srcOrig,true,eSrc);
621
622 tgt = tgtInfo.m_adj_1->theNode();
623 if(PG.original(tgt) == 0)
624 tgt = prepareAnchorNode(tgtInfo,tgtOrig,false,eTgt);
625 }
626
627
628 node MMVariableEmbeddingInserter::preparePath(
629 node vAnchor,
630 adjEntry adjPath,
631 bool bOrigEdge,
632 node vOrig)
633 {
634 PlanRepExpansion &PG = *m_pPG;
635
636 if(PG.original(adjPath->twinNode()) == vOrig) {
637 // No need for a split; can just directly go to a split node
638 return adjPath->twinNode();
639
640 } else {
641 edge e = adjPath->theEdge();
642 if(bOrigEdge) {
643 // We split a chain of an original edge
644 PG.enlargeSplit(vAnchor, e);
645 } else {
646 // We split a node split
647 PG.splitNodeSplit(e);
648 }
649 return e->target();
650 }
651 }
652
653
654 void MMVariableEmbeddingInserter::findPseudos(
655 node vDummy,
656 adjEntry adjSrc,
657 AnchorNodeInfo &infoSrc,
658 SListPure<node> &pseudos)
659 {
660 PlanRepExpansion &PG = *m_pPG;
661
662 ListConstIterator<edge> it = PG.position(adjSrc->theEdge());
663 node w;
664 if((*it)->source() == vDummy) {
665 edge e = *it;
666 while(PG.isPseudoCrossing(w = e->target())) {
667 pseudos.pushBack(w);
668 ++it; e = *it;
669 }
670
671 infoSrc.m_adj_1 = e->adjTarget();
672 infoSrc.m_adj_2 = (adjSrc->cyclicSucc() == (*PG.position(adjSrc->theEdge()).pred())->adjTarget()) ?
673 infoSrc.m_adj_1->cyclicSucc() : infoSrc.m_adj_1->cyclicPred();
674
675 } else {
676 edge e = *it;
677 while(PG.isPseudoCrossing(w = e->source())) {
678 pseudos.pushBack(w);
679 --it; e = *it;
680 }
681
682 infoSrc.m_adj_1 = e->adjSource();
683 infoSrc.m_adj_2 = (adjSrc->cyclicPred() == (*PG.position(adjSrc->theEdge()).succ())->adjSource()) ?
684 infoSrc.m_adj_1->cyclicPred() : infoSrc.m_adj_1->cyclicSucc();
685 }
686
687 }
688
689
690 void MMVariableEmbeddingInserter::insertWithCommonDummy(
691 edge eOrig,
692 node vDummy,
693 node &src,
694 node &tgt)
695 {
696 PlanRepExpansion &PG = *m_pPG;
697 #ifdef OGDF_DEBUG
698 bool isPlanar =
699 #endif
700 PG.embed();
701 OGDF_ASSERT(isPlanar);
702
703 node vSrc = 0, vTgt = 0;
704 adjEntry adjSrc = 0, adjTgt = 0;
705 bool bOrigEdgeSrc = true, bOrigEdgeTgt = true;
706
707 adjEntry adj;
708 forall_adj(adj,vDummy) {
709 edge e = adj->theEdge();
710 edge eStraight;
711 PlanRepExpansion::NodeSplit *nsStraight;
712 List<edge> &pathStraight = PG.setOrigs(e, eStraight, nsStraight);
713
714 node vAnchor;
715 if(vDummy == e->source())
716 vAnchor = pathStraight.back()->target();
717 else
718 vAnchor = pathStraight.front()->source();
719
720 node vOrig = PG.original(vAnchor);
721 if(vOrig == eOrig->source()) {
722 vSrc = vAnchor;
723 adjSrc = adj;
724 bOrigEdgeSrc = (eStraight != 0);
725 } else if(vOrig == eOrig->target()) {
726 vTgt = vAnchor;
727 adjTgt = adj;
728 bOrigEdgeTgt = (eStraight != 0);
729 }
730 }
731
732 OGDF_ASSERT(vSrc != 0 && vTgt != 0 && adjSrc != 0 && adjTgt != 0);
733
734 if(adjSrc == adjTgt->cyclicPred() || adjSrc == adjTgt->cyclicSucc())
735 {
736 src = preparePath(vSrc, adjSrc, bOrigEdgeSrc, eOrig->source());
737 tgt = preparePath(vTgt, adjTgt, bOrigEdgeTgt, eOrig->target());
738
739 } else {
740 SListPure<node> pseudos;
741 AnchorNodeInfo infoSrc;
742 AnchorNodeInfo infoTgt;
743
744 findPseudos(vDummy,adjSrc,infoSrc,pseudos);
745 findPseudos(vDummy,adjTgt,infoTgt,pseudos);
746
747 SListConstIterator<node> it;
748 for(it = pseudos.begin(); it.valid(); ++it)
749 PG.resolvePseudoCrossing(*it);
750
751 edge eExtra = 0;
752 src = infoSrc.m_adj_1->theNode();
753 if(PG.original(src) == 0)
754 src = prepareAnchorNode(infoSrc,eOrig->source(),true,eExtra);
755 OGDF_ASSERT(eExtra == 0);
756
757 tgt = infoTgt.m_adj_1->theNode();
758 if(PG.original(tgt) == 0)
759 tgt = prepareAnchorNode(infoTgt,eOrig->target(),false,eExtra);
760 OGDF_ASSERT(eExtra == 0);
761
762
763
764 //adjEntry adjTgt_2 = adjTgt->cyclicSucc()->cyclicSucc();
765 //OGDF_ASSERT(PG.nodeSplitOf(adjTgt->theEdge()) == PG.nodeSplitOf(adjTgt_2->theEdge()) &&
766 // PG.originalEdge(adjTgt->theEdge()) == PG.originalEdge(adjTgt_2->theEdge()));
767
768 //edge e = PG.insertBySepDummy(eOrig, vSrc, vTgt, adjSrc, adjTgt, adjTgt_2);
769 // //separateDummy(adjTgt, adjTgt_2, vTgt, false);
770 //PG.assignOrig(e,eOrig);
771 }
772 }
773
774 //-------------------------------------------------------------------
775 // Block represents a block of the original graph
776 //-------------------------------------------------------------------
777
778 class MMVariableEmbeddingInserter::Block : public Graph
779 {
780 public:
781 // constructor
782 Block(PlanRepExpansion &PG) : m_PG(PG)
783 {
784 m_adjBCtoG .init(*this,0);
785 m_forbidden .init(*this,false);
786 m_vBCtoG .init(*this,0);
787 m_isSource .init(*this,false);
788 m_isTarget .init(*this,false);
789 m_isSplittable.init(*this,false);
790 m_pT = 0;
791 }
792
793 ~Block() { delete m_pT; }
794
795 // avoid automatic generation of assignment operator
796 Block &operator=(const Block &);
797
798 node containsSource(node v) const;
799 node containsTarget(node v) const;
800
801 adjEntry containsSourceAdj(node v) const;
802 adjEntry containsTargetAdj(node v) const;
803
804 PlanRepExpansion &m_PG;
805 StaticPlanarSPQRTree *m_pT;
806
807 AdjEntryArray<adjEntry> m_adjBCtoG;
808 EdgeArray<bool> m_forbidden;
809 NodeArray<node> m_vBCtoG;
810
811 NodeArray<bool> m_isSource;
812 NodeArray<bool> m_isTarget;
813 NodeArray<bool> m_isSplittable;
814 };
815
816
817 node MMVariableEmbeddingInserter::Block::containsSource(node v) const
818 {
819 const Skeleton &S = m_pT->skeleton(v);
820 const Graph &M = S.getGraph();
821
822 node w;
823 forall_nodes(w,M) {
824 node wOrig = S.original(w);
825 if(m_isSource[wOrig])
826 return wOrig;
827 }
828
829 return 0;
830 }
831
832 node MMVariableEmbeddingInserter::Block::containsTarget(node v) const
833 {
834 const Skeleton &S = m_pT->skeleton(v);
835 const Graph &M = S.getGraph();
836
837 node w;
838 forall_nodes(w,M) {
839 node wOrig = S.original(w);
840 if(m_isTarget[wOrig])
841 return wOrig;
842 }
843
844 return 0;
845 }
846
847 adjEntry MMVariableEmbeddingInserter::Block::containsSourceAdj(node v) const
848 {
849 const Skeleton &S = m_pT->skeleton(v);
850 const Graph &M = S.getGraph();
851
852 node w, wOrig = 0;
853 forall_nodes(w,M) {
854 wOrig = S.original(w);
855 if(m_isSource[wOrig])
856 break;
857 }
858
859 if(wOrig == 0) return 0;
860
861 adjEntry adj;
862 forall_adj(adj,wOrig) {
863 if(m_pT->skeletonOfReal(adj->theEdge()).treeNode() == v)
864 return adj;
865 }
866
867 return wOrig->firstAdj();
868 }
869
870 adjEntry MMVariableEmbeddingInserter::Block::containsTargetAdj(node v) const
871 {
872 const Skeleton &S = m_pT->skeleton(v);
873 const Graph &M = S.getGraph();
874
875 node w, wOrig = 0;
876 forall_nodes(w,M) {
877 wOrig = S.original(w);
878 if(m_isTarget[wOrig])
879 break;
880 }
881
882 if(wOrig == 0) return 0;
883
884 adjEntry adj;
885 forall_adj(adj,wOrig) {
886 if(m_pT->skeletonOfReal(adj->theEdge()).treeNode() == v)
887 return adj;
888 }
889
890 return wOrig->firstAdj();
891 }
892
893
894 //-------------------------------------------------------------------
895 // ExpandedSkeleton represents the (partially) expanded skeleton with
896 // its dual graph (search network)
897 //-------------------------------------------------------------------
898
899 class MMVariableEmbeddingInserter::ExpandedSkeleton
900 {
901 Block &m_BC;
902
903 NodeArray<node> m_GtoExp;
904 List<node> m_nodesG;
905 Graph m_exp; // expanded graph
906 AdjEntryArray<adjEntry> m_expToG;
907 edge m_eS, m_eT; // (virtual) edges in exp representing s and t (if any)
908
909 ConstCombinatorialEmbedding m_E; //!< Embedding of expanded graph.
910
911 Graph m_dual; //!< Search network of expanded skeleton.
912 NodeArray<node> m_primalNode; //!< The node in PG corresponding to dual node (0 if face).
913 EdgeArray<adjEntry> m_primalAdj; //!< The adjacency entry in primal graph corresponding to edge in dual.
914 EdgeArray<int> m_dualCost; //!< The cost of an edge in the seach network.
915
916 node m_startEdge;
917 node m_startSource;
918 node m_startTarget;
919 node m_endEdge;
920 node m_endSource;
921 node m_endTarget;
922
923
924 public:
925 ExpandedSkeleton(Block &BC) :
926 m_BC(BC),
927 m_GtoExp(BC.m_pT->originalGraph(),0),
928 m_expToG(m_exp,0),
929 m_primalNode(m_dual,0),
930 m_primalAdj(m_dual,0),
931 m_dualCost(m_dual,0) { }
932
933 void expand(node v, edge eIn, edge eOut);
934
935 void constructDual(bool bPathToEdge, bool bPathToSrc, bool bPathToTgt);
936
937 void findShortestPath(bool &bPathToEdge, bool &bPathToSrc, bool &bPathToTgt, Paths &paths);
938
939 // avoid automatic generation of assignment operator
940 ExpandedSkeleton &operator=(const ExpandedSkeleton &);
941
942 private:
943 edge insertEdge(node vG, node wG, edge eG);
944 void expandSkeleton(node v, edge e1, edge e2);
945
946 static void addOutgoingEdges(node v, SListPure<edge> &edges);
947 PathType reconstructInsertionPath(
948 node v,
949 AnchorNodeInfo &m_srcInfo,
950 AnchorNodeInfo &m_tgtInfo,
951 List<Crossing> &crossed,
952 SList<adjEntry> &addLeft,
953 SList<adjEntry> &addRight,
954 NodeArray<edge> &spPred);
955 };
956
957
958 //-------------------------------------------------------------------
959 // build expanded graph (by expanding skeleton(v), edges eIn and eOut
960 // are the adjacent tree edges on the path from v1 to v2
961 //-------------------------------------------------------------------
962
963 void MMVariableEmbeddingInserter::ExpandedSkeleton::expand(
964 node v, edge eIn, edge eOut)
965 {
966 m_exp.clear();
967
968 while (!m_nodesG.empty())
969 m_GtoExp[m_nodesG.popBackRet()] = 0;
970
971 const StaticSPQRTree &T = *m_BC.m_pT;
972 const Skeleton &S = T.skeleton(v);
973
974 m_eS = 0;
975 if (eIn != 0) {
976 edge eInS = (v != eIn->source()) ? T.skeletonEdgeTgt(eIn) :
977 T.skeletonEdgeSrc(eIn);
978 node x = S.original(eInS->source()), y = S.original(eInS->target());
979 m_eS = insertEdge(x,y,0);
980 }
981
982 m_eT = 0;
983 if (eOut != 0) {
984 edge eOutS = (v != eOut->source()) ? T.skeletonEdgeTgt(eOut) :
985 T.skeletonEdgeSrc(eOut);
986 node x = S.original(eOutS->source()), y = S.original(eOutS->target());
987 m_eT = insertEdge(x,y,0);
988 }
989
990 expandSkeleton(v, eIn, eOut);
991
992 planarEmbed(m_exp);
993 m_E.init(m_exp);
994 }
995
996
997 //-------------------------------------------------------------------
998 // insert edge in exp (from a node corresponding to vG in G to a node
999 // corresponding to wG)
1000 //-------------------------------------------------------------------
1001
1002 edge MMVariableEmbeddingInserter::ExpandedSkeleton::insertEdge(
1003 node vG, node wG, edge eG)
1004 {
1005 node &rVG = m_GtoExp[vG];
1006 node &rWG = m_GtoExp[wG];
1007
1008 if (rVG == 0) {
1009 rVG = m_exp.newNode();
1010 m_nodesG.pushBack(vG);
1011 }
1012 if (rWG == 0) {
1013 rWG = m_exp.newNode();
1014 m_nodesG.pushBack(wG);
1015 }
1016
1017 edge e1 = m_exp.newEdge(rVG,rWG);
1018
1019 if(eG != 0) {
1020 m_expToG[e1->adjSource()] = eG->adjSource();
1021 m_expToG[e1->adjTarget()] = eG->adjTarget();
1022 } else {
1023 m_expToG[e1->adjSource()] = 0;
1024 m_expToG[e1->adjTarget()] = 0;
1025 }
1026
1027 return e1;
1028 }
1029
1030
1031 //-------------------------------------------------------------------
1032 // expand one skeleton (recursive construction)
1033 //-------------------------------------------------------------------
1034
1035 void MMVariableEmbeddingInserter::ExpandedSkeleton::expandSkeleton(
1036 node v, edge e1, edge e2)
1037 {
1038 const StaticSkeleton &S = *dynamic_cast<StaticSkeleton*>(&m_BC.m_pT->skeleton(v));
1039 const Graph &M = S.getGraph();
1040
1041 edge e;
1042 forall_edges(e,M)
1043 {
1044 edge eG = S.realEdge(e);
1045 if (eG != 0) {
1046 insertEdge(eG->source(),eG->target(),eG);
1047
1048 } else {
1049 edge eT = S.treeEdge(e);
1050
1051 // do not expand virtual edges corresponding to tree edges e1 or e2
1052 if (eT != e1 && eT != e2) {
1053 expandSkeleton((v == eT->source()) ? eT->target() : eT->source(),
1054 eT,0);
1055 }
1056 }
1057 }
1058 }
1059
1060
1061 //-------------------------------------------------------------------
1062 // construct augmented dual graph (search network)
1063 //-------------------------------------------------------------------
1064
1065 void MMVariableEmbeddingInserter::ExpandedSkeleton::constructDual(
1066 bool bPathToEdge, bool bPathToSrc, bool bPathToTgt)
1067 {
1068 m_dual.clear();
1069
1070 // insert a node in the dual graph for each face in E
1071 FaceArray<node> dualOfFace(m_E);
1072
1073 face f;
1074 forall_faces(f,m_E)
1075 dualOfFace[f] = m_dual.newNode();
1076
1077 SListPure<node> sources, targets;
1078
1079 // insert a node in the dual graph for each splittable node in PG
1080 NodeArray<node> dualOfNode(m_exp,0);
1081
1082 ListConstIterator<node> itV;
1083 for(itV = m_nodesG.begin(); itV.valid(); ++itV) {
1084 node vBC = *itV;
1085 node v = m_GtoExp[vBC];
1086
1087 bool addDualNode = m_BC.m_isSplittable[vBC];
1088
1089 if(m_BC.m_isSource[vBC]) {
1090 sources.pushBack(v);
1091 addDualNode = true;
1092 }
1093 if(m_BC.m_isTarget[vBC]) {
1094 targets.pushBack(v);
1095 addDualNode = true;
1096 }
1097
1098 if(addDualNode)
1099 m_primalNode[dualOfNode[v] = m_dual.newNode()] = v;
1100 }
1101
1102 // Insert an edge into the dual graph for each adjacency entry in E.
1103 // The edges are directed from the left face to the right face.
1104 node v;
1105 forall_nodes(v,m_exp)
1106 {
1107 node vDual = dualOfNode[v];
1108
1109 adjEntry adj;
1110 forall_adj(adj,v)
1111 {
1112 // cannot cross virtual edge representing sources / targets
1113 adjEntry adjBC = m_expToG[adj];
1114 if(adjBC == 0)
1115 continue;
1116
1117 node vLeft = dualOfFace[m_E.leftFace (adj)];
1118 node vRight = dualOfFace[m_E.rightFace(adj)];
1119
1120 if(m_BC.m_forbidden[adjBC->theEdge()] == false) {
1121 edge e = m_dual.newEdge(vLeft,vRight);
1122 m_primalAdj[e] = adj;
1123 m_dualCost [e] = 1;
1124 }
1125
1126 if(vDual) {
1127 //if(m_eT == 0 || (v != m_eT->source() && v != m_eT->target())) {
1128 edge eOut = m_dual.newEdge(vDual,vLeft);
1129 m_primalAdj[eOut] = adj;
1130 m_dualCost [eOut] = 0;
1131 //}
1132
1133 if(m_eS == 0 ||
1134 ((bPathToSrc == false || v != m_eS->source()) && (bPathToTgt == false || v != m_eS->target())))
1135 {
1136 edge eIn = m_dual.newEdge(vLeft,vDual);
1137 m_primalAdj[eIn] = adj;
1138 m_dualCost [eIn] = 1;
1139 }
1140 }
1141 }
1142 }
1143
1144 m_startEdge = (bPathToEdge) ? m_dual.newNode() : 0;
1145 if(m_eS != 0) {
1146 if(m_startEdge) {
1147 m_dual.newEdge(m_startEdge, dualOfFace[m_E.rightFace(m_eS->adjSource())]);
1148 m_dual.newEdge(m_startEdge, dualOfFace[m_E.rightFace(m_eS->adjTarget())]);
1149 }
1150
1151 m_startSource = (bPathToSrc) ? dualOfNode[m_eS->source()] : 0;
1152 m_startTarget = (bPathToTgt) ? dualOfNode[m_eS->target()] : 0;
1153
1154 } else {
1155 m_startSource = m_startTarget = 0;
1156 SListConstIterator<node> it;
1157 for(it = sources.begin(); it.valid(); ++it)
1158 m_dual.newEdge(m_startEdge, dualOfNode[*it]);
1159 }
1160
1161 m_endEdge = m_dual.newNode();
1162 if(m_eT != 0) {
1163 m_dual.newEdge(dualOfFace[m_E.rightFace(m_eT->adjSource())], m_endEdge);
1164 m_dual.newEdge(dualOfFace[m_E.rightFace(m_eT->adjTarget())], m_endEdge);
1165
1166 m_endSource = dualOfNode[m_eT->source()];
1167 m_endTarget = dualOfNode[m_eT->target()];
1168
1169 } else {
1170 m_endSource = m_endTarget = 0;
1171 SListConstIterator<node> it;
1172 for(it = targets.begin(); it.valid(); ++it)
1173 m_dual.newEdge(dualOfNode[*it], m_endEdge);
1174 }
1175 }
1176
1177
1178 //-------------------------------------------------------------------
1179 // finds shortest paths in the search network
1180 //-------------------------------------------------------------------
1181
1182 void MMVariableEmbeddingInserter::ExpandedSkeleton::addOutgoingEdges(
1183 node v, SListPure<edge> &edges)
1184 {
1185 edge e;
1186 forall_adj_edges(e,v)
1187 if(e->target() != v)
1188 edges.pushBack(e);
1189 }
1190
1191 MMVariableEmbeddingInserter::PathType
1192 MMVariableEmbeddingInserter::ExpandedSkeleton::reconstructInsertionPath(
1193 node v,
1194 AnchorNodeInfo &srcInfo,
1195 AnchorNodeInfo &tgtInfo,
1196 List<Crossing> &crossed,
1197 SList<adjEntry> &addLeft,
1198 SList<adjEntry> &addRight,
1199 NodeArray<edge> &spPred)
1200 {
1201 // handle last node on path split first
1202 if(v == m_endEdge) {
1203 edge eDual = spPred[v];
1204 v = eDual->source();
1205 if(m_primalNode[v] != 0) {
1206 eDual = spPred[v];
1207 // hier Ziel speichern: m_expToG[m_primalAdj[eDual]]->theNode()
1208 //tgt = m_expToG[m_primalAdj[eDual]]->theNode();
1209 tgtInfo.m_adj_1 = m_expToG[m_primalAdj[eDual]];
1210 tgtInfo.m_adj_2 = m_expToG[m_primalAdj[eDual]->cyclicPred()];
1211
1212 OGDF_ASSERT(tgtInfo.m_adj_1 != 0);
1213
1214 v = eDual->source();
1215 }
1216
1217 } else {
1218 edge eDual = spPred[v];
1219
1220 if(eDual != 0) {
1221 adjEntry adj_1 = m_primalAdj[eDual];
1222 Crossing &cr = *crossed.pushFront(Crossing());
1223
1224 adjEntry adj;
1225 for(adj = adj_1; adj->theEdge() != m_eT; adj = adj->cyclicSucc()) {
1226 adjEntry adjBC = m_expToG[adj];
1227 if(adjBC != 0)
1228 cr.m_partitionLeft.pushBack(adjBC);
1229 //OGDF_ASSERT(m_expToG[adj] != 0);
1230 }
1231 for(adj = adj->cyclicSucc(); adj != adj_1; adj = adj->cyclicSucc()) {
1232 adjEntry adjBC = m_expToG[adj];
1233 if(adjBC != 0)
1234 cr.m_partitionRight.pushBack(adjBC);
1235 //OGDF_ASSERT(m_expToG[adj] != 0);
1236 }
1237
1238 v = eDual->source();
1239
1240 } else {
1241 node vExp = m_primalNode[v];
1242 OGDF_ASSERT(m_eS->source() == vExp || m_eS->target() == vExp);
1243 OGDF_ASSERT(m_eT->source() == vExp || m_eT->target() == vExp);
1244 adjEntry adjS = (m_eS->source() == vExp) ? m_eS->adjSource() : m_eS->adjTarget();
1245 adjEntry adjT = (m_eT->source() == vExp) ? m_eT->adjSource() : m_eT->adjTarget();
1246 OGDF_ASSERT(adjS->theNode() == vExp && adjT->theNode() == vExp);
1247
1248 adjEntry adj;
1249 for(adj = adjS->cyclicSucc(); adj != adjT; adj = adj->cyclicSucc()) {
1250 addLeft.pushBack(m_expToG[adj]);
1251 OGDF_ASSERT(m_expToG[adj] != 0);
1252 }
1253 for(adj = adj->cyclicSucc(); adj != adjS; adj = adj->cyclicSucc()) {
1254 addRight.pushBack(m_expToG[adj]);
1255 OGDF_ASSERT(m_expToG[adj] != 0);
1256 }
1257 }
1258 }
1259
1260 while(v != m_startEdge && v != m_startSource && v != m_startTarget) {
1261 OGDF_ASSERT(m_primalNode[v] == 0);
1262
1263 edge eDual = spPred[v];
1264 node w = eDual->source();
1265
1266 if(m_primalNode[w] == 0) {
1267 // w is a face node
1268 adjEntry adjExp = m_primalAdj[spPred[v]];
1269 if(adjExp != 0)
1270 crossed.pushFront(Crossing(m_expToG[adjExp]));
1271
1272 } else {
1273 edge eDual2 = spPred[w];
1274
1275 if(eDual2 != 0) {
1276 adjEntry adj_1 = m_primalAdj[eDual2];
1277 adjEntry adj_2 = m_primalAdj[eDual];
1278
1279 w = eDual2->source();
1280 if(adj_1 != 0) {
1281 Crossing &cr = *crossed.pushFront(Crossing());
1282
1283 adjEntry adj;
1284 for(adj = adj_1; adj != adj_2; adj = adj->cyclicSucc()) {
1285 adjEntry adjBC = m_expToG[adj];
1286 if(adjBC != 0)
1287 cr.m_partitionLeft.pushBack(adjBC);
1288 //OGDF_ASSERT(m_expToG[adj] != 0);
1289 }
1290 for(; adj != adj_1; adj = adj->cyclicSucc()) {
1291 adjEntry adjBC = m_expToG[adj];
1292 if(adjBC != 0)
1293 cr.m_partitionRight.pushBack(adjBC);
1294 //OGDF_ASSERT(m_expToG[adj] != 0);
1295 }
1296
1297 } else {
1298 // speichere Startkonoten hier:
1299 //src = m_expToG[m_primalAdj[eDual]]->theNode();
1300 srcInfo.m_adj_1 = m_expToG[m_primalAdj[eDual]];
1301 srcInfo.m_adj_2 = m_expToG[m_primalAdj[eDual]->cyclicPred()];
1302
1303 OGDF_ASSERT(srcInfo.m_adj_1 != 0);
1304 }
1305
1306 } else {
1307 adjEntry adj_2 = m_primalAdj[eDual];
1308
1309 adjEntry adj;
1310 for(adj = adj_2; adj->theEdge() != m_eS; adj = adj->cyclicSucc()) {
1311 adjEntry adjBC = m_expToG[adj];
1312 if(adjBC != 0)
1313 addLeft.pushBack(adjBC);
1314 //OGDF_ASSERT(m_expToG[adj] != 0);
1315 }
1316 for(adj = adj->cyclicSucc(); adj != adj_2; adj = adj->cyclicSucc()) {
1317 adjEntry adjBC = m_expToG[adj];
1318 if(adjBC != 0)
1319 addRight.pushBack(adjBC);
1320 //OGDF_ASSERT(m_expToG[adj] != 0);
1321 }
1322 }
1323 }
1324
1325 v = w;
1326 }
1327
1328 if(v == m_startEdge)
1329 return pathToEdge;
1330 else if (v == m_startSource)
1331 return pathToSource;
1332 else
1333 return pathToTarget;
1334 }
1335
1336 void MMVariableEmbeddingInserter::ExpandedSkeleton::findShortestPath(
1337 bool &bPathToEdge,
1338 bool &bPathToSrc,
1339 bool &bPathToTgt,
1340 Paths &paths)
1341 {
1342 const int maxCost = 2;
1343
1344 Array<SListPure<edge> > nodesAtDist(maxCost);
1345 NodeArray<edge> spPred(m_dual,0);
1346
1347 // start edges
1348 if(m_startEdge)
1349 addOutgoingEdges(m_startEdge, nodesAtDist[0]);
1350 if(m_startSource)
1351 addOutgoingEdges(m_startSource, nodesAtDist[0]);
1352 if(m_startTarget)
1353 addOutgoingEdges(m_startTarget, nodesAtDist[0]);
1354
1355 bool vEdgeReached = false;
1356 bool vSourceReached = (m_endSource == 0 || m_endSource == m_startSource || m_endSource == m_startTarget);
1357 bool vTargetReached = (m_endTarget == 0 || m_endTarget == m_startSource || m_endTarget == m_startTarget);
1358
1359 // actual search (using extended bfs on directed dual)
1360 int currentDist = 0;
1361
1362 for( ; ; )
1363 {
1364 // next candidate edge
1365 while(nodesAtDist[currentDist % maxCost].empty())
1366 ++currentDist;
1367
1368 edge eCand = nodesAtDist[currentDist % maxCost].popFrontRet();
1369 node v = eCand->target();
1370
1371 // leads to an unvisited node?
1372 if (spPred[v] == 0)
1373 {
1374 // yes, then we set v's predecessor in search tree
1375 spPred[v] = eCand;
1376 if(v == m_endEdge ) vEdgeReached = true;
1377 if(v == m_endSource) vSourceReached = true;
1378 if(v == m_endTarget) vTargetReached = true;
1379
1380 // all targets reached?
1381 if (vEdgeReached && vSourceReached && vTargetReached)
1382 {
1383 paths.m_pred[pathToEdge] = reconstructInsertionPath(m_endEdge,
1384 paths.m_src[pathToEdge], paths.m_tgt[pathToEdge],
1385 paths.m_paths[pathToEdge],
1386 paths.m_addPartLeft[pathToEdge], paths.m_addPartRight[pathToEdge],
1387 spPred);
1388 if(m_endSource != 0)
1389 paths.m_pred[pathToSource] = reconstructInsertionPath(m_endSource,
1390 paths.m_src[pathToSource], paths.m_tgt[pathToSource],
1391 paths.m_paths[pathToSource],
1392 paths.m_addPartLeft[pathToSource], paths.m_addPartRight[pathToSource],
1393 spPred);
1394 if(m_endTarget != 0)
1395 paths.m_pred[pathToTarget] = reconstructInsertionPath(m_endTarget,
1396 paths.m_src[pathToTarget], paths.m_tgt[pathToTarget],
1397 paths.m_paths[pathToTarget],
1398 paths.m_addPartLeft[pathToTarget], paths.m_addPartRight[pathToTarget],
1399 spPred);
1400
1401 break;
1402 }
1403
1404 // append next candidate edges to queue
1405 // (all edges leaving v)
1406 edge e;
1407 forall_adj_edges(e,v) {
1408 if (v != e->source()) continue;
1409
1410 int listPos = (currentDist + m_dualCost[e]) % maxCost;
1411 nodesAtDist[listPos].pushBack(e);
1412 }
1413 }
1414 }
1415
1416 int lenEdge = paths.m_paths[pathToEdge].size();
1417 int lenSrc = paths.m_paths[pathToSource].size();
1418 int lenTgt = paths.m_paths[pathToTarget].size();
1419 OGDF_ASSERT(m_endSource == 0 || lenSrc >= lenEdge);
1420 OGDF_ASSERT(m_endTarget == 0 || lenTgt >= lenEdge);
1421
1422 //bPathToEdge = ((m_endSource == 0 || lenEdge <= lenSrc) && (m_endTarget == 0 || lenEdge <= lenTgt));
1423 bPathToEdge = true;
1424 bPathToSrc = (m_endSource != 0 && lenSrc == lenEdge);
1425 bPathToTgt = (m_endTarget != 0 && lenTgt == lenEdge);
1426 }
1427
1428
1429 bool MMVariableEmbeddingInserter::dfsVertex(
1430 node v,
1431 int parent,
1432 List<Crossing> &eip,
1433 AnchorNodeInfo &vStart,
1434 AnchorNodeInfo &vEnd)
1435 {
1436 // forall biconnected components containing v (except predecessor parent)
1437 SListConstIterator<int> itI;
1438 for(itI = m_compV[v].begin(); itI.valid(); ++itI)
1439 {
1440 int i = *itI;
1441
1442 if (i == parent) continue;
1443
1444 node repS; // representative of s in B(i)
1445 if (dfsBlock(i,v,repS,eip,vStart,vEnd) == true) { // path found?
1446 if(m_conFinished) return true;
1447
1448 // build graph BC of biconnected component B(i)
1449 SList<node> nodesG;
1450 Block BC(*m_pPG);
1451
1452 SListConstIterator<edge> itE;
1453 for(itE = m_edgeB[i].begin(); itE.valid(); ++itE)
1454 {
1455 edge e = *itE;
1456
1457 node vSrc = e->source();
1458 if (m_GtoBC[vSrc] == 0) {
1459 BC.m_vBCtoG[m_GtoBC[vSrc] = BC.newNode()] = vSrc;
1460 nodesG.pushBack(vSrc);
1461 if(m_pSources->isMember(vSrc) || vSrc == repS)
1462 BC.m_isSource[m_GtoBC[vSrc]] = true;
1463 if(m_pTargets->isMember(vSrc) || vSrc == v)
1464 BC.m_isTarget[m_GtoBC[vSrc]] = true;
1465 BC.m_isSplittable[m_GtoBC[vSrc]] = m_pPG->splittable(vSrc);
1466 }
1467
1468 node vTgt = e->target();
1469 if (m_GtoBC[vTgt] == 0) {
1470 BC.m_vBCtoG[m_GtoBC[vTgt] = BC.newNode()] = vTgt;
1471 nodesG.pushBack(vTgt);
1472 if(m_pSources->isMember(vTgt) || vTgt == repS)
1473 BC.m_isSource[m_GtoBC[vTgt]] = true;
1474 if(m_pTargets->isMember(vTgt) || vTgt == v)
1475 BC.m_isTarget[m_GtoBC[vTgt]] = true;
1476 BC.m_isSplittable[m_GtoBC[vTgt]] = m_pPG->splittable(vTgt);
1477 }
1478
1479 edge eBC = BC.newEdge(m_GtoBC[vSrc],m_GtoBC[vTgt]);
1480 BC.m_adjBCtoG[eBC->adjSource()] = e->adjSource();
1481 BC.m_adjBCtoG[eBC->adjTarget()] = e->adjTarget();
1482
1483 if(m_forbiddenEdgeOrig != 0) {
1484 edge eOrig = m_pPG->originalEdge(e);
1485 if(eOrig != 0)
1486 BC.m_forbidden[eBC] = (*m_forbiddenEdgeOrig)[eOrig];
1487 }
1488 }
1489
1490 AnchorNodeInfo srcInfo = repS->firstAdj();
1491 AnchorNodeInfo tgtInfo = v->firstAdj();
1492
1493 // less than 3 nodes requires no crossings (cannot build SPQR-tree
1494 // for a graph with less than 3 nodes!)
1495 if (nodesG.size() >= 3) {
1496 // call biconnected case
1497 List<Crossing> L;
1498 blockInsert(BC, L, srcInfo, tgtInfo);
1499
1500 srcInfo.m_adj_1 = BC.m_adjBCtoG[srcInfo.m_adj_1];
1501 if(srcInfo.m_adj_2 != 0)
1502 srcInfo.m_adj_2 = BC.m_adjBCtoG[srcInfo.m_adj_2];
1503 tgtInfo.m_adj_1 = BC.m_adjBCtoG[tgtInfo.m_adj_1];
1504 if(tgtInfo.m_adj_2 != 0)
1505 tgtInfo.m_adj_2 = BC.m_adjBCtoG[tgtInfo.m_adj_2];
1506
1507 // transform crossed edges to edges in G
1508 ListIterator<Crossing> it;
1509 for(it = L.begin(); it.valid(); ++it) {
1510 Crossing &cr = *it;
1511 if(cr.m_adj != 0) cr.m_adj = BC.m_adjBCtoG[cr.m_adj];
1512 SListIterator<adjEntry> itAdj;
1513 for(itAdj = cr.m_partitionLeft.begin(); itAdj.valid(); ++itAdj)
1514 *itAdj = BC.m_adjBCtoG[*itAdj];
1515 for(itAdj = cr.m_partitionRight.begin(); itAdj.valid(); ++itAdj)
1516 *itAdj = BC.m_adjBCtoG[*itAdj];
1517
1518 //adjEntry adj1 = BC.m_BCtoG[(*it).m_adj1];
1519 //adjEntry adj2 = ((*it).m_adj1 == 0) ? 0 : BC.m_BCtoG[(*it).m_adj1];
1520 //eip.pushBack(Crossing(adj1,adj2));
1521 }
1522 eip.conc(L);
1523 }
1524
1525 if(m_pSources->isMember(srcInfo.m_adj_1->theNode()))
1526 vStart = srcInfo;
1527
1528 if(m_pTargets->isMember(tgtInfo.m_adj_1->theNode())) {
1529 vEnd = tgtInfo;
1530 m_conFinished = true;
1531 }
1532
1533 // set entries of GtoBC back to nil (GtoBC allocated only once
1534 // in insert()!)
1535 SListConstIterator<node> itV;
1536 for(itV = nodesG.begin(); itV.valid(); ++itV)
1537 m_GtoBC[*itV] = 0;
1538
1539 return true; // path found
1540 }
1541 }
1542
1543 return false; // path not found
1544 }
1545
1546
1547 bool MMVariableEmbeddingInserter::dfsBlock(int i,
1548 node parent,
1549 node &repS,
1550 List<Crossing> &eip,
1551 AnchorNodeInfo &vStart,
1552 AnchorNodeInfo &vEnd)
1553 {
1554 // forall nodes in biconected component B(i) (except predecessor parent)
1555 SListConstIterator<node> it;
1556 for(it = m_nodeB[i].begin(); it.valid(); ++it)
1557 {
1558 repS = *it;
1559
1560 if (repS == parent) continue;
1561 if (m_pSources->isMember(repS) == true) { // s found?
1562 return true;
1563 }
1564
1565 if (dfsVertex(repS,i,eip,vStart,vEnd) == true) {
1566 return true; // path found
1567 }
1568 }
1569
1570 return false; // path not found
1571 }
1572
1573
1574 //-------------------------------------------------------------------
1575 // find optimal edge insertion path for biconnected graph G
1576 //-------------------------------------------------------------------
1577
1578 bool MMVariableEmbeddingInserter::pathSearch(
1579 node v,
1580 edge parent,
1581 const Block &BC,
1582 List<edge> &path)
1583 {
1584 if(BC.containsTarget(v) != 0)
1585 return true;
1586
1587 edge e;
1588 forall_adj_edges(e,v) {
1589 if(e == parent) continue;
1590 if(pathSearch(e->opposite(v),e,BC,path) == true) {
1591 path.pushFront(e);
1592 return true;
1593 }
1594 }
1595
1596 return false;
1597 }
1598
1599 void MMVariableEmbeddingInserter::blockInsert(
1600 Block &BC,
1601 List<Crossing> &L,
1602 AnchorNodeInfo &srcInfo,
1603 AnchorNodeInfo &tgtInfo)
1604 {
1605 L.clear();
1606 srcInfo = tgtInfo = AnchorNodeInfo();
1607
1608 // construct SPQR-tree
1609 BC.m_pT = new StaticPlanarSPQRTree(BC);
1610 const StaticSPQRTree &T = *BC.m_pT;
1611 const Graph &tree = T.tree();
1612
1613 node v, v1 = 0, vx = 0;
1614 forall_nodes(v,tree) {
1615 if(BC.containsSource(v) != 0) {
1616 if(v1 == 0)
1617 v1 = v;
1618 if(T.typeOf(v) == SPQRTree::RNode && BC.containsTarget(v) != 0) {
1619 vx = v; break;
1620 }
1621 }
1622 }
1623
1624 List<edge> path;
1625 if(vx == 0) {
1626 // find path in tree connecting a nodes whose skeleton contains and
1627 // source and a target, resp.
1628 pathSearch(v1,0,BC,path);
1629
1630 // remove unnecessary allocation nodes of sources from start of path
1631 while(!path.empty() && BC.containsSource(v = path.front()->opposite(v1)) != 0)
1632 {
1633 v1 = v;
1634 path.popFront();
1635 }
1636 } else
1637 v1 = vx;
1638
1639 // call build_subpath for every R-node building the list of crossed edges/nodes
1640 ExpandedSkeleton exp(BC);
1641
1642 bool bPathToEdge = true;
1643 bool bPathToSrc = false;
1644 bool bPathToTgt = false;
1645 Array<Paths> pathsInSks(path.size()+1);
1646 int i = 0;
1647
1648 switch(T.typeOf(v1)) {
1649 case SPQRTree::RNode:
1650 buildSubpath(v1, 0,
1651 (path.empty()) ? 0 : path.front(),
1652 pathsInSks[i++],
1653 bPathToEdge,
1654 bPathToSrc,
1655 bPathToTgt,
1656 exp);
1657 break;
1658
1659 case SPQRTree::PNode:
1660 break;
1661
1662 case SPQRTree::SNode:
1663 srcInfo.m_adj_1 = BC.containsSourceAdj(v1);
1664 break;
1665 }
1666
1667 v = v1;
1668 ListConstIterator<edge> it;
1669 for(it = path.begin(); it.valid(); ++it)
1670 {
1671 edge e = *it;
1672 v = e->opposite(v);
1673
1674 switch(T.typeOf(v)) {
1675 case SPQRTree::RNode:
1676 buildSubpath(v, e,
1677 (it.succ().valid() == false) ? 0 : *(it.succ()),
1678 pathsInSks[i++],
1679 bPathToEdge,
1680 bPathToSrc,
1681 bPathToTgt,
1682 exp);
1683 break;
1684
1685 case SPQRTree::PNode:
1686 break;
1687
1688 case SPQRTree::SNode:
1689 if(it.succ().valid()) {
1690 edge eNext = *it.succ();
1691
1692 edge e_1 = (v == e ->target()) ? T.skeletonEdgeTgt(e ) : T.skeletonEdgeSrc(e );
1693 edge e_2 = (v == eNext->target()) ? T.skeletonEdgeTgt(eNext) : T.skeletonEdgeSrc(eNext);
1694
1695 bool bPathToSrcOld = bPathToSrc;
1696 bool bPathToTgtOld = bPathToTgt;
1697
1698 Paths &p = pathsInSks[i];
1699 if(e_2->source() == e_1->source() && bPathToSrcOld) {
1700 p.m_pred[pathToSource] = pathToSource;
1701 bPathToSrc = true;
1702 } else if (e_2->source() == e_1->target() && bPathToTgtOld) {
1703 p.m_pred[pathToSource] = pathToTarget;
1704 bPathToSrc = true;
1705 } else
1706 bPathToSrc = false;
1707
1708 if(e_2->target() == e_1->target() && bPathToTgtOld) {
1709 p.m_pred[pathToTarget] = pathToTarget;
1710 bPathToTgt = true;
1711 } else if (e_2->target() == e_1->source() && bPathToSrcOld) {
1712 p.m_pred[pathToTarget] = pathToSource;
1713 bPathToTgt = true;
1714 } else
1715 bPathToTgt = false;
1716
1717 i++;
1718 }
1719 break;
1720 }
1721 }
1722
1723 if(T.typeOf(v) == SPQRTree::SNode)
1724 tgtInfo.m_adj_1 = BC.containsTargetAdj(v);
1725 //tgtInfo.m_adj_1 = BC.containsTarget(v)->firstAdj();
1726
1727 if(i == 0) return;
1728
1729 // construct list of crossings L
1730 int currentPath = pathToEdge;
1731 AnchorNodeInfo &x = pathsInSks[i-1].m_tgt[currentPath];
1732 if(x.m_adj_1 != 0)
1733 tgtInfo = x;
1734 SList<adjEntry> *pAddLeft = 0;
1735 SList<adjEntry> *pAddRight = 0;
1736
1737 while(--i >= 0) {
1738 List<Crossing> &eip = pathsInSks[i].m_paths[currentPath];
1739
1740 if(currentPath > 0) {
1741 if(eip.empty()) {
1742 pathsInSks[i].m_addPartLeft [currentPath].conc(*pAddLeft );
1743 pathsInSks[i].m_addPartRight[currentPath].conc(*pAddRight);
1744
1745 } else {
1746 Crossing &cr = *eip.rbegin();
1747 cr.m_partitionLeft .conc(*pAddLeft );
1748 cr.m_partitionRight.conc(*pAddRight);
1749 }
1750 }
1751
1752 L.concFront(eip);
1753
1754 pAddLeft = &pathsInSks[i].m_addPartLeft [currentPath];
1755 pAddRight = &pathsInSks[i].m_addPartRight[currentPath];
1756 if(i == 0) {
1757 AnchorNodeInfo &x = pathsInSks[0].m_src[currentPath];
1758 if(x.m_adj_1 != 0)
1759 srcInfo = x;
1760 OGDF_ASSERT(srcInfo.m_adj_1 != 0);
1761 }
1762
1763 currentPath = pathsInSks[i].m_pred[currentPath];
1764 }
1765 }
1766
1767
1768 //-------------------------------------------------------------------
1769 // find the shortest path from represent. of s to represent. of t in
1770 // the dual of the (partially) expanded skeleton of v
1771 //-------------------------------------------------------------------
1772
1773 void MMVariableEmbeddingInserter::buildSubpath(
1774 node v,
1775 edge eIn,
1776 edge eOut,
1777 Paths &paths,
1778 bool &bPathToEdge,
1779 bool &bPathToSrc,
1780 bool &bPathToTgt,
1781 ExpandedSkeleton &Exp)
1782 {
1783 // build expanded graph Exp
1784 Exp.expand(v,eIn,eOut);
1785
1786 // construct augmented dual of expanded graph
1787 Exp.constructDual(bPathToEdge,bPathToSrc,bPathToTgt);
1788
1789 // find shortest path in augmented dual
1790 Exp.findShortestPath(bPathToEdge, bPathToSrc, bPathToTgt, paths);
1791 }
1792
1793
1794 void MMVariableEmbeddingInserter::contractSplitIfReq(node u)
1795 {
1796 if(u->degree() == 2) {
1797 edge eContract = u->firstAdj()->theEdge();
1798 edge eExpand = u->lastAdj ()->theEdge();
1799 if(m_pPG->nodeSplitOf(eContract) == 0)
1800 swap(eContract,eExpand);
1801
1802 if(m_pPG->nodeSplitOf(eContract) != 0) {
1803 edge e = m_pPG->unsplitExpandNode(u,eContract,eExpand);
1804
1805 if(e->isSelfLoop())
1806 m_pPG->removeSelfLoop(e);
1807 }
1808 }
1809 }
1810
1811
1812 void MMVariableEmbeddingInserter::convertDummy(
1813 node u,
1814 node vOrig,
1815 PlanRepExpansion::nodeSplit ns_0)
1816 {
1817 PlanRepExpansion::nodeSplit ns_1 = m_pPG->convertDummy(u,vOrig,ns_0);
1818
1819 if(ns_0->m_path.size() == 1)
1820 m_pPG->contractSplit(ns_0);
1821 if(ns_1->m_path.size() == 1)
1822 m_pPG->contractSplit(ns_1);
1823 }
1824
1825
1826 void MMVariableEmbeddingInserter::collectAnchorNodes(
1827 node v,
1828 NodeSet &nodes,
1829 const PlanRepExpansion::NodeSplit *nsParent) const
1830 {
1831 if(m_pPG->original(v) != 0)
1832 nodes.insert(v);
1833
1834 adjEntry adj;
1835 forall_adj(adj,v) {
1836 edge e = adj->theEdge();
1837 const PlanRepExpansion::NodeSplit *ns = m_pPG->nodeSplitOf(e);
1838 if(ns == 0) {
1839 // add dummy nodes of non-node-split edge
1840 ListConstIterator<edge> it = m_pPG->chain(m_pPG->originalEdge(e)).begin();
1841 for(++it; it.valid(); ++it)
1842 nodes.insert((*it)->source());
1843
1844 } else if(ns != nsParent) {
1845 // add dummy nodes of node-split edge
1846 ListConstIterator<edge> it = ns->m_path.begin();
1847 for(++it; it.valid(); ++it)
1848 nodes.insert((*it)->source());
1849
1850 node w = (v == e->source()) ? ns->target() : ns->source();
1851 collectAnchorNodes(w, nodes, ns);
1852 }
1853 }
1854 }
1855
1856
1857 void MMVariableEmbeddingInserter::findSourcesAndTargets(
1858 node src, node tgt,
1859 NodeSet &sources,
1860 NodeSet &targets) const
1861 {
1862 collectAnchorNodes(src, sources, 0);
1863 collectAnchorNodes(tgt, targets, 0);
1864 }
1865
1866
1867 void MMVariableEmbeddingInserter::anchorNodes(
1868 node vOrig,
1869 NodeSet &nodes) const
1870 {
1871 node vFirst = m_pPG->expansion(vOrig).front();
1872 if(m_pPG->splittableOrig(vOrig) == true)
1873 collectAnchorNodes(vFirst, nodes, 0);
1874 else
1875 nodes.insert(vFirst);
1876 }
1877
1878
1879 node MMVariableEmbeddingInserter::commonDummy(
1880 NodeSet &sources,
1881 NodeSet &targets)
1882 {
1883 ListConstIterator<node> it;
1884 for(it = sources.nodes().begin(); it.valid(); ++it)
1885 if(targets.isMember(*it))
1886 return *it;
1887
1888 return 0;
1889 }
1890
1891
1892
1893 } // end namespace ogdf
Windows Explorer Extension to Operate Git