ext/OGDF/src/energybased/NodePairEnergy.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 class NodePairEnergy
  11  *
  12  * \author Rene Weiskircher
  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/energybased/NodePairEnergy.h>
  45
  46
  47 #ifdef OGDF_SYSTEM_UNIX
  48 #include <climits>
  49 #endif
  50
  51 #ifdef OGDF_SYSTEM_WINDOWS
  52 #include <limits>
  53 #endif
  54
  55 using namespace std;
  56
  57 namespace ogdf {
  58
  59
  60 NodePairEnergy::NodePairEnergy(const String energyname, GraphAttributes &AG) :
  61         EnergyFunction(energyname,AG),
  62         m_candPairEnergy(m_G),
  63         m_shape(m_G),
  64         m_adjacentOracle(m_G)
  65 {
  66         node v;
  67         double lengthSum = 0;
  68         forall_nodes(v,m_G) { //saving the shapes of the nodes in m_shape
  69                 DPoint center(AG.x(v),AG.y(v));
  70                 lengthSum += AG.width(v);
  71                 lengthSum += AG.height(v);
  72                 m_shape[v] = IntersectionRectangle(center,AG.width(v),AG.height(v));
  73         }
  74         m_G.allNodes(m_nonIsolated);
  75         ListIterator<node> it, itSucc;
  76         for(it = m_nonIsolated.begin(); it.valid(); it = itSucc) {
  77                 itSucc = it.succ();
  78                 if((*it)->degree() == 0) m_nonIsolated.del(it);
  79         }
  80         m_nodeNums = OGDF_NEW NodeArray<int>(m_G,0);
  81         int n_num = 1;
  82         for(it = m_nonIsolated.begin(); it.valid(); ++it) {
  83                 (*m_nodeNums)[*it] = n_num;
  84                 n_num++;
  85         }
  86         n_num--;
  87         m_pairEnergy = new Array2D<double> (1,n_num,1,n_num);
  88 }
  89
  90
  91 void NodePairEnergy::computeEnergy()
  92 {
  93         int n_num = m_nonIsolated.size();
  94         double energySum = 0.0;
  95         Array<node> numNodes(1,n_num);
  96
  97         ListIterator<node> it;
  98         for(it = m_nonIsolated.begin(); it.valid(); ++it) {
  99                 numNodes[(*m_nodeNums)[*it]] = *it;
 100         }
 101         for(int i = 1; i <= n_num-1 ; i++) {
 102                 for(int j = i+1; j <= n_num; j++) {
 103                         double E = computePairEnergy(numNodes[i],numNodes[j]);
 104                         (*m_pairEnergy)(i,j) = E;
 105                         energySum += E;
 106                 }
 107         }
 108         m_energy = energySum;
 109 }
 110
 111
 112 double NodePairEnergy::computePairEnergy(const node v, const node w) const {
 113         return computeCoordEnergy(v,w,currentPos(v),currentPos(w));
 114 }
 115
 116
 117 void NodePairEnergy::internalCandidateTaken() {
 118         node v = testNode();
 119         int candNum = (*m_nodeNums)[v];
 120         ListIterator<node> it;
 121         for(it = m_nonIsolated.begin(); it.valid(); ++ it) {
 122                 if((*it) != v) {
 123                         int numit = (*m_nodeNums)[*it];
 124                         (*m_pairEnergy)(min(numit,candNum),max(numit,candNum)) = m_candPairEnergy[*it];
 125                         m_candPairEnergy[*it] = 0.0;
 126                 }
 127         }
 128 }
 129
 130
 131 void NodePairEnergy::compCandEnergy()
 132 {
 133         node v = testNode();
 134         int numv = (*m_nodeNums)[v];
 135         m_candidateEnergy = energy();
 136         ListIterator<node> it;
 137         for(it = m_nonIsolated.begin(); it.valid(); ++ it) {
 138                 if(*it != v) {
 139                         int j = (*m_nodeNums)[*it];
 140                         m_candidateEnergy -= (*m_pairEnergy)(min(j,numv),max(j,numv));
 141                         m_candPairEnergy[*it] = computeCoordEnergy(v,*it,testPos(),currentPos(*it));
 142                         m_candidateEnergy += m_candPairEnergy[*it];
 143                         if(m_candidateEnergy < 0.0) {
 144                                 OGDF_ASSERT(m_candidateEnergy > -0.00001);
 145                                 m_candidateEnergy = 0.0;
 146                         }
 147                 }
 148                 else m_candPairEnergy[*it] = 0.0;
 149         }
 150         OGDF_ASSERT(m_candidateEnergy >= -0.0001);
 151 }
 152
 153
 154 #ifdef OGDF_DEBUG
 155 void NodePairEnergy::printInternalData() const {
 156         ListConstIterator<node> it;
 157         for(it = m_nonIsolated.begin(); it.valid(); ++it) {
 158                 cout << "\nNode: " << (*m_nodeNums)[*it];
 159                 cout << " CandidatePairEnergy: " << m_candPairEnergy[*it];
 160         }
 161         cout << "\nPair energies:";
 162         for(int i=1; i< m_nonIsolated.size(); i++)
 163                 for(int j=i+1; j <= m_nonIsolated.size(); j++)
 164                         if((*m_pairEnergy)(i,j) != 0.0)
 165                                 cout << "\nEnergy(" << i << ',' << j << ") = " << (*m_pairEnergy)(i,j);
 166 }
 167 #endif
 168
 169 } //namespace ogdf