ext/OGDF/src/planarlayout/IOPoints.h

   1 /*
   2  * $Revision: 2571 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-10 17:25:20 +0200 (Di, 10. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of classes InOutPoint and IOPoints which
  11  * implement the management of in-/out-points
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_IO_POINTS_H
  49 #define OGDF_IO_POINTS_H
  50
  51
  52 #include <ogdf/planarity/PlanRep.h>
  53
  54
  55 namespace ogdf {
  56
  57
  58 /********************************************************************
  59                         representation of an in- or outpoint
  60 ********************************************************************/
  61
  62 struct InOutPoint
  63 {
  64         int  m_dx, m_dy;
  65         adjEntry m_adj;
  66
  67         InOutPoint() {
  68                 m_dx = m_dy = 0; m_adj = 0;
  69         }
  70         InOutPoint(adjEntry adj) {
  71                 m_adj = adj; m_dx = m_dy = 0;
  72         }
  73 };
  74
  75
  76 /********************************************************************
  77                         representation of in- and outpoint lists
  78 ********************************************************************/
  79
  80 class IOPoints {
  81 public:
  82         IOPoints() { }
  83         IOPoints(const Graph &G) : m_depth(G,0), m_height(G,0), m_in(G), m_out(G),
  84                 m_mark(G,false), m_pointOf(G,0)  { }
  85
  86         ~IOPoints () { }
  87
  88
  89         // length of in- or outpoint list
  90         int out(node v) const {
  91                 return m_out[v].size();
  92         }
  93         int in(node v) const {
  94                 return m_in[v].size();
  95         }
  96
  97         // getting a const-reference to in- or outpoint list
  98         const List<InOutPoint> &inpoints(node v) const {
  99                 return m_in [v];
 100         }
 101         List<InOutPoint> &inpoints(node v) {
 102                 return m_in [v];
 103         }
 104
 105         const List<InOutPoint> &outpoints(node v) const {
 106                 return m_out [v];
 107         }
 108         List<InOutPoint> &outpoints(node v) {
 109                 return m_out [v];
 110         }
 111
 112         // getting the in-/outpoint belonging to an adjacency entry
 113         const InOutPoint *pointOf(adjEntry adj) const {
 114                 return m_pointOf[adj];
 115         }
 116
 117         // marking adjacency entries
 118         bool marked(adjEntry adj) const {
 119                 return m_mark[adj];
 120         }
 121
 122         bool marked(node v) {
 123                 return (v->outdeg() == 1 && marked(v->firstAdj()));
 124         }
 125
 126         // finding outpoints belonging to non-marked edges
 127         ListConstIterator<InOutPoint> firstRealOut(node v) const {
 128                 return searchRealForward(m_out[v].begin());
 129         }
 130
 131         ListConstIterator<InOutPoint> lastRealOut(node v) const {
 132                 return searchRealBackward(m_out[v].rbegin());
 133         }
 134
 135         ListConstIterator<InOutPoint> nextRealOut(ListConstIterator<InOutPoint> it) const {
 136                 return searchRealForward(it.succ());
 137         }
 138
 139         ListConstIterator<InOutPoint> prevRealOut(ListConstIterator<InOutPoint> it) const {
 140                 return searchRealBackward(it.pred());
 141         }
 142
 143         // building in-/outpoint lists
 144         void appendInpoint(adjEntry adj) {
 145                 node v = adj->theNode();
 146                 m_pointOf[adj] = &(*m_in[v].pushBack(InOutPoint(adj)));
 147         }
 148         void appendOutpoint(adjEntry adj) {
 149                 node v = adj->theNode();
 150                 m_pointOf[adj] = &(*m_out[v].pushBack(InOutPoint(adj)));
 151         }
 152         void pushInpoint(adjEntry adj) {
 153                 node v = adj->theNode();
 154                 m_pointOf[adj] = &(*m_in[v].pushFront(InOutPoint(adj)));
 155         }
 156
 157         // setting relative coordinates
 158         void setOutCoord (ListIterator<InOutPoint> it, int dx, int dy) {
 159                 (*it).m_dx = dx;
 160                 (*it).m_dy = dy;
 161         }
 162         void setInCoord (ListIterator<InOutPoint> it, int dx, int dy) {
 163                 (*it).m_dx = dx;
 164                 (*it).m_dy = dy;
 165         }
 166
 167         void setOutDx(ListIterator<InOutPoint> it, int dx) {
 168                 (*it).m_dx = dx;
 169         }
 170
 171         void restoreDeg1Nodes(PlanRep &PG, Stack<PlanRep::Deg1RestoreInfo> &S);
 172
 173         void changeEdge(node v, adjEntry adj_new) {
 174                 m_out[v].popBack();
 175                 appendInpoint(adj_new);
 176         }
 177
 178         // belongs v to a chain (= at most to non-marked incoming edges
 179         bool isChain(node v) const {
 180                 int i = 0;
 181                 ListConstIterator<InOutPoint> it;
 182                 for(it = m_in[v].begin(); it.valid(); ++it)
 183                         if (!marked((*it).m_adj)) ++i;
 184                 return (i <= 2);
 185         }
 186
 187         // width of the left-/right side of an in-/outpoint list
 188         int outLeft(node v) const {
 189                 return (m_out[v].empty()) ? 0 : (-m_out[v].front().m_dx);
 190         }
 191
 192         int outRight(node v) const {
 193                 return (m_out[v].empty()) ? 0 : (m_out[v].back().m_dx);
 194         }
 195
 196         int inLeft(node v) const {
 197                 return (m_in[v].empty()) ? 0 : (-m_in[v].front().m_dx);
 198         }
 199
 200         int inRight(node v) const {
 201                 return (m_in[v].empty()) ? 0 : (m_in[v].back().m_dx);
 202         }
 203
 204         int maxLeft(node v) const {
 205                 return max(inLeft(v), outLeft(v));
 206         }
 207
 208         int maxRight(node v) const {
 209                 return max(inRight(v), outRight(v));
 210         }
 211
 212         int maxPlusLeft(node v) const {
 213                 return (in(v) >= 3) ?
 214                         max(inLeft(v)+1, outLeft(v)) : maxLeft(v);
 215         }
 216
 217         int maxPlusRight(node v) const {
 218                 return (in(v) >= 3) ?
 219                         max(inRight(v)+1, outRight(v)) : maxRight(v);
 220         }
 221
 222         InOutPoint middleNeighbor(node z1) const;
 223
 224         void numDeg1(node v, int &xl, int &xr,
 225                 bool doubleCount) const;
 226
 227         adjEntry switchBeginIn(node v);
 228         adjEntry switchEndIn  (node v);
 229
 230         void switchBeginOut(node v);
 231         void switchEndOut  (node v);
 232
 233
 234         NodeArray<int> m_depth, m_height;
 235
 236
 237 private:
 238         NodeArray<List<InOutPoint> > m_in, m_out;
 239         AdjEntryArray<bool> m_mark;
 240         AdjEntryArray<InOutPoint *> m_pointOf;
 241
 242         ListConstIterator<InOutPoint> searchRealForward (ListConstIterator<InOutPoint> it) const;
 243         ListConstIterator<InOutPoint> searchRealBackward(ListConstIterator<InOutPoint> it) const;
 244 };
 245
 246
 247
 248 } // end namespace ogdf
 249
 250
 251 #endif