6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief Computes an embedding of a biconnected graph with maximum
13 * \author Thorsten Kerkhof
16 * This file is part of the Open Graph Drawing Framework (OGDF).
20 * See README.txt in the root directory of the OGDF installation for details.
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
48 #ifndef OGDF_EMBEDDER_MAX_FACE_BICONNECTED_GRAPHS_H
49 #define OGDF_EMBEDDER_MAX_FACE_BICONNECTED_GRAPHS_H
51 #include <ogdf/decomposition/StaticSPQRTree.h>
52 #include <ogdf/basic/CombinatorialEmbedding.h>
53 #include <ogdf/basic/extended_graph_alg.h>
58 //! Computes an embedding of a biconnected graph with maximum external face.
60 * See the paper "Graph Embedding with Minimum Depth and
61 * Maximum External Face" by C. Gutwenger and P. Mutzel (2004) for
65 class EmbedderMaxFaceBiconnectedGraphs
68 //! Creates an embedder.
69 EmbedderMaxFaceBiconnectedGraphs() { }
72 * \brief Embeds \a G by computing and extending a maximum face in \a G
74 * \param G is the original graph.
75 * \param adjExternal is assigned an adjacency entry of the external face.
76 * \param nodeLength stores for each vertex in \a G its length.
77 * \param edgeLength stores for each edge in \a G its length.
78 * \param n is a vertex of the original graph. If n is given, a maximum face
79 * containing n is computed, otherwise any maximum face.
83 adjEntry
& adjExternal
,
84 const NodeArray
<T
>& nodeLength
,
85 const EdgeArray
<T
>& edgeLength
,
89 * \brief Computes the component lengths of all virtual edges in spqrTree.
90 * \param G is the original graph.
91 * \param nodeLength is saving for each vertex in \a G its length.
92 * \param edgeLength is saving for each edge in \a G its length.
93 * \param spqrTree is the SPQR-tree of \a G.
94 * \param edgeLengthSkel is saving for each skeleton graph of the SPQR-tree
99 const NodeArray
<T
>& nodeLength
,
100 const EdgeArray
<T
>& edgeLength
,
101 StaticSPQRTree
& spqrTree
,
102 NodeArray
< EdgeArray
<T
> >& edgeLengthSkel
);
105 * \brief Returns the size of a maximum external face in \a G containing the node \a n.
106 * \param G is the original graph.
107 * \param n is a node of the original graph.
108 * \param nodeLength is saving for each vertex in \a G its length.
109 * \param edgeLength is saving for each edge in \a G its length.
110 * \return The size of a maximum external face in \a G containing the node \a n.
112 static T
computeSize(
115 const NodeArray
<T
>& nodeLength
,
116 const EdgeArray
<T
>& edgeLength
);
119 * \brief Returns the size of a maximum external face in \a G containing
122 * \param G is the original graph.
123 * \param n is a node of the original graph.
124 * \param nodeLength is saving for each vertex in \a G its length.
125 * \param edgeLength is saving for each edge in \a G its length.
126 * \param spqrTree is the SPQR-tree of G.
127 * \return The size of a maximum external face in \a G containing the node \a n.
129 static T
computeSize(
132 const NodeArray
<T
>& nodeLength
,
133 const EdgeArray
<T
>& edgeLength
,
134 StaticSPQRTree
& spqrTree
);
137 * \brief Returns the size of a maximum external face in \a G containing
140 * \param G is the original graph.
141 * \param n is a node of the original graph.
142 * \param nodeLength is saving for each vertex in \a G its length.
143 * \param edgeLength is saving for each edge in \a G its length.
144 * \param spqrTree is the SPQR-tree of G.
145 * \param edgeLengthSkel is saving for each skeleton graph the length
147 * \return The size of a maximum external face in \a G containing the node \a n.
149 static T
computeSize(
152 const NodeArray
<T
>& nodeLength
,
153 const EdgeArray
<T
>& edgeLength
,
154 StaticSPQRTree
& spqrTree
,
155 const NodeArray
< EdgeArray
<T
> >& edgeLengthSkel
);
158 * \brief Returns the size of a maximum external face in \a G.
159 * \param G is the original graph.
160 * \param nodeLength is saving for each vertex in \a G its length.
161 * \param edgeLength is saving for each edge in \a G its length.
162 * \return The size of a maximum external face in \a G.
164 static T
computeSize(
166 const NodeArray
<T
>& nodeLength
,
167 const EdgeArray
<T
>& edgeLength
);
170 * \brief Returns the size of a maximum external face in \a G.
171 * The SPQR-tree is given. The computed component lengths are
172 * computed and returned.
174 * \param G is the original graph.
175 * \param nodeLength is saving for each vertex in \a G its length.
176 * \param edgeLength is saving for each edge in \a G its length.
177 * \param spqrTree is the SPQR-tree of G.
178 * \param edgeLengthSkel is saving for each skeleton graph the length
180 * \return The size of a maximum external face in \a G.
182 static T
computeSize(
184 const NodeArray
<T
>& nodeLength
,
185 const EdgeArray
<T
>& edgeLength
,
186 StaticSPQRTree
& spqrTree
,
187 NodeArray
< EdgeArray
<T
> >& edgeLengthSkel
);
191 * \brief Bottom up traversal of SPQR-tree computing the component length of
192 * all non-reference edges.
193 * \param spqrTree is the SPQR-tree of \a G.
194 * \param mu is the SPQR-tree node treated in this function call.
195 * \param nodeLength is saving for each node of the original graph \a G its
197 * \param edgeLength is saving for each skeleton graph the length of each
200 static void bottomUpTraversal(
201 StaticSPQRTree
& spqrTree
,
203 const NodeArray
<T
>& nodeLength
,
204 NodeArray
< EdgeArray
<T
> >& edgeLength
);
207 * \brief Top down traversal of SPQR-tree computing the component length of
208 * all reference edges.
209 * \param spqrTree is the SPQR-tree of \a G.
210 * \param mu is the SPQR-tree node treated in this function call.
211 * \param nodeLength is saving for each node of the original graph \a G its
213 * \param edgeLength is saving for each skeleton graph the length of each
216 static void topDownTraversal(
217 StaticSPQRTree
& spqrTree
,
219 const NodeArray
<T
>& nodeLength
,
220 NodeArray
< EdgeArray
<T
> >& edgeLength
);
223 * \brief Computes the size of a maximum face in the skeleton graph of \a mu
225 * \param spqrTree is the SPQR-tree of \a G.
226 * \param mu is the SPQR-tree node treated in this function call.
227 * \param n is a node of the original graph \a G.
228 * \param nodeLength is saving for each node of the original graph \a G its
230 * \param edgeLength is saving for each skeleton graph the length of each
233 static T
largestFaceContainingNode(
234 const StaticSPQRTree
& spqrTree
,
237 const NodeArray
<T
>& nodeLength
,
238 const NodeArray
< EdgeArray
<T
> >& edgeLength
);
241 * \brief Computes the size of a maximum face in the skeleton graph of \a mu.
242 * \param spqrTree is the SPQR-tree of \a G.
243 * \param mu is the SPQR-tree node treated in this function call.
244 * \param nodeLength is saving for each node of the original graph \a G its
246 * \param edgeLength is saving for each skeleton graph the length of each
249 static T
largestFaceInSkeleton(
250 const StaticSPQRTree
& spqrTree
,
252 const NodeArray
<T
>& nodeLength
,
253 const NodeArray
< EdgeArray
<T
> >& edgeLength
);
255 /* \brief ExpandEdge embeds all edges in the skeleton graph \a S into an
256 * existing embedding and calls recursively itself for all virtual edges
259 * \param spqrTree The SPQR-tree of the treated graph.
260 * \param treeNodeTreated is an array saving for each SPQR-tree node \a mu
261 * whether it was already treated by any call of ExpandEdge or not. Every
262 * \a mu should only be treated once.
263 * \param mu is a node in the SPQR-tree.
264 * \param leftNode is the node adjacent to referenceEdge, which should be "left"
266 * \param nodeLength is an array saving the lengths of the nodes of \a G.
267 * \param edgeLength is saving the edge lengths of all edges in each skeleton
268 * graph of all tree nodes.
269 * \param newOrder is saving for each node \a n in \a G the new adjacency
270 * list. This is an output parameter.
271 * \param adjBeforeNodeArraySource is saving for the source of the reference edge
272 * of the skeleton of mu the adjacency entry, before which new entries have
274 * \param adjBeforeNodeArrayTarget is saving for the target of the reference edge
275 * of the skeleton of mu the adjacency entry, before which new entries have
277 * \param adjExternal is an adjacency entry in the external face.
278 * \param n is only set, if ExpandEdge is called for the first time, because
279 * then there is no virtual edge which has to be expanded, but the max face
280 * has to contain a certain node \a n.
282 static void expandEdge(
283 const StaticSPQRTree
& spqrTree
,
284 NodeArray
<bool>& treeNodeTreated
,
286 const node
& leftNode
,
287 const NodeArray
<T
>& nodeLength
,
288 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
289 NodeArray
< List
<adjEntry
> >& newOrder
,
290 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
291 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
292 adjEntry
& adjExternal
,
295 /* \brief Embeds all edges in the skeleton graph \a S of an S-node of the
296 * SPQR-tree into an existing embedding and calls recursively itself for
297 * all virtual edges in S.
299 * \param spqrTree The SPQR-tree of the treated graph.
300 * \param treeNodeTreated is an array saving for each SPQR-tree node \a mu
301 * whether it was already treated by any call of ExpandEdge or not. Every
302 * \a mu should only be treated once.
303 * \param mu is a node in the SPQR-tree.
304 * \param leftNode is the node adjacent to referenceEdge, which should be "left"
306 * \param nodeLength is an array saving the lengths of the nodes of \a G.
307 * \param edgeLength is saving the edge lengths of all edges in each skeleton
308 * graph of all tree nodes.
309 * \param newOrder is saving for each node \a n in \a G the new adjacency
310 * list. This is an output parameter.
311 * \param adjBeforeNodeArraySource is saving for the source of the reference edge
312 * of the skeleton of mu the adjacency entry, before which new entries have
314 * \param adjBeforeNodeArrayTarget is saving for the target of the reference edge
315 * of the skeleton of mu the adjacency entry, before which new entries have
317 * \param adjExternal is an adjacency entry in the external face.
319 static void expandEdgeSNode(
320 const StaticSPQRTree
& spqrTree
,
321 NodeArray
<bool>& treeNodeTreated
,
323 const node
& leftNode
,
324 const NodeArray
<T
>& nodeLength
,
325 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
326 NodeArray
< List
<adjEntry
> >& newOrder
,
327 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
328 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
329 adjEntry
& adjExternal
);
331 /* \brief Embeds all edges in the skeleton graph \a S of an P-node of the
332 * SPQR-tree into an existing embedding and calls recursively itself for
333 * all virtual edges in S.
335 * \param spqrTree The SPQR-tree of the treated graph.
336 * \param treeNodeTreated is an array saving for each SPQR-tree node \a mu
337 * whether it was already treated by any call of ExpandEdge or not. Every
338 * \a mu should only be treated once.
339 * \param mu is a node in the SPQR-tree.
340 * \param leftNode is the node adjacent to referenceEdge, which should be "left"
342 * \param nodeLength is an array saving the lengths of the nodes of \a G.
343 * \param edgeLength is saving the edge lengths of all edges in each skeleton
344 * graph of all tree nodes.
345 * \param newOrder is saving for each node \a n in \a G the new adjacency
346 * list. This is an output parameter.
347 * \param adjBeforeNodeArraySource is saving for the source of the reference edge
348 * of the skeleton of mu the adjacency entry, before which new entries have
350 * \param adjBeforeNodeArrayTarget is saving for the target of the reference edge
351 * of the skeleton of mu the adjacency entry, before which new entries have
353 * \param adjExternal is an adjacency entry in the external face.
355 static void expandEdgePNode(
356 const StaticSPQRTree
& spqrTree
,
357 NodeArray
<bool>& treeNodeTreated
,
359 const node
& leftNode
,
360 const NodeArray
<T
>& nodeLength
,
361 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
362 NodeArray
< List
<adjEntry
> >& newOrder
,
363 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
364 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
365 adjEntry
& adjExternal
);
367 /* \brief Embeds all edges in the skeleton graph \a S of an R-node of the
368 * SPQR-tree into an existing embedding and calls recursively itself for
369 * all virtual edges in S.
371 * \param spqrTree The SPQR-tree of the treated graph.
372 * \param treeNodeTreated is an array saving for each SPQR-tree node \a mu
373 * whether it was already treated by any call of ExpandEdge or not. Every
374 * \a mu should only be treated once.
375 * \param mu is a node in the SPQR-tree.
376 * \param leftNode is the node adjacent to referenceEdge, which should be "left"
378 * \param nodeLength is an array saving the lengths of the nodes of \a G.
379 * \param edgeLength is saving the edge lengths of all edges in each skeleton
380 * graph of all tree nodes.
381 * \param newOrder is saving for each node \a n in \a G the new adjacency
382 * list. This is an output parameter.
383 * \param adjBeforeNodeArraySource is saving for the source of the reference edge
384 * of the skeleton of mu the adjacency entry, before which new entries have
386 * \param adjBeforeNodeArrayTarget is saving for the target of the reference edge
387 * of the skeleton of mu the adjacency entry, before which new entries have
389 * \param adjExternal is an adjacency entry in the external face.
390 * \param n is only set, if ExpandEdge is called for the first time, because
391 * then there is no virtual edge which has to be expanded, but the max face
392 * has to contain a certain node \a n.
394 static void expandEdgeRNode(
395 const StaticSPQRTree
& spqrTree
,
396 NodeArray
<bool>& treeNodeTreated
,
398 const node
& leftNode
,
399 const NodeArray
<T
>& nodeLength
,
400 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
401 NodeArray
< List
<adjEntry
> >& newOrder
,
402 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
403 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
404 adjEntry
& adjExternal
,
407 /* \brief Writes a given adjacency entry into the newOrder. If the edge
408 * belonging to ae is a virtual edge, it is expanded.
410 * \param ae is the adjacency entry which has to be expanded.
411 * \param before is the adjacency entry of the node in \a G, before
412 * which ae has to be inserted.
413 * \param spqrTree The SPQR-tree of the treated graph.
414 * \param treeNodeTreated is an array saving for each SPQR-tree node \a mu
415 * whether it was already treated by any call of ExpandEdge or not. Every
416 * \a mu should only be treated once.
417 * \param mu is a node in the SPQR-tree.
418 * \param leftNode is the node adjacent to referenceEdge, which should be "left"
420 * \param nodeLength is an array saving the lengths of the nodes of \a G.
421 * \param edgeLength is saving the edge lengths of all edges in each skeleton
422 * graph of all tree nodes.
423 * \param newOrder is saving for each node \a n in \a G the new adjacency
424 * list. This is an output parameter.
425 * \param adjBeforeNodeArraySource is saving for the source of the reference edge
426 * of the skeleton of mu the adjacency entry, before which new entries have
428 * \param adjBeforeNodeArrayTarget is saving for the target of the reference edge
429 * of the skeleton of mu the adjacency entry, before which new entries have
431 * \param adjExternal is an adjacency entry in the external face.
433 static void adjEntryForNode(
435 ListIterator
<adjEntry
>& before
,
436 const StaticSPQRTree
& spqrTree
,
437 NodeArray
<bool>& treeNodeTreated
,
439 const node
& leftNode
,
440 const NodeArray
<T
>& nodeLength
,
441 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
442 NodeArray
< List
<adjEntry
> >& newOrder
,
443 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
444 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
445 adjEntry
& adjExternal
);
450 void EmbedderMaxFaceBiconnectedGraphs
<T
>::embed(
452 adjEntry
& adjExternal
,
453 const NodeArray
<T
>& nodeLength
,
454 const EdgeArray
<T
>& edgeLength
,
455 const node
& n
/* = 0*/)
457 //Base cases (SPQR-Tree implementation would crash with these inputs):
458 OGDF_ASSERT(G
.numberOfNodes() >= 2)
459 if (G
.numberOfEdges() <= 2)
461 edge e
= G
.firstEdge();
462 adjExternal
= e
->adjSource();
466 //****************************************************************************
467 //First step: calculate maximum face and edge lengths for virtual edges
468 //****************************************************************************
469 StaticSPQRTree
spqrTree(G
);
470 NodeArray
< EdgeArray
<T
> > edgeLengthSkel
;
471 compute(G
, nodeLength
, edgeLength
, spqrTree
, edgeLengthSkel
);
473 //****************************************************************************
474 //Second step: Embed G
475 //****************************************************************************
481 forall_nodes(mu
, spqrTree
.tree())
483 //Expand all faces in skeleton(mu) and get size of the largest of them:
484 T sizeMu
= largestFaceInSkeleton(spqrTree
, mu
, nodeLength
, edgeLengthSkel
);
485 if (sizeMu
> biggestFace
)
487 biggestFace
= sizeMu
;
495 node
* mus
= new node
[n
->degree()];
497 forall_adj_edges(nAdjEdge
, n
)
499 mus
[i
] = spqrTree
.skeletonOfReal(nAdjEdge
).treeNode();
500 bool alreadySeenMu
= false;
501 for (int j
= 0; j
< i
&& !alreadySeenMu
; j
++)
503 if (mus
[i
] == mus
[j
])
504 alreadySeenMu
= true;
513 //Expand all faces in skeleton(mu) containing n and get size of
514 //the largest of them:
515 T sizeInMu
= largestFaceContainingNode(spqrTree
, mus
[i
], n
,
516 nodeLength
, edgeLengthSkel
);
517 if (sizeInMu
> biggestFace
)
519 biggestFace
= sizeInMu
;
529 bigFaceMu
= spqrTree
.rootTreeAt(bigFaceMu
);
531 NodeArray
< List
<adjEntry
> > newOrder(G
);
532 NodeArray
<bool> treeNodeTreated(spqrTree
.tree(), false);
533 ListIterator
<adjEntry
> it
;
535 NodeArray
< ListIterator
<adjEntry
> > adjBeforeNodeArraySource(spqrTree
.tree());
536 NodeArray
< ListIterator
<adjEntry
> > adjBeforeNodeArrayTarget(spqrTree
.tree());
537 expandEdge(spqrTree
, treeNodeTreated
, bigFaceMu
, 0, nodeLength
,
538 edgeLengthSkel
, newOrder
, adjBeforeNodeArraySource
,
539 adjBeforeNodeArrayTarget
, adjExternal
, n
);
543 G
.sort(v
, newOrder
[v
]);
548 void EmbedderMaxFaceBiconnectedGraphs
<T
>::adjEntryForNode(
550 ListIterator
<adjEntry
>& before
,
551 const StaticSPQRTree
& spqrTree
,
552 NodeArray
<bool>& treeNodeTreated
,
554 const node
& leftNode
,
555 const NodeArray
<T
>& nodeLength
,
556 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
557 NodeArray
< List
<adjEntry
> >& newOrder
,
558 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
559 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
560 adjEntry
& adjExternal
)
562 Skeleton
& S
= spqrTree
.skeleton(mu
);
563 edge referenceEdge
= S
.referenceEdge();
564 if (S
.isVirtual(ae
->theEdge()))
566 edge twinE
= S
.twinEdge(ae
->theEdge());
567 node twinNT
= S
.twinTreeNode(ae
->theEdge());
568 //Skeleton& twinS = spqrTree.skeleton(twinNT);
570 if (!treeNodeTreated
[twinNT
])
573 if (ae
->theEdge()->source() == leftNode
)
574 m_leftNode
= twinE
->source();
576 m_leftNode
= twinE
->target();
578 if (ae
->theEdge()->source() == ae
->theNode())
579 adjBeforeNodeArraySource
[twinNT
] = before
;
581 adjBeforeNodeArrayTarget
[twinNT
] = before
;
584 expandEdge(spqrTree
, treeNodeTreated
, twinNT
, m_leftNode
,
585 nodeLength
, edgeLength
, newOrder
,
586 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
588 } //if (!treeNodeTreated[twinNT])
590 if (ae
->theEdge() == referenceEdge
)
592 if (ae
->theNode() == ae
->theEdge()->source())
594 ListIterator
<adjEntry
> tmpBefore
= adjBeforeNodeArraySource
[mu
];
595 adjBeforeNodeArraySource
[mu
] = before
;
600 ListIterator
<adjEntry
> tmpBefore
= adjBeforeNodeArrayTarget
[mu
];
601 adjBeforeNodeArrayTarget
[mu
] = before
;
605 else //!(ae->theEdge() == referenceEdge)
607 if (ae
->theNode() == ae
->theEdge()->source())
608 before
= adjBeforeNodeArraySource
[twinNT
];
610 before
= adjBeforeNodeArrayTarget
[twinNT
];
613 else //!(S.isVirtual(ae->theEdge()))
615 node origNode
= S
.original(ae
->theNode());
616 edge origEdge
= S
.realEdge(ae
->theEdge());
617 if (origNode
== origEdge
->source())
620 before
= newOrder
[origNode
].pushBack(origEdge
->adjSource());
622 before
= newOrder
[origNode
].insertBefore(origEdge
->adjSource(), before
);
627 before
= newOrder
[origNode
].pushBack(origEdge
->adjTarget());
629 before
= newOrder
[origNode
].insertBefore(origEdge
->adjTarget(), before
);
631 } //else //!(S.isVirtual(ae->theEdge()))
636 void EmbedderMaxFaceBiconnectedGraphs
<T
>::expandEdge(
637 const StaticSPQRTree
& spqrTree
,
638 NodeArray
<bool>& treeNodeTreated
,
640 const node
& leftNode
,
641 const NodeArray
<T
>& nodeLength
,
642 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
643 NodeArray
< List
<adjEntry
> >& newOrder
,
644 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
645 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
646 adjEntry
& adjExternal
,
647 const node
& n
/*= 0*/)
649 treeNodeTreated
[mu
] = true;
651 switch(spqrTree
.typeOf(mu
))
653 case SPQRTree::SNode
:
654 expandEdgeSNode(spqrTree
, treeNodeTreated
, mu
, leftNode
,
655 nodeLength
, edgeLength
, newOrder
, adjBeforeNodeArraySource
,
656 adjBeforeNodeArrayTarget
, adjExternal
);
658 case SPQRTree::PNode
:
659 expandEdgePNode(spqrTree
, treeNodeTreated
, mu
, leftNode
,
660 nodeLength
, edgeLength
, newOrder
, adjBeforeNodeArraySource
,
661 adjBeforeNodeArrayTarget
, adjExternal
);
663 case SPQRTree::RNode
:
664 expandEdgeRNode(spqrTree
, treeNodeTreated
, mu
, leftNode
,
665 nodeLength
, edgeLength
, newOrder
, adjBeforeNodeArraySource
,
666 adjBeforeNodeArrayTarget
, adjExternal
, n
);
674 void EmbedderMaxFaceBiconnectedGraphs
<T
>::expandEdgeSNode(
675 const StaticSPQRTree
& spqrTree
,
676 NodeArray
<bool>& treeNodeTreated
,
678 const node
& leftNode
,
679 const NodeArray
<T
>& nodeLength
,
680 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
681 NodeArray
< List
<adjEntry
> >& newOrder
,
682 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
683 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
684 adjEntry
& adjExternal
)
686 Skeleton
& S
= spqrTree
.skeleton(mu
);
687 edge referenceEdge
= S
.referenceEdge();
688 adjEntry startAdjEntry
;
692 forall_edges(e
, S
.getGraph())
696 startAdjEntry
= e
->adjSource();
701 else if (leftNode
->firstAdj()->theEdge() == referenceEdge
)
702 startAdjEntry
= leftNode
->lastAdj();
704 startAdjEntry
= leftNode
->firstAdj();
706 adjEntry ae
= startAdjEntry
;
707 if (adjExternal
== 0)
709 edge orgEdge
= S
.realEdge(ae
->theEdge());
710 if (orgEdge
->source() == S
.original(ae
->theNode()))
711 adjExternal
= orgEdge
->adjSource()->twin();
713 adjExternal
= orgEdge
->adjTarget()->twin();
716 ListIterator
<adjEntry
> before
;
717 if (!(referenceEdge
== 0) && leftNode
== referenceEdge
->source())
718 before
= adjBeforeNodeArraySource
[mu
];
719 else if (!(referenceEdge
== 0))
720 before
= adjBeforeNodeArrayTarget
[mu
];
721 ListIterator
<adjEntry
> beforeSource
;
723 bool firstStep
= true;
724 while (firstStep
|| ae
!= startAdjEntry
)
726 //first treat ae with ae->theNode() is left node, then treat its twin:
727 node m_leftNode
= ae
->theNode();
729 if (ae
->theEdge() == referenceEdge
)
731 if (ae
->theNode() == referenceEdge
->source())
732 adjBeforeNodeArraySource
[mu
] = before
;
734 adjBeforeNodeArrayTarget
[mu
] = before
;
737 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
738 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
739 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
744 beforeSource
= before
;
750 if (ae
->theEdge() == referenceEdge
)
752 if (ae
->theNode() == referenceEdge
->source())
753 adjBeforeNodeArraySource
[mu
] = beforeSource
;
755 adjBeforeNodeArrayTarget
[mu
] = beforeSource
;
758 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
759 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
760 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
763 //set new adjacency entry pair (ae and its twin):
764 if (ae
->theNode()->firstAdj() == ae
)
765 ae
= ae
->theNode()->lastAdj();
767 ae
= ae
->theNode()->firstAdj();
773 void EmbedderMaxFaceBiconnectedGraphs
<T
>::expandEdgePNode(
774 const StaticSPQRTree
& spqrTree
,
775 NodeArray
<bool>& treeNodeTreated
,
777 const node
& leftNode
,
778 const NodeArray
<T
>& nodeLength
,
779 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
780 NodeArray
< List
<adjEntry
> >& newOrder
,
781 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
782 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
783 adjEntry
& adjExternal
)
785 //Choose face defined by virtual edge and the longest edge different from it.
786 Skeleton
& S
= spqrTree
.skeleton(mu
);
787 edge referenceEdge
= S
.referenceEdge();
788 edge altReferenceEdge
= 0;
790 node m_leftNode
= leftNode
;
794 S
.getGraph().allNodes(nodeList
);
795 m_leftNode
= *(nodeList
.begin());
797 node m_rightNode
= m_leftNode
->firstAdj()->twinNode();
800 if (referenceEdge
== 0)
802 forall_edges(e
, S
.getGraph())
806 altReferenceEdge
= e
;
807 edge orgEdge
= S
.realEdge(e
);
808 if (orgEdge
->source() == S
.original(m_leftNode
))
809 adjExternal
= orgEdge
->adjSource();
811 adjExternal
= orgEdge
->adjTarget();
818 edge longestEdge
= 0;
819 forall_edges(e
, S
.getGraph())
821 if (e
== referenceEdge
|| e
== altReferenceEdge
)
823 if (longestEdge
== 0 || edgeLength
[mu
][e
] > edgeLength
[mu
][longestEdge
])
827 List
<edge
> rightEdgeOrder
;
828 ListIterator
<adjEntry
> beforeAltRefEdge
;
830 //begin with left node and longest edge:
831 for (int i
= 0; i
< 2; i
++)
833 ListIterator
<adjEntry
> before
;
840 before
= beforeAltRefEdge
;
843 if (!(referenceEdge
== 0))
845 if (n
== referenceEdge
->source())
846 before
= adjBeforeNodeArraySource
[mu
];
848 before
= adjBeforeNodeArrayTarget
[mu
];
852 S
.getGraph().allEdges(edgeList
);
855 //if left node, longest edge at first:
858 if (longestEdge
->source() == n
)
859 ae
= longestEdge
->adjSource();
861 ae
= longestEdge
->adjTarget();
863 if (!(referenceEdge
== 0) && S
.isVirtual(longestEdge
))
865 node nu
= S
.twinTreeNode(longestEdge
);
866 if (longestEdge
->source() == n
)
868 if (referenceEdge
->source() == n
)
869 adjBeforeNodeArrayTarget
[nu
] = adjBeforeNodeArrayTarget
[mu
];
871 adjBeforeNodeArrayTarget
[nu
] = adjBeforeNodeArraySource
[mu
];
875 if (referenceEdge
->source() == n
)
876 adjBeforeNodeArraySource
[nu
] = adjBeforeNodeArrayTarget
[mu
];
878 adjBeforeNodeArraySource
[nu
] = adjBeforeNodeArraySource
[mu
];
882 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
883 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
884 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
888 //all edges except reference edge and longest edge:
892 for (ListIterator
<edge
> it
= edgeList
.begin(); it
.valid(); it
++)
894 if (*it
== referenceEdge
|| *it
== longestEdge
|| *it
== altReferenceEdge
|| !S
.isVirtual(*it
))
897 node nu
= S
.twinTreeNode(*it
);
898 if (!(referenceEdge
== 0) && (*it
)->source() == n
)
900 if (referenceEdge
->source() == n
)
901 adjBeforeNodeArrayTarget
[nu
] = adjBeforeNodeArrayTarget
[mu
];
903 adjBeforeNodeArrayTarget
[nu
] = adjBeforeNodeArraySource
[mu
];
905 else if (!(referenceEdge
== 0))
907 if (referenceEdge
->source() == n
)
908 adjBeforeNodeArraySource
[nu
] = adjBeforeNodeArrayTarget
[mu
];
910 adjBeforeNodeArraySource
[nu
] = adjBeforeNodeArraySource
[mu
];
913 rightEdgeOrder
.pushFront(*it
);
915 if ((*it
)->source() == n
)
916 ae
= (*it
)->adjSource();
918 ae
= (*it
)->adjTarget();
920 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
921 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
922 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
927 for (ListIterator
<edge
> it
= edgeList
.begin(); it
.valid(); it
++)
929 if (*it
== referenceEdge
|| *it
== longestEdge
|| *it
== altReferenceEdge
|| S
.isVirtual(*it
))
932 rightEdgeOrder
.pushFront(*it
);
934 if ((*it
)->source() == n
)
935 ae
= (*it
)->adjSource();
937 ae
= (*it
)->adjTarget();
939 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
940 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
941 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
947 for (ListIterator
<edge
> it
= rightEdgeOrder
.begin(); it
.valid(); it
++)
949 if ((*it
)->source() == n
)
950 ae
= (*it
)->adjSource();
952 ae
= (*it
)->adjTarget();
954 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
955 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
956 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
961 //if not left node, longest edge:
964 if (longestEdge
->source() == n
)
965 ae
= longestEdge
->adjSource();
967 ae
= longestEdge
->adjTarget();
969 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
970 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
971 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
975 //(alternative) reference edge at last:
976 if (!(referenceEdge
== 0))
978 if (n
== referenceEdge
->source())
979 adjBeforeNodeArraySource
[mu
] = before
;
981 adjBeforeNodeArrayTarget
[mu
] = before
;
987 newLeftNode
= m_leftNode
->firstAdj()->twinNode();
989 newLeftNode
= m_leftNode
;
991 if (altReferenceEdge
->source() == n
)
992 ae
= altReferenceEdge
->adjSource();
994 ae
= altReferenceEdge
->adjTarget();
996 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
997 newLeftNode
, nodeLength
, edgeLength
, newOrder
,
998 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
1001 if (i
== 0 && S
.isVirtual(altReferenceEdge
))
1003 node nu
= S
.twinTreeNode(altReferenceEdge
);
1004 if (altReferenceEdge
->source() == n
)
1005 beforeAltRefEdge
= adjBeforeNodeArrayTarget
[nu
];
1007 beforeAltRefEdge
= adjBeforeNodeArraySource
[nu
];
1015 void EmbedderMaxFaceBiconnectedGraphs
<T
>::expandEdgeRNode(
1016 const StaticSPQRTree
& spqrTree
,
1017 NodeArray
<bool>& treeNodeTreated
,
1019 const node
& leftNode
,
1020 const NodeArray
<T
>& nodeLength
,
1021 const NodeArray
< EdgeArray
<T
> >& edgeLength
,
1022 NodeArray
< List
<adjEntry
> >& newOrder
,
1023 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArraySource
,
1024 NodeArray
< ListIterator
<adjEntry
> >& adjBeforeNodeArrayTarget
,
1025 adjEntry
& adjExternal
,
1026 const node
& n
/* = 0 */)
1028 Skeleton
& S
= spqrTree
.skeleton(mu
);
1029 edge referenceEdge
= S
.referenceEdge();
1031 //compute biggest face containing the reference edge:
1032 face maxFaceContEdge
;
1033 List
<node
> maxFaceNodes
;
1034 planarEmbed(S
.getGraph());
1035 CombinatorialEmbedding
combinatorialEmbedding(S
.getGraph());
1037 adjEntry m_adjExternal
= 0;
1039 forall_faces(f
, combinatorialEmbedding
)
1041 bool containsVirtualEdgeOrN
= false;
1042 adjEntry this_m_adjExternal
= 0;
1044 List
<node
> faceNodes
;
1046 forall_face_adj(ae
, f
)
1048 faceNodes
.pushBack(ae
->theNode());
1049 if ( (n
== 0 && (ae
->theEdge() == referenceEdge
|| referenceEdge
== 0))
1050 || S
.original(ae
->theNode()) == n
)
1052 containsVirtualEdgeOrN
= true;
1053 if (!(referenceEdge
== 0))
1054 this_m_adjExternal
= ae
;
1057 if (referenceEdge
== 0 && !S
.isVirtual(ae
->theEdge()))
1058 this_m_adjExternal
= ae
;
1060 sizeOfFace
+= edgeLength
[mu
][ae
->theEdge()]
1061 + nodeLength
[S
.original(ae
->theNode())];
1064 if (containsVirtualEdgeOrN
&& !(this_m_adjExternal
== 0) && sizeOfFace
> bigFaceSize
)
1066 maxFaceNodes
= faceNodes
;
1067 bigFaceSize
= sizeOfFace
;
1068 maxFaceContEdge
= f
;
1069 m_adjExternal
= this_m_adjExternal
;
1073 if (adjExternal
== 0)
1075 edge orgEdge
= S
.realEdge(m_adjExternal
->theEdge());
1076 if (orgEdge
->source() == S
.original(m_adjExternal
->theNode()))
1077 adjExternal
= orgEdge
->adjSource();
1079 adjExternal
= orgEdge
->adjTarget();
1082 adjEntry adjMaxFace
= maxFaceContEdge
->firstAdj();
1084 //if embedding is mirror symmetrical embedding of desired embedding,
1085 //invert adjacency list of all nodes:
1086 if (!(referenceEdge
== 0))
1088 //successor of adjEntry of virtual edge in adjacency list of leftNode:
1089 adjEntry succ_virtualEdge_leftNode
;
1090 if (leftNode
== referenceEdge
->source())
1091 succ_virtualEdge_leftNode
= referenceEdge
->adjSource()->succ();
1093 succ_virtualEdge_leftNode
= referenceEdge
->adjTarget()->succ();
1094 if (!succ_virtualEdge_leftNode
)
1095 succ_virtualEdge_leftNode
= leftNode
->firstAdj();
1097 bool succVELNAEInExtFace
= false;
1099 forall_face_adj(aeExtFace
, maxFaceContEdge
)
1101 if (aeExtFace
->theEdge() == succ_virtualEdge_leftNode
->theEdge())
1103 succVELNAEInExtFace
= true;
1108 if (!succVELNAEInExtFace
)
1111 forall_nodes(v
, S
.getGraph())
1113 List
<adjEntry
> newAdjOrder
;
1114 for (adjEntry ae
= v
->firstAdj(); ae
; ae
= ae
->succ())
1115 newAdjOrder
.pushFront(ae
);
1116 S
.getGraph().sort(v
, newAdjOrder
);
1118 adjMaxFace
= adjMaxFace
->twin();
1122 NodeArray
<bool> nodeTreated(S
.getGraph(), false);
1124 if (!(referenceEdge
== 0))
1126 start_ae
= adjMaxFace
;
1129 if (start_ae
->theEdge() == referenceEdge
)
1131 start_ae
= start_ae
->faceCycleSucc();
1134 start_ae
= start_ae
->faceCycleSucc();
1135 } while(start_ae
!= adjMaxFace
);
1138 start_ae
= adjMaxFace
;
1140 //For every edge a buffer saving adjacency entries written in embedding step
1141 //for nodes on the maximum face, needed in step for other nodes.
1142 EdgeArray
< List
<adjEntry
> > buffer(S
.getGraph());
1144 bool firstStep
= true;
1145 bool after_start_ae
= true;
1146 for (adjEntry ae
= start_ae
;
1147 firstStep
|| ae
!= start_ae
;
1148 after_start_ae
= (!after_start_ae
|| !ae
->succ()) ? false : true,
1149 ae
= after_start_ae
? ae
->faceCycleSucc()
1150 : (!ae
->faceCycleSucc() ? adjMaxFace
: ae
->faceCycleSucc()))
1153 //node nodeG = S.original(ae->theNode());
1154 nodeTreated
[ae
->theNode()] = true;
1156 //copy adjacency list of nodes into newOrder:
1157 ListIterator
<adjEntry
> before
;
1158 edge vE
= (ae
->theEdge() == referenceEdge
) ? referenceEdge
: ae
->theEdge();
1159 node nu
= (ae
->theEdge() == referenceEdge
) ? mu
: S
.twinTreeNode(ae
->theEdge());
1160 if (S
.isVirtual(vE
))
1162 if (ae
->theNode() == vE
->source())
1163 before
= adjBeforeNodeArraySource
[nu
];
1165 before
= adjBeforeNodeArrayTarget
[nu
];
1168 bool after_ae
= true;
1169 adjEntry m_start_ae
;
1170 if (ae
->theEdge() == referenceEdge
)
1173 m_start_ae
= ae
->succ();
1175 m_start_ae
= ae
->theNode()->firstAdj();
1180 for (adjEntry aeN
= m_start_ae
;
1181 after_ae
|| aeN
!= m_start_ae
;
1182 after_ae
= (!after_ae
|| !aeN
->succ()) ? false : true,
1183 aeN
= after_ae
? aeN
->succ() : (!aeN
->succ() ? ae
->theNode()->firstAdj() : aeN
->succ())
1186 node m_leftNode
= 0;
1187 if (S
.isVirtual(aeN
->theEdge()) && aeN
->theEdge() != referenceEdge
)
1189 //Compute left node of aeN->theNode(). First get adjacency entry in ext. face
1190 //(if edge is in ext. face) and compare face cycle successor with successor
1191 //in node adjacency list. If it is the same, it is the right node, otherwise
1193 adjEntry aeExtFace
= 0;
1194 bool succInExtFace
= false;
1195 bool aeNInExtFace
= false;
1196 adjEntry aeNSucc
= (aeN
->succ()) ? aeN
->succ() : ae
->theNode()->firstAdj();
1197 aeExtFace
= adjMaxFace
;
1200 if (aeExtFace
->theEdge() == aeNSucc
->theEdge())
1202 succInExtFace
= true;
1206 if (aeExtFace
->theEdge() == aeN
->theEdge())
1208 aeNInExtFace
= true;
1212 aeExtFace
= aeExtFace
->faceCycleSucc();
1213 } while(aeExtFace
!= adjMaxFace
);
1214 if (aeNInExtFace
&& succInExtFace
)
1215 m_leftNode
= aeN
->twinNode();
1217 m_leftNode
= aeN
->theNode();
1219 node twinTN
= S
.twinTreeNode(aeN
->theEdge());
1220 if (!(referenceEdge
== 0))
1222 if (aeN
->theEdge()->source() == aeN
->theNode())
1224 if (aeN
->theEdge()->target() == referenceEdge
->source())
1225 adjBeforeNodeArrayTarget
[twinTN
] = adjBeforeNodeArraySource
[mu
];
1226 else if (aeN
->theEdge()->target() == referenceEdge
->target())
1227 adjBeforeNodeArrayTarget
[twinTN
] = adjBeforeNodeArrayTarget
[mu
];
1231 if (aeN
->theEdge()->source() == referenceEdge
->source())
1232 adjBeforeNodeArraySource
[twinTN
] = adjBeforeNodeArraySource
[mu
];
1233 else if (aeN
->theEdge()->source() == referenceEdge
->target())
1234 adjBeforeNodeArraySource
[twinTN
] = adjBeforeNodeArrayTarget
[mu
];
1239 adjEntryForNode(aeN
, before
, spqrTree
, treeNodeTreated
, mu
,
1240 m_leftNode
, nodeLength
, edgeLength
, newOrder
,
1241 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
1244 //if the other node adjacent to the current treated edge is not in the
1245 //max face, put written edges into an buffer and clear the adjacency
1246 //list of that node.
1247 if (maxFaceNodes
.search(aeN
->twinNode()) == -1)
1249 node orig_aeN_twin_theNode
= S
.original(aeN
->twinNode());
1250 buffer
[aeN
->theEdge()] = newOrder
[orig_aeN_twin_theNode
];
1251 newOrder
[orig_aeN_twin_theNode
].clear();
1253 } //for (adjEntry aeN = m_start_ae; [...]
1254 } //for (adjEntry ae = start_ae; [...]
1256 //Simple copy of not treated node's adjacency lists (internal nodes). Setting
1257 //of left node not necessary, because all nodes are not in external face.
1259 forall_nodes(v
, S
.getGraph())
1264 node v_original
= S
.original(v
);
1265 nodeTreated
[v
] = true;
1266 ListIterator
<adjEntry
> before
;
1267 for (adjEntry ae
= v
->firstAdj(); ae
; ae
= ae
->succ())
1269 if (buffer
[ae
->theEdge()].empty())
1271 adjEntryForNode(ae
, before
, spqrTree
, treeNodeTreated
, mu
,
1272 ae
->theNode(), nodeLength
, edgeLength
, newOrder
,
1273 adjBeforeNodeArraySource
, adjBeforeNodeArrayTarget
,
1276 if (!nodeTreated
[ae
->twinNode()])
1278 node orig_ae_twin_theNode
= S
.original(ae
->twinNode());
1279 buffer
[ae
->theEdge()] = newOrder
[orig_ae_twin_theNode
];
1280 newOrder
[orig_ae_twin_theNode
].clear();
1285 buffer
[ae
->theEdge()].reverse();
1286 for (ListIterator
<adjEntry
> it
= buffer
[ae
->theEdge()].begin(); it
.valid(); it
++)
1288 if (!before
.valid())
1289 before
= newOrder
[v_original
].pushFront(*it
);
1291 before
= newOrder
[v_original
].insertBefore(*it
, before
);
1300 void EmbedderMaxFaceBiconnectedGraphs
<T
>::compute(
1302 const NodeArray
<T
>& nodeLength
,
1303 const EdgeArray
<T
>& edgeLength
,
1304 StaticSPQRTree
& spqrTree
,
1305 NodeArray
< EdgeArray
<T
> >& edgeLengthSkel
)
1307 //base cases (SPQR-tree implementation would crash for such graphs):
1308 if (G
.numberOfNodes() <= 1 || G
.numberOfEdges() <= 2)
1311 //set length for all real edges in skeletons to length of the original edge
1312 //and initialize edge lengths for virtual edges with 0:
1313 edgeLengthSkel
.init(spqrTree
.tree());
1315 forall_nodes(v
, spqrTree
.tree())
1317 edgeLengthSkel
[v
].init(spqrTree
.skeleton(v
).getGraph());
1319 forall_edges(e
, spqrTree
.skeleton(v
).getGraph())
1321 if (spqrTree
.skeleton(v
).isVirtual(e
))
1322 edgeLengthSkel
[v
][e
] = 0;
1324 edgeLengthSkel
[v
][e
] = edgeLength
[spqrTree
.skeleton(v
).realEdge(e
)];
1328 //set component-length for all non-reference edges:
1329 bottomUpTraversal(spqrTree
, spqrTree
.rootNode(), nodeLength
, edgeLengthSkel
);
1330 //set component length for all reference edges:
1331 topDownTraversal(spqrTree
, spqrTree
.rootNode(), nodeLength
, edgeLengthSkel
);
1336 T EmbedderMaxFaceBiconnectedGraphs
<T
>::computeSize(
1338 const NodeArray
<T
>& nodeLength
,
1339 const EdgeArray
<T
>& edgeLength
)
1341 //base cases (SPQR-tree implementation would crash for such graphs):
1342 OGDF_ASSERT(G
.numberOfNodes() >= 2)
1343 if (G
.numberOfEdges() == 1)
1345 edge e
= G
.firstEdge();
1346 return edgeLength
[e
] + nodeLength
[e
->source()]+ nodeLength
[e
->target()];
1348 if (G
.numberOfEdges() == 2)
1350 edge e1
= G
.firstEdge();
1351 edge e2
= e1
->succ();
1352 return edgeLength
[e1
] + edgeLength
[e2
] + nodeLength
[e1
->source()] + nodeLength
[e1
->target()];
1354 StaticSPQRTree
spqrTree(G
);
1355 NodeArray
< EdgeArray
<T
> > edgeLengthSkel
;
1356 return computeSize(G
, nodeLength
, edgeLength
, spqrTree
, edgeLengthSkel
);
1361 T EmbedderMaxFaceBiconnectedGraphs
<T
>::computeSize(
1363 const NodeArray
<T
>& nodeLength
,
1364 const EdgeArray
<T
>& edgeLength
,
1365 StaticSPQRTree
& spqrTree
,
1366 NodeArray
< EdgeArray
<T
> >& edgeLengthSkel
)
1368 //base cases (SPQR-tree implementation would crash for such graphs):
1369 OGDF_ASSERT(G
.numberOfNodes() >= 2)
1370 if (G
.numberOfEdges() == 1)
1372 edge e
= G
.firstEdge();
1373 return edgeLength
[e
] + nodeLength
[e
->source()]+ nodeLength
[e
->target()];
1375 if (G
.numberOfEdges() == 2)
1377 edge e1
= G
.firstEdge();
1378 edge e2
= e1
->succ();
1379 return edgeLength
[e1
] + edgeLength
[e2
] + nodeLength
[e1
->source()] + nodeLength
[e1
->target()];
1382 //set length for all real edges in skeletons to length of the original edge
1383 //and initialize edge lengths for virtual edges with 0:
1384 edgeLengthSkel
.init(spqrTree
.tree());
1386 forall_nodes(v
, spqrTree
.tree())
1388 edgeLengthSkel
[v
].init(spqrTree
.skeleton(v
).getGraph());
1390 forall_edges(e
, spqrTree
.skeleton(v
).getGraph())
1392 if (spqrTree
.skeleton(v
).isVirtual(e
))
1393 edgeLengthSkel
[v
][e
] = 0;
1395 edgeLengthSkel
[v
][e
] = edgeLength
[spqrTree
.skeleton(v
).realEdge(e
)];
1399 //set component-length for all non-reference edges:
1400 bottomUpTraversal(spqrTree
, spqrTree
.rootNode(), nodeLength
, edgeLengthSkel
);
1401 //set component length for all reference edges:
1402 topDownTraversal(spqrTree
, spqrTree
.rootNode(), nodeLength
, edgeLengthSkel
);
1406 forall_nodes(mu
, spqrTree
.tree())
1408 //Expand all faces in skeleton(mu) and get size of the largest of them:
1409 T sizeMu
= largestFaceInSkeleton(spqrTree
, mu
, nodeLength
, edgeLengthSkel
);
1410 if (sizeMu
> biggestFace
)
1411 biggestFace
= sizeMu
;
1419 T EmbedderMaxFaceBiconnectedGraphs
<T
>::computeSize(
1422 const NodeArray
<T
>& nodeLength
,
1423 const EdgeArray
<T
>& edgeLength
)
1425 //base cases (SPQR-tree implementation would crash for such graphs):
1426 OGDF_ASSERT(G
.numberOfNodes() >= 2)
1427 if (G
.numberOfEdges() == 1)
1429 edge e
= G
.firstEdge();
1430 return edgeLength
[e
] + nodeLength
[e
->source()] + nodeLength
[e
->target()];
1432 if (G
.numberOfEdges() == 2)
1434 edge e1
= G
.firstEdge();
1435 edge e2
= e1
->succ();
1436 return edgeLength
[e1
] + edgeLength
[e2
] + nodeLength
[e1
->source()] + nodeLength
[e1
->target()];
1438 StaticSPQRTree
spqrTree(G
);
1439 NodeArray
< EdgeArray
<T
> > edgeLengthSkel
;
1440 compute(G
, nodeLength
, edgeLength
, spqrTree
, edgeLengthSkel
);
1441 return computeSize(G
, n
, nodeLength
, edgeLength
, spqrTree
, edgeLengthSkel
);
1446 T EmbedderMaxFaceBiconnectedGraphs
<T
>::computeSize(
1449 const NodeArray
<T
>& nodeLength
,
1450 const EdgeArray
<T
>& edgeLength
,
1451 StaticSPQRTree
& spqrTree
)
1453 NodeArray
< EdgeArray
<T
> > edgeLengthSkel
;
1454 compute(G
, nodeLength
, edgeLength
, spqrTree
, edgeLengthSkel
);
1455 return computeSize(G
, n
, nodeLength
, edgeLength
, spqrTree
, edgeLengthSkel
);
1460 T EmbedderMaxFaceBiconnectedGraphs
<T
>::computeSize(
1463 const NodeArray
<T
>& nodeLength
,
1464 const EdgeArray
<T
>& edgeLength
,
1465 StaticSPQRTree
& spqrTree
,
1466 const NodeArray
< EdgeArray
<T
> >& edgeLengthSkel
)
1468 //base cases (SPQR-tree implementation would crash for such graphs):
1469 OGDF_ASSERT(G
.numberOfNodes() >= 2)
1470 if (G
.numberOfEdges() == 1)
1472 edge e
= G
.firstEdge();
1473 return edgeLength
[e
] + nodeLength
[e
->source()] + nodeLength
[e
->target()];
1475 else if (G
.numberOfEdges() == 2)
1477 edge e1
= G
.firstEdge();
1478 edge e2
= e1
->succ();
1479 return edgeLength
[e1
] + edgeLength
[e2
] + nodeLength
[e1
->source()] + nodeLength
[e1
->target()];
1483 node
* mus
= new node
[n
->degree()];
1486 forall_adj_edges(nAdjEdges
, n
)
1488 mus
[i
] = spqrTree
.skeletonOfReal(nAdjEdges
).treeNode();
1489 bool alreadySeenMu
= false;
1490 for (int j
= 0; j
< i
&& !alreadySeenMu
; j
++)
1492 if (mus
[i
] == mus
[j
])
1493 alreadySeenMu
= true;
1502 //Expand all faces in skeleton(mu) containing n and get size of the largest of them:
1503 T sizeInMu
= largestFaceContainingNode(spqrTree
, mus
[i
], n
, nodeLength
, edgeLengthSkel
);
1504 if (sizeInMu
> biggestFace
)
1505 biggestFace
= sizeInMu
;
1517 void EmbedderMaxFaceBiconnectedGraphs
<T
>::bottomUpTraversal(
1518 StaticSPQRTree
& spqrTree
,
1520 const NodeArray
<T
>& nodeLength
,
1521 NodeArray
< EdgeArray
<T
> >& edgeLength
)
1525 forall_adj_edges(ed
, mu
)
1527 if (ed
->source() == mu
)
1528 bottomUpTraversal(spqrTree
, ed
->target(), nodeLength
, edgeLength
);
1532 forall_edges(e
, spqrTree
.skeleton(mu
).getGraph())
1534 //do not treat real edges here and do not treat reference edges:
1535 if (!spqrTree
.skeleton(mu
).isVirtual(e
) || e
== spqrTree
.skeleton(mu
).referenceEdge())
1538 //pertinent node of e in the SPQR-tree:
1539 node nu
= spqrTree
.skeleton(mu
).twinTreeNode(e
);
1540 //reference edge of nu (virtual edge in nu associated with mu):
1541 edge er
= spqrTree
.skeleton(nu
).referenceEdge();
1542 //sum of the lengths of the two poles of mu:
1543 node refEdgeSource
= spqrTree
.skeleton(nu
).referenceEdge()->source();
1544 node origRefEdgeSource
= spqrTree
.skeleton(nu
).original(refEdgeSource
);
1545 node refEdgeTarget
= spqrTree
.skeleton(nu
).referenceEdge()->target();
1546 node origRefEdgeTarget
= spqrTree
.skeleton(nu
).original(refEdgeTarget
);
1547 T ell
= nodeLength
[origRefEdgeSource
] + nodeLength
[origRefEdgeTarget
];
1549 if (spqrTree
.typeOf(nu
) == SPQRTree::SNode
)
1551 //size of a face in skeleton(nu) minus ell
1554 forall_nodes(nS
, spqrTree
.skeleton(nu
).getGraph())
1555 sizeOfFace
+= nodeLength
[spqrTree
.skeleton(nu
).original(nS
)];
1558 forall_edges(eS
, spqrTree
.skeleton(nu
).getGraph())
1559 sizeOfFace
+= edgeLength
[nu
][eS
];
1561 edgeLength
[mu
][e
] = sizeOfFace
- ell
;
1563 else if (spqrTree
.typeOf(nu
) == SPQRTree::PNode
)
1565 //length of the longest edge different from er in skeleton(nu)
1566 edge longestEdge
= 0;
1567 forall_edges(ed
, spqrTree
.skeleton(nu
).getGraph())
1569 if (!(ed
== er
) && ( longestEdge
== 0
1570 || edgeLength
[nu
][ed
] > edgeLength
[nu
][longestEdge
]))
1575 edgeLength
[mu
][e
] = edgeLength
[nu
][longestEdge
];
1577 else if (spqrTree
.typeOf(nu
) == SPQRTree::RNode
)
1579 //size of the largest face containing er in skeleton(nu) minus ell
1580 //Calculate an embedding of the graph (it exists only two which are
1581 //mirror-symmetrical):
1582 planarEmbed(spqrTree
.skeleton(nu
).getGraph());
1583 CombinatorialEmbedding
combinatorialEmbedding(spqrTree
.skeleton(nu
).getGraph());
1584 T biggestFaceSize
= -1;
1586 forall_faces(f
, combinatorialEmbedding
)
1589 bool containsEr
= false;
1591 forall_face_adj(ae
, f
)
1593 if (ae
->theEdge() == er
)
1595 sizeOfFace
+= edgeLength
[nu
][ae
->theEdge()]
1596 + nodeLength
[spqrTree
.skeleton(nu
).original(ae
->theNode())];
1599 if (containsEr
&& sizeOfFace
> biggestFaceSize
)
1600 biggestFaceSize
= sizeOfFace
;
1603 edgeLength
[mu
][e
] = biggestFaceSize
- ell
;
1605 else //should never happen
1606 edgeLength
[mu
][e
] = 1;
1612 void EmbedderMaxFaceBiconnectedGraphs
<T
>::topDownTraversal(
1613 StaticSPQRTree
& spqrTree
,
1615 const NodeArray
<T
>& nodeLength
,
1616 NodeArray
< EdgeArray
<T
> >& edgeLength
)
1619 Skeleton
& S
= spqrTree
.skeleton(mu
);
1621 //Get all reference edges of the children nu of mu and set their component length:
1623 forall_adj_edges(ed
, mu
)
1625 if (ed
->source() != mu
)
1628 node nu
= ed
->target();
1629 edge referenceEdgeOfNu
= spqrTree
.skeleton(nu
).referenceEdge();
1630 edge eSnu
= spqrTree
.skeleton(nu
).twinEdge(referenceEdgeOfNu
);
1631 if (spqrTree
.typeOf(mu
) == SPQRTree::SNode
)
1633 //Let L be the sum of the length of all vertices and edges in S. The component
1634 //length of the reference edge of nu is L minus the length of e_{S, nu} minus
1635 //the lengths of the two vertices incident to e_{S, nu}.
1638 forall_edges(ed2
, S
.getGraph())
1639 L
+= edgeLength
[mu
][ed2
];
1641 forall_nodes(no
, S
.getGraph())
1642 L
+= nodeLength
[S
.original(no
)];
1644 edgeLength
[nu
][referenceEdgeOfNu
] =
1645 L
- edgeLength
[mu
][eSnu
] - nodeLength
[S
.original(eSnu
->source())] - nodeLength
[S
.original(eSnu
->target())];
1647 else if (spqrTree
.typeOf(mu
) == SPQRTree::PNode
)
1649 //The component length of the reference edge of nu is the length of the longest
1650 //edge in S different from e_{S, nu}.
1652 edge longestEdge
= 0;
1653 forall_edges(ed2
, S
.getGraph())
1655 if (ed2
!= eSnu
&& ( longestEdge
== 0 || edgeLength
[mu
][ed2
] > edgeLength
[mu
][longestEdge
] ))
1660 edgeLength
[nu
][referenceEdgeOfNu
] = edgeLength
[mu
][longestEdge
];
1662 else if (spqrTree
.typeOf(mu
) == SPQRTree::RNode
)
1664 //Let f be the largest face in S containing e_{S, nu}. The component length of
1665 //the reference edge of nu is the size of f minus the length of e_{S, nu} minus
1666 //the lengths of the two vertices incident to e_{S, nu}.
1668 //Calculate an embedding of the graph (it exists only two which are
1669 //mirror-symmetrical):
1670 planarEmbed(S
.getGraph());
1671 CombinatorialEmbedding
combinatorialEmbedding(S
.getGraph());
1672 T biggestFaceSize
= -1;
1674 forall_faces(f
, combinatorialEmbedding
)
1677 bool containsESnu
= false;
1679 forall_face_adj(ae
, f
)
1681 if (ae
->theEdge() == eSnu
)
1682 containsESnu
= true;
1683 sizeOfFace
+= edgeLength
[mu
][ae
->theEdge()]
1684 + nodeLength
[S
.original(ae
->theNode())];
1686 if (containsESnu
&& sizeOfFace
> biggestFaceSize
)
1687 biggestFaceSize
= sizeOfFace
;
1689 edgeLength
[nu
][referenceEdgeOfNu
] =
1690 biggestFaceSize
- edgeLength
[mu
][eSnu
]
1691 - nodeLength
[S
.original(eSnu
->source())]
1692 - nodeLength
[S
.original(eSnu
->target())];
1694 else //should never happen
1695 edgeLength
[nu
][referenceEdgeOfNu
] = 0;
1698 topDownTraversal(spqrTree
, ed
->target(), nodeLength
, edgeLength
);
1704 T EmbedderMaxFaceBiconnectedGraphs
<T
>::largestFaceContainingNode(
1705 const StaticSPQRTree
& spqrTree
,
1708 const NodeArray
<T
>& nodeLength
,
1709 const NodeArray
< EdgeArray
<T
> >& edgeLength
)
1711 bool containsARealEdge
= false;
1712 if (spqrTree
.typeOf(mu
) == SPQRTree::RNode
)
1714 //The largest face containing n is the largest face containg n in any embedding of S.
1715 planarEmbed(spqrTree
.skeleton(mu
).getGraph());
1716 CombinatorialEmbedding
combinatorialEmbedding(spqrTree
.skeleton(mu
).getGraph());
1717 T biggestFaceSize
= -1;
1719 forall_faces(f
, combinatorialEmbedding
)
1722 bool containingN
= false;
1723 bool m_containsARealEdge
= false;
1725 forall_face_adj(ae
, f
)
1727 if (spqrTree
.skeleton(mu
).original(ae
->theNode()) == n
)
1729 if (!spqrTree
.skeleton(mu
).isVirtual(ae
->theEdge()))
1730 m_containsARealEdge
= true;
1731 sizeOfFace
+= edgeLength
[mu
][ae
->theEdge()];
1732 sizeOfFace
+= nodeLength
[spqrTree
.skeleton(mu
).original(ae
->theNode())];
1734 if (containingN
&& sizeOfFace
> biggestFaceSize
)
1736 biggestFaceSize
= sizeOfFace
;
1737 containsARealEdge
= m_containsARealEdge
;
1741 if (!containsARealEdge
)
1743 return biggestFaceSize
;
1745 else if (spqrTree
.typeOf(mu
) == SPQRTree::PNode
)
1747 //Find the two longest edges, they define the largest face containg n.
1749 edge longestEdges
[2] = {0, 0};
1750 forall_edges(edgeWalker
, spqrTree
.skeleton(mu
).getGraph())
1752 if ( longestEdges
[1] == 0
1753 || edgeLength
[mu
][edgeWalker
] > edgeLength
[mu
][longestEdges
[1]])
1755 if ( longestEdges
[0] == 0
1756 || edgeLength
[mu
][edgeWalker
] > edgeLength
[mu
][longestEdges
[0]])
1758 longestEdges
[1] = longestEdges
[0];
1759 longestEdges
[0] = edgeWalker
;
1762 longestEdges
[1] = edgeWalker
;
1766 if ( !spqrTree
.skeleton(mu
).isVirtual(longestEdges
[0])
1767 || !spqrTree
.skeleton(mu
).isVirtual(longestEdges
[1]))
1769 containsARealEdge
= true;
1772 if (!containsARealEdge
)
1775 return edgeLength
[mu
][longestEdges
[0]] + edgeLength
[mu
][longestEdges
[1]];
1777 else if (spqrTree
.typeOf(mu
) == SPQRTree::SNode
)
1779 //The largest face containing n is any face in the single existing embedding of S.
1782 forall_nodes(nS
, spqrTree
.skeleton(mu
).getGraph())
1783 sizeOfFace
+= nodeLength
[spqrTree
.skeleton(mu
).original(nS
)];
1786 forall_edges(eS
, spqrTree
.skeleton(mu
).getGraph())
1788 if (!spqrTree
.skeleton(mu
).isVirtual(eS
))
1789 containsARealEdge
= true;
1790 sizeOfFace
+= edgeLength
[mu
][eS
];
1793 if (!containsARealEdge
)
1799 //should never end here...
1805 T EmbedderMaxFaceBiconnectedGraphs
<T
>::largestFaceInSkeleton(
1806 const StaticSPQRTree
& spqrTree
,
1808 const NodeArray
<T
>& nodeLength
,
1809 const NodeArray
< EdgeArray
<T
> >& edgeLength
)
1811 bool containsARealEdge
= false;
1812 if (spqrTree
.typeOf(mu
) == SPQRTree::RNode
)
1814 //The largest face is a largest face in any embedding of S.
1815 planarEmbed(spqrTree
.skeleton(mu
).getGraph());
1816 CombinatorialEmbedding
combinatorialEmbedding(spqrTree
.skeleton(mu
).getGraph());
1817 T biggestFaceSize
= -1;
1819 forall_faces(f
, combinatorialEmbedding
)
1821 bool m_containsARealEdge
= false;
1824 forall_face_adj(ae
, f
)
1826 //node originalNode = spqrTree.skeleton(mu).original(ae->theNode());
1827 if (!spqrTree
.skeleton(mu
).isVirtual(ae
->theEdge()))
1828 m_containsARealEdge
= true;
1829 sizeOfFace
+= edgeLength
[mu
][ae
->theEdge()]
1830 + nodeLength
[spqrTree
.skeleton(mu
).original(ae
->theNode())];
1833 if (sizeOfFace
> biggestFaceSize
)
1835 biggestFaceSize
= sizeOfFace
;
1836 containsARealEdge
= m_containsARealEdge
;
1840 if (!containsARealEdge
)
1843 return biggestFaceSize
;
1845 else if (spqrTree
.typeOf(mu
) == SPQRTree::PNode
)
1847 //Find the two longest edges, they define the largest face.
1849 edge longestEdges
[2] = {0, 0};
1850 forall_edges(edgeWalker
, spqrTree
.skeleton(mu
).getGraph())
1852 if ( longestEdges
[1] == 0
1853 || edgeLength
[mu
][edgeWalker
] > edgeLength
[mu
][longestEdges
[1]])
1855 if ( longestEdges
[0] == 0
1856 || edgeLength
[mu
][edgeWalker
] > edgeLength
[mu
][longestEdges
[0]])
1858 longestEdges
[1] = longestEdges
[0];
1859 longestEdges
[0] = edgeWalker
;
1862 longestEdges
[1] = edgeWalker
;
1866 if ( !spqrTree
.skeleton(mu
).isVirtual(longestEdges
[0])
1867 || !spqrTree
.skeleton(mu
).isVirtual(longestEdges
[1]))
1869 containsARealEdge
= true;
1872 if (!containsARealEdge
)
1875 return edgeLength
[mu
][longestEdges
[0]] + edgeLength
[mu
][longestEdges
[1]];
1877 else if (spqrTree
.typeOf(mu
) == SPQRTree::SNode
)
1879 //The largest face is any face in the single existing embedding of S.
1882 forall_nodes(nS
, spqrTree
.skeleton(mu
).getGraph())
1883 sizeOfFace
+= nodeLength
[spqrTree
.skeleton(mu
).original(nS
)];
1886 forall_edges(eS
, spqrTree
.skeleton(mu
).getGraph())
1888 if (!spqrTree
.skeleton(mu
).isVirtual(eS
))
1889 containsARealEdge
= true;
1890 sizeOfFace
+= edgeLength
[mu
][eS
];
1893 if (!containsARealEdge
)
1899 //should never end here...
1904 } // end namespace ogdf