ext/OGDF/src/energybased/multilevelmixer/ModularMultilevelMixer.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 MMM is a Multilevel Graph drawing Algorithm that can use different modules.
  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
  44
  45 #include <ogdf/basic/basic.h>
  46 #include <ogdf/energybased/multilevelmixer/ModularMultilevelMixer.h>
  47 #include <ogdf/energybased/multilevelmixer/SolarMerger.h>
  48 #include <ogdf/energybased/multilevelmixer/BarycenterPlacer.h>
  49 #include <ogdf/energybased/FastMultipoleEmbedder.h>
  50 #include <ogdf/energybased/SpringEmbedderFR.h>
  51 #include <time.h>
  52
  53 #ifdef OGDF_MMM_LEVEL_OUTPUTS
  54 #include <sstream>
  55 #include <string>
  56 #endif
  57
  58
  59 namespace ogdf {
  60
  61 ModularMultilevelMixer::ModularMultilevelMixer()
  62 {
  63         // options
  64         m_times              = 1;
  65         m_fixedEdgeLength    = -1.0f;
  66         m_fixedNodeSize      = -1.0f;
  67         m_coarseningRatio    = 1.0;
  68         m_levelBound         = false;
  69         m_randomize          = false;
  70
  71         // module options
  72         setMultilevelBuilder(new SolarMerger);
  73         setInitialPlacer    (new BarycenterPlacer);
  74         setLevelLayoutModule(new SpringEmbedderFR);
  75 }
  76
  77
  78 void ModularMultilevelMixer::call(GraphAttributes &GA)
  79 {   //ensure consistent behaviour of the two call Methods
  80         MultilevelGraph MLG(GA);
  81         call(MLG);
  82         MLG.exportAttributes(GA);
  83 }
  84
  85
  86 void ModularMultilevelMixer::call(MultilevelGraph &MLG)
  87 {
  88         const Graph &G = MLG.getGraph();
  89
  90         m_errorCode = ercNone;
  91         clock_t time = clock();
  92         if ((m_multilevelBuilder.valid() == false || m_initialPlacement.valid() == false) && m_oneLevelLayoutModule.valid() == false) {
  93                 OGDF_THROW(AlgorithmFailureException);
  94         }
  95
  96         if (m_fixedEdgeLength > 0.0) {
  97                 edge e;
  98                 forall_edges(e,G) {
  99                         MLG.weight(e, m_fixedEdgeLength);
 100                 }
 101         }
 102
 103         if (m_fixedNodeSize > 0.0) {
 104                 node v;
 105                 forall_nodes(v,G) {
 106                         MLG.radius(v, m_fixedNodeSize);
 107                 }
 108         }
 109
 110         if (m_multilevelBuilder.valid() && m_initialPlacement.valid())
 111         {
 112                 double lbound = 16.0 * log(double(G.numberOfNodes()))/log(2.0);
 113                 m_multilevelBuilder.get().buildAllLevels(MLG);
 114
 115                 //Part for experiments: Stop if number of levels too high
 116 #ifdef OGDF_MMM_LEVEL_OUTPUTS
 117                 int nlevels = m_multilevelBuilder.get().getNumLevels();
 118 #endif
 119                 if (m_levelBound)
 120                 {
 121                         if ( m_multilevelBuilder.get().getNumLevels() > lbound)
 122                         {
 123                                 m_errorCode = ercLevelBound;
 124                                 return;
 125                         }
 126                 }
 127                 node v;
 128                 if (m_randomize)
 129                 {
 130                         forall_nodes(v,G) {
 131                                 MLG.x(v, (float)randomDouble(-1.0, 1.0));
 132                                 MLG.y(v, (float)randomDouble(-1.0, 1.0));
 133                         }
 134                 }
 135
 136                 while(MLG.getLevel() > 0)
 137                 {
 138                         if (m_oneLevelLayoutModule.valid()) {
 139                                 for(int i = 1; i <= m_times; i++) {
 140                                         m_oneLevelLayoutModule.get().call(MLG.getGraphAttributes());
 141                                 }
 142                         }
 143
 144 #ifdef OGDF_MMM_LEVEL_OUTPUTS
 145                         //Debugging output
 146                         std::stringstream ss;
 147                         ss << nlevels--;
 148                         std::string s;
 149                         ss >> s;
 150                         s = "LevelLayout"+s;
 151                         String fs(s.c_str());
 152                         fs += ".gml";
 153                         MLG.writeGML(fs);
 154 #endif
 155
 156                         MLG.moveToZero();
 157
 158                         int nNodes = G.numberOfNodes();
 159                         m_initialPlacement.get().placeOneLevel(MLG);
 160                         m_coarseningRatio = float(G.numberOfNodes()) / nNodes;
 161
 162 #ifdef OGDF_MMM_LEVEL_OUTPUTS
 163                         //debug only
 164                         s = s+"_placed.gml";
 165                         MLG.writeGML(String(s.c_str()));
 166 #endif
 167                 } //while level
 168         }
 169
 170         //Final level
 171
 172         if(m_finalLayoutModule.valid() ||  m_oneLevelLayoutModule.valid())
 173         {
 174                 LayoutModule &lastLayoutModule = (m_finalLayoutModule.valid() != 0 ? m_finalLayoutModule.get() : m_oneLevelLayoutModule.get());
 175
 176                 for(int i = 1; i <= m_times; i++) {
 177                         lastLayoutModule.call(MLG.getGraphAttributes());
 178                 }
 179         }
 180
 181         time = clock() - time;
 182 }
 183
 184
 185 } // namespace ogdf