ext/OGDF/src/planarity/EmbedderMaxFace.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 maximum external face.
  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/EmbedderMaxFace.h>
  46 #include <ogdf/internal/planarity/ConnectedSubgraph.h>
  47 #include <ogdf/internal/planarity/EmbedderMaxFaceBiconnectedGraphs.h>
  48
  49 namespace ogdf {
  50
  51 void EmbedderMaxFace::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         if (G.numberOfEdges() == 1)
  60         {
  61                 edge e = G.firstEdge();
  62                 adjExternal = e->adjSource();
  63                 return;
  64         }
  65
  66         //HINT: Edges are directed from child to parent in BC-trees
  67         pBCTree = new BCTree(G);
  68
  69         //base case of biconnected graph:
  70         if (pBCTree->bcTree().numberOfNodes() == 1)
  71         {
  72                 NodeArray<int> m_nodeLength(G, 0);
  73                 EdgeArray<int> m_edgeLength(G, 1);
  74                 adjEntry m_adjExternal;
  75                 EmbedderMaxFaceBiconnectedGraphs<int>::embed(G, m_adjExternal, m_nodeLength, m_edgeLength);
  76                 adjExternal = m_adjExternal->twin();
  77
  78                 delete pBCTree;
  79                 return;
  80         }
  81
  82         //***************************************************************************/
  83         //First step: calculate maximum face and node lengths
  84         //***************************************************************************/
  85
  86         //Find root Block (root node is only node with out-degree of 0):
  87         node rootBlockNode;
  88         node n;
  89         forall_nodes(n, pBCTree->bcTree())
  90         {
  91                 if (n->outdeg() == 0)
  92                 {
  93                         rootBlockNode = n;
  94                         break;
  95                 }
  96         }
  97
  98         //compute block graphs and SPQR trees:
  99         blockG.init(pBCTree->bcTree());
 100         nBlockEmbedding_to_nH.init(pBCTree->bcTree());
 101         eBlockEmbedding_to_eH.init(pBCTree->bcTree());
 102         nH_to_nBlockEmbedding.init(pBCTree->bcTree());
 103         eH_to_eBlockEmbedding.init(pBCTree->bcTree());
 104         nodeLength.init(pBCTree->bcTree());
 105         cstrLength.init(pBCTree->bcTree());
 106         spqrTrees.init(pBCTree->bcTree(),0);
 107         computeBlockGraphs(rootBlockNode, 0);
 108
 109         //Bottom-Up-Traversal:
 110         edge e;
 111         forall_adj_edges(e, rootBlockNode)
 112         {
 113                 node cT = e->source();
 114                 node cH = pBCTree->cutVertex(cT, rootBlockNode);
 115                 node cB = nH_to_nBlockEmbedding[rootBlockNode][cH];
 116
 117                 //set length of v in block graph of root block node:
 118                 int length_v_in_rootBlock = 0;
 119                 edge e2;
 120                 forall_adj_edges(e2, cT)
 121                 {
 122                         //check if edge is an incoming edge:
 123                         if (e2->target() != cT)
 124                                 continue;
 125
 126                         node blockNode = e2->source();
 127                         node cutVertex = pBCTree->cutVertex(cT, blockNode);
 128                         length_v_in_rootBlock += constraintMaxFace(blockNode, cutVertex);
 129                 }
 130                 nodeLength[rootBlockNode][cB] = length_v_in_rootBlock;
 131         }
 132
 133         node bT_opt = G.chooseNode(); //= G.chooseNode() only to get rid of warning
 134         int ell_opt = 0;
 135         maximumFaceRec(rootBlockNode, bT_opt, ell_opt);
 136
 137
 138         //****************************************************************************
 139         //Second step: Embed G by expanding a maximum face in bT_opt
 140         //****************************************************************************
 141         newOrder.init(G);
 142         treeNodeTreated.init(pBCTree->bcTree(), false);
 143         embedBlock(bT_opt);
 144
 145         node v;
 146         forall_nodes(v, G)
 147                 G.sort(v, newOrder[v]);
 148
 149         forall_nodes(v, pBCTree->bcTree())
 150                 delete spqrTrees[v];
 151
 152         delete pBCTree;
 153 }
 154
 155
 156 void EmbedderMaxFace::computeBlockGraphs(const node& bT, const node& cH)
 157 {
 158         //recursion:
 159         edge e;
 160         forall_adj_edges(e, bT)
 161         {
 162                 if (e->source() == bT)
 163                         continue;
 164
 165                 node cT = e->source();
 166                 edge e2;
 167                 forall_adj_edges(e2, cT)
 168                 {
 169                         if (e2->source() == cT)
 170                                 continue;
 171                         node cH2 = pBCTree->cutVertex(cT, e2->source());
 172                         computeBlockGraphs(e2->source(), cH2);
 173                 }
 174         }
 175
 176         //embed block bT:
 177         node m_cH = cH;
 178         if (m_cH == 0)
 179                 m_cH = pBCTree->cutVertex(bT->firstAdj()->twinNode(), bT);
 180         ConnectedSubgraph<int>::call(pBCTree->auxiliaryGraph(), blockG[bT], m_cH,
 181                 nBlockEmbedding_to_nH[bT], eBlockEmbedding_to_eH[bT],
 182                 nH_to_nBlockEmbedding[bT], eH_to_eBlockEmbedding[bT]);
 183         nodeLength[bT].init(blockG[bT], 0);
 184         cstrLength[bT].init(blockG[bT], 0);
 185         if (   !blockG[bT].empty()
 186                 && blockG[bT].numberOfNodes() != 1
 187                 && blockG[bT].numberOfEdges() > 2)
 188         {
 189                 spqrTrees[bT] = new StaticSPQRTree(blockG[bT]);
 190         }
 191 }
 192
 193
 194 int EmbedderMaxFace::constraintMaxFace(const node& bT, const node& cH)
 195 {
 196         //forall (v \in B, v \neq c) do:
 197         //  length_B(v) := \sum_{(v, B') \in B} ConstraintMaxFace(B', v);
 198         edge e;
 199         forall_adj_edges(e, bT)
 200         {
 201                 if (e->target() != bT)
 202                         continue;
 203                 node vT = e->source();
 204                 node vH = pBCTree->cutVertex(vT, bT);
 205
 206                 //set length of vertex v in block graph of bT:
 207                 int length_v_in_block = 0;
 208                 edge e2;
 209                 forall_adj_edges(e2, vT)
 210                 {
 211                         //check if edge is an incoming edge:
 212                         if (e2->target() != vT)
 213                                 continue;
 214
 215                         node bT2 = e2->source();
 216                         node cutVertex = pBCTree->cutVertex(vT, bT2);
 217                         length_v_in_block += constraintMaxFace(bT2, cutVertex);
 218                 }
 219                 nodeLength[bT][nH_to_nBlockEmbedding[bT][vH]] = length_v_in_block;
 220         }
 221
 222         EdgeArray<int> edgeLength(blockG[bT], 1);
 223         int cstrLengthBc = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
 224                 blockG[bT],
 225                 nH_to_nBlockEmbedding[bT][cH],
 226                 nodeLength[bT],
 227                 edgeLength,
 228                 *spqrTrees[bT]);
 229         cstrLength[bT][nH_to_nBlockEmbedding[bT][cH]] = cstrLengthBc;
 230         return cstrLengthBc;
 231 }
 232
 233
 234 void EmbedderMaxFace::maximumFaceRec(const node& bT, node& bT_opt, int& ell_opt)
 235 {
 236         //(B*, \ell*) := (B, size of a maximum face in B):
 237         node m_bT_opt = bT;
 238         EdgeArray<int> edgeLength(blockG[bT], 1);
 239         NodeArray< EdgeArray<int> > edgeLengthSkel;
 240         int m_ell_opt = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(
 241                 blockG[bT], nodeLength[bT], edgeLength, *spqrTrees[bT], edgeLengthSkel);
 242
 243         edge e;
 244         forall_adj_edges(e, bT)
 245         {
 246                 if (e->target() != bT)
 247                         continue;
 248                 node cT = e->source();
 249                 node cH = pBCTree->cutVertex(cT, bT);
 250
 251                 EdgeArray<int> edgeLength(blockG[bT], 1);
 252                 cstrLength[bT][nH_to_nBlockEmbedding[bT][cH]]
 253                         = EmbedderMaxFaceBiconnectedGraphs<int>::computeSize(blockG[bT],
 254                                 nH_to_nBlockEmbedding[bT][cH],
 255                                 nodeLength[bT],
 256                                 edgeLength,
 257                                 *spqrTrees[bT],
 258                                 edgeLengthSkel);
 259
 260                 //L := \sum_{(B', c) \in bcTree} cstrLength(B', c)
 261                 int L = 0;
 262                 edge e2;
 263                 {
 264                         forall_adj_edges(e2, cT)
 265                         {
 266                                 //check if edge is an incoming edge:
 267                                 if (e2->source() != cT)
 268                                         continue;
 269
 270                                 //get partner vertex of c in the block graph of B'=e->target() and add
 271                                 //cstrLength(B', c) to L:
 272                                 node bT2 = e2->target();
 273                                 L += cstrLength[bT2][nH_to_nBlockEmbedding[bT2][pBCTree->cutVertex(cT, bT2)]];
 274                         }
 275                 }
 276
 277                 forall_adj_edges(e2, cT)
 278                 {
 279                         //check if edge is an outgoing edge or the edge from bT to cT:
 280                         if (e2->target() != cT || e2->source() == bT)
 281                                 continue;
 282
 283                         //get partner vertex of c in the block graph of B'=e->source():
 284                         node pT = e2->source();
 285                         node partnerV = pBCTree->cutVertex(cT, pT);
 286                         node pB = nH_to_nBlockEmbedding[pT][partnerV];
 287                         nodeLength[pT][pB] = L - cstrLength[pT][pB];
 288
 289                         //pBCTree->originalGraph().chooseNode() just to get rid of warning:
 290                         node thisbT_opt = pBCTree->originalGraph().chooseNode();
 291                         int thisell_opt = 0;
 292                         maximumFaceRec(pT, thisbT_opt, thisell_opt);
 293                         if (thisell_opt > m_ell_opt)
 294                         {
 295                                 m_bT_opt = thisbT_opt;
 296                                 m_ell_opt = thisell_opt;
 297                         }
 298                 }
 299         }
 300
 301         //return (B*, \ell*):
 302         bT_opt = m_bT_opt;
 303         ell_opt = m_ell_opt;
 304 }
 305
 306
 307 void EmbedderMaxFace::embedBlock(const node& bT)
 308 {
 309         ListIterator<adjEntry> after;
 310         node cT = 0;
 311         embedBlock(bT, cT, after);
 312 }
 313
 314
 315 void EmbedderMaxFace::embedBlock(
 316         const node& bT,
 317         const node& cT,
 318         ListIterator<adjEntry>& after)
 319 {
 320         treeNodeTreated[bT] = true;
 321         node cH = 0;
 322         if (!(cT == 0))
 323                 cH = pBCTree->cutVertex(cT, bT);
 324
 325         //***************************************************************************
 326         // 1. Compute embedding of block
 327         //***************************************************************************
 328         EdgeArray<int> edgeLength(blockG[bT], 1);
 329         adjEntry m_adjExternal = 0;
 330         if (cH == 0)
 331                 EmbedderMaxFaceBiconnectedGraphs<int>::embed(blockG[bT], m_adjExternal,
 332                         nodeLength[bT], edgeLength);
 333         else
 334                 EmbedderMaxFaceBiconnectedGraphs<int>::embed(blockG[bT], m_adjExternal,
 335                         nodeLength[bT], edgeLength, nH_to_nBlockEmbedding[bT][cH]);
 336
 337         //***************************************************************************
 338         // 2. Copy block embedding into graph embedding and call recursively
 339         //    embedBlock for all cut vertices in bT
 340         //***************************************************************************
 341         CombinatorialEmbedding CE(blockG[bT]);
 342         face f = CE.leftFace(m_adjExternal);
 343
 344         if (*pAdjExternal == 0)
 345         {
 346                 node on = pBCTree->original(nBlockEmbedding_to_nH[bT][m_adjExternal->theNode()]);
 347                 adjEntry ae1 = on->firstAdj();
 348                 for (adjEntry ae = ae1; ae; ae = ae->succ())
 349                 {
 350                         if (ae->theEdge() == pBCTree->original(eBlockEmbedding_to_eH[bT][m_adjExternal->theEdge()]))
 351                         {
 352                                 *pAdjExternal = ae->twin();
 353                                 break;
 354                         }
 355                 }
 356         }
 357
 358         node nSG;
 359         forall_nodes(nSG, blockG[bT])
 360         {
 361                 node nH = nBlockEmbedding_to_nH[bT][nSG];
 362                 node nG = pBCTree->original(nH);
 363                 adjEntry ae = nSG->firstAdj();
 364                 ListIterator<adjEntry>* pAfter;
 365                 if (pBCTree->bcproper(nG) == cT)
 366                         pAfter = &after;
 367                 else
 368                         pAfter = OGDF_NEW ListIterator<adjEntry>();
 369
 370                 if (pBCTree->typeOfGNode(nG) == BCTree::CutVertex)
 371                 {
 372                         node cT2 = pBCTree->bcproper(nG);
 373                         bool no_recursion = false;
 374                         if (cT2 == cT)
 375                         {
 376                                 node parent_bT_of_cT2;
 377                                 edge e_cT2_to_bT2;
 378                                 forall_adj_edges(e_cT2_to_bT2, cT2)
 379                                 {
 380                                         if (e_cT2_to_bT2->source() == cT2)
 381                                         {
 382                                                 parent_bT_of_cT2 = e_cT2_to_bT2->target();
 383                                                 break;
 384                                         }
 385                                 }
 386                                 if (treeNodeTreated[parent_bT_of_cT2])
 387                                         no_recursion = true;
 388                         }
 389
 390                         if (no_recursion)
 391                         {
 392                                 //find adjacency entry of nSG which lies on external face f:
 393                                 adjEntry aeFace = f->firstAdj();
 394                                 do
 395                                 {
 396                                         if (aeFace->theNode() == nSG)
 397                                         {
 398                                                 if (aeFace->succ())
 399                                                         ae = aeFace->succ();
 400                                                 else
 401                                                         ae = nSG->firstAdj();
 402                                                 break;
 403                                         }
 404                                         aeFace = aeFace->faceCycleSucc();
 405                                 } while(aeFace != f->firstAdj());
 406                         }
 407                         else //!no_recursion
 408                         {
 409                                 //(if exists) find adjacency entry of nSG which lies on external face f:
 410                                 adjEntry aeFace = f->firstAdj();
 411                                 do
 412                                 {
 413                                         if (aeFace->theNode() == nSG)
 414                                         {
 415                                                 if (aeFace->succ())
 416                                                         ae = aeFace->succ();
 417                                                 else
 418                                                         ae = nSG->firstAdj();
 419                                                 break;
 420                                         }
 421                                         aeFace = aeFace->faceCycleSucc();
 422                                 } while(aeFace != f->firstAdj());
 423
 424                                 edge e_cT2_to_bT2;
 425                                 forall_adj_edges(e_cT2_to_bT2, cT2)
 426                                 {
 427                                         node bT2;
 428                                         if (e_cT2_to_bT2->source() == cT2)
 429                                                 bT2 = e_cT2_to_bT2->target();
 430                                         else
 431                                                 bT2 = e_cT2_to_bT2->source();
 432                                         if (!treeNodeTreated[bT2])
 433                                                 embedBlock(bT2, cT2, *pAfter);
 434                                 }
 435                         }
 436                 }
 437
 438                 //embed all edges of block bT:
 439                 bool after_ae = true;
 440                 for (adjEntry aeNode = ae;
 441                         after_ae || aeNode != ae;
 442                         after_ae = (!after_ae || !aeNode->succ()) ? false : true,
 443                         aeNode = aeNode->succ() ? aeNode->succ() : nSG->firstAdj())
 444                 {
 445                         edge eG = pBCTree->original(eBlockEmbedding_to_eH[bT][aeNode->theEdge()]);
 446                         if (nG == eG->source())
 447                         {
 448                                 if (!pAfter->valid())
 449                                         *pAfter = newOrder[nG].pushBack(eG->adjSource());
 450                                 else
 451                                         *pAfter = newOrder[nG].insertAfter(eG->adjSource(), *pAfter);
 452                         }
 453                         else //!(nG == eG->source())
 454                         {
 455                                 if (!pAfter->valid())
 456                                         *pAfter = newOrder[nG].pushBack(eG->adjTarget());
 457                                 else
 458                                         *pAfter = newOrder[nG].insertAfter(eG->adjTarget(), *pAfter);
 459                         }
 460                 } //for (adjEntry aeNode = ae; aeNode; aeNode = aeNode->succ())
 461
 462                 if (!(*pAfter == after))
 463                         delete pAfter;
 464         } //forall_nodes(nSG, blockG[bT])
 465 }
 466
 467 } // end namespace ogdf