ext/OGDF/src/planarity/BoyerMyrvoldInit.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 implementation of the class BoyerMyrvoldInit
  11  *
  12  * \author Jens Schmidt
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include <ogdf/internal/planarity/BoyerMyrvoldInit.h>
  45
  46
  47 namespace ogdf {
  48
  49
  50 // constructor
  51 BoyerMyrvoldInit::BoyerMyrvoldInit(BoyerMyrvoldPlanar* pBM) :
  52         m_g(pBM->m_g),
  53         // initialize Members of BoyerMyrvoldPlanar
  54         m_embeddingGrade(pBM->m_embeddingGrade),
  55         m_randomDFSTree(pBM->m_randomDFSTree),
  56
  57         m_realVertex(pBM->m_realVertex),
  58         m_dfi(pBM->m_dfi),
  59         m_nodeFromDFI(pBM->m_nodeFromDFI),
  60         m_link(pBM->m_link),
  61         m_adjParent(pBM->m_adjParent),
  62         m_leastAncestor(pBM->m_leastAncestor),
  63         m_edgeType(pBM->m_edgeType),
  64         m_lowPoint(pBM->m_lowPoint),
  65         m_highestSubtreeDFI(pBM->m_highestSubtreeDFI),
  66         m_separatedDFSChildList(pBM->m_separatedDFSChildList),
  67         m_pNodeInParent(pBM->m_pNodeInParent)
  68 {
  69         OGDF_ASSERT(pBM != NULL);
  70         OGDF_ASSERT(m_embeddingGrade <= BoyerMyrvoldPlanar::doNotFind ||
  71                                 m_highestSubtreeDFI.graphOf() == &m_g);
  72 }
  73
  74 // start DFS-traversal
  75 void BoyerMyrvoldInit::computeDFS() {
  76         StackPure<adjEntry> stack;
  77         int nextDFI = 1;
  78         const int numberOfNodes = m_g.numberOfNodes();
  79         node v,w,next,parentNode;
  80         adjEntry adj,prnt;
  81         edge e;
  82
  83         // get random dfs-tree, if wanted
  84         if (m_randomDFSTree) {
  85                 SListPure<node> list;
  86                 SListPure<adjEntry> adjList;
  87                 SListIterator<node> it;
  88                 // permute nodelist
  89                 m_g.allNodes(list);
  90                 list.permute();
  91                 for (it = list.begin(); it.valid(); ++it) {
  92                         node& v(*it);
  93                         // permute adjEntries
  94                         if (v->degree() == 0) {
  95                                 m_dfi[v] = nextDFI;
  96                                 m_leastAncestor[v] = nextDFI;
  97                                 m_nodeFromDFI[nextDFI] = v;
  98                                 ++nextDFI;
  99                         } else {
 100                                 adjList.clear();
 101                                 m_g.adjEntries(v,adjList);
 102                                 adjList.permute();
 103                                 m_g.sort(v,adjList);
 104                                 stack.push(v->firstAdj());
 105                         }
 106                 }
 107         } else {
 108                 for (next = m_g.firstNode(); next; next = next->succ())
 109                         if (next->degree() == 0) {
 110                                 m_dfi[next] = nextDFI;
 111                                 m_leastAncestor[next] = nextDFI;
 112                                 m_nodeFromDFI[nextDFI] = next;
 113                                 ++nextDFI;
 114                         } else stack.push(next->firstAdj());
 115         }
 116
 117         while (nextDFI <= numberOfNodes) {
 118                 OGDF_ASSERT(!stack.empty());
 119                 prnt = stack.pop();
 120                 v = prnt->theNode();
 121                 // check, if node v was visited before.
 122                 if (m_dfi[v] != 0) continue;
 123                 // parentNode=NULL on first node on connected component
 124                 parentNode = prnt->twinNode();
 125                 if (m_dfi[parentNode] == 0) parentNode = NULL;
 126
 127                 // if not, mark node as visited and initialize NodeArrays
 128                 m_dfi[v] = nextDFI;
 129                 m_leastAncestor[v] = nextDFI;
 130                 m_nodeFromDFI[nextDFI] = v;
 131                 ++nextDFI;
 132
 133                 // push all adjacent nodes onto stack
 134                 forall_adj(adj,v) {
 135                         e = adj->theEdge();
 136                         if (adj == prnt && parentNode != NULL) continue;
 137
 138                         // check for self-loops and dfs- and dfs-parallel edges
 139                         w = adj->twinNode();
 140                         if (m_dfi[w] == 0) {
 141                                 m_edgeType[e] = EDGE_DFS;
 142                                 m_adjParent[w] = adj;
 143                                 m_link[CW][w] = adj;
 144                                 m_link[CCW][w] = adj;
 145
 146                                 // found new dfs-edge: preorder
 147                                 stack.push(adj->twin());
 148                         } else if (w == v) {
 149                                 // found self-loop
 150                                 m_edgeType[e] = EDGE_SELFLOOP;
 151                         } else {
 152                                 // node w already has been visited and is an dfs-ancestor of v
 153                                 OGDF_ASSERT(m_dfi[w] < m_dfi[v]);
 154                                 if (w == parentNode) {
 155                                         // found parallel edge of dfs-parent-edge
 156                                         m_edgeType[e] = EDGE_DFS_PARALLEL;
 157                                 } else {
 158                                         // found backedge
 159                                         m_edgeType[e] = EDGE_BACK;
 160                                         // set least Ancestor
 161                                         if (m_dfi[w] < m_leastAncestor[v])
 162                                                 m_leastAncestor[v] = m_dfi[w];
 163                                 }
 164                         }
 165                 }
 166         }
 167 }
 168
 169 // creates a virtual vertex of vertex father and embeds it as
 170 // root in the biconnected child component containing of one edge
 171 void BoyerMyrvoldInit::createVirtualVertex(const adjEntry father)
 172 {
 173         // check that adjEntry is valid
 174         OGDF_ASSERT(father != NULL);
 175
 176         // create new virtual Vertex and copy properties from non-virtual node
 177         const node virt = m_g.newNode();
 178         m_realVertex[virt] = father->theNode();
 179         m_dfi[virt] = -m_dfi[father->twinNode()];
 180         m_nodeFromDFI[m_dfi[virt]] = virt;
 181
 182         // set links for traversal of bicomps
 183         m_link[CW][virt] = father->twin();
 184         m_link[CCW][virt] = father->twin();
 185
 186         // move edge to new virtual Vertex
 187         edge e = father->theEdge();
 188         if (e->source() == father->theNode()) {
 189                 // e is outgoing edge
 190                 m_g.moveSource(e,virt);
 191         } else {
 192                 // e is ingoing edge
 193                 m_g.moveTarget(e,virt);
 194         }
 195 }
 196
 197 // calculates the lowpoints
 198 void BoyerMyrvoldInit::computeLowPoints()
 199 {
 200         node w;
 201         adjEntry adj,lastAdj;
 202
 203         for (int i = m_g.numberOfNodes(); i >= 1; --i) {
 204                 const node v = m_nodeFromDFI[i];
 205
 206                 // initialize lowpoints with least Ancestors and highpoints with dfi of node
 207                 m_lowPoint[v] = m_leastAncestor[v];
 208                 if (m_embeddingGrade > BoyerMyrvoldPlanar::doNotFind) m_highestSubtreeDFI[v] = i;
 209
 210                 // set the lowPoint of v by minimizing over its children lowPoints
 211                 // create virtual vertex for each child
 212                 adj = v->firstAdj();
 213                 while (adj) {
 214                         lastAdj = adj;
 215                         adj = adj->succ();
 216
 217                         // avoid self-loops, parallel- and backedges
 218                         if (m_edgeType[lastAdj->theEdge()] != EDGE_DFS) continue;
 219                         w = lastAdj->twinNode();
 220
 221                         // avoid parent dfs-node
 222                         if (m_dfi[w] <= i) continue;
 223
 224                         // set lowPoints and highpoints
 225                         if (m_lowPoint[w] < m_lowPoint[v]) m_lowPoint[v] = m_lowPoint[w];
 226                         if (m_embeddingGrade > BoyerMyrvoldPlanar::doNotFind &&
 227                                                                         m_highestSubtreeDFI[w] > m_highestSubtreeDFI[v])
 228                                 m_highestSubtreeDFI[v] = m_highestSubtreeDFI[w];
 229
 230                         // create virtual vertex for each dfs-child
 231                         createVirtualVertex(lastAdj);
 232                 }
 233         }
 234 }
 235
 236 // compute the separated DFS children for all nodes in ascending order of
 237 // their lowpoint values in linear time
 238 void BoyerMyrvoldInit::computeDFSChildLists() {
 239         // Bucketsort by lowpoint values
 240         BucketLowPoint blp(m_lowPoint);
 241
 242         // copy all non-virtual nodes in a list and sort them with Bucketsort
 243         SListPure<node> allNodes;
 244         node v;
 245         forall_nodes(v,m_g) if (m_dfi[v]>0) allNodes.pushBack(v);
 246         allNodes.bucketSort(1,m_nodeFromDFI.high(),blp);
 247
 248         // build DFS-child list
 249         SListConstIterator<node> it;
 250         for (it = allNodes.begin(); it.valid(); ++it) {
 251                 v = *it;
 252                 OGDF_ASSERT(m_dfi[v]>0);
 253
 254                 // if node is not root: insert node after last element of parent's DFSChildList
 255                 // to achieve constant time deletion later:
 256                 // set a pointer for each node to predecessor of his representative in the list
 257                 if (m_adjParent[v] != NULL) {
 258                         OGDF_ASSERT(m_realVertex[m_adjParent[v]->theNode()]!=NULL);
 259
 260                         m_pNodeInParent[v] = m_separatedDFSChildList[m_realVertex[m_adjParent[v]->theNode()]].pushBack(v);
 261
 262                         OGDF_ASSERT(m_pNodeInParent[v].valid());
 263                         OGDF_ASSERT(v == *m_pNodeInParent[v]);
 264                 } else m_pNodeInParent[v] = NULL;
 265         }
 266 }
 267
 268 }
 269