ext/OGDF/src/planarity/EmbedderMinDepth.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Computes an embedding of a graph with minimum depth.
  11  * See paper "Graph Embedding with Minimum Depth and Maximum External
  12  * Face" by C. Gutwenger and P. Mutzel (2004) for details.
  13  *
  14  * \author Thorsten Kerkhof
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45 #include <ogdf/planarity/EmbedderMinDepth.h>
  46 #include <ogdf/internal/planarity/EmbedderMaxFaceBiconnectedGraphs.h>
  47 #include <ogdf/internal/planarity/ConnectedSubgraph.h>
  48
  49 namespace ogdf {
  50
  51 void EmbedderMinDepth::call(Graph& G, adjEntry& adjExternal)
  52 {
  53         adjExternal = 0;
  54         pAdjExternal = &adjExternal;
  55
  56         //simple base cases:
  57         if (G.numberOfNodes() <= 1)
  58                 return;
  59
  60         if (G.numberOfEdges() == 1)
  61         {
  62                 edge e = G.firstEdge();
  63                 adjExternal = e->adjSource();
  64                 return;
  65         }
  66
  67         //HINT: Edges are directed from child to parent in BC-trees
  68         pBCTree = new BCTree(G);
  69
  70         //base case of biconnected graph:
  71         if (pBCTree->bcTree().numberOfNodes() == 1)
  72         {
  73                 NodeArray<int> m_nodeLength(G, 0);
  74                 EdgeArray<int> m_edgeLength(G, 0);
  75                 adjEntry m_adjExternal;
  76                 EmbedderMaxFaceBiconnectedGraphs<int>::embed(G, m_adjExternal, m_nodeLength, m_edgeLength);
  77                 adjExternal = m_adjExternal->twin();
  78
  79                 delete pBCTree;
  80                 return;
  81         }
  82
  83
  84         //***************************************************************************/
  85         //First step: calculate min depth and node lengths
  86         //***************************************************************************/
  87         //Find root Block (only node with out-degree of 0):
  88         node rootBlockNode;
  89         node n;
  90         forall_nodes(n, pBCTree->bcTree())
  91         {
  92                 if (n->outdeg() == 0)
  93                 {
  94                         rootBlockNode = n;
  95                         break;
  96                 }
  97         }
  98
  99         //compute block graphs:
 100         blockG.init(pBCTree->bcTree());
 101         nBlockEmbedding_to_nH.init(pBCTree->bcTree());
 102         eBlockEmbedding_to_eH.init(pBCTree->bcTree());
 103         nH_to_nBlockEmbedding.init(pBCTree->bcTree());
 104         eH_to_eBlockEmbedding.init(pBCTree->bcTree());
 105         nodeLength.init(pBCTree->bcTree());
 106         spqrTrees.init(pBCTree->bcTree(),0);
 107         computeBlockGraphs(rootBlockNode, 0);
 108
 109         //Edge lengths of BC-tree, values m_{c, B} for all (c, B) \in bcTree:
 110         m_cB.init(pBCTree->bcTree(), 0);
 111
 112         //Bottom-up traversal: (set m_cB for all {c, B} \in bcTree)
 113         nodeLength[rootBlockNode].init(blockG[rootBlockNode], 0);
 114         edge e;
 115         forall_adj_edges(e, rootBlockNode)
 116         {
 117                 node cT = e->source();
 118                 //node cH = pBCTree->cutVertex(cT, rootBlockNode);
 119
 120                 //set length of c in block graph of root block node:
 121                 edge e2;
 122                 forall_adj_edges(e2, cT)
 123                 {
 124                         if (e2->target() != cT)
 125                                 continue;
 126
 127                         node blockNode = e2->source();
 128                         node cutVertex = pBCTree->cutVertex(cT, blockNode);
 129
 130                         //Start recursion:
 131                         m_cB[e2] = bottomUpTraversal(blockNode, cutVertex);
 132                 }
 133         }
 134
 135         //Top-down traversal: (set m_cB for all {B, c} \in bcTree and get min depth
 136         //for each block)
 137         int maxint = 2147483647;
 138         minDepth.init(pBCTree->bcTree(), maxint);
 139         M_B.init(pBCTree->bcTree());
 140         M2.init(pBCTree->bcTree());
 141         topDownTraversal(rootBlockNode);
 142
 143         //compute bT_opt:
 144         int depth = maxint;
 145         node bT_opt;
 146         forall_nodes(n, pBCTree->bcTree())
 147         {
 148                 if (pBCTree->typeOfBNode(n) != BCTree::BComp)
 149                         continue;
 150                 if (minDepth[n] < depth)
 151                 {
 152                         depth = minDepth[n];
 153                         bT_opt = n;
 154                 }
 155         }
 156
 157         //****************************************************************************
 158         //Second step: Embed G by expanding a maximum face in bT_opt
 159         //****************************************************************************
 160         newOrder.init(G);
 161         treeNodeTreated.init(pBCTree->bcTree(), false);
 162         embedBlock(bT_opt);
 163
 164         forall_nodes(n, G)
 165                 G.sort(n, newOrder[n]);
 166
 167         forall_nodes(n, pBCTree->bcTree())
 168                 delete spqrTrees[n];
 169
 170         delete pBCTree;
 171 }
 172
 173
 174 void EmbedderMinDepth::computeBlockGraphs(const node& bT, const node& cH)
 175 {
 176         //recursion:
 177         edge e;
 178         forall_adj_edges(e, bT)
 179         {
 180                 if (e->source() == bT)
 181                         continue;
 182
 183                 node cT = e->source();
 184                 edge e2;
 185                 forall_adj_edges(e2, cT)
 186                 {
 187                         if (e2->source() == cT)
 188                                 continue;
 189                         node cH2 = pBCTree->cutVertex(cT, e2->source());
 190                         computeBlockGraphs(e2->source(), cH2);
 191                 }
 192         }
 193
 194         //embed block bT:
 195         node m_cH = cH;
 196         if (m_cH == 0)
 197                 m_cH = pBCTree->cutVertex(bT->firstAdj()->twinNode(), bT);
 198         ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockG[bT], m_cH,
 199                 nBlockEmbedding_to_nH[bT], eBlockEmbedding_to_eH[bT],
 200                 nH_to_nBlockEmbedding[bT], eH_to_eBlockEmbedding[bT]);
 201
 202         if ( !blockG[bT].empty()
 203                 && blockG[bT].numberOfNodes() != 1
 204                 && blockG[bT].numberOfEdges() > 2)
 205         {
 206                 spqrTrees[bT] = new StaticSPQRTree(blockG[bT]);
 207         }
 208 }
 209
 210
 211 int EmbedderMinDepth::bottomUpTraversal(const node& bT, const node& cH)
 212 {
 213         int m_B = 0; //max_{c \in B} m_B(c)
 214         List<node> M_B; //{c \in B | m_B(c) = m_B}
 215
 216         //Recursion:
 217         edge e;
 218         forall_adj_edges(e, bT)
 219         {
 220                 if (e->target() != bT)
 221                         continue;
 222                 node cT = e->source();
 223                 //node c_in_bT = pBCTree->cutVertex(cT, bT);
 224
 225                 //set length of c in block graph of root block node:
 226                 edge e_cT_bT2;
 227                 forall_adj_edges(e_cT_bT2, cT)
 228                 {
 229                         if (e == e_cT_bT2)
 230                                 continue;
 231
 232                         node bT2 = e_cT_bT2->source();
 233                         node c_in_bT2 = pBCTree->cutVertex(cT, bT2);
 234                         m_cB[e_cT_bT2] = bottomUpTraversal(bT2, c_in_bT2);
 235
 236                         //update m_B and M_B:
 237                         if (m_B < m_cB[e_cT_bT2])
 238                         {
 239                                 node cV_in_bT = pBCTree->cutVertex(cT, bT);
 240                                 m_B = m_cB[e_cT_bT2];
 241                                 M_B.clear();
 242                                 M_B.pushBack(cV_in_bT);
 243                         }
 244                         else if (m_B == m_cB[e_cT_bT2] && M_B.search(pBCTree->cutVertex(cT, bT)) == -1)
 245                         {
 246                                 node cV_in_bT = pBCTree->cutVertex(cT, bT);
 247                                 M_B.pushBack(cV_in_bT);
 248                         }
 249                 }
 250         }
 251
 252         //set vertex length for all vertices in bH to 1 if vertex is in M_B:
 253         nodeLength[bT].init(blockG[bT], 0);
 254         for (ListIterator<node> iterator = M_B.begin(); iterator.valid(); iterator++)
 255                 nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 256
 257         //leafs of BC-tree:
 258         if (M_B.size() == 0)
 259                 return 1;
 260
 261         //set edge length for all edges in block graph to 0:
 262         EdgeArray<int> edgeLength(blockG[bT], 0);
 263
 264         //compute maximum external face of block graph and get its size:
 265         int cstrLength_B_c = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
 266                 blockG[bT],
 267                 nH_to_nBlockEmbedding[bT][cH],
 268                 nodeLength[bT],
 269                 edgeLength,
 270                 *spqrTrees[bT]);
 271
 272         if (cstrLength_B_c == M_B.size())
 273                 return m_B;
 274         //else:
 275         return m_B + 2;
 276 }
 277
 278
 279 void EmbedderMinDepth::topDownTraversal(const node& bT)
 280 {
 281         //m_B(c) = max {0} \cup {m_{c, B'} | c \in B', B' \neq B}
 282         int m_B = 0; //max_{c \in B} m_B(c)
 283
 284         //Compute m_B and M_B:
 285         node cT_parent = 0;
 286         edge e_bT_cT;
 287         {
 288                 forall_adj_edges(e_bT_cT, bT)
 289                 {
 290                         if (e_bT_cT->source() == bT)
 291                                 cT_parent = e_bT_cT->target();
 292                         node cT = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
 293                         edge e_cT_bT2;
 294                         forall_adj_edges(e_cT_bT2, cT)
 295                         {
 296                                 if (e_cT_bT2 == e_bT_cT)
 297                                         continue;
 298
 299                                 //update m_B and M_B:
 300                                 if (m_B < m_cB[e_cT_bT2])
 301                                 {
 302                                         m_B = m_cB[e_cT_bT2];
 303                                         M_B[bT].clear();
 304                                         M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
 305                                 }
 306                                 else if (   m_B == m_cB[e_cT_bT2] && M_B[bT].search(pBCTree->cutVertex(cT, bT)) == -1)
 307                                 {
 308                                         M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
 309                                 }
 310                         }//forall_adj_edges(e_cT_bT2, cT)
 311                 }//forall_adj_edges(e_bT_cT, bT)
 312         }
 313         //set vertex length for all vertices in bH to 1 if vertex is in M_B:
 314         nodeLength[bT].fill(0);
 315         NodeArray<int> m_nodeLength(blockG[bT], 0);
 316         for (ListIterator<node> iterator = M_B[bT].begin(); iterator.valid(); iterator++)
 317         {
 318                 nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 319                 m_nodeLength[nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 320         }
 321
 322         //set edge length for all edges in block graph to 0:
 323         EdgeArray<int> edgeLengthBlock(blockG[bT], 0);
 324
 325         //compute size of a maximum external face of block graph:
 326         NodeArray< EdgeArray<int> > edgeLengthSkel;
 327         int cstrLength_B_c = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
 328                 blockG[bT],
 329                 m_nodeLength,
 330                 edgeLengthBlock,
 331                 *spqrTrees[bT],
 332                 edgeLengthSkel);
 333
 334         //Prepare recursion by setting m_{c, B} for all edges {B, c} \in bcTree:
 335         if (M_B[bT].size() > 0)
 336         {
 337                 node cT1 = pBCTree->bcproper(pBCTree->original(*(M_B[bT].begin())));
 338                 bool calculateNewNodeLengths;
 339                 if (M_B[bT].size() == 1 && cT1 == cT_parent)
 340                         calculateNewNodeLengths = true;
 341                 else
 342                         calculateNewNodeLengths = false;
 343                 forall_adj_edges(e_bT_cT, bT)
 344                 {
 345                         if (e_bT_cT->target() != bT)
 346                                 continue;
 347                         node cT = e_bT_cT->source();
 348                         node cH = pBCTree->cutVertex(cT, bT);
 349
 350                         if (M_B[bT].size() == 1 && cT1 == cT)
 351                         {
 352                                 //Compute new vertex lengths according to
 353                                 //m2 = max_{v \in V_B, v != c} m_B(v) and
 354                                 //M2 = {c \in V_B \ {v} | m_B(c) = m2}.
 355                                 int m2 = 0;
 356
 357                                 //Compute m2 and M2:
 358                                 edge e_bT_cT2;
 359                                 forall_adj_edges(e_bT_cT2, bT)
 360                                 {
 361                                         node cT2 = (e_bT_cT2->source() == bT) ? e_bT_cT2->target() : e_bT_cT2->source();
 362                                         if (cT1 == cT2)
 363                                                 continue;
 364                                         edge e_cT2_bT2;
 365                                         forall_adj_edges(e_cT2_bT2, cT2)
 366                                         {
 367                                                 if (e_cT2_bT2 == e_bT_cT2)
 368                                                         continue;
 369
 370                                                 //update m_B and M_B:
 371                                                 if (m2 < m_cB[e_cT2_bT2])
 372                                                 {
 373                                                         m2 = m_cB[e_cT2_bT2];
 374                                                         M2[bT].clear();
 375                                                         M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
 376                                                 }
 377                                                 else if (   m2 == m_cB[e_cT2_bT2] && M2[bT].search(pBCTree->cutVertex(cT2, bT)) == -1)
 378                                                 {
 379                                                         M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
 380                                                 }
 381                                         }//forall_adj_edges(e_cT2_bT2, cT2)
 382                                 }//forall_adj_edges(e_bT_cT2, bT)
 383
 384                                 //set vertex length for all vertices in bH to 1 if vertex is in M2 and
 385                                 //0 otherwise:
 386                                 nodeLength[bT][nH_to_nBlockEmbedding[bT][*(M_B[bT].begin())]] = 0;
 387                                 for (ListIterator<node> iterator = M2[bT].begin(); iterator.valid(); iterator++)
 388                                         nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 389
 390                                 //set edge length for all edges in block graph to 0:
 391                                 EdgeArray<int> edgeLength(blockG[bT], 0);
 392
 393                                 //compute a maximum external face size of a face containing c in block graph:
 394                                 int maxFaceSize = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
 395                                         blockG[bT],
 396                                         nH_to_nBlockEmbedding[bT][cH],
 397                                         nodeLength[bT],
 398                                         edgeLength,
 399                                         *spqrTrees[bT]);
 400                                 if (M2[bT].size() == 0)
 401                                         m_cB[e_bT_cT] = 1;
 402                                 else
 403                                 {
 404                                         if (maxFaceSize == M2[bT].size())
 405                                                 m_cB[e_bT_cT] = m2;
 406                                         else
 407                                                 m_cB[e_bT_cT] = m2 + 2;
 408                                 }
 409
 410                                 if (calculateNewNodeLengths)
 411                                         calculateNewNodeLengths = false;
 412                                 else
 413                                 {
 414                                         //reset node lengths:
 415                                         for (ListIterator<node> iterator = M2[bT].begin(); iterator.valid(); iterator++)
 416                                                 nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 0;
 417                                         nodeLength[bT][nH_to_nBlockEmbedding[bT][*(M_B[bT].begin())]] = 1;
 418                                 }
 419                         }
 420                         else //M_B.size() != 1
 421                         {
 422                                 //Compute a maximum face in block B containing c using the vertex lengths
 423                                 //already assigned.
 424
 425                                 //set edge length for all edges in block graph to 0:
 426                                 EdgeArray<int> edgeLength(blockG[bT], 0);
 427
 428                                 //compute a maximum external face size of a face containing c in block graph:
 429                                 int maxFaceSize = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
 430                                         blockG[bT],
 431                                         nH_to_nBlockEmbedding[bT][cH],
 432                                         nodeLength[bT],
 433                                         edgeLength,
 434                                         *spqrTrees[bT],
 435                                         edgeLengthSkel);
 436                                 if (M_B[bT].size() == 0)
 437                                         m_cB[e_bT_cT] = 1;
 438                                 else
 439                                 {
 440                                         if (maxFaceSize == M_B[bT].size())
 441                                                 m_cB[e_bT_cT] = m_B;
 442                                         else
 443                                                 m_cB[e_bT_cT] = m_B + 2;
 444                                 }
 445                         }
 446                 }//forall_adj_edges(e_bT_cT, bT)
 447
 448                 if (calculateNewNodeLengths)
 449                 {
 450                         //Compute new vertex lengths according to
 451                         //m2 = max_{v \in V_B, v != c} m_B(v) and
 452                         //M2 = {c \in V_B \ {v} | m_B(c) = m2}.
 453                         int m2 = 0;
 454
 455                         //Compute m2 and M2:
 456                         edge e_bT_cT2;
 457                         forall_adj_edges(e_bT_cT2, bT)
 458                         {
 459                                 node cT2 = (e_bT_cT2->source() == bT) ? e_bT_cT2->target() : e_bT_cT2->source();
 460                                 if (cT1 == cT2)
 461                                         continue;
 462                                 edge e_cT2_bT2;
 463                                 forall_adj_edges(e_cT2_bT2, cT2)
 464                                 {
 465                                         if (e_cT2_bT2 == e_bT_cT2)
 466                                                 continue;
 467
 468                                         //update m_B and M_B:
 469                                         if (m2 < m_cB[e_cT2_bT2])
 470                                         {
 471                                                 m2 = m_cB[e_cT2_bT2];
 472                                                 M2[bT].clear();
 473                                                 M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
 474                                         }
 475                                         else if (   m2 == m_cB[e_cT2_bT2] && M2[bT].search(pBCTree->cutVertex(cT2, bT)) == -1)
 476                                         {
 477                                                 M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
 478                                         }
 479                                 }//forall_adj_edges(e_cT2_bT2, cT2)
 480                         }//forall_adj_edges(e_bT_cT2, bT)
 481
 482                         //set vertex length for all vertices in bH to 1 if vertex is in M2 and
 483                         //0 otherwise:
 484                         nodeLength[bT][nH_to_nBlockEmbedding[bT][*(M_B[bT].begin())]] = 0;
 485                         for (ListIterator<node> iterator = M2[bT].begin(); iterator.valid(); iterator++)
 486                                 nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 487                 } //if (calculateNewNodeLengths
 488                 else if (M_B[bT].size() == 1)
 489                 {
 490                         //Compute M2 = {c \in V_B \ {v} | m_B(c) = m2} with
 491                         //m2 = max_{v \in V_B, v != c} m_B(v).
 492                         int m2 = 0;
 493                         edge e_bT_cT2;
 494                         forall_adj_edges(e_bT_cT2, bT)
 495                         {
 496                                 node cT2 = (e_bT_cT2->source() == bT) ? e_bT_cT2->target() : e_bT_cT2->source();
 497                                 if (cT1 == cT2)
 498                                         continue;
 499                                 edge e_cT2_bT2;
 500                                 forall_adj_edges(e_cT2_bT2, cT2)
 501                                 {
 502                                         if (e_cT2_bT2 == e_bT_cT2)
 503                                                 continue;
 504
 505                                         //update m_B and M_B:
 506                                         if (m2 < m_cB[e_cT2_bT2])
 507                                         {
 508                                                 m2 = m_cB[e_cT2_bT2];
 509                                                 M2[bT].clear();
 510                                                 M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
 511                                         }
 512                                         else if (   m2 == m_cB[e_cT2_bT2] && M2[bT].search(pBCTree->cutVertex(cT2, bT)) == -1)
 513                                         {
 514                                                 M2[bT].pushBack(pBCTree->cutVertex(cT2, bT));
 515                                         }
 516                                 }//forall_adj_edges(e_cT2_bT2, cT2)
 517                         }//forall_adj_edges(e_bT_cT2, bT)
 518                 }
 519         }
 520
 521         //Recursion:
 522         forall_adj_edges(e_bT_cT, bT)
 523         {
 524                 if (e_bT_cT->target() != bT)
 525                         continue;
 526
 527                 node cT = e_bT_cT->source();
 528                 edge e_cT_bT2;
 529                 forall_adj_edges(e_cT_bT2, cT)
 530                 {
 531                         if (e_cT_bT2 == e_bT_cT)
 532                                 continue;
 533
 534                         topDownTraversal(e_cT_bT2->source());
 535                 }
 536         }
 537
 538         //Compute M_B and M2 for embedBlock-function:
 539         {
 540                 M_B[bT].clear();
 541                 M2[bT].clear();
 542                 m_B = 0;
 543                 int m2 = 0;
 544                 forall_adj_edges(e_bT_cT, bT)
 545                 {
 546                         node cT = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
 547                         edge e_cT_bT2;
 548                         forall_adj_edges(e_cT_bT2, cT)
 549                         {
 550                                 if (e_bT_cT == e_cT_bT2)
 551                                         continue;
 552
 553                                 //update m_B and M_B:
 554                                 if (m_B < m_cB[e_cT_bT2])
 555                                 {
 556                                         m_B = m_cB[e_cT_bT2];
 557                                         M_B[bT].clear();
 558                                         M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
 559                                 }
 560                                 else if (   m_B == m_cB[e_cT_bT2] && M_B[bT].search(pBCTree->cutVertex(cT, bT)) == -1)
 561                                 {
 562                                         M_B[bT].pushBack(pBCTree->cutVertex(cT, bT));
 563                                 }
 564                         }//forall_adj_edges(e_cT_bT2, cT)
 565                 }//forall_adj_edges(e_bT_cT, bT)
 566
 567                 if (M_B[bT].size() == 1)
 568                 {
 569                         node cT1 = pBCTree->bcproper(pBCTree->original(*(M_B[bT].begin())));
 570                         forall_adj_edges(e_bT_cT, bT)
 571                         {
 572                                 node cT2 = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
 573                                 if (cT1 == cT2)
 574                                         continue;
 575                                 node cT = (e_bT_cT->source() == bT) ? e_bT_cT->target() : e_bT_cT->source();
 576                                 edge e_cT_bT2;
 577                                 forall_adj_edges(e_cT_bT2, cT)
 578                                 {
 579                                         //update m2 and M2:
 580                                         if (m2 < m_cB[e_cT_bT2])
 581                                         {
 582                                                 m2 = m_cB[e_cT_bT2];
 583                                                 M2[bT].clear();
 584                                                 M2[bT].pushBack(pBCTree->cutVertex(cT, bT));
 585                                         }
 586                                         else if (   m2 == m_cB[e_cT_bT2]
 587                                                                          && M2[bT].search(pBCTree->cutVertex(cT, bT)) == -1)
 588                                         {
 589                                                 M2[bT].pushBack(pBCTree->cutVertex(cT, bT));
 590                                         }
 591                                 }//forall_adj_edges(e_cT_bT2, cT)
 592                         }//forall_adj_edges(e_bT_cT, bT)
 593                 }
 594         }
 595
 596         if (cstrLength_B_c == M_B[bT].size())
 597                 minDepth[bT] = m_B;
 598         else
 599                 minDepth[bT] = m_B + 2;
 600 }
 601
 602
 603 void EmbedderMinDepth::embedBlock(const node& bT)
 604 {
 605         ListIterator<adjEntry> after;
 606         node cT = 0;
 607         embedBlock(bT, cT, after);
 608 }
 609
 610
 611 void EmbedderMinDepth::embedBlock(
 612         const node& bT,
 613         const node& cT,
 614         ListIterator<adjEntry>& after)
 615 {
 616         treeNodeTreated[bT] = true;
 617         node cH = 0;
 618         if (!(cT == 0))
 619                 cH = pBCTree->cutVertex(cT, bT);
 620
 621         //***************************************************************************
 622         // 1. Compute node lengths depending on M_B, M2 and cT
 623         //***************************************************************************
 624         nodeLength[bT].fill(0);
 625         if (!(cT == 0) && M_B[bT].size() == 1 && *(M_B[bT].begin()) == cH)
 626         {
 627                 //set node length to 1 if node is in M2 and 0 otherwise
 628                 for (ListIterator<node> iterator = M2[bT].begin(); iterator.valid(); iterator++)
 629                         nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 630         }
 631         else
 632         {
 633                 //set node length to 1 if node is in M_B and 0 otherwise
 634                 for (ListIterator<node> iterator = M_B[bT].begin(); iterator.valid(); iterator++)
 635                         nodeLength[bT][nH_to_nBlockEmbedding[bT][*iterator]] = 1;
 636         }
 637
 638         //***************************************************************************
 639         // 2. Compute embedding of block
 640         //***************************************************************************
 641         EdgeArray<int> edgeLength(blockG[bT], 0);
 642         adjEntry m_adjExternal = 0;
 643         if (cH == 0)
 644                 EmbedderMaxFaceBiconnectedGraphs<int>::embed(blockG[bT], m_adjExternal, nodeLength[bT], edgeLength);
 645         else
 646                 EmbedderMaxFaceBiconnectedGraphs<int>::embed(blockG[bT], m_adjExternal, nodeLength[bT], edgeLength,
 647                         nH_to_nBlockEmbedding[bT][cH]);
 648
 649         //***************************************************************************
 650         // 3. Copy block embedding into graph embedding and call recursively
 651         //    embedBlock for all cut vertices in bT
 652         //***************************************************************************
 653         CombinatorialEmbedding CE(blockG[bT]);
 654         face f = CE.leftFace(m_adjExternal);
 655
 656         if (*pAdjExternal == 0)
 657         {
 658                 node on = pBCTree->original(nBlockEmbedding_to_nH[bT][m_adjExternal->theNode()]);
 659                 adjEntry ae1 = on->firstAdj();
 660                 for (adjEntry ae = ae1; ae; ae = ae->succ())
 661                 {
 662                         if (ae->theEdge() == pBCTree->original(eBlockEmbedding_to_eH[bT][m_adjExternal->theEdge()]))
 663                         {
 664                                 *pAdjExternal = ae->twin();
 665                                 break;
 666                         }
 667                 }
 668         }
 669
 670         node nSG;
 671         forall_nodes(nSG, blockG[bT])
 672         {
 673                 node nH = nBlockEmbedding_to_nH[bT][nSG];
 674                 node nG = pBCTree->original(nH);
 675                 adjEntry ae = nSG->firstAdj();
 676                 ListIterator<adjEntry>* pAfter;
 677                 if (pBCTree->bcproper(nG) == cT)
 678                         pAfter = &after;
 679                 else
 680                         pAfter = OGDF_NEW ListIterator<adjEntry>();
 681
 682                 if (pBCTree->typeOfGNode(nG) == BCTree::CutVertex)
 683                 {
 684                         node cT2 = pBCTree->bcproper(nG);
 685                         bool no_recursion = false;
 686                         if (cT2 == cT)
 687                         {
 688                                 node parent_bT_of_cT2;
 689                                 edge e_cT2_to_bT2;
 690                                 forall_adj_edges(e_cT2_to_bT2, cT2)
 691                                 {
 692                                         if (e_cT2_to_bT2->source() == cT2)
 693                                         {
 694                                                 parent_bT_of_cT2 = e_cT2_to_bT2->target();
 695                                                 break;
 696                                         }
 697                                 }
 698                                 if (treeNodeTreated[parent_bT_of_cT2])
 699                                         no_recursion = true;
 700                         }
 701
 702                         if (no_recursion)
 703                         {
 704                                 //find adjacency entry of nSG which lies on external face f:
 705                                 adjEntry aeFace = f->firstAdj();
 706                                 do
 707                                 {
 708                                         if (aeFace->theNode() == nSG)
 709                                         {
 710                                                 if (aeFace->succ())
 711                                                         ae = aeFace->succ();
 712                                                 else
 713                                                         ae = nSG->firstAdj();
 714                                                 break;
 715                                         }
 716                                         aeFace = aeFace->faceCycleSucc();
 717                                 } while(aeFace != f->firstAdj());
 718                         }
 719                         else //!no_recursion
 720                         {
 721                                 //(if exists) find adjacency entry of nSG which lies on external face f:
 722                                 //bool aeExtExists = false;
 723                                 adjEntry aeFace = f->firstAdj();
 724                                 //List<edge> extFaceEdges;
 725                                 do
 726                                 {
 727                                         //extFaceEdges.pushBack(aeFace->theEdge());
 728                                         if (aeFace->theNode() == nSG)
 729                                         {
 730                                                 if (aeFace->succ())
 731                                                         ae = aeFace->succ();
 732                                                 else
 733                                                         ae = nSG->firstAdj();
 734                                                 //aeExtExists = true;
 735                                                 break;
 736                                         }
 737                                         aeFace = aeFace->faceCycleSucc();
 738                                 } while(aeFace != f->firstAdj());
 739
 740                                 //if (aeExtExists)
 741                                 //{
 742                                         edge e_cT2_to_bT2;
 743                                         forall_adj_edges(e_cT2_to_bT2, cT2)
 744                                         {
 745                                                 node bT2;
 746                                                 if (e_cT2_to_bT2->source() == cT2)
 747                                                         bT2 = e_cT2_to_bT2->target();
 748                                                 else
 749                                                         bT2 = e_cT2_to_bT2->source();
 750                                                 if (!treeNodeTreated[bT2])
 751                                                         embedBlock(bT2, cT2, *pAfter);
 752                                         }
 753                                 //}
 754                                 //else
 755                                 //{
 756                                 //      //cannot embed block into external face, so find a face with an adjacent
 757                                 //      //edge of the external face:
 758                                 //      bool foundIt = false;
 759                                 //      edge adjEdge;
 760                                 //      forall_adj_edges(adjEdge, nSG)
 761                                 //      {
 762                                 //              face m_f = CE.leftFace(adjEdge->adjSource());
 763                                 //              adjEntry aeF = m_f->firstAdj();
 764                                 //              do
 765                                 //              {
 766                                 //                      if (extFaceEdges.search(aeF->theEdge()) != -1)
 767                                 //                      {
 768                                 //                              ae = adjEdge->adjSource();
 769                                 //                              foundIt = true;
 770                                 //                              break;
 771                                 //                      }
 772                                 //                      aeF = aeF->faceCycleSucc();
 773                                 //              } while(aeF != m_f->firstAdj());
 774                                 //              if (foundIt)
 775                                 //                      break;
 776                                 //      }
 777                                 //}
 778                         }
 779                 }
 780
 781                 //embed all edges of block bT:
 782                 bool after_ae = true;
 783                 for (adjEntry aeNode = ae;
 784                         after_ae || aeNode != ae;
 785                         after_ae = (!after_ae || !aeNode->succ()) ? false : true,
 786                         aeNode = aeNode->succ() ? aeNode->succ() : nSG->firstAdj())
 787                 {
 788                         edge eG = pBCTree->original(eBlockEmbedding_to_eH[bT][aeNode->theEdge()]);
 789                         if (nG == eG->source())
 790                         {
 791                                 if (!pAfter->valid())
 792                                         *pAfter = newOrder[nG].pushBack(eG->adjSource());
 793                                 else
 794                                         *pAfter = newOrder[nG].insertAfter(eG->adjSource(), *pAfter);
 795                         }
 796                         else //!(nG == eG->source())
 797                         {
 798                                 if (!pAfter->valid())
 799                                         *pAfter = newOrder[nG].pushBack(eG->adjTarget());
 800                                 else
 801                                         *pAfter = newOrder[nG].insertAfter(eG->adjTarget(), *pAfter);
 802                         }
 803                 } //for (adjEntry aeNode = ae; aeNode; aeNode = aeNode->succ())
 804
 805                 if (!(*pAfter == after))
 806                         delete pAfter;
 807         } //forall_nodes(nSG, blockG[bT])
 808 }
 809
 810 } // end namespace ogdf