ext/OGDF/src/basic/DualGraph.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 dual graph
  11  *
  12  * \author Michael Schulz
  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 #include <ogdf/basic/DualGraph.h>
  44
  45 namespace ogdf{
  46
  47 // Computes combinatorial embedding of dual graph
  48 // Precondition: CE must be combinatorial embedding of connected planar graph
  49 DualGraph::DualGraph(CombinatorialEmbedding &CE)
  50 {
  51         m_primalEmbedding = &CE;
  52         Graph &primalGraph = CE.getGraph();
  53         init(*(new Graph));
  54         Graph &dualGraph = getGraph();
  55
  56         m_dualNode.init(CE);
  57         m_dualEdge.init(primalGraph);
  58         m_dualFace.init(primalGraph);
  59         m_primalNode.init(*this);
  60         m_primalFace.init(dualGraph);
  61         m_primalEdge.init(dualGraph);
  62
  63         // create dual nodes
  64         face f;
  65         forall_faces(f, CE)
  66         {
  67                 node vDual = dualGraph.newNode();
  68                 m_dualNode[f] = vDual;
  69                 m_primalFace[vDual] = f;
  70         }
  71
  72         // create dual edges
  73         edge e;
  74         forall_edges(e, primalGraph)
  75         {
  76                 adjEntry aE = e->adjSource();
  77                 node vDualSource = m_dualNode[CE.rightFace(aE)];
  78                 node vDualTarget = m_dualNode[CE.leftFace(aE)];
  79                 edge eDual = dualGraph.newEdge(vDualSource, vDualTarget);
  80                 m_primalEdge[eDual] = e;
  81                 m_dualEdge[e] = eDual;
  82         }
  83
  84         // sort adjElements of every dual node corresponding to dual embedding
  85         EdgeArray<bool> visited(dualGraph, false);   // needed for self-loops
  86         forall_faces(f, CE)
  87         {
  88                 node vDual = m_dualNode[f];
  89                 adjEntry aePrimal = f->firstAdj();
  90                 List<adjEntry> aeList;
  91                 do
  92                 {
  93                         edge eDual = m_dualEdge[aePrimal->theEdge()];
  94                         adjEntry aeDual = eDual->adjSource();
  95                         if((aeDual->theNode()!=vDual) || (eDual->isSelfLoop() && visited[eDual]))
  96                                 aeDual = eDual->adjTarget();
  97                         aeList.pushBack( aeDual );
  98                         visited[eDual] = true; // only needed for self-loops
  99                         aePrimal = aePrimal->faceCycleSucc();
 100                 }
 101                 while(aePrimal != f->firstAdj());
 102                 dualGraph.sort(vDual, aeList);
 103         }
 104
 105         // calculate dual faces and links to corresponding primal nodes
 106         computeFaces();
 107         node v;
 108         forall_nodes(v, primalGraph)
 109         {
 110                 edge ePrimal = v->firstAdj()->theEdge();
 111                 edge eDual = m_dualEdge[ePrimal];
 112                 face fDual = rightFace(eDual->adjSource());
 113                 if(ePrimal->source()==v)
 114                         fDual = leftFace(eDual->adjSource());
 115                 m_dualFace[v] = fDual;
 116                 m_primalNode[fDual] = v;
 117         }
 118 }
 119
 120 // Destructor
 121 DualGraph::~DualGraph()
 122 {
 123         clear();
 124         delete m_cpGraph;
 125 }
 126
 127 }