ext/OGDF/src/energybased/Planarity.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 Planarity
  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 #include <ogdf/internal/energybased/Planarity.h>
  44
  45 namespace ogdf {
  46
  47         Planarity::~Planarity()
  48         {
  49                 delete m_edgeNums;
  50                 delete m_crossingMatrix;
  51         }
  52
  53
  54         // intializes number of edges and allocates memory for  crossingMatrix
  55         Planarity::Planarity(GraphAttributes &AG):
  56         EnergyFunction("Planarity",AG)
  57         {
  58                 m_edgeNums = OGDF_NEW EdgeArray<int>(m_G,0);
  59                 m_G.allEdges(m_nonSelfLoops);
  60                 ListIterator<edge> it, itSucc;
  61                 for(it = m_nonSelfLoops.begin(); it.valid(); it = itSucc) {
  62                         itSucc = it.succ();
  63                         if((*it)->isSelfLoop()) m_nonSelfLoops.del(it);
  64                 }
  65                 int e_num = 1;
  66                 for(it = m_nonSelfLoops.begin(); it.valid(); ++it) (*m_edgeNums)[*it] = e_num ++;
  67                 e_num --;
  68                 m_crossingMatrix = new Array2D<bool> (1,e_num,1,e_num);
  69         }
  70
  71
  72         // computes energy of layout, stores it and sets the crossingMatrix
  73         void Planarity::computeEnergy()
  74         {
  75                 int e_num = m_nonSelfLoops.size();
  76                 int energySum = 0;
  77                 Array<edge> numEdge(1,e_num);
  78                 edge e;
  79                 ListIterator<edge> it;
  80
  81                 for(it = m_nonSelfLoops.begin(); it.valid(); ++it)
  82                         numEdge[(*m_edgeNums)[*it]] = *it;
  83                 for(int i = 1; i < e_num; i++) {
  84                         e = numEdge[i];
  85                         for(int j = i+1; j <= e_num ; j++) {
  86                                 bool cross = intersect(e,numEdge[j]);
  87                                 (*m_crossingMatrix)(i,j) = cross;
  88                                 if(cross) energySum += 1;
  89                         }
  90                 }
  91                 m_energy = energySum;
  92         }
  93
  94
  95         // tests if two edges cross
  96         bool Planarity::intersect(const edge e1, const edge e2) const
  97         {
  98                 node v1s = e1->source();
  99                 node v1t = e1->target();
 100                 node v2s = e2->source();
 101                 node v2t = e2->target();
 102
 103                 bool cross = false;
 104                 if(v1s != v2s && v1s != v2t && v1t != v2s && v1t != v2t)
 105                         cross = lowLevelIntersect(currentPos(v1s),currentPos(v1t), currentPos(v2s),currentPos(v2t));
 106                 return cross;
 107         }
 108
 109
 110         // tests if two lines given by four points cross
 111         bool Planarity::lowLevelIntersect(
 112                 const DPoint &e1s,
 113                 const DPoint &e1t,
 114                 const DPoint &e2s,
 115                 const DPoint &e2t) const
 116         {
 117                 DPoint s1(e1s),t1(e1t),s2(e2s),t2(e2t);
 118                 DLine l1(s1,t1), l2(s2,t2);
 119                 DPoint dummy;
 120                 return l1.intersection(l2,dummy);
 121         }
 122
 123
 124         // computes the energy if the node returned by testNode() is moved
 125         // to position testPos().
 126         void Planarity::compCandEnergy()
 127         {
 128                 node v = testNode();
 129                 m_candidateEnergy = energy();
 130                 edge e;
 131                 m_crossingChanges.clear();
 132
 133                 forall_adj_edges(e,v) if(!e->isSelfLoop()) {
 134                         // first we compute the two endpoints of e if v is on its new position
 135                         node s = e->source();
 136                         node t = e->target();
 137                         DPoint p1 = testPos();
 138                         DPoint p2 = (s==v)? currentPos(t) : currentPos(s);
 139                         int e_num = (*m_edgeNums)[e];
 140                         edge f;
 141                         // now we compute the crossings of all other edges with e
 142                         ListIterator<edge> it;
 143                         for(it = m_nonSelfLoops.begin(); it.valid(); ++it) if(*it != e) {
 144                                 f = *it;
 145                                 node s2 = f->source();
 146                                 node t2 = f->target();
 147                                 if(s2 != s && s2 != t && t2 != s && t2 != t) {
 148                                         bool cross = lowLevelIntersect(p1,p2,currentPos(s2),currentPos(t2));
 149                                         int f_num = (*m_edgeNums)[f];
 150                                         bool priorIntersect = (*m_crossingMatrix)(min(e_num,f_num),max(e_num,f_num));
 151                                         if(priorIntersect != cross) {
 152                                                 if(priorIntersect) m_candidateEnergy --; // this intersection was saved
 153                                                 else m_candidateEnergy ++; // produced a new intersection
 154                                                 ChangedCrossing cc;
 155                                                 cc.edgeNum1 = min(e_num,f_num);
 156                                                 cc.edgeNum2 = max(e_num,f_num);
 157                                                 cc.cross = cross;
 158                                                 m_crossingChanges.pushBack(cc);
 159                                         }
 160                                 }
 161                         }
 162                 }
 163         }
 164
 165
 166         // this functions sets the crossingMatrix according to candidateCrossings
 167         void Planarity::internalCandidateTaken() {
 168                 ListIterator<ChangedCrossing> it;
 169                 for(it = m_crossingChanges.begin(); it.valid(); ++ it) {
 170                         ChangedCrossing cc = *(it);
 171                         (*m_crossingMatrix)(cc.edgeNum1,cc.edgeNum2) = cc.cross;
 172                 }
 173         }
 174
 175
 176 #ifdef OGDF_DEBUG
 177 void Planarity::printInternalData() const {
 178         cout << "\nCrossing Matrix:";
 179         int e_num = m_nonSelfLoops.size();
 180         for(int i = 1; i < e_num; i++) {
 181                 cout << "\n Edge " << i << " crosses: ";
 182                 for(int j = i+1; j <= e_num; j++)
 183                         if((*m_crossingMatrix)(i,j)) cout << j << " ";
 184         }
 185         cout << "\nChanged crossings:";
 186         if(testNode() == NULL) cout << " None.";
 187         else {
 188                 ListConstIterator<ChangedCrossing> it;
 189                 for(it = m_crossingChanges.begin(); it.valid(); ++it) {
 190                         ChangedCrossing cc = *(it);
 191                         cout << " (" << cc.edgeNum1 << "," << cc.edgeNum2 << ")" << cc.cross;
 192                 }
 193         }
 194 }
 195 #endif
 196
 197 }