ext/OGDF/src/energybased/multilevelmixer/SolarMerger.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 Merges nodes with Solar System rules
  11  *
  12  * \author Gereon Bartel
  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/energybased/multilevelmixer/SolarMerger.h>
  44
  45 namespace ogdf {
  46
  47 SolarMerger::SolarMerger(bool simple, bool massAsNodeRadius)
  48 :m_sunSelectionSimple(simple), m_massAsNodeRadius(massAsNodeRadius)
  49 {
  50 }
  51
  52
  53 int SolarMerger::calcSystemMass(node v) {
  54         unsigned int sum = m_mass[v];
  55         adjEntry adj;
  56         forall_adj(adj, v) {
  57                 sum += m_mass[adj->twinNode()];
  58         }
  59         return sum;
  60 }
  61
  62
  63 std::vector<node> SolarMerger::selectSuns(MultilevelGraph &MLG)
  64 {
  65         Graph &G = MLG.getGraph();
  66         std::vector<node> suns;
  67         std::vector<node> candidates;
  68
  69         node v;
  70         forall_nodes(v, G) {
  71                 candidates.push_back(v);
  72         }
  73
  74         if (m_sunSelectionSimple) {
  75                 while (!candidates.empty()) {
  76                         // select random node
  77                         int index = randomNumber(0, (int)candidates.size()-1);
  78                         node sun = candidates[index];
  79                         candidates[index] = candidates.back();
  80                         candidates.pop_back();
  81                         if (m_celestial[sun] != 0) {
  82                                 continue;
  83                         }
  84                         bool hasForeignPlanet = false;
  85                         adjEntry adj;
  86                         forall_adj(adj, sun) {
  87                                 if(m_celestial[adj->twinNode()] != 0) {
  88                                         hasForeignPlanet = true;
  89                                         break;
  90                                 }
  91                         }
  92                         if (hasForeignPlanet) {
  93                                 continue;
  94                         }
  95                         // mark node as sun
  96                         m_celestial[sun] = 1;
  97                         suns.push_back(sun);
  98                         // mark neighbours as planet
  99                         forall_adj(adj, sun) {
 100                                 m_celestial[adj->twinNode()] = 2;
 101                                 m_orbitalCenter[adj->twinNode()] = sun;
 102                                 m_distanceToOrbit[adj->twinNode()] = MLG.weight(adj->theEdge());
 103                         }
 104                 }
 105         } else {
 106                 while (!candidates.empty()) {
 107                         std::vector< std::pair<node, int> > sunCandidates;
 108                         int i = 1;
 109                         int n = 10;
 110                         while (i<=n && !candidates.empty()) {
 111                                 // select random node
 112                                 int index = randomNumber(0, (int)candidates.size()-1);
 113                                 node rndNode = candidates[index];
 114                                 candidates[index] = candidates.back();
 115                                 candidates.pop_back();
 116                                 if (m_celestial[rndNode] != 0) {
 117                                         continue;
 118                                 }
 119                                 bool hasForeignPlanet = false;
 120                                 adjEntry adj;
 121                                 forall_adj(adj, rndNode) {
 122                                         if(m_celestial[adj->twinNode()] != 0) {
 123                                                 hasForeignPlanet = true;
 124                                                 break;
 125                                         }
 126                                 }
 127                                 if (hasForeignPlanet) {
 128                                         continue;
 129                                 }
 130                                 unsigned int mass = calcSystemMass(rndNode);
 131                                 sunCandidates.push_back(std::pair<node, int>(rndNode, mass));
 132                                 i++;
 133                         }
 134                         if (sunCandidates.empty()) {
 135                                 continue;
 136                         }
 137
 138                         node minNode = sunCandidates.front().first;
 139                         unsigned int minMass = sunCandidates.front().second;
 140                         // select sun with smalles mass from sunCandidates
 141                         for (std::vector< std::pair<node, int> >::iterator i = sunCandidates.begin();
 142                                 i != sunCandidates.end(); i++)
 143                         {
 144                                 node nod = (*i).first;
 145                                 unsigned int mass = (*i).second;
 146                                 if (mass < minMass) {
 147                                         minMass = mass;
 148                                         minNode = nod;
 149                                 }
 150                         }
 151
 152                         for (std::vector< std::pair<node, int> >::iterator i = sunCandidates.begin();
 153                                 i != sunCandidates.end(); i++)
 154                         {
 155                                 node temp = (*i).first;
 156                                 if (temp == minNode) {
 157                                         continue;
 158                                 }
 159                                 candidates.push_back(temp);
 160                         }
 161
 162                         // mark node as sun
 163                         m_celestial[minNode] = 1;
 164                         suns.push_back(minNode);
 165                         // mark neighbours as planet
 166                         adjEntry adj;
 167                         forall_adj(adj, minNode) {
 168                                 m_celestial[adj->twinNode()] = 2;
 169                                 m_orbitalCenter[adj->twinNode()] = minNode;
 170                                 m_distanceToOrbit[adj->twinNode()] = MLG.weight(adj->theEdge());
 171                         }
 172                 }
 173         }
 174
 175         forall_nodes(v, G) {
 176                 if (m_celestial[v] == 0) {
 177                         m_celestial[v] = 3;
 178                         adjEntry adj;
 179                         std::vector<adjEntry> planets;
 180                         node planet;
 181                         forall_adj(adj, v) {
 182                                 planet = adj->twinNode();
 183                                 if (m_celestial[planet] == 2) {
 184                                         planets.push_back(adj);
 185                                 }
 186                         }
 187                         OGDF_ASSERT(planets.size() > 0);
 188                         int index = randomNumber(0, (int)planets.size()-1);
 189                         planet = planets[index]->twinNode();
 190                         m_orbitalCenter[v] = planet;
 191                         m_distanceToOrbit[v] = MLG.weight(planets[index]->theEdge());
 192                 }
 193         }
 194
 195         return suns;
 196 }
 197
 198
 199 void SolarMerger::buildAllLevels(MultilevelGraph &MLG)
 200 {
 201         m_numLevels = 1;
 202         Graph &G = MLG.getGraph();
 203         if (m_massAsNodeRadius || !m_sunSelectionSimple) {
 204                 m_mass.init(G, 1);
 205                 m_radius.init(G);
 206                 node v;
 207                 forall_nodes(v, G) {
 208                         m_radius[v] = MLG.radius(v);
 209                 }
 210         }
 211         MLG.updateReverseIndizes();
 212         while (buildOneLevel(MLG))
 213         {//this is not needed anymore locally since Multilevelbuilder keeps this info
 214                 m_numLevels++;
 215         }
 216         MLG.updateReverseIndizes();
 217 }
 218
 219
 220 node SolarMerger::sunOf(node object)
 221 {
 222         if (object == 0 || m_celestial[object] == 0) {
 223                 return 0;
 224         }
 225         if (m_celestial[object] == 1) {
 226                 return object;
 227         }
 228         return sunOf(m_orbitalCenter[object]);
 229 }
 230
 231
 232 void SolarMerger::addPath(node sourceSun, node targetSun, double distance)
 233 {
 234         node source = sourceSun;
 235         node target = targetSun;
 236         if (targetSun->index() < sourceSun->index()) {
 237                 source = targetSun;
 238                 target = sourceSun;
 239         }
 240         PathData data = m_interSystemPaths[source->index()][target->index()];
 241         OGDF_ASSERT(data.targetSun == target->index() || data.number == 0);
 242
 243         int num = data.number;
 244         double len = data.length;
 245
 246         len = len * num + distance;
 247         num++;
 248         len /= num;
 249         data.length = len;
 250         data.number = num;
 251         data.targetSun = target->index();
 252
 253         m_interSystemPaths[source->index()][target->index()] = data;
 254 }
 255
 256
 257 double SolarMerger::distanceToSun(node object, MultilevelGraph &MLG)
 258 {
 259         double dist = 0.0;
 260
 261         if (object == 0 || m_celestial[object] <= 1) {
 262                 return dist;
 263         }
 264
 265         node center = m_orbitalCenter[object];
 266         OGDF_ASSERT(center != 0);
 267
 268         bool found = false;
 269         adjEntry adj;
 270         forall_adj(adj, object) {
 271                 if (adj->twinNode() == center) {
 272                         found = true;
 273                         dist = MLG.weight(adj->theEdge());
 274                         OGDF_ASSERT(dist > 0);
 275                         break;
 276                 }
 277         }
 278         OGDF_ASSERT(found);
 279
 280         return distanceToSun(center, MLG) + dist;
 281 }
 282
 283
 284 void SolarMerger::findInterSystemPaths(Graph &G, MultilevelGraph &MLG)
 285 {
 286         edge e;
 287         forall_edges(e, G) {
 288                 node source = e->source();
 289                 node target = e->target();
 290                 if (sunOf(source) != sunOf(target)) {
 291                         // construct intersystempath
 292                         double len = distanceToSun(source, MLG) + distanceToSun(target, MLG) + MLG.weight(e);
 293                         OGDF_ASSERT(len > 0);
 294                         addPath(sunOf(source), sunOf(target), len);
 295
 296                         // save positions of nodes on the path.
 297                         node src = source;
 298                         do {
 299                                 double dist = distanceToSun(src, MLG);
 300                                 m_pathDistances[src].push_back(PathData(sunOf(target)->index(), dist / len, 1));
 301                                 src = m_orbitalCenter[src];
 302                         } while(src != 0);
 303
 304                         node tgt = target;
 305                         do {
 306                                 double dist = distanceToSun(tgt, MLG);
 307                                 m_pathDistances[tgt].push_back(PathData(sunOf(source)->index(), dist / len, 1));
 308                                 tgt = m_orbitalCenter[tgt];
 309                         } while(tgt != 0);
 310                 }
 311         }
 312 }
 313
 314
 315 bool SolarMerger::buildOneLevel(MultilevelGraph &MLG)
 316 {
 317         Graph &G = MLG.getGraph();
 318         int level = MLG.getLevel() + 1;
 319
 320         int numNodes = G.numberOfNodes();
 321
 322         if (numNodes <= 3) {
 323                 return false;
 324         }
 325
 326         m_orbitalCenter.init(G, 0);
 327         m_distanceToOrbit.init(G, 1.0);
 328         m_pathDistances.init(G, std::vector<PathData>());
 329         m_celestial.init(G, 0);
 330         m_interSystemPaths.clear();
 331
 332         std::vector<node> suns = selectSuns(MLG);
 333
 334         if (suns.empty()) {
 335                 return false;
 336         }
 337
 338         findInterSystemPaths(G, MLG);
 339
 340         for(std::vector<node>::iterator i = suns.begin(); i != suns.end(); i++) {
 341                 if (!collapsSolarSystem(MLG, *i, level)) {
 342                         return false;
 343                 }
 344         }
 345
 346         NodeMerge * lastMerge = MLG.getLastMerge();
 347         edge e;
 348         forall_edges(e, G) {
 349                 node source = e->source();
 350                 node target = e->target();
 351                 if (target->index() < source->index())
 352                 {
 353                         node temp = source;
 354                         source = target;
 355                         target = temp;
 356                 }
 357
 358                 if (!m_interSystemPaths[source->index()].empty()) {
 359                         if (m_interSystemPaths[source->index()][target->index()].number != 0) {
 360                                 MLG.changeEdge(lastMerge, e, m_interSystemPaths[source->index()][target->index()].length, source, target);
 361                         }
 362                 }
 363         }
 364
 365         return true;
 366 }
 367
 368
 369 bool SolarMerger::collapsSolarSystem(MultilevelGraph &MLG, node sun, int level)
 370 {
 371         bool retVal = false;
 372
 373         std::vector<node> systemNodes;
 374         unsigned int mass = 0;
 375         if (m_massAsNodeRadius || !m_sunSelectionSimple) {
 376                 mass = m_mass[sun];
 377         }
 378
 379         OGDF_ASSERT(m_celestial[sun] == 1)
 380
 381         adjEntry adj;
 382         forall_adj(adj, sun) {
 383 #ifdef OGDF_DEBUG
 384                 node planet = adj->twinNode();
 385 #endif
 386                 OGDF_ASSERT(m_celestial[planet] == 2)
 387                 OGDF_ASSERT(m_orbitalCenter[planet] == sun)
 388                 systemNodes.push_back(adj->twinNode());
 389         }
 390         forall_adj(adj, sun) {
 391                 node planet = adj->twinNode();
 392                 OGDF_ASSERT(m_celestial[planet] == 2)
 393                 OGDF_ASSERT(m_orbitalCenter[planet] == sun)
 394                 adjEntry adj2;
 395                 forall_adj(adj2, planet) {
 396                         node moon = adj2->twinNode();
 397                         if(m_celestial[moon] == 3 && m_orbitalCenter[moon] == planet) {
 398                                 systemNodes.push_back(moon);
 399                         }
 400                 }
 401         }
 402
 403         if (m_massAsNodeRadius || !m_sunSelectionSimple) {
 404                 for(std::vector<node>::iterator i = systemNodes.begin(); i != systemNodes.end(); i++) {
 405                         mass += m_mass[*i];
 406                 }
 407                 m_mass[sun] = mass;
 408         }
 409
 410         for(std::vector<node>::iterator i = systemNodes.begin(); i != systemNodes.end(); i++) {
 411                 node mergeNode = *i;
 412
 413                 if (MLG.getNode(sun->index()) != sun
 414                         || MLG.getNode(mergeNode->index()) != mergeNode)
 415                 {
 416                         return false;
 417                 }
 418
 419                 NodeMerge * NM = new NodeMerge(level);
 420                 std::vector<PathData> positions = m_pathDistances[mergeNode];
 421                 for (std::vector<PathData>::iterator j = positions.begin(); j != positions.end(); j++) {
 422                         NM->m_position.push_back(std::pair<int,double>((*j).targetSun, (*j).length));
 423                 }
 424
 425                 bool ret;
 426                 if (i == systemNodes.begin() && m_massAsNodeRadius) {
 427                         ret = MLG.changeNode(NM, sun, sqrt((float)m_mass[sun]) * m_radius[sun], mergeNode);
 428                 } else {
 429                         ret = MLG.changeNode(NM, sun, MLG.radius(sun), mergeNode);
 430                 }
 431                 OGDF_ASSERT( ret );
 432                 MLG.moveEdgesToParent(NM, mergeNode, sun, true, m_adjustEdgeLengths);
 433                 ret = MLG.postMerge(NM, mergeNode);
 434                 if( !ret ) {
 435                         delete NM;
 436                 } else {
 437                         retVal = true;
 438                 }
 439         }
 440
 441         return retVal;
 442 }
 443
 444 } // namespace ogdf