?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / src / cluster / CconnectClusterPlanarEmbed.cpp
blob479a192d7ca5f0249e6969128e16754e8ea1b2f3
1 /*
2 * $Revision: 2599 $
3 *
4 * last checkin:
5 * $Author: chimani $
6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of Cluster Planarity tests and Cluster
11 * Planar embedding for C-connected Cluster Graphs
12 *
13 * \author Sebastian Leipert
14 *
15 * \par License:
16 * This file is part of the Open Graph Drawing Framework (OGDF).
17 *
18 * \par
19 * Copyright (C)<br>
20 * See README.txt in the root directory of the OGDF installation for details.
21 *
22 * \par
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
27 * for details.
28 *
29 * \par
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.
34 *
35 * \par
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.
40 *
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
43
44
45 //#include <qapplication.h>
46 #include <ogdf/basic/Graph.h>
47
48 #include <ogdf/cluster/CconnectClusterPlanarEmbed.h>
49
50 #include <ogdf/basic/simple_graph_alg.h>
51 #include <ogdf/basic/extended_graph_alg.h>
52 #include <ogdf/basic/AdjEntryArray.h>
53
54 #include <ogdf/internal/planarity/EmbedPQTree.h>
55
56
57 namespace ogdf {
58
59 // Constructor
60 CconnectClusterPlanarEmbed::CconnectClusterPlanarEmbed()
61 {
62 ogdf::strcpy(errorCode,124,"\0");
63 m_errorCode = none;
64 }
65
66 // Destructor
67 CconnectClusterPlanarEmbed::~CconnectClusterPlanarEmbed()
68 {
69 }
70
71
72 // Tests if a ClusterGraph is c-planar and embedds it.
73 bool CconnectClusterPlanarEmbed::embed(ClusterGraph &C,Graph &G)
74 {
75
76 OGDF_ASSERT(C.consistencyCheck())
77
78 if (G.numberOfNodes() <= 1) return true;
79
80 // Initialize Node and cluster arrays associated with original graph.
81 m_instance = &C;
82 m_nodeTableOrig2Copy.init(G,0);
83 m_clusterTableOrig2Copy.init(C,0);
84 m_clusterEmbedding.init(C,0);
85 m_clusterSubgraph.init(C,0);
86 m_clusterSubgraphHubs.init(C,0);
87 m_clusterSubgraphWheelGraph.init(C,0);
88 m_clusterClusterGraph.init(C,0);
89 m_clusterNodeTableNew2Orig.init(C,0);
90 m_clusterOutgoingEdgesAnker.init(C,0);
91 m_clusterSuperSink.init(C,0);
92 m_clusterPQContainer.init(C);
93 m_unsatisfiedCluster.init(C,false);
94
95 // Copy the graph (necessary, since we modify it throughout the planarity test)
96 Graph Gcopy;
97 ClusterGraph Ccopy(C,Gcopy,m_clusterTableOrig2Copy,m_nodeTableOrig2Copy);
98
99 // Initialize translation tables for nodes and clusters
100 m_clusterTableCopy2Orig.init(Ccopy,0);
101 cluster c;
102 forall_clusters(c,C)
103 {
104 cluster c1 = m_clusterTableOrig2Copy[c];
105 m_clusterTableCopy2Orig[c1] = c;
106 }
107 m_nodeTableCopy2Orig.init(Gcopy,0);
108 node v;
109 forall_nodes(v,G)
110 {
111 node w = m_nodeTableOrig2Copy[v];
112 m_nodeTableCopy2Orig[w] = v;
113 }
114 // Remove empty clusters
115 SList<cluster> removeCluster;
116 forall_clusters(c,Ccopy)
117 {
118 if (c->cCount() == 0 && c->nCount() == 0)
119 removeCluster.pushBack(c);
120 }
121 while (!removeCluster.empty())
122 {
123 c = removeCluster.popFrontRet();
124 m_unsatisfiedCluster[m_clusterTableCopy2Orig[c]] = true;
125 cluster parent = c->parent();
126 Ccopy.delCluster(c);
127 if (parent->cCount() == 0 && parent->nCount() == 0)
128 removeCluster.pushBack(parent);
129 }
130 while (Ccopy.rootCluster()->cCount() == 1 && Ccopy.rootCluster()->nCount() == 0)
131 {
132 c = (*(Ccopy.rootCluster()->cBegin()));
133 m_unsatisfiedCluster[m_clusterTableCopy2Orig[c]] = true;
134 Ccopy.delCluster(c);
135 }
136
137 OGDF_ASSERT(Ccopy.consistencyCheck());
138
139 // Initialize node and cluster arrays associated with copied graph.
140 m_clusterPQTree.init(Ccopy,0);
141 m_currentHubs.init(Gcopy,false);
142 m_wheelGraphNodes.init(Gcopy,0);
143 m_outgoingEdgesAnker.init(Gcopy,0);
144
145 // Planarity test
146 bool cPlanar = preProcess(Ccopy,Gcopy);
147
148 if (cPlanar)
149 {
150 OGDF_ASSERT(Gcopy.representsCombEmbedding())
151 //OGDF_ASSERT(Ccopy.consistencyCheck());
152
153 recursiveEmbed(Ccopy,Gcopy);
154 OGDF_ASSERT(Ccopy.consistencyCheck());
155
156 copyEmbedding(Ccopy,Gcopy,C,G);
157
158 C.adjAvailable(true);
159
160 }
161 else
162 nonPlanarCleanup(Ccopy,Gcopy);
163
164
165 // Cleanup
166 forall_clusters(c,C)
167 {
168 if (m_clusterSubgraph[c] != 0 && c != C.rootCluster())
169 delete m_clusterSubgraph[c];
170 }
171
172
173 // Deinitialize all node and cluster arrays
174 m_parallelEdges.init();
175 m_isParallel.init();
176 m_clusterPQTree.init();
177 m_clusterEmbedding.init();
178 m_clusterSubgraph.init();
179 m_clusterSubgraphHubs.init();
180 m_clusterSubgraphWheelGraph.init();
181 m_clusterClusterGraph.init();
182 m_clusterNodeTableNew2Orig.init();
183 m_clusterOutgoingEdgesAnker.init();
184 m_clusterSuperSink.init();
185 m_clusterPQContainer.init();
186
187 m_clusterTableOrig2Copy.init();
188 m_clusterTableCopy2Orig.init();
189 m_nodeTableOrig2Copy.init();
190 m_nodeTableCopy2Orig.init();
191 m_currentHubs.init();
192 m_wheelGraphNodes.init();
193 m_outgoingEdgesAnker.init();
194
195 return cPlanar;
196 }
197
198
199
200 // Tests if a ClusterGraph is c-planar and embedds it.
201 // Specifies reason for non planarity
202 bool CconnectClusterPlanarEmbed::embed(ClusterGraph &C,Graph &G, char (&code)[124])
203 {
204
205 bool cPlanar = embed(C,G);
206 ogdf::strcpy(code,124,errorCode);
207 return cPlanar;
208 }
209
210
211
212
213
214 //
215 // CallTree:
216 //
217 // call(ClusterGraph &C)
218 //
219 // preProcess(ClusterGraph &C,Graph &G)
220 //
221 // planarityTest(ClusterGraph &C,cluster &act,Graph &G)
222 //
223 // foreach ChildCluster
224 // planarityTest(ClusterGraph &C,cluster &act,Graph &G)
225 //
226 // preparation(Graph &G,cluster &origCluster)
227 //
228 // foreach biconnected Component
229 // doTest(Graph &G,NodeArray<int> &numbering,cluster &origCluster)
230 //
231
232
233
234 /*******************************************************************************
235 copyEmbedding
236 ********************************************************************************/
237
238 // Copies the embedding of Ccopy to C
239
240 void CconnectClusterPlanarEmbed::copyEmbedding(
241 ClusterGraph &Ccopy,
242 Graph &Gcopy,
243 ClusterGraph &C,
244 Graph &G)
245 {
246
247 node vCopy;
248 node v;
249 cluster c;
250 OGDF_ASSERT(Gcopy.representsCombEmbedding())
251
252 OGDF_ASSERT(Ccopy.representsCombEmbedding())
253
254 AdjEntryArray<adjEntry> adjTableCopy2Orig(Gcopy);
255 AdjEntryArray<adjEntry> adjTableOrig2Copy(G);
256 AdjEntryArray<bool> visited(G,false); // For parallel edges
257 EdgeArray<edge> edgeTableCopy2Orig(Gcopy,0); // Translation table for parallel edges
258 EdgeArray<bool> parallelEdge(Gcopy,false); // Marks parallel edges in copy Graph
259 AdjEntryArray<adjEntry> parallelEntryPoint(G,0); // For storing information on parallel
260 // edges for cluster adjlistst.
261 AdjEntryArray<bool> parallelToBeIgnored(Gcopy,false);// For storing information on parallel
262 // edges for cluster adjlistst.
263
264 // prepare parallel Edges
265 prepareParallelEdges(G);
266 NodeArray<SListPure<adjEntry> > entireEmbedding(G);
267
268 //process over all copy nodes
269 forall_nodes(vCopy,Gcopy)
270 {
271 //get the original node
272 node wOrig = m_nodeTableCopy2Orig[vCopy];
273
274 adjEntry vAdj;
275
276 //process over all adjacent copy edges
277 SList<adjEntry> entries;
278 Gcopy.adjEntries(vCopy,entries);
279 SListIterator<adjEntry> itv;
280 for (itv = entries.begin(); itv.valid(); itv++)
281 {
282 vAdj = *itv;
283 node vN = vAdj->twinNode();
284 node wN = m_nodeTableCopy2Orig[vN];
285 m_nodeTableOrig2Copy[wN] = vN;
286
287 adjEntry wAdj;
288 forall_adj(wAdj,wOrig)
289 {
290
291 if (edgeTableCopy2Orig[vAdj->theEdge()] != 0 &&
292 m_isParallel[edgeTableCopy2Orig[vAdj->theEdge()]])
293 // Break if parallel edge (not a reference edge) that has already been assigned.
294 break;
295 if (wAdj->twinNode() == wN
296 && !visited[wAdj] && !m_isParallel[wAdj->theEdge()])
297 // && !m_isParallel[wAdj->theEdge()])
298 // Either a non parallel edge or the reference edge of a set of
299 // parallel edges.
300 {
301 adjTableCopy2Orig[vAdj] = wAdj;
302 adjTableOrig2Copy[wAdj] = vAdj;
303 // adjTableCopy2Orig[vAdj->twin()] = wAdj->twin();
304 // adjTableOrig2Copy[wAdj->twin()] = vAdj->twin();
305 edgeTableCopy2Orig[vAdj->theEdge()] = wAdj->theEdge();
306 #ifdef OGDF_DEBUG
307 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
308 cout << "Orig " << wAdj << " " << wAdj->index() << "\t twin " << wAdj->twin()->index() << endl;
309 cout << "Copy " << vAdj << " " << vAdj->index() << "\t twin " << vAdj->twin()->index() << endl << endl;}
310 //qDebug ("Visited: %d->%d %d", wAdj->theNode()->index(),
311 // wAdj->twinNode()->index(),
312 // wAdj->index());
313 #endif
314 entireEmbedding[wOrig].pushBack(wAdj); // if no parallel edges exist,
315 // this will be our embedding.
316 // entireEmbedding[wN].pushFront(wAdj->twin());
317 visited[wAdj] = true; // for multi-edges
318 // visited[wAdj->twin()] = true; // for multi-edges
319 break;
320 }
321 else if (wAdj->twinNode() == wN && !visited[wAdj])
322 // A parallel edge that is not the reference edge.
323 // We need to set the translation table
324 {
325 adjTableCopy2Orig[vAdj] = wAdj;
326 adjTableOrig2Copy[wAdj] = vAdj;
327 adjTableCopy2Orig[vAdj->twin()] = wAdj->twin();
328 adjTableOrig2Copy[wAdj->twin()] = vAdj->twin();
329 edgeTableCopy2Orig[vAdj->theEdge()] = wAdj->theEdge();
330 visited[wAdj] = true; // So we do not consider parallel edges twice.
331 visited[wAdj->twin()] = true; // So we do not consider parallel edges twice.
332 }
333
334 }
335 }
336 }
337
338 // Locate all parallel edges
339 // Sort them within the adjacency lists,
340 // such that they appear consecutively.
341 NodeArray<SListPure<adjEntry> > newEntireEmbedding(G);
342 NodeArray<SListPure<adjEntry> > newEntireEmbeddingCopy(Gcopy);
343
344 if (m_parallelCount > 0)
345 {
346 forall_nodes(v,G)
347 {
348 SListIterator<adjEntry> it;
349 for(it = entireEmbedding[v].begin();it.valid();it++)
350 {
351 edge e = (*it)->theEdge();
352
353 if (!m_parallelEdges[e].empty())
354 {
355 // This edge is the reference edge
356 // of a bundle of parallel edges
357
358 ListIterator<edge> it;
359 // If v is source of e, insert the parallel edges
360 // in the order stored in the list.
361 if (e->adjSource()->theNode() == v)
362 {
363 adjEntry adj = e->adjSource();
364
365 newEntireEmbedding[v].pushBack(adj);
366 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]].pushBack(adjTableOrig2Copy[adj]);
367
368 parallelEntryPoint[e->adjSource()] = adj;
369 parallelToBeIgnored[adjTableOrig2Copy[adj]] = true;
370
371 for (it = m_parallelEdges[e].begin(); it.valid(); it++)
372 {
373 edge parallel = (*it);
374 adjEntry adj = parallel->adjSource()->theNode() == v ?
375 parallel->adjSource() : parallel->adjTarget();
376 parallelToBeIgnored[adjTableOrig2Copy[adj]] = true;
377 #ifdef OGDF_DEBUG
378 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
379 cout << adj << " " << adj->index() << "\t twin " << adj->twin()->index() << endl;}
380 #endif
381 newEntireEmbedding[v].pushBack(adj);
382 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]].pushBack(adjTableOrig2Copy[adj]);
383 }
384 }
385 else
386 // v is target of e, insert the parallel edges
387 // in the opposite order stored in the list.
388 // This keeps the embedding.
389 {
390 bool first = true;
391 for (it = m_parallelEdges[e].rbegin(); it.valid(); it--)
392 {
393 edge parallel = (*it);
394 adjEntry adj = parallel->adjSource()->theNode() == v ?
395 parallel->adjSource() : parallel->adjTarget();
396 parallelToBeIgnored[adjTableOrig2Copy[adj]] = true;
397
398 newEntireEmbedding[v].pushBack(adj);
399 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]].pushBack(adjTableOrig2Copy[adj]);
400 if (first)
401 {
402 // parallelEntryPoint[adjTableOrig2Copy[adj]] = adj;
403 parallelEntryPoint[e->adjTarget()] = adj;
404 first = false;
405 }
406 }
407 adjEntry adj = e->adjTarget();
408
409 newEntireEmbedding[v].pushBack(adj);
410 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]];//.pushBack(adjTableOrig2Copy[adj]);
411 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]].pushBack(adjTableOrig2Copy[adj]);
412 parallelToBeIgnored[adjTableOrig2Copy[adj]] = true;
413 }
414 }//if parallel edges
415 else if (!m_isParallel[e])
416 // normal non-multi-edge
417 {
418 adjEntry adj = e->adjSource()->theNode() == v?
419 e->adjSource() : e->adjTarget();
420
421 newEntireEmbedding[v].pushBack(adj);
422 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]];//pushBack(adjTableOrig2Copy[adj]);
423 adjTableOrig2Copy[adj];
424 newEntireEmbeddingCopy[m_nodeTableOrig2Copy[v]].pushBack(adjTableOrig2Copy[adj]);
425 }
426 // else e is a multi-edge but not the reference edge
427 }
428 }
429
430 forall_nodes(v,G)
431 G.sort(v,newEntireEmbedding[v]);
432 forall_nodes(v,Gcopy)
433 Gcopy.sort(v,newEntireEmbeddingCopy[v]);
434
435 }
436 else
437 {
438 forall_nodes(v,G)
439 G.sort(v,entireEmbedding[v]);
440 OGDF_ASSERT(G.representsCombEmbedding())
441 }
442
443 adjEntry adj;
444
445 OGDF_ASSERT(G.representsCombEmbedding())
446
447 forall_clusters(c,Ccopy)
448 {
449 SListPure<adjEntry> embedding;
450
451
452 ListIterator<adjEntry> it;
453
454 for(it = c->firstAdj();it.valid(); it++)
455 {
456 adj = *it;
457 edge e = adj->theEdge();
458
459 if (!m_parallelEdges[edgeTableCopy2Orig[e]].empty())
460 {
461 adjEntry padj = parallelEntryPoint[adjTableCopy2Orig[adj]];
462
463 bool lastMultiEdgeFound = false;
464 node target = padj->twinNode();
465
466 while (!lastMultiEdgeFound) // Scan the parallel edges of e
467 // in the original graph along the embedded
468 // adjacency list of its target
469 {
470 if (padj->twinNode() == target) // is a multi edge
471 {
472 embedding.pushBack(padj);
473 padj = padj->succ();
474 if (!padj) break; //only multi edges
475 }
476 else // Not a multi Edge
477 break;
478 }
479 }
480 else if (!parallelToBeIgnored[adj])
481 {
482 embedding.pushBack(adjTableCopy2Orig[adj]);
483 }
484 }
485
486 C.makeAdjEntries(m_clusterTableCopy2Orig[c],embedding.begin());
487 }
488
489 }
490
491 /*******************************************************************************
492 nonPlanarCleanup
493 ********************************************************************************/
494
495
496 // Deallocates all memory, if the cluster graph is not cluster planar
497
498 void CconnectClusterPlanarEmbed::nonPlanarCleanup(ClusterGraph &Ccopy,Graph &Gcopy)
499 {
500
501 while (!m_callStack.empty())
502 {
503 cluster act = m_callStack.pop();
504
505 Graph *subGraph = m_clusterSubgraph[act];
506
507 node superSink = m_clusterPQContainer[act].m_superSink;
508 if (superSink)
509 {
510 edge e;
511 forall_edges(e,*subGraph)
512 {
513 if (e->source() != superSink && e->target() != superSink)
514 if ((*m_clusterOutgoingEdgesAnker[act])[e])
515 delete (*m_clusterOutgoingEdgesAnker[act])[e];
516 }
517 }
518
519 if (m_clusterEmbedding[act] != 0)
520 delete m_clusterEmbedding[act];
521 delete m_clusterSubgraphHubs[act];
522 delete m_clusterSubgraphWheelGraph[act];
523 delete m_clusterNodeTableNew2Orig[act];
524 delete m_clusterOutgoingEdgesAnker[act];
525
526 m_clusterPQContainer[act].Cleanup();
527 }
528
529
530 edge e;
531 forall_edges(e,Gcopy)
532 {
533 if (m_outgoingEdgesAnker[e])
534 delete m_outgoingEdgesAnker[e];
535 }
536 }
537
538
539
540 /*******************************************************************************
541 hubControl
542 ********************************************************************************/
543
544
545 // This function is called by recursiveEmbed only. It fixes
546 // the adjacency lists of the hubs in Gcopy after a cluster has been
547 // reembedded.
548
549 void CconnectClusterPlanarEmbed::hubControl(Graph &G,NodeArray<bool> &hubs)
550 {
551 node hub;
552 forall_nodes(hub,G)
553 {
554 if (hubs[hub]) // hub is a hub
555 {
556 node firstNode;
557 node secNode;
558
559 adjEntry startAdj = hub->firstAdj();
560 adjEntry firstAdj = 0;
561 adjEntry secAdj = 0;
562 while (firstAdj != startAdj)
563 {
564 if (firstAdj == 0)
565 firstAdj = startAdj;
566 secAdj = firstAdj->cyclicSucc();
567 firstNode = firstAdj->twinNode();
568 secNode = secAdj->twinNode();
569
570 adjEntry cyclicPredOfFirst = firstAdj->twin()->cyclicPred();
571 while(cyclicPredOfFirst->twinNode()
572 != secNode)
573 {
574 cyclicPredOfFirst = cyclicPredOfFirst->cyclicPred();
575 }
576 G.moveAdjBefore(cyclicPredOfFirst,firstAdj->twin());
577
578
579 adjEntry cyclicSuccOfSec= secAdj->twin()->cyclicSucc();
580 while(cyclicSuccOfSec->twinNode()
581 != firstNode)
582 {
583 cyclicSuccOfSec = cyclicSuccOfSec->cyclicSucc();
584 }
585 G.moveAdjAfter(cyclicSuccOfSec,secAdj->twin());
586
587 firstAdj = secAdj;
588
589 }
590
591 }
592 }
593 }
594
595
596
597
598
599
600 /*******************************************************************************
601 recursiveEmbed
602 ********************************************************************************/
603
604
605 // Function computes the cluster planar embedding of a cluster graph
606 // by recursively reinserting the clusters back into Gcopy and embedding
607 // their corresponding subgraphs within the planar embedding of Gcopy.
608
609
610 void CconnectClusterPlanarEmbed::recursiveEmbed(ClusterGraph &Ccopy,Graph &Gcopy)
611 {
612
613 node v;
614 // Remove root cluster from stack.
615 // Induced subgraph of root cluster corresponds to Gcopy
616 cluster root = m_callStack.pop();
617
618 OGDF_ASSERT(Gcopy.representsCombEmbedding())
619
620 hubControl(Gcopy,m_currentHubs);
621
622 while (!m_callStack.empty())
623 {
624
625 // Cluster act is reinserted into Gcopy.
626 cluster act = m_callStack.pop();
627 if (m_unsatisfiedCluster[act] == true)
628 continue;
629
630 // subgraph is the graph that replaces the wheelGraph of act in Gcopy
631 Graph *subGraph = m_clusterSubgraph[act];
632 // embedding contains the (partial) embedding of all biconnected components
633 // that do not have outgoing edges of the cluster act.
634 NodeArray<SListPure<adjEntry> > *embedding = m_clusterEmbedding[act];
635 // For every node of subGraph hubs is true if the node is a hub in subGraph
636 NodeArray<bool> *hubs = m_clusterSubgraphHubs[act];
637 // For every node in subGraph wheelGraphNodes stores the corresponding
638 // cluster, if the node is a node of a wheel graph
639 NodeArray<cluster> *wheelGraphNodes= m_clusterSubgraphWheelGraph[act];
640 EmbedPQTree *T = m_clusterPQContainer[act].m_T;
641 EdgeArray<Stack<edge>*> *outgoingAnker = m_clusterOutgoingEdgesAnker[act];
642
643 // What else do we have:
644 //
645 // 1. In m_wheelGraphNodes we have for every node of Gcopy that
646 // is a wheel graph node its corresponding cluster.
647 // Must UPDATE this information after we have replaced the current
648 // wheel graph by subGraph.
649
650 // Make sure that:
651 //
652 // 1. When inserting new Nodes to Gcopy, that correspond to nodes of subGraph
653 // copy the information on the wheel graphs (stored in wheelGraphNodes)
654 // 2. When inserting new Nodes to Gcopy, that correspond to nodes of subGraph
655 // copy the information if it is a hub (stored in hubs)
656
657
658 //----------------------------------------//
659 // Translation tables between the subgraph and
660 // its corresponding subgraph in Gcopy
661 AdjEntryArray<adjEntry> tableAdjEntrySubGraph2Gcopy(*subGraph);
662 NodeArray<node> nodeTableGcopy2SubGraph(Gcopy,0);
663 NodeArray<node> nodeTableSubGraph2Gcopy(*subGraph,0);
664
665
666 //----------------------------------------//
667 // Identify all wheelgraph nodes in Gcopy that correspond to act.
668 // These nodes have to be removed and replaced by subGraph.
669
670 SList<node> replaceNodes;
671 forall_nodes(v,Gcopy)
672 if (m_wheelGraphNodes[v] == act)
673 replaceNodes.pushBack(v);
674
675
676 //----------------------------------------//
677 // Introduce a new cluster in Gcopy
678 cluster newCluster = 0;
679 if (m_unsatisfiedCluster[act->parent()] == true)
680 newCluster = Ccopy.newCluster(Ccopy.rootCluster());
681 else
682 newCluster = Ccopy.newCluster(m_clusterTableOrig2Copy[act->parent()]);
683 m_clusterTableOrig2Copy[act] = newCluster;
684 m_clusterTableCopy2Orig[newCluster] = act;
685
686
687 //----------------------------------------//
688 // Insert for every node of subGraph
689 // a new node in Gcopy.
690 forall_nodes(v,*subGraph)
691 {
692 if (v != m_clusterSuperSink[act])
693 {
694 node newNode = Gcopy.newNode();
695 Ccopy.reassignNode(newNode,newCluster);
696 nodeTableGcopy2SubGraph[newNode] = v;
697 nodeTableSubGraph2Gcopy[v] = newNode;
698
699 // Copy information from subGraph nodes to new Gcopy nodes.
700 if ((*wheelGraphNodes)[v])
701 m_wheelGraphNodes[newNode] = (*wheelGraphNodes)[v];
702 if ((*hubs)[v])
703 m_currentHubs[newNode] = (*hubs)[v];
704 m_nodeTableCopy2Orig[newNode] = (*m_clusterNodeTableNew2Orig[act])[v];
705 }
706 }
707
708
709 //----------------------------------------//
710 // Insert the edges between the new nodes
711 EdgeArray<bool> visited((*subGraph),false);
712 forall_nodes(v,*subGraph)
713 {
714 node newV = nodeTableSubGraph2Gcopy[v];
715 edge e;
716
717 if (v != m_clusterSuperSink[act])
718 {
719 forall_adj_edges (e,v)
720 {
721 node w = e->opposite(v);
722
723 if (w != m_clusterSuperSink[act] && !visited[e])
724 {
725 node newW = nodeTableSubGraph2Gcopy[w];
726 edge eNew = Gcopy.newEdge(newV,newW);
727 if ((e->adjSource()->theNode() == v &&
728 eNew->adjSource()->theNode() == nodeTableSubGraph2Gcopy[v]) ||
729 (e->adjTarget()->theNode() == v &&
730 eNew->adjTarget()->theNode() == nodeTableSubGraph2Gcopy[v]))
731 {
732 tableAdjEntrySubGraph2Gcopy[e->adjSource()] = eNew->adjSource();
733 tableAdjEntrySubGraph2Gcopy[e->adjTarget()] = eNew->adjTarget();
734 }
735 else
736 {
737 tableAdjEntrySubGraph2Gcopy[e->adjTarget()] = eNew->adjSource();
738 tableAdjEntrySubGraph2Gcopy[e->adjSource()] = eNew->adjTarget();
739 }
740
741 // Copy the information of outgoing edges
742 // to the new edge.
743 m_outgoingEdgesAnker[eNew] = (*outgoingAnker)[e];
744 visited[e] = true;
745 }
746 }
747 }
748 }//forallnodes
749 //edge borderEdge = m_clusterPQContainer[act].m_stEdgeLeaf->userStructKey();
750
751
752
753 //----------------------------------------//
754
755 edge startEdge = 0; // first outgoing edge of cluster
756 // start embedding here
757 SListIterator<node> its;
758 for (its = replaceNodes.begin(); its.valid(); its++)
759 {
760 v = (*its);
761 // Assert that v is a node of the wheelgraph belonging
762 // to cluster child.
763 OGDF_ASSERT(m_wheelGraphNodes[v] == act)
764
765 // Traverse all edges adajcent to v to locate an outgoing edge.
766 edge e;
767 forall_adj_edges(e,v)
768 {
769 node w = e->opposite(v);
770 if (act != m_wheelGraphNodes[w])
771 {
772 // Outgoing Edge of wheelgraph detected.
773 startEdge = e;
774 its = replaceNodes.rbegin(); // break outer for loop
775 break;
776 }
777 }
778 }
779
780
781 // Stack outgoing edges according to embedding
782
783 // Assert that there is an outgoing edge of the cluster
784 OGDF_ASSERT(startEdge);
785 List<edge> outgoingEdges;
786 outgoingEdges.pushBack(startEdge);
787
788 adjEntry adj = startEdge->adjSource()->theNode() == v ?
789 startEdge->adjSource() : startEdge->adjTarget();
790 edge currentEdge = 0;
791 while (currentEdge != startEdge)
792 {
793 adjEntry newAdj = adj->cyclicSucc();
794 newAdj = newAdj->twin();
795 currentEdge = newAdj->theEdge();
796 if (act != m_wheelGraphNodes[newAdj->theNode()])
797 {
798 // Outgoing Edge of wheelgraph detected.
799 if (currentEdge != startEdge)
800 outgoingEdges.pushBack(currentEdge);
801 adj = adj->cyclicSucc();
802 }
803 else
804 adj = newAdj;
805
806 }
807
808 //----------------------------------------//
809 // Insert the edges between the new nodes and
810 // the existing nodes of Gcopy.
811
812 PlanarLeafKey<IndInfo*>* leftKey = 0;
813 PlanarLeafKey<IndInfo*>* rightKey = 0;
814 edge firstEdge = 0;
815 node t = m_clusterPQContainer[act].m_superSink;
816 SListPure<PlanarLeafKey<IndInfo*>*> allOutgoing;
817
818 #ifdef OGDF_DEBUG
819 EdgeArray<edge> debugTableOutgoingSubGraph2Gcopy(*subGraph,0);
820 #endif
821
822 ListIterator<edge> ite;
823 for (ite = outgoingEdges.begin(); ite.valid();)
824 {
825 edge e = (*ite);
826 ListIterator<edge> succ = ite.succ();
827
828
829 // Assert that stack for anker nodes is not empty
830 OGDF_ASSERT(!m_outgoingEdgesAnker[e]->empty())
831
832 node nonWheelNode; // The node of Gcopy that does not
833 // correspond to cluster act
834 if (act != m_wheelGraphNodes[e->source()])
835 nonWheelNode = e->source();
836 else {
837 OGDF_ASSERT(act != m_wheelGraphNodes[e->target()])
838 nonWheelNode = e->target();
839 }
840
841 edge subGraphEdge = m_outgoingEdgesAnker[e]->pop();
842 node subGraphNode = subGraphEdge->opposite(t);
843
844 #ifdef OGDF_DEBUG
845 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
846 debugTableOutgoingSubGraph2Gcopy[subGraphEdge] = e;}
847 #endif
848
849 rightKey = (*m_clusterPQContainer[act].m_edge2Key)[subGraphEdge];
850 allOutgoing.pushBack(rightKey);
851 if (leftKey)
852 {
853 SListPure<PlanarLeafKey<IndInfo*>*> pair;
854 pair.pushBack(leftKey);
855 pair.pushBack(rightKey);
856 #ifdef OGDF_DEBUG
857 bool planar =
858 #endif
859 T->Reduction(pair);
860 // Assert that the Reduction did not fail
861 OGDF_ASSERT(planar)
862 T->PQTree<edge,IndInfo*,bool>::emptyAllPertinentNodes();
863 }
864 else
865 firstEdge = subGraphEdge;
866
867 leftKey = rightKey;
868
869 // Assert that the anker node is a node
870 // of the subgraph.
871 OGDF_ASSERT(subGraphNode->graphOf() == subGraph)
872
873 // Redirect the edge to the new node.
874 // This keeps the embedding of Gcopy.
875 if (nonWheelNode == e->source())
876 {
877 Gcopy.moveTarget(e, nodeTableSubGraph2Gcopy[subGraphNode]);
878
879 if (subGraphEdge->source() == subGraphNode)
880 {
881 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjSource()] = e->adjTarget();
882 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjTarget()] = e->adjSource();
883 }
884 else
885 {
886 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjSource()] = e->adjSource();
887 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjTarget()] = e->adjTarget();
888 }
889 }
890 else
891 {
892 Gcopy.moveSource(e,nodeTableSubGraph2Gcopy[subGraphNode]);
893
894 if (subGraphEdge->target() == subGraphNode)
895 {
896 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjSource()] = e->adjTarget();
897 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjTarget()] = e->adjSource();
898 }
899 else
900 {
901 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjSource()] = e->adjSource();
902 tableAdjEntrySubGraph2Gcopy[subGraphEdge->adjTarget()] = e->adjTarget();
903 }
904 }
905
906 ite = succ;
907 }
908
909
910 //----------------------------------------//
911 // Compute an embedding of the subgraph
912
913 // Mark all leaves as relevant
914 #ifdef OGDF_DEBUG
915 bool planar =
916 #endif
917 T->Reduction(allOutgoing);
918 // Assert that the Reduction did not fail
919 OGDF_ASSERT(planar)
920
921 // Stores for every node v the keys corresponding to the incoming edges of v
922 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > >* inLeaves
923 = m_clusterPQContainer[act].m_inLeaves;
924
925 // Stores for every node v the keys corresponding to the outgoing edges of v
926 /*NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > >* outLeaves
927 = m_clusterPQContainer[act].m_outLeaves;*/
928
929 // Stores for every node v the sequence of incoming edges of v according
930 // to the embedding
931 NodeArray<SListPure<edge> >* frontier
932 = m_clusterPQContainer[act].m_frontier;
933
934 // Stores for every node v the nodes corresponding to the
935 // opposed sink indicators found in the frontier of v.
936 NodeArray<SListPure<node> >* opposed
937 = m_clusterPQContainer[act].m_opposed;
938
939 // Stores for every node v the nodes corresponding to the
940 // opposed sink indicators found in the frontier of v.
941 NodeArray<SListPure<node> >* nonOpposed
942 = m_clusterPQContainer[act].m_nonOpposed;
943
944 // Stores for every node the st-number
945 NodeArray<int>* numbering = m_clusterPQContainer[act].m_numbering;
946
947 // Stores for every st-Number the corresponding node
948 Array<node>* tableNumber2Node = m_clusterPQContainer[act].m_tableNumber2Node;
949
950 Array<bool> toReverse(1,(*numbering)[t],false);
951
952 // Get necessary embedding information
953 T->ReplaceRoot((*inLeaves)[t], (*frontier)[t], (*opposed)[t], (*nonOpposed)[t],t);
954
955
956 //---------------------------------------------------------//
957 // Compute a regular embedding of the biconnected component.
958
959 // Reverse adjacency lists if necessary
960 edge check = (*frontier)[t].front();
961
962 // Check if the order of edges around t has to be reversed.
963 if (firstEdge == check)
964 toReverse[(*numbering)[t]] = true;
965
966 int i;
967 for (i = (*numbering)[t]; i >= 2; i--)
968 {
969 if (toReverse[i])
970 {
971 while (!(*nonOpposed)[(*tableNumber2Node)[i]].empty())
972 {
973 v = (*nonOpposed)[(*tableNumber2Node)[i]].popFrontRet();
974 OGDF_ASSERT(!toReverse[(*numbering)[v]])
975 toReverse[(*numbering)[v]] = true;
976 }
977 (*frontier)[(*tableNumber2Node)[i]].reverse();
978 }
979 else
980 {
981 while (!(*opposed)[(*tableNumber2Node)[i]].empty())
982 {
983 v = (*opposed)[(*tableNumber2Node)[i]].popFrontRet();
984 OGDF_ASSERT(!toReverse[(*numbering)[v]])
985 toReverse[(*numbering)[v]] = true;
986 }
987 }
988 (*nonOpposed)[(*tableNumber2Node)[i]].clear();
989 (*opposed)[(*tableNumber2Node)[i]].clear();
990 }
991
992 #ifdef OGDF_DEBUG
993 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
994 cout << endl << "New Lists after Reversing " << endl;
995 for (i = 1; i <= (*numbering)[t]; i++){v = (*tableNumber2Node)[i];
996 cout<<"v = "<<v<<" : "<<" ";SListIterator<edge> it;
997 for(it=(*frontier)[v].begin();it.valid();it++)cout<<*it<<" ";
998 cout << endl;}}
999 #endif
1000
1001 // Compute the upward embedding
1002
1003 NodeArray<SListPure<adjEntry> > biCompEmbedding(*subGraph);
1004 for (i = 1; i <= (*numbering)[t]; i++)
1005 {
1006 v = (*tableNumber2Node)[i];
1007 while (!(*frontier)[v].empty())
1008 {
1009 edge e = (*frontier)[v].popFrontRet();
1010 biCompEmbedding[v].pushBack(
1011 (e->adjSource()->theNode() == v)? e->adjSource() : e->adjTarget());
1012 }
1013 }
1014
1015 //---------------------------------------------//
1016 // Compute the entire embedding of the subGraph
1017
1018 NodeArray<bool> mark(*subGraph,false);
1019 NodeArray<SListIterator<adjEntry> > adjMarker(*subGraph,0);
1020 for (i = 1; i <= (*numbering)[t]; i++)
1021 {
1022 v = (*tableNumber2Node)[i];
1023 adjMarker[v] = biCompEmbedding[v].begin();
1024 }
1025 v = (*tableNumber2Node)[(*numbering)[t]];
1026 entireEmbed(*subGraph,biCompEmbedding,adjMarker,mark,v);
1027
1028
1029 //--------------------------------------------------//
1030 // Sort the adjacency list of the new nodes in Gcopy
1031 // using the entire embedding of subGraph
1032
1033 NodeArray<SListPure<adjEntry> > embeddingGcopy(Gcopy);
1034
1035 // Copy Embedding of biconnected Componts with no outging edges first
1036
1037 forall_nodes(v,(*subGraph))
1038 {
1039 SListIterator<adjEntry> it;
1040 for (it = (*embedding)[v].begin(); it.valid(); it++)
1041 embeddingGcopy[nodeTableSubGraph2Gcopy[v]].pushBack(
1042 tableAdjEntrySubGraph2Gcopy[*it]);
1043 }
1044
1045
1046 // Copy Embedding of the biconnected componts
1047 // with outging edges. Don't add the outgoing edges
1048
1049 for (i = 1; i < (*numbering)[t]; i++)
1050 {
1051 v = (*tableNumber2Node)[i];
1052 SListIterator<adjEntry> it;
1053 while (!biCompEmbedding[v].empty())
1054 {
1055 adjEntry adj = biCompEmbedding[v].popFrontRet();
1056 (*embedding)[v].pushBack(adj);
1057 embeddingGcopy[nodeTableSubGraph2Gcopy[v]].pushBack(
1058 tableAdjEntrySubGraph2Gcopy[adj]);
1059 }
1060 }
1061
1062
1063 forall_nodes(v,*subGraph)
1064 if (v != t)
1065 Gcopy.sort(nodeTableSubGraph2Gcopy[v], embeddingGcopy[nodeTableSubGraph2Gcopy[v]]);
1066
1067
1068 //----------------------------------------//
1069 // Sort the adjacency list of the new cluster nodes in Gcopy
1070 // using the adjacency list of t
1071
1072 SListPure<adjEntry> embeddingClusterList;
1073 while (!biCompEmbedding[t].empty())
1074 {
1075 adjEntry adj = biCompEmbedding[t].popFrontRet();
1076 (*embedding)[t].pushBack(adj);
1077 // Choose the twin of adj, since adj is associated with t
1078 // which is the outside of the cluster.
1079 embeddingClusterList.pushFront(tableAdjEntrySubGraph2Gcopy[adj->twin()]);
1080 }
1081
1082 Ccopy.makeAdjEntries(newCluster,embeddingClusterList.begin());
1083
1084
1085
1086
1087 //----------------------------------------//
1088 // Delete the wheelGraph nodes from Gcopy
1089 while (!replaceNodes.empty())
1090 {
1091 v = replaceNodes.popFrontRet();
1092 // Ccopy.unassignNode(v);
1093 Gcopy.delNode(v);
1094 }
1095
1096 OGDF_ASSERT(Gcopy.representsCombEmbedding())
1097
1098
1099 if (m_clusterEmbedding[act] != 0)
1100 delete m_clusterEmbedding[act];
1101 delete m_clusterSubgraphHubs[act];
1102 delete m_clusterSubgraphWheelGraph[act];
1103 delete m_clusterNodeTableNew2Orig[act];
1104 delete m_clusterOutgoingEdgesAnker[act];
1105
1106 m_clusterPQContainer[act].Cleanup();
1107
1108 hubControl(Gcopy,m_currentHubs);
1109
1110 }
1111
1112 edge e;
1113 forall_edges(e,Gcopy)
1114 {
1115 if (m_outgoingEdgesAnker[e])
1116 delete m_outgoingEdgesAnker[e];
1117 }
1118
1119 delete m_clusterSubgraphHubs[root];
1120 delete m_clusterSubgraphWheelGraph[root];
1121 delete m_clusterOutgoingEdgesAnker[root];
1122
1123
1124 Ccopy.adjAvailable(true);
1125 }
1126
1127
1128
1129
1130
1131 /*******************************************************************************
1132 preProcess
1133 ********************************************************************************/
1134
1135 //Checks if the algorithm is applicable (input is c-connected and planar) and
1136 //then calls the planarity test method
1137
1138 bool CconnectClusterPlanarEmbed::preProcess(ClusterGraph &Ccopy,Graph &Gcopy)
1139 {
1140 m_errorCode = none;
1141 if (!isCConnected(Ccopy))
1142 {
1143 ogdf::sprintf(errorCode,124,"Graph is not Ccopy-connected \n");
1144 m_errorCode = nonCConnected;
1145 return false;
1146 }
1147
1148 if (!isPlanar(Ccopy))
1149 {
1150 ogdf::sprintf(errorCode,124,"Graph is not planar\n");
1151 m_errorCode = nonPlanar;
1152 return false;
1153 }
1154
1155 cluster c;
1156
1157 SListPure<node> selfLoops;
1158 makeLoopFree(Gcopy,selfLoops);
1159
1160 c = Ccopy.rootCluster();
1161
1162 bool cPlanar = planarityTest(Ccopy,c,Gcopy);
1163
1164
1165 return cPlanar;
1166 }
1167
1168
1169
1170 /*******************************************************************************
1171 planarityTest
1172 ********************************************************************************/
1173
1174
1175 // Recursive call for testing Planarity of a Cluster
1176
1177 bool CconnectClusterPlanarEmbed::planarityTest(
1178 ClusterGraph &Ccopy,
1179 cluster &act,
1180 Graph &Gcopy)
1181 {
1182 cluster origOfAct = m_clusterTableCopy2Orig[act];
1183
1184
1185 // Test children first
1186 ListConstIterator<cluster> it;
1187 for (it = act->cBegin(); it.valid();)
1188 {
1189 ListConstIterator<cluster> succ = it.succ();
1190 cluster next = (*it);
1191 if (!planarityTest(Ccopy,next,Gcopy))
1192 return false;
1193 it = succ;
1194 }
1195
1196
1197 m_callStack.push(origOfAct);
1198
1199 // Get induced subgraph of cluster act and test it for planarity
1200
1201 #ifdef OGDF_DEBUG
1202 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1203 cout << endl << endl << "Testing cluster " << origOfAct->index()<<endl;}
1204 #endif
1205
1206 List<node> subGraphNodes;
1207 ListIterator<node> its;
1208 for (its = act->nBegin(); its.valid(); its++)
1209 subGraphNodes.pushBack(*its);
1210
1211 Graph *subGraph = OGDF_NEW Graph();
1212 NodeArray<node> nodeTableOrig2New;
1213 EdgeArray<edge> edgeTableOrig2New;
1214 inducedSubGraph(Gcopy, subGraphNodes.begin(), (*subGraph), nodeTableOrig2New, edgeTableOrig2New);
1215 NodeArray<node> nodeTableNew2Orig((*subGraph),0);
1216
1217 // Necessary only for root cluster.
1218 EdgeArray<edge> edgeTableNew2Orig(*subGraph,0);
1219
1220 if (act != Ccopy.rootCluster())
1221 {
1222 m_clusterSubgraph[origOfAct] = subGraph;
1223 m_clusterNodeTableNew2Orig[origOfAct] = new NodeArray<node>((*subGraph),0);
1224 m_clusterSubgraphHubs[origOfAct] = OGDF_NEW NodeArray<bool>((*subGraph),0);
1225 m_clusterSubgraphWheelGraph[origOfAct] = OGDF_NEW NodeArray<cluster>((*subGraph),0);
1226 m_clusterOutgoingEdgesAnker[origOfAct] = OGDF_NEW EdgeArray<Stack<edge>*>((*subGraph),0);
1227 for (its = act->nBegin(); its.valid(); its++)
1228 {
1229 node w = (*its);
1230 (*m_clusterNodeTableNew2Orig[origOfAct])[nodeTableOrig2New[w]]
1231 = m_nodeTableCopy2Orig[w];
1232 }
1233 edge e;
1234 forall_edges(e,Gcopy)
1235 {
1236 if (edgeTableOrig2New[e] && m_outgoingEdgesAnker[e])
1237 (*m_clusterOutgoingEdgesAnker[origOfAct])[edgeTableOrig2New[e]]
1238 = m_outgoingEdgesAnker[e];
1239 }
1240 }
1241 else
1242 {
1243 m_clusterSubgraph[origOfAct] = &Gcopy;
1244 m_clusterSubgraphHubs[origOfAct] = OGDF_NEW NodeArray<bool>(Gcopy,0);
1245 m_clusterSubgraphWheelGraph[origOfAct] = OGDF_NEW NodeArray<cluster>(Gcopy,0);
1246 m_clusterOutgoingEdgesAnker[origOfAct] = OGDF_NEW EdgeArray<Stack<edge>*>(Gcopy,0);
1247 for (its = act->nBegin(); its.valid(); its++)
1248 {
1249 node w = (*its);
1250 node ttt = nodeTableOrig2New[w];
1251 nodeTableNew2Orig[ttt] = w;
1252 }
1253 edge e;
1254 forall_edges(e,Gcopy)
1255 {
1256 edgeTableNew2Orig[edgeTableOrig2New[e]] = e;
1257 if (m_outgoingEdgesAnker[e])
1258 (*m_clusterOutgoingEdgesAnker[origOfAct])[e]
1259 = m_outgoingEdgesAnker[e];
1260 }
1261 }
1262
1263
1264
1265 // Introduce super sink and add edges corresponding
1266 // to outgoing edges of the cluster
1267
1268 node superSink = subGraph->newNode();
1269 EdgeArray<node> outgoingTable((*subGraph),0);
1270
1271 for (its = act->nBegin(); its.valid(); its++)
1272 {
1273 node w = (*its);
1274 adjEntry adj = w->firstAdj();
1275 forall_adj(adj,w)
1276 {
1277 edge e = adj->theEdge();
1278 edge cor = 0;
1279 if (nodeTableOrig2New[e->source()] == 0)
1280 // edge is connected to a node outside the cluster
1281 {
1282 cor = subGraph->newEdge(nodeTableOrig2New[e->target()],superSink);
1283 outgoingTable[cor] = e->source();
1284 if (m_outgoingEdgesAnker[e])
1285 (*m_clusterOutgoingEdgesAnker[origOfAct])[cor]
1286 = m_outgoingEdgesAnker[e];
1287 }
1288 else if (nodeTableOrig2New[e->target()] == 0) // dito
1289 {
1290 cor = subGraph->newEdge(nodeTableOrig2New[e->source()],superSink);
1291 outgoingTable[cor] = e->target();
1292 if (m_outgoingEdgesAnker[e])
1293 (*m_clusterOutgoingEdgesAnker[origOfAct])[cor]
1294 = m_outgoingEdgesAnker[e]; }
1295
1296 // else edge connects two nodes of the cluster
1297 }
1298 }
1299 if (superSink->degree() == 0) // root cluster is not connected to outside clusters
1300 {
1301 subGraph->delNode(superSink);
1302 superSink = 0;
1303 }
1304 else
1305 m_clusterSuperSink[origOfAct] = superSink;
1306
1307 #ifdef OGDF_DEBUG
1308 if (int(ogdf::debugLevel) >= int(dlHeavyChecks)){
1309 char filename[124];
1310 ogdf::sprintf(filename,124,"Ccopy%d.gml",origOfAct->index());
1311 subGraph->writeGML(filename);
1312 }
1313 #endif
1314
1315
1316 bool cPlanar = preparation((*subGraph),origOfAct,superSink);
1317
1318
1319 if (cPlanar && act != Ccopy.rootCluster())
1320 {
1321 // Remove induced subgraph and the cluster act.
1322 // Replace it by a wheel graph
1323 while (!subGraphNodes.empty())
1324 {
1325 node w = subGraphNodes.popFrontRet();
1326 if (m_currentHubs[w])
1327 (*m_clusterSubgraphHubs[origOfAct])[nodeTableOrig2New[w]]
1328 = true;
1329 if (m_wheelGraphNodes[w])
1330 (*m_clusterSubgraphWheelGraph[origOfAct])[nodeTableOrig2New[w]]
1331 = m_wheelGraphNodes[w];
1332
1333 // Ccopy.unassignNode(w);
1334 Gcopy.delNode(w);
1335 }
1336
1337 cluster parent = act->parent();
1338
1339 if (superSink && m_clusterPQContainer[origOfAct].m_T)
1340 constructWheelGraph(Ccopy,Gcopy,parent,origOfAct,
1341 m_clusterPQContainer[origOfAct].m_T,
1342 outgoingTable,superSink);
1343
1344
1345 m_clusterTableOrig2Copy[origOfAct] = 0;
1346 Ccopy.delCluster(act);
1347 }
1348
1349 else if (cPlanar && act == Ccopy.rootCluster())
1350 {
1351
1352 node w ;
1353 forall_nodes(w,Gcopy)
1354 {
1355 if (m_currentHubs[w])
1356 (*m_clusterSubgraphHubs[origOfAct])[w] = true;
1357 if (m_wheelGraphNodes[w])
1358 (*m_clusterSubgraphWheelGraph[origOfAct])[w] = m_wheelGraphNodes[w];
1359 }
1360
1361 forall_nodes(w,*subGraph)
1362 subGraph->sort(w,(*m_clusterEmbedding[origOfAct])[w]);
1363
1364 forall_nodes(w,(*subGraph))
1365 {
1366 node originalOfw = nodeTableNew2Orig[w];
1367
1368 SListPure<adjEntry> adjList;
1369
1370 adjEntry a;
1371 forall_adj(a,w)
1372 {
1373 edge e = edgeTableNew2Orig[a->theEdge()];
1374 adjEntry adj = (e->adjSource()->theNode() == originalOfw)?
1375 e->adjSource() : e->adjTarget();
1376 adjList.pushBack(adj);
1377 }
1378
1379 Gcopy.sort(originalOfw,adjList);
1380 }
1381
1382 // Test if embedding was determined correctly.
1383 OGDF_ASSERT(subGraph->representsCombEmbedding())
1384
1385 edgeTableNew2Orig.init();
1386 outgoingTable.init();
1387 nodeTableNew2Orig.init();
1388 delete m_clusterEmbedding[origOfAct];
1389 m_clusterEmbedding[origOfAct] = 0;
1390 delete subGraph;
1391
1392 }
1393
1394 else if (!cPlanar && act == Ccopy.rootCluster())
1395 {
1396 edgeTableNew2Orig.init();
1397 outgoingTable.init();
1398 nodeTableNew2Orig.init();
1399 delete m_clusterEmbedding[origOfAct];
1400 m_clusterEmbedding[origOfAct] = 0;
1401 delete subGraph;
1402 }
1403
1404 if (!cPlanar)
1405 {
1406 ogdf::sprintf(errorCode,124,"Graph is not planar at cluster %d.\n",act->index());
1407 m_errorCode = nonCPlanar;
1408 }//if
1409
1410
1411 return cPlanar;
1412
1413 }
1414
1415
1416
1417
1418 /*******************************************************************************
1419 preparation
1420 ********************************************************************************/
1421
1422
1423 //
1424 // Prepare planarity test for one cluster
1425 //
1426 bool CconnectClusterPlanarEmbed::preparation(Graph &subGraph,
1427 cluster &origCluster,
1428 node superSink)
1429 {
1430
1431 node v;
1432 edge e;
1433 int bcIdSuperSink = -1; // ID of biconnected component that contains superSink
1434 // Initialization with -1 necessary for assertion
1435 bool cPlanar = true;
1436
1437
1438 NodeArray<node> tableNodesSubGraph2BiComp(subGraph,0);
1439 EdgeArray<edge> tableEdgesSubGraph2BiComp(subGraph,0);
1440 NodeArray<bool> mark(subGraph,0);
1441
1442 EdgeArray<int> componentID(subGraph);
1443
1444 // Generate datastructure for embedding, even if it is left empty.
1445 // Embedding either contains
1446 // Embedding of the root cluster
1447 // or
1448 // Partial Embedding of the biconnected components not having
1449 // outgoing edges.
1450
1451 NodeArray<SListPure<adjEntry> >
1452 *entireEmbedding = OGDF_NEW NodeArray<SListPure<adjEntry> >(subGraph);
1453 m_clusterEmbedding[origCluster] = entireEmbedding;
1454
1455 // Determine Biconnected Components
1456 int bcCount = biconnectedComponents(subGraph,componentID);
1457
1458 // Determine edges per biconnected component
1459 Array<SList<edge> > blockEdges(0,bcCount-1);
1460 forall_edges(e,subGraph)
1461 {
1462 blockEdges[componentID[e]].pushFront(e);
1463 }
1464
1465 // Determine nodes per biconnected component.
1466 Array<SList<node> > blockNodes(0,bcCount-1);
1467 for (int i = 0; i < bcCount; i++)
1468 {
1469 SListIterator<edge> it;
1470 for (it = blockEdges[i].begin(); it.valid(); ++it)
1471 {
1472 e = *it;
1473 if (!mark[e->source()])
1474 {
1475 blockNodes[i].pushBack(e->source());
1476 mark[e->source()] = true;
1477 }
1478 if (!mark[e->target()])
1479 {
1480 blockNodes[i].pushBack(e->target());
1481 mark[e->target()] = true;
1482 }
1483 }
1484 if (superSink && mark[superSink])
1485 {
1486 OGDF_ASSERT(bcIdSuperSink == -1);
1487 bcIdSuperSink = i;
1488 }
1489 SListIterator<node> itn;
1490 for (itn = blockNodes[i].begin(); itn.valid(); ++itn)
1491 {
1492 v = *itn;
1493 if (mark[v])
1494 mark[v] = false;
1495 else
1496 {
1497 OGDF_ASSERT(mark[v]); // v has been placed two times on the list.
1498 }
1499 }
1500
1501 }
1502
1503
1504
1505 // Perform Planarity Test for every biconnected component
1506
1507 if (bcCount == 1)
1508 {
1509 // Compute st-numbering
1510 NodeArray<int> numbering(subGraph,0);
1511 int n;
1512 if (superSink)
1513 n = stNumber(subGraph,numbering,0,superSink);
1514 else
1515 n = stNumber(subGraph,numbering);
1516 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(subGraph,numbering,n))
1517
1518 EdgeArray<edge> tableEdgesBiComp2SubGraph(subGraph,0);
1519 NodeArray<node> tableNodesBiComp2SubGraph(subGraph,0);
1520 forall_edges(e,subGraph)
1521 tableEdgesBiComp2SubGraph[e] = e;
1522 forall_nodes(v,subGraph)
1523 tableNodesBiComp2SubGraph[v] = v;
1524
1525 // Initialize the container class for storing all information
1526 // if it does not belong to the root cluster.
1527 if (bcIdSuperSink == 0)
1528 m_clusterPQContainer[origCluster].init(&subGraph);
1529
1530 cPlanar = doEmbed(
1531 &subGraph,
1532 numbering,
1533 origCluster,
1534 superSink,
1535 subGraph,
1536 tableEdgesBiComp2SubGraph,
1537 tableEdgesBiComp2SubGraph,
1538 tableNodesBiComp2SubGraph);
1539
1540 // Do not save the embedding of the subgraph. It is not complete.
1541 if (bcIdSuperSink == -1)
1542 {
1543 // The root cluster is embedded.
1544 // Gather the embeddding of the biconnected graph, if it belongs to
1545 // the root cluster.
1546 // The embedding of the subgraph is saved, as it is the root cluster graph.
1547 forall_nodes(v,subGraph)
1548 {
1549 adjEntry a;
1550 forall_adj(a,v)
1551 (*entireEmbedding)[v].pushBack(a);
1552 }
1553 }
1554
1555 }
1556 else
1557 {
1558 for (int i = 0; i < bcCount; i++)
1559 {
1560 Graph *biCompOfSubGraph = OGDF_NEW Graph();
1561
1562 SListIterator<node> itn;
1563 for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
1564 {
1565 v = *itn;
1566 node w = biCompOfSubGraph->newNode();
1567 tableNodesSubGraph2BiComp[v] = w;
1568 }
1569
1570 NodeArray<node> tableNodesBiComp2SubGraph(*biCompOfSubGraph,0);
1571 for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
1572 tableNodesBiComp2SubGraph[tableNodesSubGraph2BiComp[*itn]] = *itn;
1573
1574 SListIterator<edge> it;
1575 for (it = blockEdges[i].begin(); it.valid(); ++it)
1576 {
1577 e = *it;
1578 edge f = biCompOfSubGraph->newEdge(
1579 tableNodesSubGraph2BiComp[e->source()], tableNodesSubGraph2BiComp[e->target()]);
1580 tableEdgesSubGraph2BiComp[e] = f;
1581 }
1582
1583 EdgeArray<edge> tableEdgesBiComp2SubGraph(*biCompOfSubGraph,0);
1584 for (it = blockEdges[i].begin(); it.valid(); ++it)
1585 tableEdgesBiComp2SubGraph[tableEdgesSubGraph2BiComp[*it]] = *it;
1586
1587 NodeArray<int> numbering(*biCompOfSubGraph,0);
1588 int n;
1589 if (bcIdSuperSink == i)
1590 {
1591 n = stNumber(*biCompOfSubGraph,numbering,0,tableNodesSubGraph2BiComp[superSink]);
1592 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(*biCompOfSubGraph,numbering,n))
1593
1594 // Initialize the container class for storing all information
1595 m_clusterPQContainer[origCluster].init(&subGraph);
1596
1597 cPlanar = doEmbed(
1598 biCompOfSubGraph,
1599 numbering,
1600 origCluster,
1601 tableNodesSubGraph2BiComp[superSink],
1602 subGraph,
1603 tableEdgesBiComp2SubGraph,
1604 tableEdgesSubGraph2BiComp,
1605 tableNodesBiComp2SubGraph);
1606 }
1607 else
1608 {
1609 n = stNumber(*biCompOfSubGraph,numbering);
1610 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(*biCompOfSubGraph,numbering,n));
1611 cPlanar = doEmbed(
1612 biCompOfSubGraph,
1613 numbering,
1614 origCluster,
1615 0,
1616 subGraph,
1617 tableEdgesBiComp2SubGraph,
1618 tableEdgesSubGraph2BiComp,
1619 tableNodesBiComp2SubGraph);
1620 }
1621
1622 if (!cPlanar)
1623 {
1624 numbering.init();
1625 tableEdgesBiComp2SubGraph.init();
1626 tableNodesBiComp2SubGraph.init();
1627 delete biCompOfSubGraph;
1628 break;
1629 }
1630
1631 if (bcIdSuperSink == -1)
1632 {
1633 // The root cluster is embedded.
1634 // Gather the embedding of the biconnected graph, if it belongs to
1635 // the root cluster.
1636 // The embedding of the subgraph is saved, as it is the root cluster graph.
1637 forall_nodes(v,*biCompOfSubGraph)
1638 {
1639 node w = tableNodesBiComp2SubGraph[v];
1640 adjEntry a;
1641 forall_adj(a,v)
1642 {
1643 edge e = tableEdgesBiComp2SubGraph[a->theEdge()];
1644 adjEntry adj = (e->adjSource()->theNode() == w)?
1645 e->adjSource() : e->adjTarget();
1646 (*entireEmbedding)[w].pushBack(adj);
1647 }
1648 }
1649 }
1650 else if (bcIdSuperSink != i)
1651 {
1652 // A non root cluster is embedded.
1653 // Gather the embeddings of the biconnected components
1654 // that do not have outgoing edges of the cluster.
1655 forall_nodes(v,*biCompOfSubGraph)
1656 {
1657 node w = tableNodesBiComp2SubGraph[v];
1658 adjEntry a;
1659 forall_adj(a,v)
1660 {
1661 edge e = tableEdgesBiComp2SubGraph[a->theEdge()];
1662 adjEntry adj = (e->adjSource()->theNode() == w)?
1663 e->adjSource() : e->adjTarget();
1664 (*entireEmbedding)[w].pushBack(adj);
1665 }
1666 }
1667
1668 }
1669 numbering.init();
1670 tableEdgesBiComp2SubGraph.init();
1671 tableNodesBiComp2SubGraph.init();
1672 delete biCompOfSubGraph;
1673
1674
1675 }//for bccount
1676
1677 // m_clusterEmbedding[origCluster] now contains the (partial) embedding
1678 // of all biconnected components that do not have outgoing edges
1679 // of the cluster origCluster.
1680 }
1681
1682 return cPlanar;
1683
1684 }// preparation
1685
1686
1687
1688
1689 /*******************************************************************************
1690 doEmbed
1691 ********************************************************************************/
1692
1693
1694 // Performs a planarity test on a biconnected component
1695 // of subGraph and embedds it planar.
1696 // numbering contains an st-numbering of the component.
1697 bool CconnectClusterPlanarEmbed::doEmbed(Graph *biconComp,
1698 NodeArray<int> &numbering,
1699 cluster &origCluster,
1700 node superSink,
1701 Graph &subGraph,
1702 EdgeArray<edge> &tableEdgesBiComp2SubGraph,
1703 EdgeArray<edge> &tableEdgesSubGraph2BiComp,
1704 NodeArray<node> &tableNodesBiComp2SubGraph)
1705 {
1706 node v;
1707 bool cPlanar = true;
1708
1709 // Definition
1710 // incoming edge of v: an edge e = (v,w) with number(v) < number(w)
1711
1712
1713 // Stores for every node v the keys corresponding to the incoming edges of v
1714 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > inLeaves(*biconComp);
1715
1716 // Stores for every node v the keys corresponding to the outgoing edges of v
1717 NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > outLeaves(*biconComp);
1718
1719 // Stores for every node v the sequence of incoming edges of v according
1720 // to the embedding
1721 NodeArray<SListPure<edge> > frontier(*biconComp);
1722
1723 // Stores for every node v the nodes corresponding to the
1724 // opposed sink indicators found in the frontier of v.
1725 NodeArray<SListPure<node> > opposed(*biconComp);
1726
1727 // Stores for every node v the nodes corresponding to the
1728 // non opposed sink indicators found in the frontier of v.
1729 NodeArray<SListPure<node> > nonOpposed(*biconComp);
1730
1731 // Stores for every st-Number the corresponding node
1732 Array<node> tableNumber2Node(biconComp->numberOfNodes()+1);
1733
1734 Array<bool> toReverse(1,biconComp->numberOfNodes()+1,false);
1735
1736 PlanarLeafKey<IndInfo*>* stEdgeLeaf;
1737
1738 forall_nodes(v,*biconComp)
1739 {
1740 edge e;
1741
1742 forall_adj_edges(e,v)
1743 {
1744 if (numbering[e->opposite(v)] > numbering[v])
1745 {
1746 PlanarLeafKey<IndInfo*>* L = OGDF_NEW PlanarLeafKey<IndInfo*>(e);
1747 inLeaves[v].pushFront(L);
1748 if (numbering[v] == 1 && numbering[e->opposite(v)])
1749 stEdgeLeaf = L;
1750 }
1751 }
1752 tableNumber2Node[numbering[v]] = v;
1753 }
1754
1755 forall_nodes(v,*biconComp)
1756 {
1757 SListIterator<PlanarLeafKey<IndInfo*>* > it;
1758 for (it = inLeaves[v].begin(); it.valid(); ++it)
1759 {
1760 PlanarLeafKey<IndInfo*>* L = *it;
1761 outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
1762 }
1763 }
1764
1765 EmbedPQTree* T = new EmbedPQTree();
1766
1767 T->Initialize(inLeaves[tableNumber2Node[1]]);
1768 int i;
1769 for (i = 2; i < biconComp->numberOfNodes(); i++)
1770 {
1771 if (T->Reduction(outLeaves[tableNumber2Node[i]]))
1772 {
1773 T->ReplaceRoot(
1774 inLeaves[tableNumber2Node[i]],
1775 frontier[tableNumber2Node[i]],
1776 opposed[tableNumber2Node[i]],
1777 nonOpposed[tableNumber2Node[i]],
1778 tableNumber2Node[i]);
1779 T->emptyAllPertinentNodes();
1780 }
1781 else
1782 {
1783 cPlanar = false;
1784 break;
1785 }
1786 }
1787
1788 if (cPlanar && superSink)
1789 {
1790 // The tested component contains the outgoing edges
1791 // of the cluster.
1792
1793 // Keep the PQTree to construct a Wheelgraph
1794 // Replace the edge stored in the keys of T
1795 // by the original edges.
1796 // Necessary, since the edges currently in T
1797 // correspond to a graph that mirrors a biconnected
1798 // component and thus is deallocated
1799
1800 // For embedding the graph, we need to keep the
1801 // PQTree as well.
1802
1803 SListIterator<PlanarLeafKey<IndInfo*>* > it;
1804 //int n = biconComp->numberOfNodes();
1805
1806 // Replace the edge stored in the keys of T
1807 // by the original edges.
1808
1809
1810 //--------------------------------------//
1811 // All information that we keep is dependend on subGraph.
1812 // Translate the information back from biconComp to subGraph.
1813
1814
1815 m_clusterPQContainer[origCluster].m_superSink
1816 = tableNodesBiComp2SubGraph[superSink];
1817
1818 forall_nodes(v,*biconComp)
1819 {
1820 // Replace the edge stored in the every key used for constructing T
1821 // by the original edges.
1822 // This implicity replaces the keys at the leaves and at inLeaves.
1823
1824
1825 node orig = tableNodesBiComp2SubGraph[v];
1826
1827 // Assert that m_outLeaves is empty
1828 OGDF_ASSERT((*m_clusterPQContainer[origCluster].m_outLeaves)[orig].empty())
1829 for (it = outLeaves[v].begin(); it.valid(); ++it)
1830 {
1831 PlanarLeafKey<IndInfo*>* key = *it;
1832 key->m_userStructKey = tableEdgesBiComp2SubGraph[key->m_userStructKey];
1833 (*m_clusterPQContainer[origCluster].m_edge2Key)[key->m_userStructKey] = key;
1834 (*m_clusterPQContainer[origCluster].m_outLeaves)[orig].pushBack(key);
1835 }
1836
1837 // Assert that m_inLeaves is empty
1838 OGDF_ASSERT((*m_clusterPQContainer[origCluster].m_inLeaves)[orig].empty())
1839 for (it = inLeaves[v].begin(); it.valid(); ++it)
1840 {
1841 PlanarLeafKey<IndInfo*>* key = *it;
1842 (*m_clusterPQContainer[origCluster].m_inLeaves)[orig].pushBack(key);
1843 }
1844
1845 // Replace the nodes stored in the lists opposed and nonOpposed
1846 // by the original nodes
1847
1848 // Assert that m_opposed and m_nonOpposed are empty
1849 OGDF_ASSERT((*m_clusterPQContainer[origCluster].m_opposed)[orig].empty())
1850 OGDF_ASSERT((*m_clusterPQContainer[origCluster].m_nonOpposed)[orig].empty())
1851 SListIterator<node> itn;
1852 for (itn = nonOpposed[v].begin(); itn.valid(); itn++)
1853 {
1854 node w = tableNodesBiComp2SubGraph[(*itn)];
1855 (*m_clusterPQContainer[origCluster].m_nonOpposed)[orig].pushBack(w);
1856 }
1857 for (itn = opposed[v].begin(); itn.valid(); itn++)
1858 {
1859 node w = tableNodesBiComp2SubGraph[(*itn)];
1860 (*m_clusterPQContainer[origCluster].m_opposed)[orig].pushBack(w);
1861 }
1862
1863 (*m_clusterPQContainer[origCluster].m_numbering)[orig] = numbering[v];
1864 (*m_clusterPQContainer[origCluster].m_tableNumber2Node)[numbering[v]] = orig;
1865
1866
1867 // Replace the edges stored in frontier
1868 // by the original edges of subgraph.
1869
1870 OGDF_ASSERT((*m_clusterPQContainer[origCluster].m_frontier)[orig].empty())
1871 SListIterator<edge> ite;
1872 for (ite = frontier[v].begin(); ite.valid(); ite++)
1873 {
1874 edge e = tableEdgesBiComp2SubGraph[(*ite)];
1875 (*m_clusterPQContainer[origCluster].m_frontier)[orig].pushBack(e);
1876 }
1877
1878
1879 }
1880 m_clusterPQContainer[origCluster].m_T = T;
1881 m_clusterPQContainer[origCluster].m_stEdgeLeaf = stEdgeLeaf;
1882 SListPure<PQBasicKey<edge,IndInfo*,bool>*> leafKeys;
1883 T->getFront(T->root(),leafKeys);
1884 SListIterator<PQBasicKey<edge,IndInfo*,bool>* > itk;
1885 for (itk = leafKeys.begin(); itk.valid(); itk++)
1886 {
1887 if ((*itk)->nodePointer()->status() == PQNodeRoot::INDICATOR)
1888 {
1889 node ofInd = (*itk)->nodePointer()->getNodeInfo()->userStructInfo()->getAssociatedNode();
1890 (*itk)->nodePointer()->getNodeInfo()->userStructInfo()->resetAssociatedNode(tableNodesBiComp2SubGraph[ofInd]);
1891 }
1892 }
1893 }
1894 else if (cPlanar)
1895 {
1896 // The tested component does not contain outgoing edges
1897 // of the cluster.
1898 // Compute a regular embedding of the biconnected component.
1899 int i = biconComp->numberOfNodes();
1900 if (T->Reduction(outLeaves[tableNumber2Node[i]]))
1901 {
1902 T->ReplaceRoot(
1903 inLeaves[tableNumber2Node[i]],
1904 frontier[tableNumber2Node[i]],
1905 opposed[tableNumber2Node[i]],
1906 nonOpposed[tableNumber2Node[i]],
1907 tableNumber2Node[i]);
1908 }
1909 delete T;
1910 }
1911
1912 // Cleanup
1913 if (!origCluster || !superSink || !cPlanar)
1914 // Do not cleanup information of component
1915 // with outgoing edges.
1916 {
1917 forall_nodes(v,*biconComp)
1918 {
1919 if (v != superSink || !cPlanar)
1920 {
1921 while (!outLeaves[v].empty())
1922 {
1923 PlanarLeafKey<IndInfo*>* L = outLeaves[v].popFrontRet();
1924 delete L;
1925 }
1926 }
1927 }
1928 }
1929 if (!cPlanar)
1930 delete T;
1931
1932
1933 if (cPlanar && (!origCluster || !superSink))
1934 {
1935 // The tested component does not contain outgoing edges
1936 // of the cluster.
1937 // Compute a regular embedding of the biconnected component.
1938
1939 // Reverse adjacency lists if necessary
1940 // This gives an upward embedding
1941 for (i = biconComp->numberOfNodes(); i >= 2; i--)
1942 {
1943 if (toReverse[i])
1944 {
1945 while (!nonOpposed[tableNumber2Node[i]].empty())
1946 {
1947 v = nonOpposed[tableNumber2Node[i]].popFrontRet();
1948 OGDF_ASSERT(!toReverse[numbering[v]])
1949 toReverse[numbering[v]] = true;
1950 }
1951 frontier[tableNumber2Node[i]].reverse();
1952 }
1953 else
1954 {
1955 while (!opposed[tableNumber2Node[i]].empty())
1956 {
1957 v = opposed[tableNumber2Node[i]].popFrontRet();
1958 OGDF_ASSERT(!toReverse[numbering[v]])
1959 toReverse[numbering[v]] = true;
1960 }
1961 }
1962 nonOpposed[tableNumber2Node[i]].clear();
1963 opposed[tableNumber2Node[i]].clear();
1964 }
1965
1966 // Compute the entire embedding
1967 NodeArray<SListPure<adjEntry> > entireEmbedding(*biconComp);
1968 forall_nodes(v,*biconComp)
1969 {
1970 while (!frontier[v].empty())
1971 {
1972 edge e = frontier[v].popFrontRet();
1973 entireEmbedding[v].pushBack(
1974 (e->adjSource()->theNode() == v)? e->adjSource() : e->adjTarget());
1975 }
1976 }
1977
1978
1979 NodeArray<bool> mark(*biconComp,false);
1980 NodeArray<SListIterator<adjEntry> > adjMarker(*biconComp,0);
1981 forall_nodes(v,*biconComp)
1982 adjMarker[v] = entireEmbedding[v].begin();
1983 v = tableNumber2Node[biconComp->numberOfNodes()];
1984 entireEmbed(*biconComp,entireEmbedding,adjMarker,mark,v);
1985
1986
1987 forall_nodes(v,*biconComp)
1988 biconComp->sort(v,entireEmbedding[v]);
1989
1990 // Test if embedding was determined correctly.
1991 OGDF_ASSERT(biconComp->representsCombEmbedding())
1992
1993 }
1994
1995 return cPlanar;
1996
1997
1998 }// doEmbed
1999
2000
2001
2002
2003
2004 /*******************************************************************************
2005 entireEmbed
2006 ********************************************************************************/
2007
2008
2009 // Used by doEmbed. Computes an entire embedding from an
2010 // upward embedding.
2011 void CconnectClusterPlanarEmbed::entireEmbed(
2012 Graph &biconComp,
2013 NodeArray<SListPure<adjEntry> > &entireEmbedding,
2014 NodeArray<SListIterator<adjEntry> > &adjMarker,
2015 NodeArray<bool> &mark,
2016 node v)
2017 {
2018 mark[v] = true;
2019 SListIterator<adjEntry> it;
2020 for (it = adjMarker[v]; it.valid(); ++it)
2021 {
2022 adjEntry a = *it;
2023 edge e = a->theEdge();
2024 adjEntry adj = (e->adjSource()->theNode() == v)?
2025 e->adjTarget() : e->adjSource();
2026 node w = adj->theNode();
2027 entireEmbedding[w].pushFront(adj);
2028 if (!mark[w])
2029 entireEmbed(biconComp,entireEmbedding,adjMarker,mark,w);
2030 }
2031 }
2032
2033
2034
2035
2036
2037
2038 /*******************************************************************************
2039 prepareParallelEdges
2040 ********************************************************************************/
2041
2042
2043 void CconnectClusterPlanarEmbed::prepareParallelEdges(Graph &G)
2044 {
2045
2046 edge e;
2047
2048 // Stores for one reference edge all parallel edges.
2049 m_parallelEdges.init(G);
2050 // Is true for any multiedge, except for the reference edge.
2051 m_isParallel.init(G,false);
2052 getParallelFreeUndirected(G,m_parallelEdges);
2053 m_parallelCount = 0;
2054 forall_edges(e,G)
2055 {
2056 if (!m_parallelEdges[e].empty())
2057 {
2058 ListIterator<edge> it;
2059 for (it = m_parallelEdges[e].begin(); it.valid(); it++)
2060 {
2061 m_isParallel[*it] = true;
2062 m_parallelCount++;
2063 }
2064 }
2065 }
2066 }
2067
2068
2069
2070
2071 /*******************************************************************************
2072 constructWheelGraph
2073 ********************************************************************************/
2074
2075
2076 void CconnectClusterPlanarEmbed::constructWheelGraph(ClusterGraph &Ccopy,
2077 Graph &Gcopy,
2078 cluster &parent,
2079 cluster &origOfAct,
2080 EmbedPQTree* T,
2081 EdgeArray<node> &outgoingTable,
2082 node superSink)
2083 {
2084
2085 OGDF_ASSERT(Ccopy.consistencyCheck());
2086 PQNode<edge,IndInfo*,bool>* root = T->root();
2087 PQNode<edge,IndInfo*,bool>* checkNode = 0;
2088
2089 Queue<PQNode<edge,IndInfo*,bool>*> treeNodes;
2090 treeNodes.append(root);
2091
2092 node correspond = Gcopy.newNode(); // Corresponds to the root node.
2093 // root node is either a leaf or a P-node
2094 m_nodeTableCopy2Orig[correspond] = 0; // Node does not correspond to a node
2095 // in the original graph
2096 m_wheelGraphNodes[correspond] = origOfAct;
2097 Ccopy.reassignNode(correspond,parent);
2098
2099 Queue<node> graphNodes;
2100 graphNodes.append(correspond);
2101
2102 node hub;
2103 node next = 0;
2104 node pre;
2105 node newNode; // corresponds to anchor of a hub or a cut node
2106
2107
2108
2109 while (!treeNodes.empty())
2110 {
2111 checkNode = treeNodes.pop();
2112 correspond = graphNodes.pop();
2113
2114 PQNode<edge,IndInfo*,bool>* firstSon = 0;
2115 PQNode<edge,IndInfo*,bool>* nextSon = 0;
2116 PQNode<edge,IndInfo*,bool>* oldSib = 0;
2117 PQNode<edge,IndInfo*,bool>* holdSib = 0;
2118
2119
2120 if (checkNode->type() == PQNodeRoot::PNode)
2121 {
2122 // correspond is a cut node
2123
2124 OGDF_ASSERT(checkNode->referenceChild())
2125 firstSon = checkNode->referenceChild();
2126
2127 if (firstSon->type() != PQNodeRoot::leaf)
2128 {
2129 treeNodes.append(firstSon);
2130 newNode = Gcopy.newNode();
2131 m_nodeTableCopy2Orig[newNode] = 0;
2132 m_wheelGraphNodes[newNode] = origOfAct;
2133 Ccopy.reassignNode(newNode,parent);
2134 graphNodes.append(newNode);
2135 Gcopy.newEdge(correspond,newNode);
2136 }
2137 else
2138 {
2139 // insert Edge to the outside
2140 PQLeaf<edge,IndInfo*,bool>* leaf =
2141 (PQLeaf<edge,IndInfo*,bool>*) firstSon;
2142 edge f = leaf->getKey()->m_userStructKey;
2143 //node x = outgoingTable[f];
2144 edge newEdge = Gcopy.newEdge(correspond,outgoingTable[f]);
2145
2146
2147 if ((*m_clusterOutgoingEdgesAnker[origOfAct])[f])
2148 {
2149 m_outgoingEdgesAnker[newEdge]
2150 = (*m_clusterOutgoingEdgesAnker[origOfAct])[f];
2151 }
2152 else
2153 m_outgoingEdgesAnker[newEdge] = OGDF_NEW Stack<edge>;
2154 m_outgoingEdgesAnker[newEdge]->push(f);
2155 }
2156
2157 nextSon = firstSon->getNextSib(oldSib);
2158 oldSib = firstSon;
2159 pre = next;
2160 while (nextSon && nextSon != firstSon)
2161 {
2162 if (nextSon->type() != PQNodeRoot::leaf)
2163 {
2164 treeNodes.append(nextSon);
2165 newNode = Gcopy.newNode(); // new node corresponding to anchor
2166 // or cutnode
2167 m_nodeTableCopy2Orig[newNode] = 0;
2168 m_wheelGraphNodes[newNode] = origOfAct;
2169 Ccopy.reassignNode(newNode,parent);
2170 graphNodes.append(newNode);
2171 Gcopy.newEdge(correspond,newNode);
2172 }
2173 else
2174 {
2175 // insert Edge to the outside
2176 PQLeaf<edge,IndInfo*,bool>* leaf =
2177 (PQLeaf<edge,IndInfo*,bool>*) nextSon;
2178 edge f = leaf->getKey()->m_userStructKey;
2179 //node x = outgoingTable[f];
2180 edge newEdge = Gcopy.newEdge(correspond,outgoingTable[f]);
2181
2182 if ((*m_clusterOutgoingEdgesAnker[origOfAct])[f])
2183 {
2184 m_outgoingEdgesAnker[newEdge]
2185 = (*m_clusterOutgoingEdgesAnker[origOfAct])[f];
2186 }
2187 else
2188 m_outgoingEdgesAnker[newEdge] = OGDF_NEW Stack<edge>;
2189 m_outgoingEdgesAnker[newEdge]->push(f);
2190 }
2191 holdSib = nextSon->getNextSib(oldSib);
2192 oldSib = nextSon;
2193 nextSon = holdSib;
2194 }
2195
2196 }
2197 else if (checkNode->type() == PQNodeRoot::QNode)
2198 {
2199
2200 // correspond is the achor of a hub
2201 OGDF_ASSERT(T->scanLeftEndmost(checkNode))
2202 firstSon = T->scanLeftEndmost(checkNode);
2203
2204 hub = Gcopy.newNode();
2205 m_nodeTableCopy2Orig[hub] = 0;
2206 m_currentHubs[hub] = true;
2207 m_wheelGraphNodes[hub] = origOfAct;
2208 Ccopy.reassignNode(hub,parent);
2209
2210 Gcopy.newEdge(hub,correspond); // link achor and hub
2211 next = Gcopy.newNode(); // for first son
2212 m_nodeTableCopy2Orig[next] = 0;
2213 m_wheelGraphNodes[next] = origOfAct;
2214 Ccopy.reassignNode(next,parent);
2215 Gcopy.newEdge(hub,next);
2216 Gcopy.newEdge(correspond,next);
2217
2218 if (firstSon->type() != PQNodeRoot::leaf)
2219 {
2220 treeNodes.append(firstSon);
2221 newNode = Gcopy.newNode();
2222 m_nodeTableCopy2Orig[newNode] = 0;
2223 m_wheelGraphNodes[newNode] = origOfAct;
2224 Ccopy.reassignNode(newNode,parent);
2225 graphNodes.append(newNode);
2226 Gcopy.newEdge(next,newNode);
2227 }
2228 else
2229 {
2230 // insert Edge to the outside
2231 PQLeaf<edge,IndInfo*,bool>* leaf =
2232 (PQLeaf<edge,IndInfo*,bool>*) firstSon;
2233 edge f = leaf->getKey()->m_userStructKey;
2234 //node x = outgoingTable[f];
2235 edge newEdge = Gcopy.newEdge(next,outgoingTable[f]);
2236
2237 if ((*m_clusterOutgoingEdgesAnker[origOfAct])[f])
2238 {
2239 m_outgoingEdgesAnker[newEdge]
2240 = (*m_clusterOutgoingEdgesAnker[origOfAct])[f];
2241 }
2242 else
2243 m_outgoingEdgesAnker[newEdge] = OGDF_NEW Stack<edge>;
2244 m_outgoingEdgesAnker[newEdge]->push(f);
2245 }
2246
2247 nextSon = T->scanNextSib(firstSon,oldSib);
2248 oldSib = firstSon;
2249 pre = next;
2250 while (nextSon)
2251 {
2252 next = Gcopy.newNode();
2253 m_nodeTableCopy2Orig[next] = 0;
2254 m_wheelGraphNodes[next] = origOfAct;
2255 Ccopy.reassignNode(next,parent);
2256 Gcopy.newEdge(hub,next);
2257 Gcopy.newEdge(pre,next);
2258 if (nextSon->type() != PQNodeRoot::leaf)
2259 {
2260 treeNodes.append(nextSon);
2261 newNode = Gcopy.newNode(); // new node corresponding to anchor
2262 // or cutnode
2263 m_nodeTableCopy2Orig[newNode] = 0;
2264 m_wheelGraphNodes[newNode] = origOfAct;
2265 Ccopy.reassignNode(newNode,parent);
2266 graphNodes.append(newNode);
2267
2268 Gcopy.newEdge(next,newNode);
2269 }
2270 else
2271 {
2272 // insert Edge to the outside
2273 PQLeaf<edge,IndInfo*,bool>* leaf =
2274 (PQLeaf<edge,IndInfo*,bool>*) nextSon;
2275 edge f = leaf->getKey()->m_userStructKey;
2276 //node x = outgoingTable[f];
2277 edge newEdge = Gcopy.newEdge(next,outgoingTable[f]);
2278
2279 if ((*m_clusterOutgoingEdgesAnker[origOfAct])[f])
2280 {
2281 m_outgoingEdgesAnker[newEdge]
2282 = (*m_clusterOutgoingEdgesAnker[origOfAct])[f];
2283 }
2284 else
2285 m_outgoingEdgesAnker[newEdge] = OGDF_NEW Stack<edge>;
2286 m_outgoingEdgesAnker[newEdge]->push(f);
2287 }
2288 holdSib = T->scanNextSib(nextSon,oldSib);
2289 oldSib = nextSon;
2290 nextSon = holdSib;
2291 pre = next;
2292
2293 }
2294 Gcopy.newEdge(next,correspond);
2295 }
2296 }
2297
2298 OGDF_ASSERT(Ccopy.consistencyCheck());
2299 }// constructWheelGraph
2300
2301
2302 } // end namespace ogdf
2303
Windows Explorer Extension to Operate Git