6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of class PlanRepExpansion.
12 * \author Carsten Gutwenger
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
44 #include <ogdf/planarity/PlanRepExpansion.h>
45 #include <ogdf/basic/simple_graph_alg.h>
46 #include <ogdf/basic/extended_graph_alg.h>
47 #include <ogdf/basic/CombinatorialEmbedding.h>
48 #include <ogdf/basic/FaceSet.h>
49 #include <ogdf/basic/NodeSet.h>
54 PlanRepExpansion::PlanRepExpansion(const Graph
& G
)
56 List
<node
> splittableNodes
;
60 splittableNodes
.pushBack(v
);
63 doInit(G
,splittableNodes
);
66 PlanRepExpansion::PlanRepExpansion(const Graph
& G
, const List
<node
> &splittableNodes
)
68 doInit(G
,splittableNodes
);
71 void PlanRepExpansion::doInit(const Graph
&G
, const List
<node
> &splittableNodes
)
76 // compute connected component of G
77 NodeArray
<int> component(G
);
78 m_numCC
= connectedComponents(G
,component
);
80 // intialize the array of lists of nodes contained in a CC
81 m_nodesInCC
.init(m_numCC
);
85 m_nodesInCC
[component
[v
]].pushBack(v
);
87 m_currentCC
= -1; // not yet initialized
91 m_vOrig
.init(*this,0);
92 m_eOrig
.init(*this,0);
93 m_vIterator
.init(*this,0);
94 m_eIterator
.init(*this,0);
96 m_splittable
.init(*this,false);
97 m_splittableOrig
.init(G
,false);
98 m_eNodeSplit
.init(*this,0);
100 ListConstIterator
<node
> it
;
101 for(it
= splittableNodes
.begin(); it
.valid(); ++it
)
102 if((*it
)->degree() >= 4)
103 m_splittableOrig
[*it
] = true;
107 void PlanRepExpansion::initCC(int i
)
109 // delete copy / chain fields for originals of nodes in current cc
110 // (since we remove all these copies in initByNodes(...)
111 if (m_currentCC
>= 0)
113 const List
<node
> &origInCC
= nodesInCC(i
);
114 ListConstIterator
<node
> itV
;
116 for(itV
= origInCC
.begin(); itV
.valid(); ++itV
)
124 if ((adj
->index() & 1) == 0) continue;
125 edge eG
= adj
->theEdge();
134 NodeArray
<node
> vCopy(*m_pGraph
);
135 Graph::constructInitByNodes(*m_pGraph
,m_nodesInCC
[i
],vCopy
,m_eAuxCopy
);
137 ListConstIterator
<node
> itV
;
138 for(itV
= m_nodesInCC
[i
].begin(); itV
.valid(); ++itV
)
141 node v
= vCopy
[vOrig
];
144 m_vIterator
[v
] = m_vCopy
[vOrig
].pushBack(v
);
145 m_splittable
[v
] = m_splittableOrig
[vOrig
];
148 forall_adj(adj
,vOrig
) {
149 if ((adj
->index() & 1) == 0) {
150 edge e
= adj
->theEdge();
151 m_eIterator
[m_eAuxCopy
[e
]] = m_eCopy
[e
].pushBack(m_eAuxCopy
[e
]);
152 m_eOrig
[m_eAuxCopy
[e
]] = e
;
157 m_nodeSplits
.clear();
161 void PlanRepExpansion::delCopy(edge e
)
163 edge eOrig
= m_eOrig
[e
];
164 OGDF_ASSERT(m_eCopy
[eOrig
].size() == 1);
166 m_eCopy
[eOrig
].clear();
170 bool PlanRepExpansion::embed()
172 return planarEmbed(*this);
176 void PlanRepExpansion::prepareNodeSplit(
177 const SList
<adjEntry
> &partitionLeft
,
181 OGDF_ASSERT(!partitionLeft
.empty());
182 OGDF_ASSERT(partitionLeft
.front()->theNode()->degree() > partitionLeft
.size());
184 SListConstIterator
<adjEntry
> it
= partitionLeft
.begin();
188 for(++it
; it
.valid(); ++it
) {
189 moveAdjAfter(*it
,adj
);
193 adjRight
= adj
->cyclicSucc();
197 void PlanRepExpansion::insertEdgePath(
206 OGDF_ASSERT((eOrig
!= 0 && ns
== 0) || (eOrig
== 0 && ns
!= 0));
209 m_eCopy
[eOrig
].clear();
215 m_eIterator
[eSrc
] = m_eCopy
[eOrig
].pushBack(eSrc
);
216 m_eOrig
[eSrc
] = eOrig
;
218 m_eIterator
[eSrc
] = ns
->m_path
.pushBack(eSrc
);
219 m_eNodeSplit
[eSrc
] = ns
;
224 ListConstIterator
<Crossing
> it
;
225 for(it
= eip
.begin(); it
.valid(); ++it
)
227 adjEntry adj
= (*it
).m_adj
;
229 adjEntry adjLeft
, adjRight
;
230 prepareNodeSplit((*it
).m_partitionLeft
, adjLeft
, adjRight
);
232 node w
= splitNode(adjLeft
,adjRight
);
233 edge eNew
= adjLeft
->cyclicPred()->theEdge();
235 m_vIterator
[w
] = m_vCopy
[m_vOrig
[adjLeft
->theNode()]].pushBack(w
);
236 m_splittable
[w
] = true;
237 m_vOrig
[w
] = m_vOrig
[adjLeft
->theNode()];
239 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
240 (*itNS
).m_nsIterator
= itNS
;
241 m_eIterator
[eNew
] = (*itNS
).m_path
.pushBack(eNew
);
242 m_eNodeSplit
[eNew
] = &(*itNS
);
244 adj
= adjRight
->cyclicPred();
247 node u
= split(adj
->theEdge())->source();
248 edge eNew
= newEdge(v
,u
);
251 m_eIterator
[eNew
] = m_eCopy
[eOrig
].pushBack(eNew
);
252 m_eOrig
[eNew
] = eOrig
;
254 m_eIterator
[eNew
] = ns
->m_path
.pushBack(eNew
);
255 m_eNodeSplit
[eNew
] = ns
;
261 edge eNew
= newEdge(v
,vEnd
);
263 m_eIterator
[eNew
] = m_eCopy
[eOrig
].pushBack(eNew
);
264 m_eOrig
[eNew
] = eOrig
;
266 m_eIterator
[eNew
] = ns
->m_path
.pushBack(eNew
);
267 m_eNodeSplit
[eNew
] = ns
;
272 m_eIterator
[eTgt
] = m_eCopy
[eOrig
].pushBack(eTgt
);
273 m_eOrig
[eTgt
] = eOrig
;
275 m_eIterator
[eTgt
] = ns
->m_path
.pushBack(eTgt
);
276 m_eNodeSplit
[eTgt
] = ns
;
282 void PlanRepExpansion::insertEdgePathEmbedded(
285 CombinatorialEmbedding
&E
,
286 const List
<Tuple2
<adjEntry
,adjEntry
> > &crossedEdges
)
288 OGDF_ASSERT((eOrig
!= 0 && ns
== 0) || (eOrig
== 0 && ns
!= 0));
291 m_eCopy
[eOrig
].clear();
295 adjEntry adjSrc
, adjTgt
;
296 ListConstIterator
<Tuple2
<adjEntry
,adjEntry
> > it
= crossedEdges
.begin();
297 ListConstIterator
<Tuple2
<adjEntry
,adjEntry
> > itLast
= crossedEdges
.rbegin();
299 // iterate over all adjacency entries in crossedEdges except for first
302 for(++it
; it
!= itLast
; ++it
)
304 adjEntry adj
= (*it
).x1();
305 adjEntry adj2
= (*it
).x2();
308 OGDF_ASSERT(adj
->theNode() == adj2
->theNode());
309 OGDF_ASSERT(E
.rightFace(adjSrc
) == E
.rightFace(adj
->twin()));
310 node w
= E
.splitNode(adj
,adj2
);
311 edge eNew
= adj
->cyclicPred()->theEdge();
313 m_vIterator
[w
] = m_vCopy
[m_vOrig
[adj
->theNode()]].pushBack(w
);
314 m_splittable
[w
] = true;
315 m_vOrig
[w
] = m_vOrig
[adj
->theNode()];
317 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
318 (*itNS
).m_nsIterator
= itNS
;
319 m_eIterator
[eNew
] = (*itNS
).m_path
.pushBack(eNew
);
320 m_eNodeSplit
[eNew
] = &(*itNS
);
322 adj
= adj2
->cyclicPred();
326 node u
= E
.split(adj
->theEdge())->source();
328 // determine target adjacency entry and source adjacency entry
329 // in the next iteration step
330 adjTgt
= u
->firstAdj();
331 adjEntry adjSrcNext
= adjTgt
->succ();
333 if (adjTgt
!= adj
->twin())
334 swap(adjTgt
,adjSrcNext
);
336 OGDF_ASSERT(adjTgt
== adj
->twin());
338 // insert a new edge into the face
339 edge eNew
= E
.splitFace(adjSrc
,adjTgt
);
342 m_eIterator
[eNew
] = m_eCopy
[eOrig
].pushBack(eNew
);
343 m_eOrig
[eNew
] = eOrig
;
345 m_eIterator
[eNew
] = ns
->m_path
.pushBack(eNew
);
346 m_eNodeSplit
[eNew
] = ns
;
353 edge eNew
= E
.splitFace(adjSrc
,(*it
).x1());
356 m_eIterator
[eNew
] = m_eCopy
[eOrig
].pushBack(eNew
);
357 m_eOrig
[eNew
] = eOrig
;
359 m_eIterator
[eNew
] = ns
->m_path
.pushBack(eNew
);
360 m_eNodeSplit
[eNew
] = ns
;
365 void PlanRepExpansion::removeEdgePathEmbedded(
366 CombinatorialEmbedding
&E
,
369 FaceSetPure
&newFaces
,
370 NodeSetPure
&mergedNodes
,
374 OGDF_ASSERT((eOrig
!= 0 && ns
== 0) || (eOrig
== 0 && ns
!= 0));
376 const List
<edge
> &path
= (eOrig
) ? m_eCopy
[eOrig
] : ns
->m_path
;
377 ListConstIterator
<edge
> it
= path
.begin();
379 oldSrc
= path
.front()->source();
380 oldTgt
= path
.back()->target();
382 newFaces
.insert(E
.joinFaces(*it
));
384 for(++it
; it
.valid(); ++it
)
387 node u
= e
->source();
389 newFaces
.remove(E
.rightFace(e
->adjSource()));
390 newFaces
.remove(E
.rightFace(e
->adjTarget()));
392 newFaces
.insert(E
.joinFaces(e
));
394 edge eIn
= u
->firstAdj()->theEdge();
395 edge eOut
= u
->lastAdj()->theEdge();
396 if (eIn
->target() != u
)
402 node v
= eIn
->target();
404 node vOrig
= m_vOrig
[v
];
405 if(vOrig
!= 0 && m_vOrig
[u
] == vOrig
) {
406 m_vCopy
[vOrig
].del(m_vIterator
[v
]);
407 ListIterator
<NodeSplit
> itNS
= m_eNodeSplit
[eIn
]->m_nsIterator
;
408 m_nodeSplits
.del(itNS
);
412 if(mergedNodes
.isMember(v
))
413 mergedNodes
.remove(v
);
414 mergedNodes
.insert(u
);
416 if(oldSrc
== v
) oldSrc
= u
;
417 if(oldTgt
== v
) oldTgt
= u
;
422 m_eCopy
[eOrig
].clear();
428 void PlanRepExpansion::removeEdgePath(
434 OGDF_ASSERT((eOrig
!= 0 && ns
== 0) || (eOrig
== 0 && ns
!= 0));
436 const List
<edge
> &path
= (eOrig
) ? m_eCopy
[eOrig
] : ns
->m_path
;
437 ListConstIterator
<edge
> it
= path
.begin();
439 oldSrc
= path
.front()->source();
440 oldTgt
= path
.back()->target();
444 for(++it
; it
.valid(); ++it
)
447 node u
= e
->source();
451 edge eIn
= u
->firstAdj()->theEdge();
452 edge eOut
= u
->lastAdj()->theEdge();
453 if (eIn
->target() != u
)
459 node v
= eIn
->target();
461 node vOrig
= m_vOrig
[v
];
462 if(vOrig
!= 0 && m_vOrig
[u
] == vOrig
) {
463 m_vCopy
[vOrig
].del(m_vIterator
[v
]);
464 ListIterator
<NodeSplit
> itNS
= m_eNodeSplit
[eIn
]->m_nsIterator
;
465 m_nodeSplits
.del(itNS
);
469 if(oldSrc
== v
) oldSrc
= u
;
470 if(oldTgt
== v
) oldTgt
= u
;
475 m_eCopy
[eOrig
].clear();
481 void PlanRepExpansion::contractSplit(nodeSplit ns
, CombinatorialEmbedding
&E
)
483 OGDF_ASSERT(ns
->m_path
.size() == 1);
485 edge e
= ns
->m_path
.front();
486 node v
= e
->target();
487 node vOrig
= m_vOrig
[v
];
489 m_vCopy
[vOrig
].del(m_vIterator
[v
]);
490 ListIterator
<NodeSplit
> itNS
= ns
->m_nsIterator
;
491 m_nodeSplits
.del(itNS
);
497 void PlanRepExpansion::contractSplit(nodeSplit ns
)
499 OGDF_ASSERT(ns
->m_path
.size() == 1);
501 edge e
= ns
->m_path
.front();
502 node v
= e
->target();
503 node vOrig
= m_vOrig
[v
];
505 m_vCopy
[vOrig
].del(m_vIterator
[v
]);
506 ListIterator
<NodeSplit
> itNS
= ns
->m_nsIterator
;
507 m_nodeSplits
.del(itNS
);
513 int PlanRepExpansion::computeNumberOfCrossings() const
518 forall_nodes(v
,*this)
526 edge
PlanRepExpansion::split(edge e
)
528 edge eNew
= Graph::split(e
);
529 edge eOrig
= m_eOrig
[e
];
530 NodeSplit
*ns
= m_eNodeSplit
[e
];
532 if ((m_eOrig
[eNew
] = eOrig
) != 0) {
533 m_eIterator
[eNew
] = m_eCopy
[eOrig
].insert(eNew
,m_eIterator
[e
],after
);
535 } else if ((m_eNodeSplit
[eNew
] = ns
) != 0) {
536 m_eIterator
[eNew
] = ns
->m_path
.insert(eNew
,m_eIterator
[e
],after
);
543 void PlanRepExpansion::unsplit(edge eIn
, edge eOut
)
545 edge eOrig
= m_eOrig
[eOut
];
546 NodeSplit
*ns
= m_eNodeSplit
[eOut
];
548 // update chain of eOrig if eOrig exists
550 m_eCopy
[eOrig
].del(m_eIterator
[eOut
]);
552 } else if (ns
!= 0) {
553 ns
->m_path
.del(m_eIterator
[eOut
]);
556 Graph::unsplit(eIn
,eOut
);
560 edge
PlanRepExpansion::unsplitExpandNode(
564 CombinatorialEmbedding
&E
)
566 NodeSplit
*ns
= m_eNodeSplit
[eContract
];
567 List
<edge
> &path
= ns
->m_path
;
569 NodeSplit
*nsExp
= m_eNodeSplit
[eExpand
];
570 edge eOrigExp
= m_eOrig
[eExpand
];
571 List
<edge
> &pathExp
= (nsExp
!= 0) ? nsExp
->m_path
: m_eCopy
[eOrigExp
];
573 if((eExpand
->target() == u
&& eContract
->source() != u
) ||
574 (eExpand
->source() == u
&& eContract
->target() != u
))
576 // reverse path of eContract
577 ListConstIterator
<edge
> it
;
578 for(it
= path
.begin(); it
.valid(); ++it
) {
584 // remove u from list of copy nodes of its original
585 m_vCopy
[m_vOrig
[u
]].del(m_vIterator
[u
]);
587 // unsplit u and enlarge edge path of eOrigExp
589 if(eExpand
->target() == u
) {
591 E
.unsplit(eExpand
,eContract
);
593 ListConstIterator
<edge
> it
;
594 for(it
= path
.begin(); it
.valid(); ++it
) {
595 m_eNodeSplit
[*it
] = nsExp
;
596 m_eOrig
[*it
] = eOrigExp
;
603 E
.unsplit(eContract
,eExpand
);
605 ListConstIterator
<edge
> it
;
606 for(it
= path
.begin(); it
.valid(); ++it
) {
607 m_eNodeSplit
[*it
] = nsExp
;
608 m_eOrig
[*it
] = eOrigExp
;
611 pathExp
.concFront(path
);
614 m_nodeSplits
.del(ns
->m_nsIterator
);
619 edge
PlanRepExpansion::unsplitExpandNode(
624 NodeSplit
*ns
= m_eNodeSplit
[eContract
];
625 List
<edge
> &path
= ns
->m_path
;
627 NodeSplit
*nsExp
= m_eNodeSplit
[eExpand
];
628 edge eOrigExp
= m_eOrig
[eExpand
];
629 List
<edge
> &pathExp
= (nsExp
!= 0) ? nsExp
->m_path
: m_eCopy
[eOrigExp
];
631 if((eExpand
->target() == u
&& eContract
->source() != u
) ||
632 (eExpand
->source() == u
&& eContract
->target() != u
))
634 // reverse path of eContract
635 ListConstIterator
<edge
> it
;
636 for(it
= path
.begin(); it
.valid(); ++it
) {
642 // remove u from list of copy nodes of its original
643 m_vCopy
[m_vOrig
[u
]].del(m_vIterator
[u
]);
645 // unsplit u and enlarge edge path of eOrigExp
647 if(eExpand
->target() == u
) {
649 unsplit(eExpand
,eContract
);
651 ListConstIterator
<edge
> it
;
652 for(it
= path
.begin(); it
.valid(); ++it
) {
653 m_eNodeSplit
[*it
] = nsExp
;
654 m_eOrig
[*it
] = eOrigExp
;
661 unsplit(eContract
,eExpand
);
663 ListConstIterator
<edge
> it
;
664 for(it
= path
.begin(); it
.valid(); ++it
) {
665 m_eNodeSplit
[*it
] = nsExp
;
666 m_eOrig
[*it
] = eOrigExp
;
669 pathExp
.concFront(path
);
672 m_nodeSplits
.del(ns
->m_nsIterator
);
677 edge
PlanRepExpansion::enlargeSplit(
681 node vOrig
= m_vOrig
[v
];
682 edge eOrig
= m_eOrig
[e
];
684 edge eNew
= split(e
);
685 node u
= e
->target();
687 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
688 nodeSplit ns
= &(*itNS
);
689 ns
->m_nsIterator
= itNS
;
692 m_vIterator
[u
] = m_vCopy
[vOrig
].pushBack(u
);
693 m_splittable
[u
] = true;
695 List
<edge
> &path
= m_eCopy
[eOrig
];
696 if(v
== path
.front()->source()) {
697 ListIterator
<edge
> it
, itNext
;
698 for(it
= path
.begin(); *it
!= eNew
; it
= itNext
) {
701 path
.moveToBack(it
, ns
->m_path
);
703 m_eNodeSplit
[*it
] = ns
;
707 ListIterator
<edge
> it
, itNext
;
708 for(it
= m_eIterator
[eNew
]; it
.valid(); it
= itNext
) {
711 path
.moveToBack(it
, ns
->m_path
);
713 m_eNodeSplit
[*it
] = ns
;
721 edge
PlanRepExpansion::enlargeSplit(
724 CombinatorialEmbedding
&E
)
726 node vOrig
= m_vOrig
[v
];
727 edge eOrig
= m_eOrig
[e
];
729 edge eNew
= E
.split(e
);
730 node u
= e
->target();
732 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
733 nodeSplit ns
= &(*itNS
);
734 ns
->m_nsIterator
= itNS
;
737 m_vIterator
[u
] = m_vCopy
[vOrig
].pushBack(u
);
738 m_splittable
[u
] = true;
740 List
<edge
> &path
= m_eCopy
[eOrig
];
741 if(v
== path
.front()->source()) {
742 ListIterator
<edge
> it
, itNext
;
743 for(it
= path
.begin(); *it
!= eNew
; it
= itNext
) {
746 path
.moveToBack(it
, ns
->m_path
);
748 m_eNodeSplit
[*it
] = ns
;
752 ListIterator
<edge
> it
, itNext
;
753 for(it
= m_eIterator
[eNew
]; it
.valid(); it
= itNext
) {
756 path
.moveToBack(it
, ns
->m_path
);
758 m_eNodeSplit
[*it
] = ns
;
766 edge
PlanRepExpansion::splitNodeSplit(edge e
)
768 nodeSplit ns
= m_eNodeSplit
[e
];
769 node vOrig
= m_vOrig
[ns
->source()];
771 edge eNew
= split(e
);
772 node u
= e
->target();
774 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
775 nodeSplit nsNew
= &(*itNS
);
776 nsNew
->m_nsIterator
= itNS
;
779 m_vIterator
[u
] = m_vCopy
[vOrig
].pushBack(u
);
780 m_splittable
[u
] = true;
782 List
<edge
> &path
= ns
->m_path
;
783 path
.split(m_eIterator
[eNew
], path
, nsNew
->m_path
);
785 ListIterator
<edge
> it
;
786 for(it
= nsNew
->m_path
.begin(); it
.valid(); ++it
) {
787 m_eNodeSplit
[*it
] = nsNew
;
794 edge
PlanRepExpansion::splitNodeSplit(
796 CombinatorialEmbedding
&E
)
798 nodeSplit ns
= m_eNodeSplit
[e
];
799 node vOrig
= m_vOrig
[ns
->source()];
801 edge eNew
= E
.split(e
);
802 node u
= e
->target();
804 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
805 nodeSplit nsNew
= &(*itNS
);
806 nsNew
->m_nsIterator
= itNS
;
809 m_vIterator
[u
] = m_vCopy
[vOrig
].pushBack(u
);
810 m_splittable
[u
] = true;
812 List
<edge
> &path
= ns
->m_path
;
813 path
.split(m_eIterator
[eNew
], path
, nsNew
->m_path
);
815 ListIterator
<edge
> it
;
816 for(it
= nsNew
->m_path
.begin(); it
.valid(); ++it
) {
817 m_eNodeSplit
[*it
] = nsNew
;
824 void PlanRepExpansion::removeSelfLoop(
826 CombinatorialEmbedding
&E
)
828 node u
= e
->source();
829 nodeSplit ns
= m_eNodeSplit
[e
];
830 edge eOrig
= m_eOrig
[e
];
832 List
<edge
> &path
= (eOrig
!= 0) ? m_eCopy
[eOrig
] : ns
->m_path
;
833 path
.del(m_eIterator
[e
]);
837 edge eIn
= u
->firstAdj()->theEdge();
838 edge eOut
= u
->lastAdj ()->theEdge();
839 if(eIn
->target() != u
) swap(eIn
,eOut
);
841 OGDF_ASSERT(ns
== m_eNodeSplit
[eOut
] && eOrig
== m_eOrig
[eOut
]);
847 void PlanRepExpansion::removeSelfLoop(edge e
)
849 node u
= e
->source();
850 nodeSplit ns
= m_eNodeSplit
[e
];
851 edge eOrig
= m_eOrig
[e
];
853 List
<edge
> &path
= (eOrig
!= 0) ? m_eCopy
[eOrig
] : ns
->m_path
;
854 path
.del(m_eIterator
[e
]);
858 edge eIn
= u
->firstAdj()->theEdge();
859 edge eOut
= u
->lastAdj ()->theEdge();
860 if(eIn
->target() != u
) swap(eIn
,eOut
);
862 OGDF_ASSERT(ns
== m_eNodeSplit
[eOut
] && eOrig
== m_eOrig
[eOut
]);
868 bool PlanRepExpansion::consistencyCheck() const
870 if(Graph::consistencyCheck() == false)
873 if(isLoopFree(*this) == false)
877 forall_edges(eOrig
,*m_pGraph
) {
878 const List
<edge
> &path
= m_eCopy
[eOrig
];
879 ListConstIterator
<edge
> it
;
880 for(it
= path
.begin(); it
.valid(); ++it
) {
882 if(it
!= path
.begin()) {
883 if(e
->source()->degree() != 4)
885 if(e
->source() != (*it
.pred())->target())
892 forall_nodes(vOrig
,*m_pGraph
) {
893 const List
<node
> &nodes
= m_vCopy
[vOrig
];
895 if(nodes
.size() == 1)
896 if(m_splittable
[nodes
.front()] != m_splittableOrig
[vOrig
])
899 if(nodes
.size() <= 1) continue;
901 if(m_splittableOrig
[vOrig
] == false)
904 ListConstIterator
<node
> it
;
905 for(it
= nodes
.begin(); it
.valid(); ++it
) {
912 EdgeArray
<const NodeSplit
*> nso(*this,0);
914 ListConstIterator
<NodeSplit
> it
;
915 for(it
= m_nodeSplits
.begin(); it
.valid(); ++it
) {
916 const NodeSplit
&ns
= *it
;
918 if(ns
.m_path
.size() == 0)
921 node v
= ns
.source();
922 node w
= ns
.target();
924 node vOrig
= m_vOrig
[v
];
925 if(vOrig
== 0 || vOrig
!= m_vOrig
[w
])
928 if(m_splittable
[v
] == false || m_splittable
[w
] == false)
931 const List
<edge
> &path
= ns
.m_path
;
932 ListConstIterator
<edge
> itE
;
933 for(itE
= path
.begin(); itE
.valid(); ++itE
) {
936 if(itE
!= path
.begin()) {
937 if(e
->source()->degree() != 4)
939 if(e
->source() != (*itE
.pred())->target())
946 forall_edges(e
,*this) {
947 if(nso
[e
] != m_eNodeSplit
[e
])
955 List
<edge
> &PlanRepExpansion::setOrigs(edge e
, edge
&eOrig
, nodeSplit
&ns
)
958 ns
= m_eNodeSplit
[e
];
959 return (eOrig
!= 0) ? m_eCopy
[eOrig
] : ns
->m_path
;
963 PlanRepExpansion::nodeSplit
PlanRepExpansion::convertDummy(
966 PlanRepExpansion::nodeSplit ns_0
)
968 OGDF_ASSERT(u
->indeg() == 2 && u
->outdeg() == 2 && m_vOrig
[u
] == 0);
971 m_vIterator
[u
] = m_vCopy
[vOrig
].pushBack(u
);
972 m_splittable
[u
] = true;
974 edge ec
[2], eOrig
[2];
975 PlanRepExpansion::nodeSplit nsplit
[2];
978 forall_adj_edges(e
,u
)
979 if(e
->source() == u
) {
981 eOrig
[i
] = m_eOrig
[e
];
982 nsplit
[i
] = m_eNodeSplit
[e
];
986 List
<edge
> &path_0
= (eOrig
[0] != 0) ? m_eCopy
[eOrig
[0]] : nsplit
[0]->m_path
;
987 if(m_vOrig
[path_0
.front()->source()] == vOrig
)
988 path_0
.split(m_eIterator
[ec
[0]], ns_0
->m_path
, path_0
);
990 path_0
.split(m_eIterator
[ec
[0]], path_0
, ns_0
->m_path
);
992 ListConstIterator
<edge
> itE
;
993 for(itE
= ns_0
->m_path
.begin(); itE
.valid(); ++itE
) {
994 m_eNodeSplit
[*itE
] = ns_0
;
998 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
999 nodeSplit ns_1
= &(*itNS
);
1000 ns_1
->m_nsIterator
= itNS
;
1002 List
<edge
> &path_1
= (eOrig
[1] != 0) ? m_eCopy
[eOrig
[1]] : nsplit
[1]->m_path
;
1003 if(m_vOrig
[path_1
.front()->source()] == vOrig
)
1004 path_1
.split(m_eIterator
[ec
[1]], ns_1
->m_path
, path_1
);
1006 path_1
.split(m_eIterator
[ec
[1]], path_1
, ns_1
->m_path
);
1008 for(itE
= ns_1
->m_path
.begin(); itE
.valid(); ++itE
) {
1009 m_eNodeSplit
[*itE
] = ns_1
;
1017 edge
PlanRepExpansion::separateDummy(
1018 adjEntry adj_1
, adjEntry adj_2
, node vStraight
, bool isSrc
)
1020 node u
= adj_1
->theNode();
1021 OGDF_ASSERT(m_vOrig
[u
] == 0);
1023 node vOrig
= m_vOrig
[vStraight
];
1026 m_vOrig
[v
] = vOrig
;
1027 m_vIterator
[v
] = m_vCopy
[vOrig
].pushBack(v
);
1028 m_splittable
[v
] = true;
1030 if(adj_1
->theEdge()->target() == u
)
1031 moveTarget(adj_1
->theEdge(),v
);
1033 moveSource(adj_1
->theEdge(),v
);
1035 if(adj_2
->theEdge()->target() == u
)
1036 moveTarget(adj_2
->theEdge(),v
);
1038 moveSource(adj_2
->theEdge(),v
);
1040 edge eNew
= (isSrc
) ? newEdge(v
,u
) : newEdge(u
,v
);
1042 ListIterator
<NodeSplit
> itNS
= m_nodeSplits
.pushBack(NodeSplit());
1043 nodeSplit nsNew
= &(*itNS
);
1044 nsNew
->m_nsIterator
= itNS
;
1046 edge eOrig
= m_eOrig
[adj_1
->theEdge()];
1047 NodeSplit
*ns
= m_eNodeSplit
[adj_1
->theEdge()];
1048 List
<edge
> &path
= (eOrig
!= 0) ? m_eCopy
[eOrig
] : ns
->m_path
;
1050 if(vStraight
== path
.front()->source()) {
1051 ListIterator
<edge
> it
, itNext
;
1052 for(it
= path
.begin(); (*it
)->source() != v
; it
= itNext
) {
1054 path
.moveToBack(it
, nsNew
->m_path
);
1056 m_eNodeSplit
[*it
] = nsNew
;
1060 ListIterator
<edge
> it
, itPrev
;
1061 for(it
= path
.rbegin(); (*it
)->target() != v
; it
= itPrev
) {
1063 path
.moveToFront(it
, nsNew
->m_path
);
1065 m_eNodeSplit
[*it
] = nsNew
;
1071 //edge eOrig = m_eOrig[adjStraight->theEdge()];
1072 //NodeSplit *ns = m_eNodeSplit[adjStraight->theEdge()];
1074 //Array<adjEntry> adjA(2), adjB(2);
1078 //forall_adj(adj,u) {
1079 // edge e = adj->theEdge();
1080 // if(m_eOrig[e] == eOrig && m_eNodeSplit[e] == ns)
1086 //OGDF_ASSERT(i == 2 && j == 2);
1088 //// resolve split on adjB
1089 //edge eB = adjB[0]->theEdge();
1090 //node vB = adjB[1]->twinNode();
1094 //List<edge> &pathB = (m_eOrig[eB] != 0) ? m_eCopy[m_eOrig[eB]] : m_eNodeSplit[eB]->m_path;
1096 //if(eB->target() == u)
1097 // moveTarget(eB,vB);
1099 // moveSource(eB,vB);
1101 //edge eB2 = adjB[1]->theEdge();
1102 //pathB.del(m_eIterator[eB2]);
1105 //// split path at u
1106 //node vOrig = m_vOrig[vStraight];
1108 //m_vOrig [u] = vOrig;
1109 //m_vIterator [u] = m_vCopy[vOrig].pushBack(u);
1110 //m_splittable[u] = true;
1112 //ListIterator<NodeSplit> itNS = m_nodeSplits.pushBack(NodeSplit());
1113 //nodeSplit nsNew = &(*itNS);
1114 //nsNew->m_nsIterator = itNS;
1116 //List<edge> &pathA = (eOrig != 0) ? m_eCopy[eOrig] : ns->m_path;
1117 //if(vStraight == pathA.front()->source()) {
1118 // ListIterator<edge> it, itNext;
1119 // for(it = pathA.begin(); (*it)->source() != u; it = itNext) {
1120 // itNext = it.succ();
1121 // pathA.moveToBack(it, nsNew->m_path);
1122 // m_eOrig [*it] = 0;
1123 // m_eNodeSplit[*it] = nsNew;
1127 // ListIterator<edge> it, itPrev;
1128 // for(it = pathA.rbegin(); (*it)->target() != u; it = itPrev) {
1129 // itPrev = it.pred();
1130 // pathA.moveToFront(it, nsNew->m_path);
1131 // m_eOrig [*it] = 0;
1132 // m_eNodeSplit[*it] = nsNew;
1138 int PlanRepExpansion::numberOfSplittedNodes() const
1143 forall_nodes(vOrig
,*m_pGraph
)
1144 if(m_vCopy
[vOrig
].size() >= 2)
1151 bool PlanRepExpansion::isPseudoCrossing(node v
) const
1156 adjEntry adj_1
= v
->firstAdj();
1157 adjEntry adj_2
= adj_1
->succ();
1158 adjEntry adj_3
= adj_2
->succ();
1160 edge eOrig
= m_eOrig
[adj_2
->theEdge()];
1161 nodeSplit ns
= m_eNodeSplit
[adj_2
->theEdge()];
1163 if(m_eNodeSplit
[adj_1
->theEdge()] == ns
&& m_eOrig
[adj_1
->theEdge()] == eOrig
)
1166 if(m_eNodeSplit
[adj_3
->theEdge()] == ns
&& m_eOrig
[adj_3
->theEdge()] == eOrig
)
1173 void PlanRepExpansion::resolvePseudoCrossing(node v
)
1175 OGDF_ASSERT(isPseudoCrossing(v
));
1180 forall_adj_edges(e
,v
) {
1181 if(e
->target() == v
)
1184 OGDF_ASSERT(i
== 2);
1186 for(i
= 0; i
< 2; ++i
) {
1189 ListIterator
<edge
> it
= m_eIterator
[e
];
1190 List
<edge
> &path
= (m_eOrig
[e
] != 0) ? m_eCopy
[m_eOrig
[e
]] : m_eNodeSplit
[e
]->m_path
;
1192 edge eNext
= *(it
.succ());
1193 moveSource(eNext
, e
->source());
1201 } // end namespace ogdf