6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief Implements class UpwardPlanarModule...
12 * ...which represents the upward-planarity testing and embedding
13 * algorithm for single-source digraphs.
14 * Reference: "Optimal upward planarity testing of single-source
15 * digraphs" P. Bertolazzi, G. Di Battista, C. Mannino, and
16 * R. Tamassia, SIAM J.Comput., 27(1) Feb. 1998, pp. 132-169
19 * \author Carsten Gutwenger
22 * This file is part of the Open Graph Drawing Framework (OGDF).
26 * See README.txt in the root directory of the OGDF installation for details.
29 * This program is free software; you can redistribute it and/or
30 * modify it under the terms of the GNU General Public License
31 * Version 2 or 3 as published by the Free Software Foundation;
32 * see the file LICENSE.txt included in the packaging of this file
36 * This program is distributed in the hope that it will be useful,
37 * but WITHOUT ANY WARRANTY; without even the implied warranty of
38 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
39 * GNU General Public License for more details.
42 * You should have received a copy of the GNU General Public
43 * License along with this program; if not, write to the Free
44 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
45 * Boston, MA 02110-1301, USA.
47 * \see http://www.gnu.org/copyleft/gpl.html
48 ***************************************************************/
51 #include <ogdf/upward/UpwardPlanarModule.h>
52 #include <ogdf/upward/FaceSinkGraph.h>
53 #include <ogdf/upward/ExpansionGraph.h>
54 #include <ogdf/decomposition/StaticPlanarSPQRTree.h>
55 #include <ogdf/basic/extended_graph_alg.h>
56 #include <ogdf/basic/simple_graph_alg.h>
57 #include <ogdf/upward/UpwardPlanarizationLayout.h>
63 //---------------------------------------------------------
65 //---------------------------------------------------------
66 class UpwardPlanarModule::SkeletonInfo
70 SkeletonInfo(const Skeleton
&S
) :
71 m_degInfo(S
.getGraph()), m_containsSource(S
.getGraph(),false)
74 void init(const Skeleton
&S
) {
75 m_degInfo
.init(S
.getGraph());
76 m_containsSource
.init(S
.getGraph(),false);
79 EdgeArray
<DegreeInfo
> m_degInfo
;
80 EdgeArray
<bool> m_containsSource
;
81 ConstCombinatorialEmbedding m_E
;
83 SList
<face
> m_externalFaces
;
88 //---------------------------------------------------------
90 // maintains constraints set during upward-planarity test
91 // on rooting of SPQR-tree
92 //---------------------------------------------------------
93 class UpwardPlanarModule::ConstraintRooting
96 ConstraintRooting(const SPQRTree
&T
);
98 // constrains a Q-node vQ associated with real edge e to be directed
100 void constrainRealEdge(edge e
);
102 // constrains a tree edge e in original SPQR-tree T to be directed
103 // leaving src; returns false iff e was already constrained to be directed
104 // in opposite direction
105 bool constrainTreeEdge(edge e
, node src
);
107 // if a roting satisfying all constraints exits, return a real edge at
108 // which the SPQR-tree can be rooted, otherwise 0 is returned
111 void outputConstraints(ostream
&os
);
113 // avoid automatic creation of assignment operator
114 ConstraintRooting
&operator=(const ConstraintRooting
&);
117 bool checkEdge(edge e
, node parent
, EdgeArray
<bool> &checked
);
119 Graph m_tree
; // tree with Q-nodes
120 const SPQRTree
&m_T
; // original SPQR-tree
122 // edge in m_tree corresponding to real edge
123 EdgeArray
<edge
> m_realToConstraint
;
124 // node in m_tree corresponding to node in original SPQR-tree T
125 NodeArray
<node
> m_internalNode
;
126 // edge in m_tree corresponding to edge in original SPQR-tree T
127 EdgeArray
<edge
> m_treeToConstraint
;
128 // true <=> edge in m_tree has been constrained
129 EdgeArray
<bool> m_isConstrained
;
134 // builds copy of SPQR-tree with Q-nodes
135 UpwardPlanarModule::ConstraintRooting::ConstraintRooting(const SPQRTree
&T
) :
136 m_T(T
), m_isConstrained(m_tree
,false)
138 const Graph
>
= T
.tree();
140 m_internalNode
.init(GT
);
144 m_internalNode
[v
] = m_tree
.newNode();
146 m_treeToConstraint
.init(GT
);
150 m_treeToConstraint
[e
] = m_tree
.newEdge(
151 m_internalNode
[e
->source()],m_internalNode
[e
->target()]);
154 // create Q-nodes and adjacent edges
155 const Graph
&G
= T
.originalGraph();
156 m_realToConstraint
.init(G
);
159 node qNode
= m_tree
.newNode();
160 node internal
= m_internalNode
[T
.skeletonOfReal(e
).treeNode()];
161 // An edge adjacent with a Q-node qNode is always directed leaving
162 // qNode because this is the only constraint used for those edges.
163 // If we have to constrain such an edge, we simply mark it constrained
164 // because it is already directed correctly.
165 m_realToConstraint
[e
] = m_tree
.newEdge(qNode
,internal
);
170 // output for debugging
171 void UpwardPlanarModule::ConstraintRooting::outputConstraints(ostream
&os
)
173 const Graph
&G
= m_T
.originalGraph();
174 const Graph
>
= m_T
.tree();
176 os
<< "constrained edges in tree:\n";
181 if (m_isConstrained
[m_realToConstraint
[e
]])
185 os
<< "\ntree edges:";
187 if (m_isConstrained
[m_treeToConstraint
[e
]]) {
188 if(m_internalNode
[e
->source()] == m_treeToConstraint
[e
]->source())
189 os
<< " " << e
->source() << "->" << e
->target();
191 os
<< " " << e
->target() << "->" << e
->source();
199 // constrains a real edge to be directed leaving its Q-node
200 // (such a Q-node cannot be selected as root node)
201 void UpwardPlanarModule::ConstraintRooting::constrainRealEdge(edge e
)
203 m_isConstrained
[m_realToConstraint
[e
]] = true;
207 // constrains a tree edge to be directed leaving src
208 // if it was already constrained to be directed in opposite direction
209 // false is returned and no rooting of the tree is possible
210 bool UpwardPlanarModule::ConstraintRooting::constrainTreeEdge(
214 OGDF_ASSERT(src
== e
->source() || src
== e
->target());
216 edge eTree
= m_treeToConstraint
[e
];
217 node srcTree
= m_internalNode
[src
];
219 // tree edge in wrong direction ?
220 if (srcTree
!= eTree
->source())
222 // if it was already constriant we have a contradiction
223 if (m_isConstrained
[eTree
] == true)
226 m_tree
.reverseEdge(eTree
);
229 m_isConstrained
[eTree
] = true;
234 // find a rooting of the tree satisfying all constraints
235 // if such a rooting exists, a root edge is returned (an edge in the
236 // original graph), otherwise 0 is returned
237 edge
UpwardPlanarModule::ConstraintRooting::findRooting()
239 EdgeArray
<bool> checked(m_tree
,false);
241 // we check each constrained edge
242 // such a constraint constrains the complete subtree rooted at
243 // e->source(), hence procedure checkEdge() recursively checks
244 // all (not-checked) edges in this subtree
246 forall_edges(e
,m_tree
) {
247 if (m_isConstrained
[e
]) {
248 if (checkEdge(e
,e
->target(),checked
) == false)
253 // if all constraints are checked, we can find a rooting iff there is
254 // a Q-node whose (only) adjacent edge was not constrained
255 const Graph
&G
= m_T
.originalGraph();
257 edge eQ
= m_realToConstraint
[e
];
259 if(checked
[eQ
] == false)
267 bool UpwardPlanarModule::ConstraintRooting::checkEdge(
270 EdgeArray
<bool> &checked
)
273 return (e
->target() == parent
);
275 if (e
->target() != parent
) {
276 if (m_isConstrained
[e
])
279 m_tree
.reverseEdge(e
);
283 node child
= e
->source();
286 forall_adj_edges(eAdj
,child
) {
288 if (checkEdge(eAdj
,child
,checked
) == false)
298 //---------------------------------------------------------
299 // UpwardPlanarModule
300 //---------------------------------------------------------
302 //---------------------------------------------------------
304 //---------------------------------------------------------
307 // tests if an embeddeding of a planar biconnected single-source graph is
308 // upward and, if it is, returns the list of possible external faces
309 // Remark: the external face which is set in E is ignored!
310 bool UpwardPlanarModule::testEmbeddedBiconnected(
311 const Graph
&G
, // embedded input graph
312 const ConstCombinatorialEmbedding
&E
, // embedding of G
313 SList
<face
> &externalFaces
) // returns list of possible external faces
315 OGDF_ASSERT(G
.representsCombEmbedding());
316 //OGDF_ASSERT(isBiconnected(G));
318 if(isAcyclic(G
) == false)
322 // the single source in G
323 node s
= getSingleSource(G
);
326 FaceSinkGraph
F(E
,s
);
328 // find possible external faces (the faces in T containing s)
329 externalFaces
.clear();
330 F
.possibleExternalFaces(externalFaces
);
332 return !externalFaces
.empty();
336 bool UpwardPlanarModule::testAndAugmentEmbedded(
337 Graph
&G
, // embedded input graph
338 SList
<node
> &augmentedNodes
,
339 SList
<edge
> &augmentedEdges
)
341 OGDF_ASSERT(G
.representsCombEmbedding());
343 if(isAcyclic(G
) == false)
346 // the single source in G
347 node s
= getSingleSource(G
);
350 ConstCombinatorialEmbedding
E(G
);
351 FaceSinkGraph
F(E
,s
);
353 // find possible external faces (the faces in T containing s)
354 SList
<face
> externalFaces
;
355 F
.possibleExternalFaces(externalFaces
);
357 if (externalFaces
.empty())
361 F
.stAugmentation(F
.faceNodeOf(externalFaces
.front()),G
,augmentedNodes
,augmentedEdges
);
368 bool UpwardPlanarModule::testAndAugmentEmbedded(
369 Graph
&G
, // embedded input graph
371 SList
<edge
> &augmentedEdges
)
373 OGDF_ASSERT(G
.representsCombEmbedding());
375 if(isAcyclic(G
) == false)
378 // the single source in G
379 node s
= getSingleSource(G
);
382 ConstCombinatorialEmbedding
E(G
);
383 FaceSinkGraph
F(E
,s
);
386 // find possible external faces (the faces in T containing s)
387 SList
<face
> externalFaces
;
388 F
.possibleExternalFaces(externalFaces
);
390 if (externalFaces
.empty())
394 F
.stAugmentation(F
.faceNodeOf(externalFaces
.front()),G
,superSink
,augmentedEdges
);
401 // finds the single source in G; if it does not exist, returns 0
402 node
UpwardPlanarModule::getSingleSource(const Graph
&G
)
404 node singleSource
= 0;
407 if (v
->indeg() == 0) {
408 if (singleSource
== 0)
410 else // we have more than one source!
420 //---------------------------------------------------------
422 //---------------------------------------------------------
424 // tests if a single-source digraph G is upward-planar
425 // computes sorted adjacency lists of an upward-planar embedding if
427 bool UpwardPlanarModule::doUpwardPlanarityTest(
430 NodeArray
<SListPure
<adjEntry
> > &adjacentEdges
)
432 // test whether G is acyclic
433 if (isAcyclic(G
) == false)
436 // build expansion graph of G
437 ExpansionGraph
exp(G
);
439 // determine single source; if not present (or several sources) test fails
440 node sG
= getSingleSource(G
);
444 // If embed is true we compute also the list of adjacency entries for each
445 // node of G in an upward planar embedding.
446 // Function testBiconnectedComponent() iterates over all biconnected
447 // components of exp starting with the components adjacent to the single
449 return testBiconnectedComponent(exp
,sG
,-1,embed
,adjacentEdges
);
453 // embeds single-source digraph G upward-planar
454 // also computes a planar st-augmentation of G and returns the list of
455 // augmented nodes and edges if augment is true
456 void UpwardPlanarModule::doUpwardPlanarityEmbed(
458 NodeArray
<SListPure
<adjEntry
> > &adjacentEdges
,
460 SList
<node
> &augmentedNodes
,
461 SList
<edge
> &augmentedEdges
)
465 G
.sort(vG
, adjacentEdges
[vG
]);
468 // the following tests check if the assigned embedding is upward planar
469 OGDF_ASSERT(G
.consistencyCheck());
470 OGDF_ASSERT(G
.representsCombEmbedding());
474 CombinatorialEmbedding
E(G
);
475 SList
<face
> externalFaces
;
476 OGDF_ASSERT(testEmbeddedBiconnected(G
,E
,externalFaces
));
483 bool isUpwardPlanar
=
485 testAndAugmentEmbedded(G
,augmentedNodes
,augmentedEdges
);
486 OGDF_ASSERT(isUpwardPlanar
);
491 // embeds single-source digraph G upward-planar
492 // also computes a planar st-augmentation of G and returns the list of
493 // augmented nodes and edges if augment is true
494 void UpwardPlanarModule::doUpwardPlanarityEmbed(
496 NodeArray
<SListPure
<adjEntry
> > &adjacentEdges
,
499 SList
<edge
> &augmentedEdges
)
503 G
.sort(vG
, adjacentEdges
[vG
]);
506 // the following tests check if the assigned embedding is upward planar
507 OGDF_ASSERT(G
.consistencyCheck());
508 OGDF_ASSERT(G
.representsCombEmbedding());
512 CombinatorialEmbedding
E(G
);
513 SList
<face
> externalFaces
;
514 OGDF_ASSERT(testEmbeddedBiconnected(G
,E
,externalFaces
));
521 bool isUpwardPlanar
=
523 testAndAugmentEmbedded(G
,superSink
,augmentedEdges
);
524 OGDF_ASSERT(isUpwardPlanar
);
529 // performs the actual test (and computation of sorted adjacency lists) for
530 // each biconnected component
531 // Within this procedure all biconnected components in which sG is (the
532 // original vertex) of the single-source are handled, for all other vertices
533 // in the biconnected component the procedure is called recursively.
534 // This kind of traversal is crucial for the embedding algorithm
535 bool UpwardPlanarModule::testBiconnectedComponent(
540 NodeArray
<SListPure
<adjEntry
> > &adjacentEdges
)
542 SListConstIterator
<int> itBlock
;
543 for(itBlock
= exp
.adjacentComponents(sG
).begin();
544 itBlock
.valid(); ++itBlock
)
547 if (i
== parentBlock
) continue;
551 // cannot construct SPQR-tree of graph with a single edge so treat
552 // it as special case here
553 if (exp
.numberOfNodes() == 2) {
554 edge eST
= exp
.original(exp
.firstEdge());
556 node src
= eST
->source();
557 node tgt
= eST
->target();
560 forall_edges(e
,exp
) {
561 edge eG
= exp
.original(e
);
562 adjacentEdges
[src
].pushBack(eG
->adjSource());
563 adjacentEdges
[tgt
].pushFront(eG
->adjTarget());
568 testBiconnectedComponent(exp
,eST
->target(),i
,embed
,adjacentEdges
);
575 // test whether expansion graph is planar
576 if (isPlanar(exp
) == false)
579 // construct SPQR-tree T of exp with embedded skeleton graphs
580 StaticPlanarSPQRTree
T(exp
);
581 const Graph
&tree
= T
.tree();
583 // skeleton info maintains precomputed information, i.e., degrees of
584 // nodes in expansion graph of virtual edges, if expansion graph
585 // constains the single source
586 NodeArray
<SkeletonInfo
> skInfo(tree
);
588 forall_nodes(vT
,tree
)
589 skInfo
[vT
].init(T
.skeleton(vT
));
591 // the single source in exp
592 node s
= exp
.copy(sG
);
593 OGDF_ASSERT(exp
.original(s
) == sG
);
595 // precompute information maintained in skInfo
596 // for each virtual edge e of a skeleton, determine its in- and
597 // outdegree in the pertinent digraph of e; also determine if the
598 // pertinent digraph of e contains the source
599 computeDegreesInPertinent(T
,s
,skInfo
,T
.rootNode());
601 OGDF_ASSERT_IF(dlConsistencyChecks
, checkDegrees(T
,s
,skInfo
));
603 // For each R-node vT:
604 // compute its sT-skeleton, test whether the sT-skeleton is upward-
606 // mark the virtual edges of skeleton(vT) whose endpoints are on the
607 // external face in some upward-drawing of the sT-skeleton of vT
608 // for each unmarked edge e of skeleton(vT), constrain the tree
609 // edge associated with e to be directed towards vT
610 // if the source is not in skeleton(vT), let wT be the node neighbour
611 // of vT whose pertinet digraph contains the source, and constrain
612 // the tree edge (vT.wT) to be directed towards wT
614 // Determine whether T can be rooted at a Q-node in such a way that
615 // orienting edges from children to parents satisfies the constraints
616 // above. Procedure directSkeletons() returns true iff such a rooting
618 edge eRoot
= directSkeletons(T
,skInfo
);
624 OGDF_ASSERT(exp
.consistencyCheck());
630 embedSkeleton(exp
,T
,skInfo
,T
.rootNode(),true);
633 OGDF_ASSERT(exp
.consistencyCheck());
635 OGDF_ASSERT(exp
.representsCombEmbedding());
636 CombinatorialEmbedding
E(exp
);
638 FaceSinkGraph
F(E
,s
);
640 // find possible external faces (the faces in T containing s)
641 //externalFaces.clear();
642 SList
<face
> externalFaces
;
643 F
.possibleExternalFaces(externalFaces
);
645 OGDF_ASSERT(!externalFaces
.empty());
647 face extFace
= externalFaces
.front();
649 NodeArray
<face
> assignedFace(exp
,0);
650 assignSinks(F
,extFace
,assignedFace
);
654 if(E
.leftFace(adj1
) == extFace
)
658 OGDF_ASSERT(adj1
!= 0);
660 // handle (single) source
661 adjacentEdges
[sG
].pushBack(
662 exp
.original(adj1
->theEdge())->adjSource());
665 for(adj
= adj1
->cyclicSucc(); adj
!= adj1
; adj
= adj
->cyclicSucc()) {
666 adjacentEdges
[sG
].pushBack(
667 exp
.original(adj
->theEdge())->adjSource());
670 // handle internal vertices
674 if(exp
.original(e
)) continue;
676 node vG
= exp
.original(e
->source());
677 adj1
= e
->adjSource();
678 for(adj
= adj1
->cyclicSucc(); adj
!= adj1
;
679 adj
= adj
->cyclicSucc())
681 adjacentEdges
[vG
].pushBack(
682 exp
.original(adj
->theEdge())->adjTarget());
685 adj1
= e
->adjTarget();
686 for(adj
= adj1
->cyclicSucc(); adj
!= adj1
;
687 adj
= adj
->cyclicSucc())
689 adjacentEdges
[vG
].pushBack(
690 exp
.original(adj
->theEdge())->adjSource());
692 } // iterate over internal vertices (associated expansion edge)
698 if (v
->outdeg() > 0) continue;
699 node vG
= exp
.original(v
);
703 if(E
.leftFace(adj1
) == assignedFace
[v
])
707 OGDF_ASSERT(adj1
!= 0);
709 adjacentEdges
[vG
].pushBack(
710 exp
.original(adj1
->theEdge())->adjTarget());
712 for(adj
= adj1
->cyclicSucc(); adj
!= adj1
; adj
= adj
->cyclicSucc()) {
713 adjacentEdges
[vG
].pushBack(
714 exp
.original(adj
->theEdge())->adjTarget());
716 } // iterate over sinks
720 // for each cut-vertex, process all components different from i
721 SListPure
<node
> origNodes
;
723 forall_nodes(v
,exp
) {
724 node vG
= exp
.original(v
);
727 origNodes
.pushBack(vG
);
730 SListConstIterator
<node
> itV
;
731 for(itV
= origNodes
.begin(); itV
.valid(); ++itV
) {
733 testBiconnectedComponent(exp
,*itV
,i
,embed
,adjacentEdges
);
744 // checks if precomputed in-/outdegrees in pertinet graphs are correctly
745 // (for debugging only)
746 bool UpwardPlanarModule::checkDegrees(
749 NodeArray
<SkeletonInfo
> &skInfo
)
751 const Graph
&tree
= T
.tree();
754 forall_nodes(vT
,tree
)
758 const Skeleton
&S
= T
.skeleton(vT
);
759 const Graph
&M
= S
.getGraph();
763 node wT
= S
.twinTreeNode(e
);
764 if (wT
== 0) continue;
767 T
.pertinentGraph(wT
,P
);
769 Graph
&Gp
= P
.getGraph();
771 if (P
.referenceEdge())
772 Gp
.delEdge(P
.referenceEdge());
774 node x
= 0, y
= 0, v
;
776 if (P
.original(v
) == S
.original(e
->source()))
778 if (P
.original(v
) == S
.original(e
->target()))
782 OGDF_ASSERT(x
!= 0 && y
!= 0);
784 const DegreeInfo
°Info
= skInfo
[vT
].m_degInfo
[e
];
785 if(x
->indeg() != degInfo
.m_indegSrc
)
787 if(x
->outdeg() != degInfo
.m_outdegSrc
)
789 if(y
->indeg() != degInfo
.m_indegTgt
)
791 if(y
->outdeg() != degInfo
.m_outdegTgt
)
794 bool contSource
= false;
796 if (v
!= x
&& v
!= y
&& P
.original(v
) == s
)
800 if (skInfo
[vT
].m_containsSource
[e
] != contSource
)
809 // precompute information: in-/outdegrees in pertinent graph, contains
810 // pertinent graph the source?
811 void UpwardPlanarModule::computeDegreesInPertinent(
814 NodeArray
<SkeletonInfo
> &skInfo
,
817 const Skeleton
&S
= T
.skeleton(vT
);
818 const Graph
&M
= S
.getGraph();
819 EdgeArray
<DegreeInfo
> °Info
= skInfo
[vT
].m_degInfo
;
820 EdgeArray
<bool> &containsSource
= skInfo
[vT
].m_containsSource
;
822 // recursively compute in- and outdegrees at virtual edges except for
823 // the reference edge of S; additionally compute if source is contained
824 // in pertinent (and no endpoint of reference edge)
826 forall_adj_edges(eT
,vT
) {
827 node wT
= eT
->target();
829 computeDegreesInPertinent(T
,s
,skInfo
,wT
);
832 edge eRef
= S
.referenceEdge();
833 node src
= eRef
->source();
834 node tgt
= eRef
->target();
836 bool contSource
= false;
839 if (v
!= src
&& v
!= tgt
&& S
.original(v
) == s
)
843 // the in- and outdegree at real edges is obvious ...
844 // m_containsSource is set to false by default
847 if (S
.isVirtual(e
) == false) {
848 degInfo
[e
].m_indegSrc
= 0;
849 degInfo
[e
].m_outdegSrc
= 1;
850 degInfo
[e
].m_indegTgt
= 1;
851 degInfo
[e
].m_outdegTgt
= 0;
852 } else if (e
!= eRef
) {
853 contSource
|= containsSource
[e
];
858 if (vT
== T
.rootNode())
859 return; // no virtual reference edge
862 // compute in- and outdegree of poles of reference edge in pertinent graph
867 {forall_adj_edges(e
,src
) {
868 if (e
== eRef
) continue;
869 if (e
->source() == src
) {
870 indegSrc
+= degInfo
[e
].m_indegSrc
;
871 outdegSrc
+= degInfo
[e
].m_outdegSrc
;
873 indegSrc
+= degInfo
[e
].m_indegTgt
;
874 outdegSrc
+= degInfo
[e
].m_outdegTgt
;
880 {forall_adj_edges(e
,tgt
) {
881 if (e
== eRef
) continue;
882 if (e
->source() == tgt
) {
883 indegTgt
+= degInfo
[e
].m_indegSrc
;
884 outdegTgt
+= degInfo
[e
].m_outdegSrc
;
886 indegTgt
+= degInfo
[e
].m_indegTgt
;
887 outdegTgt
+= degInfo
[e
].m_outdegTgt
;
891 // set degrees at reference edge
892 node srcOrig
= S
.original(src
);
893 degInfo
[eRef
].m_indegSrc
= srcOrig
->indeg () - indegSrc
;
894 degInfo
[eRef
].m_outdegSrc
= srcOrig
->outdeg() - outdegSrc
;
896 node tgtOrig
= S
.original(tgt
);
897 degInfo
[eRef
].m_indegTgt
= tgtOrig
->indeg() - indegTgt
;
898 degInfo
[eRef
].m_outdegTgt
= tgtOrig
->outdeg() - outdegTgt
;
900 containsSource
[eRef
] = (contSource
== false &&
901 s
!= S
.original(src
) && s
!= S
.original(tgt
));
903 // set degres at twin edge of reference edge
904 node wT
= S
.twinTreeNode(eRef
);
905 DegreeInfo
°InfoTwin
= skInfo
[wT
].m_degInfo
[S
.twinEdge(eRef
)];
906 degInfoTwin
.m_indegSrc
= indegSrc
;
907 degInfoTwin
.m_outdegSrc
= outdegSrc
;
908 degInfoTwin
.m_indegTgt
= indegTgt
;
909 degInfoTwin
.m_outdegTgt
= outdegTgt
;
911 skInfo
[wT
].m_containsSource
[S
.twinEdge(eRef
)] = contSource
;
915 // by default, corresponding virtual edges should be oriented in the
916 // same directions, i.e., the original nodes of source/target are equal
917 // this procedure serves to assert that this really holds!
918 bool UpwardPlanarModule::virtualEdgesDirectedEqually(const SPQRTree
&T
)
921 forall_nodes(v
,T
.tree())
923 const Skeleton
&S
= T
.skeleton(v
);
924 const Graph
&M
= S
.getGraph();
928 edge eTwin
= S
.twinEdge(e
);
930 if (eTwin
== 0) continue;
932 const Skeleton
&STwin
= T
.skeleton(S
.twinTreeNode(e
));
934 if (S
.original(e
->source()) != STwin
.original(eTwin
->source()))
937 if (S
.original(e
->target()) != STwin
.original(eTwin
->target()))
946 // compute sT-skeletons
947 // test for upward-planarity, build constraints for rooting, and find a
948 // rooting of the tree satisfying all constraints
949 // returns true iff such a rooting exists
950 edge
UpwardPlanarModule::directSkeletons(
952 NodeArray
<SkeletonInfo
> &skInfo
)
954 const Graph
&tree
= T
.tree();
955 ConstraintRooting
rooting(T
);
957 // we assume that corresponding virtual edges are directed equally before,
958 // i.e., the original nodes of the sources are equal and the original nodes
959 // of the targets are equal
960 OGDF_ASSERT(virtualEdgesDirectedEqually(T
));
963 forall_nodes(vT
,tree
)
965 const StaticSkeleton
&S
= *dynamic_cast<StaticSkeleton
*>(&T
.skeleton(vT
));
966 const Graph
&M
= S
.getGraph();
970 edge eTwin
= S
.twinEdge(e
);
971 if (eTwin
== 0) continue;
973 const DegreeInfo
°Info
= skInfo
[vT
].m_degInfo
[e
];
974 bool contSource
= skInfo
[vT
].m_containsSource
[e
];
976 node u
= e
->source();
977 node v
= e
->target();
978 // K = pertinent subgraph of e
981 const DegreeInfo
°InfoTwin
=
982 skInfo
[S
.twinTreeNode(e
)].m_degInfo
[eTwin
];
984 bool uTwinIsSource
= (degInfoTwin
.m_indegSrc
== 0);
985 bool vTwinIsSource
= (degInfoTwin
.m_indegTgt
== 0);
988 // u and v are sources of K
989 if(degInfo
.m_indegSrc
== 0 && degInfo
.m_indegTgt
== 0) {
990 // replace e by a peak
991 T
.replaceSkEdgeByPeak(vT
,e
);
994 // u is a source of K and v is a sink of K
995 } else if (degInfo
.m_indegSrc
== 0 && degInfo
.m_outdegTgt
== 0) {
998 // a directed edge (u,v)
999 T
.directSkEdge(vT
,e
,u
);
1002 T
.replaceSkEdgeByPeak(vT
,e
);
1006 // v is a source of K and u is a sink of K
1007 } else if (degInfo
.m_indegTgt
== 0 && degInfo
.m_outdegSrc
== 0) {
1010 // a directed edge (v,u)
1011 T
.directSkEdge(vT
,e
,v
);
1014 T
.replaceSkEdgeByPeak(vT
,e
);
1019 // u is a source of K and v is an internal vertex of K
1020 } else if (degInfo
.m_indegSrc
== 0 &&
1021 degInfo
.m_indegTgt
> 0 && degInfo
.m_outdegTgt
> 0) {
1023 // v is a source of G-K and s not in K^0
1024 if (vTwinIsSource
&& contSource
== false) {
1025 // a directed edge (u,v)
1026 T
.directSkEdge(vT
,e
,u
);
1029 T
.replaceSkEdgeByPeak(vT
,e
);
1033 // v is a source of K and u is an internal vertex of K
1034 } else if (degInfo
.m_indegTgt
== 0 &&
1035 degInfo
.m_indegSrc
> 0 && degInfo
.m_outdegSrc
> 0) {
1037 // u is a source of G-K and s not in K^0
1038 if (uTwinIsSource
&& contSource
== false) {
1039 // a directed edge (v,u)
1040 T
.directSkEdge(vT
,e
,v
);
1043 T
.replaceSkEdgeByPeak(vT
,e
);
1047 // u and v ar not source of K
1049 // u is a source of G-K
1050 if (uTwinIsSource
) {
1051 // a directed edge (u,v)
1052 T
.directSkEdge(vT
,e
,u
);
1054 // a directed edge (v,u)
1055 T
.directSkEdge(vT
,e
,v
);
1061 // at this point, the sT-skeleton of vT is computed
1063 // if the source is not in skeleton(vT), let eWithSource be the virtual
1064 // edge in skeleton(vT) whose expansion graph contains the source
1065 edge eWithSource
= 0;
1067 if (skInfo
[vT
].m_containsSource
[e
]) {
1073 // constrain the tree edge associated with eWithSource to be directed
1076 if (rooting
.constrainTreeEdge(S
.treeEdge(eWithSource
),vT
) == false)
1081 // test whether the sT-skeletonof vT is upward planar and determine
1082 // the possible external faces
1086 // for S- and P-nodes, we know already that they are upward planar
1087 if (T
.typeOf(vT
) != SPQRTree::RNode
)
1090 //FaceSinkGraph &F = skInfo[vT].m_F;
1091 //ConstCombinatorialEmbedding &E = skInfo[vT].m_E;
1092 SList
<face
> &externalFaces
= skInfo
[vT
].m_externalFaces
;
1094 if(initFaceSinkGraph(M
,skInfo
[vT
]) == false)
1098 // mark the edges of the skeleton of vT whose endpoints are on the
1099 // external face of some upward drawing of the sT-skeleton of vT
1100 EdgeArray
<bool> marked(M
,false);
1102 SListConstIterator
<face
> it
;
1103 for(it
= externalFaces
.begin(); it
.valid(); ++it
) {
1105 forall_face_adj(adj
,*it
) {
1110 // for each unmarked edge e of the skeleton of vT, constrain the tree
1111 // edge associated with e to be directed towards vT
1113 if (marked
[e
]) continue;
1115 edge eT
= S
.treeEdge(e
);
1116 edge eR
= S
.realEdge(e
);
1118 rooting
.constrainRealEdge(eR
);
1120 if (!rooting
.constrainTreeEdge(eT
,S
.twinTreeNode(e
)))
1127 // determine whether T can be rooted at a Q-node in such a way that
1128 // orienting edges from children to parents satisfies the constraints
1130 //rooting.outputConstraints(cout);
1131 edge eRoot
= rooting
.findRooting();
1133 //cout << "\nroot edge: " << eRoot << endl;
1139 // initializes embedding and face-sink graph in skeleton info for
1140 // embedded skeleton graph
1141 // determines the possible external faces and returns true if skeleton
1142 // graph is upward planar
1143 bool UpwardPlanarModule::initFaceSinkGraph(
1145 SkeletonInfo
&skInfo
)
1147 ConstCombinatorialEmbedding
&E
= skInfo
.m_E
;
1148 FaceSinkGraph
&F
= skInfo
.m_F
;
1149 SList
<face
> &externalFaces
= skInfo
.m_externalFaces
;
1152 node s
= getSingleSource(M
);
1153 OGDF_ASSERT(s
!= 0);
1157 // find possible external faces (the faces in T containing s)
1158 F
.possibleExternalFaces(externalFaces
);
1160 return !externalFaces
.empty();
1164 // embeds skeleton(vT) and mirrors it if necessary such that the external
1165 // face is to the left of the reference edge iff extFaceIsLeft = true
1166 void UpwardPlanarModule::embedSkeleton(
1168 StaticPlanarSPQRTree
&T
,
1169 NodeArray
<SkeletonInfo
> &skInfo
,
1173 StaticSkeleton
&S
= *dynamic_cast<StaticSkeleton
*>(&T
.skeleton(vT
));
1174 Graph
&M
= S
.getGraph();
1176 edge eRef
= S
.referenceEdge();
1178 // We still have to embed skeletons of P-nodes
1179 if (T
.typeOf(vT
) == SPQRTree::PNode
) {
1181 node lowerPole
= eRef
->source();
1183 SListPure
<adjEntry
> lowerAdjs
, upperAdjs
;
1185 adjEntry adjRef
= eRef
->adjSource();
1186 adjEntry adjRefTwin
= adjRef
->twin();
1189 forall_adj(adj
, lowerPole
) {
1190 // ignore reference edge
1191 if (adj
== adjRef
) continue;
1193 adjEntry adjTwin
= adj
->twin();
1194 if (S
.original(adjTwin
->theNode()) == 0) { // peak
1195 lowerAdjs
.pushFront(adj
);
1196 upperAdjs
.pushBack (adjTwin
->cyclicSucc()->twin());
1198 } else { // non-peak
1199 lowerAdjs
.pushBack (adj
);
1200 upperAdjs
.pushFront(adjTwin
);
1204 // adjacency entries in lowerAdjs are now sorted: peaks, non-peaks
1205 // (without reference edge)
1207 // is reference edge a peak
1208 bool isRefPeak
= (S
.original(eRef
->target()) == 0);
1209 adjEntry adjRefUpper
= (isRefPeak
) ?
1210 (adjRefTwin
->cyclicSucc()->twin()) :
1214 // lowerAdjs: ref. peak, other peaks, non-peaks
1215 lowerAdjs
.pushFront(adjRef
);
1216 upperAdjs
.pushBack (adjRefUpper
);
1218 // lowerAdjs: peaks, non-peaks, ref. non-peak
1219 lowerAdjs
.pushBack (adjRef
);
1220 upperAdjs
.pushFront(adjRefUpper
);
1224 M
.sort(lowerPole
, lowerAdjs
);
1225 M
.sort(adjRefUpper
->theNode(), upperAdjs
);
1229 OGDF_ASSERT(M
.representsCombEmbedding());
1231 // we still have to compute the face-sink graph for S and P nodes
1232 if(T
.typeOf(vT
) != SPQRTree::RNode
) {
1236 initFaceSinkGraph(M
,skInfo
[vT
]);
1237 OGDF_ASSERT(testOk
);
1240 // variables stored in skeleton info
1241 ConstCombinatorialEmbedding
&E
= skInfo
[vT
].m_E
;
1242 FaceSinkGraph
&F
= skInfo
[vT
].m_F
;
1243 SList
<face
> &externalFaces
= skInfo
[vT
].m_externalFaces
;
1246 // determine a possible external face extFace adjacent to eRef
1247 face fLeft
= E
.leftFace (eRef
->adjSource());
1248 face fRight
= E
.rightFace(eRef
->adjSource());
1251 SListConstIterator
<face
> it
;
1252 for(it
= externalFaces
.begin(); it
.valid(); ++it
) {
1254 if (f
== fLeft
|| f
== fRight
)
1258 OGDF_ASSERT(extFace
!= 0);
1260 // possibly we have to mirror the embedding of S
1261 bool mirrorEmbedding
= (extFaceIsLeft
!= (extFace
== fLeft
));
1263 // assign sinks to faces (a sink t is assigned to the face above t in
1264 // an upward planar drawing)
1265 NodeArray
<face
> assignedFace(M
,0);
1266 assignSinks(F
,extFace
,assignedFace
);
1269 // Traverse SPQR-tree by depth-first search.
1270 // This kind of traversal is required for correctly embedding the
1271 // skeletons (see paper).
1275 edge eT
= S
.treeEdge(e
);
1276 if (eT
== 0) continue;
1278 node wT
= eT
->target();
1279 if (wT
== vT
) continue;
1281 bool eExtFaceLeft
= true;
1282 node p
= e
->target();
1283 if(S
.original(p
) == 0) {
1284 const Skeleton
&S2
= T
.skeleton(wT
);
1285 node vOrig
= S2
.original(S2
.referenceEdge()->source());
1286 adjEntry adj
= e
->adjSource();
1288 if (S
.original(e
->source()) != vOrig
)
1289 adj
= adj
->twin()->cyclicSucc()->twin();
1291 if(assignedFace
[p
] == E
.rightFace(adj
))
1292 eExtFaceLeft
= true;
1294 OGDF_ASSERT(assignedFace
[p
] == E
.leftFace(adj
));
1295 eExtFaceLeft
= false;
1297 if (mirrorEmbedding
)
1298 eExtFaceLeft
= !eExtFaceLeft
;
1302 embedSkeleton(G
,T
,skInfo
,wT
,eExtFaceLeft
);
1304 } // traverse SPQR-tree
1310 OGDF_ASSERT_IF(dlConsistencyChecks
,M
.consistencyCheck());
1313 // We have to unsplit all peaks in skeleton S again, since the embedding
1314 // procedure of StaticPlanarSPQRTree does not support such modified skeletons
1315 // (only reversing skeleton edges is allowed).
1317 for(v
= M
.firstNode(); v
; v
= vSucc
)
1321 if (S
.original(v
) == 0) {
1322 OGDF_ASSERT(v
->indeg() == 2 && v
->outdeg() == 0);
1324 edge e1
= v
->firstAdj()->theEdge();
1325 edge e2
= v
->lastAdj ()->theEdge();
1327 if(S
.realEdge(e1
) != 0 || S
.twinEdge(e1
) != 0) {
1330 OGDF_ASSERT(S
.realEdge(e2
) != 0 || S
.twinEdge(e2
) != 0);
1340 // assigns each sink to a face such that there exists an upward planar drawing
1341 // with exteriour fac extFace in which the assigned face of each sink t is
1343 void UpwardPlanarModule::assignSinks(
1346 NodeArray
<face
> &assignedFace
)
1348 // find the representative h of face extFace in face-sink graph F
1352 if (F
.originalFace(v
) == extFace
) {
1357 // find all roots of trees in F different from (the unique tree T)
1359 SListPure
<node
> roots
;
1361 node vOrig
= F
.originalNode(v
);
1362 if (vOrig
!= 0 && vOrig
->indeg() > 0 && vOrig
->outdeg() > 0)
1366 // recursively assign faces to sinks
1367 dfsAssignSinks(F
,h
,0,assignedFace
);
1369 SListConstIterator
<node
> itRoots
;
1370 for(itRoots
= roots
.begin(); itRoots
.valid(); ++itRoots
)
1371 dfsAssignSinks(F
,*itRoots
,0,assignedFace
);
1375 node
UpwardPlanarModule::dfsAssignSinks(
1376 FaceSinkGraph
&F
, // face-sink graph
1377 node v
, // current node
1378 node parent
, // its parent
1379 NodeArray
<face
> &assignedFace
)
1381 bool isFace
= (F
.originalFace(v
) != 0);
1384 // we perform a dfs-traversal (underlying graph is a tree)
1388 node w
= adj
->twinNode();
1390 if (w
== parent
) continue;
1393 assignedFace
[F
.originalNode(w
)] = F
.originalFace(v
);
1396 dfsAssignSinks(F
,w
,v
,assignedFace
);
1404 } // end namespace ogdf