ext/OGDF/src/energybased/GalaxyMultilevel.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of class GalaxyMultilevelBuilder.
  11  *
  12  * \author Martin Gronemann
  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 "GalaxyMultilevel.h"
  44 #include <algorithm>
  45 #include "FastUtils.h"
  46 #include <ogdf/basic/Array.h>
  47
  48 namespace ogdf {
  49
  50
  51 void GalaxyMultilevelBuilder::computeSystemMass()
  52 {
  53         node v = 0;
  54         forall_nodes(v, *m_pGraph)
  55         {
  56                 m_nodeState[v].sysMass = (*m_pNodeInfo)[v].mass;
  57                 m_nodeState[v].label = 0;
  58                 m_nodeState[v].lastVisitor = v;
  59         }
  60
  61         forall_nodes(v, *m_pGraph)
  62         {
  63                 adjEntry adj;
  64                 forall_adj(adj, v)
  65                 {
  66                         m_nodeState[v].sysMass += (*m_pNodeInfo)[adj->twinNode()].mass;
  67                 }
  68
  69                 if (v->degree()==1)
  70                         m_nodeState[v].sysMass *= m_pGraph->numberOfNodes() ;
  71         }
  72 }
  73
  74
  75 void swap(ogdf::GalaxyMultilevelBuilder::NodeOrderInfo& a, ogdf::GalaxyMultilevelBuilder::NodeOrderInfo& b)
  76 {
  77         ogdf::GalaxyMultilevelBuilder::NodeOrderInfo t = a;
  78         a = b;
  79         b = t;
  80 }
  81
  82
  83 void GalaxyMultilevelBuilder::sortNodesBySystemMass()
  84 {
  85         int i = 0;
  86         node v = 0;
  87         m_pRandomSet = new RandomNodeSet(*m_pGraph);
  88         for (i=0;i<m_pGraph->numberOfNodes();i++)
  89         {
  90                 v = m_pRandomSet->chooseNode();
  91                 m_pRandomSet->removeNode(v);
  92                 m_nodeMassOrder[i].theNode = v;
  93         }
  94
  95         delete m_pRandomSet;
  96         std::sort(m_nodeMassOrder, m_nodeMassOrder+(m_pGraph->numberOfNodes()), NodeMassComparer( m_nodeState ));
  97 }
  98
  99
 100 void GalaxyMultilevelBuilder::labelSystem(node u, node v, int d, float df)
 101 {
 102         if (d>0)
 103         {
 104                 adjEntry adj;
 105                 forall_adj(adj, v)
 106                 {
 107                         node w = adj->twinNode();
 108                         // this node may have been labeled before but its closer to the current sun
 109                         if (m_nodeState[w].label < d)
 110                         {
 111                                 float currDistFromSun = (*m_pEdgeInfo)[adj->theEdge()].length + df /*+ (*m_pNodeInfo)[w].radius*/;
 112                                 // check if we relabeling by a new sun
 113                                 if (m_nodeState[w].lastVisitor != u)
 114                                 {
 115                                         // maybe this node has never been labeled
 116                                         m_nodeState[w].lastVisitor = u;
 117                                         m_nodeState[w].edgeLengthFromSun = currDistFromSun;
 118                                 }
 119                                 // finally relabel it
 120                                 m_nodeState[w].edgeLengthFromSun = min(m_nodeState[w].edgeLengthFromSun, currDistFromSun);
 121                                 m_nodeState[w].label = d;
 122                                 labelSystem(u, w, d-1, currDistFromSun /*+(*m_pNodeInfo)[w].radius*/);
 123                         }
 124                 }
 125         }
 126 }
 127
 128
 129 void GalaxyMultilevelBuilder::labelSystem()
 130 {
 131         m_sunNodeList.clear();
 132         node v = 0;
 133         forall_nodes(v, *m_pGraph)
 134         {
 135                 m_nodeState[v].sysMass = 0;
 136                 m_nodeState[v].label = 0;
 137                 m_nodeState[v].lastVisitor = v;
 138         }
 139
 140         for (int i=0; i < m_pGraph->numberOfNodes(); i++)
 141         {
 142                 v = m_nodeMassOrder[i].theNode;
 143                 if (m_nodeState[v].label == 0)
 144                 {
 145                         m_sunNodeList.pushBack(v);
 146                         m_nodeState[v].label = (m_dist+1);
 147                         m_nodeState[v].edgeLengthFromSun = 0.0;//(*m_pNodeInfo)[v].radius;
 148                         labelSystem(v, v, m_dist, m_nodeState[v].edgeLengthFromSun);
 149                 }
 150         }
 151 }
 152
 153
 154 GalaxyMultilevel* GalaxyMultilevelBuilder::build(GalaxyMultilevel* pMultiLevel)
 155 {
 156         m_dist = 2;
 157         m_pGraph = pMultiLevel->m_pGraph;
 158         m_pNodeInfo = pMultiLevel->m_pNodeInfo;
 159         m_pEdgeInfo = pMultiLevel->m_pEdgeInfo;
 160         m_nodeMassOrder = (NodeOrderInfo*)MALLOC_16(sizeof(NodeOrderInfo)*m_pGraph->numberOfNodes());
 161         m_nodeState.init(*m_pGraph);
 162
 163         this->computeSystemMass();
 164         this->sortNodesBySystemMass();
 165         this->labelSystem();
 166         GalaxyMultilevel* pMultiLevelResult = new GalaxyMultilevel(pMultiLevel);
 167         this->createResult(pMultiLevelResult);;
 168
 169         FREE_16(m_nodeMassOrder);
 170
 171         return pMultiLevelResult;
 172 }
 173
 174
 175 void GalaxyMultilevelBuilder::createResult(GalaxyMultilevel* pMultiLevelResult)
 176 {
 177         pMultiLevelResult->m_pGraph = new Graph();
 178         m_pGraphResult = pMultiLevelResult->m_pGraph;
 179
 180         NodeArray<node> toResultNode(*m_pGraph, 0);
 181         // create all sun nodes
 182         for(List<node>::iterator it = m_sunNodeList.begin(); it.valid(); it++)
 183         {
 184                 node v = *it;
 185                 node vResult = m_pGraphResult->newNode();
 186                 toResultNode[v] = vResult;
 187         }
 188
 189         pMultiLevelResult->m_pNodeInfo = new NodeArray<GalaxyMultilevel::LevelNodeInfo>(*m_pGraphResult);
 190         m_pNodeInfoResult = pMultiLevelResult->m_pNodeInfo;
 191
 192         // calculate the real system mass. this may not be the same as calculated before
 193         node u;
 194         forall_nodes(u, *m_pGraphResult)
 195         {
 196                 (*m_pNodeInfoResult)[u].radius = 0.0f;
 197                 (*m_pNodeInfoResult)[u].mass = 0.0f;
 198         }
 199         forall_nodes(u, *m_pGraph)
 200         {
 201                 node uSun = m_nodeState[u].lastVisitor;
 202                 node uSunResult = toResultNode[uSun];
 203                 (*m_pNodeInfo)[u].parent = uSunResult;
 204                 (*m_pNodeInfoResult)[uSunResult].mass +=((*m_pNodeInfo)[u].mass);
 205                 (*m_pNodeInfoResult)[uSunResult].radius = max( (*m_pNodeInfoResult)[uSunResult].radius, m_nodeState[u].edgeLengthFromSun);//m_nodeState[u].edgeLengthFromSun;//m_nodeState[u].edgeLengthFromSun;// max( (*m_pNodeInfoResult)[uSunResult].radius, m_nodeState[u].edgeLengthFromSun);
 206         }
 207
 208         pMultiLevelResult->m_pEdgeInfo = new EdgeArray<GalaxyMultilevel::LevelEdgeInfo>(*m_pGraphResult);
 209         m_pEdgeInfoResult = pMultiLevelResult->m_pEdgeInfo;
 210
 211         edge e;
 212         forall_edges(e, *m_pGraph)
 213         {
 214                 node v = e->source();
 215                 node w = e->target();
 216                 node vSun = m_nodeState[v].lastVisitor;
 217                 node wSun = m_nodeState[w].lastVisitor;
 218                 if (vSun != wSun)
 219                 {
 220                         node vSunResult = toResultNode[vSun];
 221                         node wSunResult = toResultNode[wSun];
 222                         edge eResult = m_pGraphResult->newEdge(vSunResult, wSunResult);
 223                         (*m_pEdgeInfoResult)[eResult].length = m_nodeState[v].edgeLengthFromSun + (*m_pEdgeInfo)[e].length + m_nodeState[w].edgeLengthFromSun;
 224                 }
 225         }
 226
 227         // make fast parallel free
 228         NodeArray<node> lastVisit(*m_pGraphResult, 0);
 229         node v;
 230         forall_nodes(v, *m_pGraphResult)
 231         {
 232                 if (v->degree()>1)
 233                 {
 234                         adjEntry adj = v->firstAdj();
 235                         do{
 236                                 node w = adj->twinNode();
 237                                 edge e = adj->theEdge();
 238                                 adj = adj->cyclicSucc();
 239                                 if (lastVisit[w] ==v)
 240                                         m_pGraphResult->delEdge(e);
 241                                 else
 242                                         lastVisit[w] = v;
 243                         } while (adj !=v->firstAdj());
 244                 }
 245         }
 246 }
 247
 248 } // end of namespace
 249