ext/OGDF/src/energybased/ArrayGraph.h

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class ArrayGraph.
  11  *
  12  * \author Martin Gronemann
  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 #ifndef OGDF_ARRAY_GRAPH_H
  44 #define OGDF_ARRAY_GRAPH_H
  45
  46 #include <ogdf/basic/GraphAttributes.h>
  47
  48 namespace ogdf {
  49
  50 //! struct which keeps information aboout incident edges (16 bytes)
  51 struct NodeAdjInfo
  52 {
  53         __uint32 degree; // total count of pairs where is either the first or second node
  54         __uint32 firstEntry; // the first pair in the edges chain
  55         __uint32 lastEntry;  // the last pair in the edges chain
  56         __uint32 unused; // not used yet
  57 };
  58
  59 //! struct which keeps information about an edge (16 bytes)
  60 struct EdgeAdjInfo
  61 {
  62         __uint32 a;             // first node of the pair
  63         __uint32 b;             // second node of the pair
  64         __uint32 a_next;// next pair in the chain of the first node
  65         __uint32 b_next;// next pair in the chain of the second node
  66 };
  67
  68
  69 class ArrayGraph
  70 {
  71 public:
  72         ArrayGraph();
  73         ArrayGraph(__uint32 maxNumNodes, __uint32 maxNumEdges);
  74         ArrayGraph(const GraphAttributes& GA, const EdgeArray<float>& edgeLength, const NodeArray<float>& nodeSize);
  75         ~ArrayGraph();
  76
  77         //! returns the number of nodes
  78         /**
  79          * \return the number of nodes
  80          */
  81         inline __uint32 numNodes() const { return m_numNodes; }
  82
  83         //! returns the number of nodes
  84         /**
  85          * \return the number of nodes
  86          */
  87         inline __uint32 numEdges() const { return m_numEdges; }
  88
  89         //! updates an array graph from GraphAttributes with the given edge lenghts and node sizes and creates the edges;
  90         /**
  91          * The nodes and edges are ordered in the same way like in the Graph instance.
  92          * @param GA the GraphAttributes to read from
  93          * @param edgeLength the desired edge length
  94          */
  95         void readFrom(const GraphAttributes& GA, const EdgeArray<float>& edgeLength, const NodeArray<float>& nodeSize);
  96
  97         //! updates an array graph with the given positions, edge lenghts and node sizes and creates the edges
  98         /**
  99          * The nodes and edges are ordered in the same way like in the Graph instance.
 100          * @param G the Graph to traverse
 101          * @param xPos the x coordinate for each node
 102          * @param yPos the y coordinate for each node
 103          * @param nodeSize the x coordinate for each node in G
 104          * @param edgeLength the desired edge length for each edge
 105          */
 106         template<typename C_T, typename E_T, typename S_T>
 107         void readFrom(const Graph& G, NodeArray<C_T>& xPos, NodeArray<C_T>& yPos, const EdgeArray<E_T>& edgeLength, const NodeArray<S_T>& nodeSize)
 108         {
 109                 m_numNodes = 0;
 110                 m_numEdges = 0;
 111                 NodeArray<__uint32> nodeIndex(G);
 112                 node v;
 113                 m_numNodes = 0;
 114                 m_numEdges = 0;
 115                 m_desiredAvgEdgeLength = 0;
 116                 m_avgNodeSize = 0;
 117                 forall_nodes(v, G)
 118                 {
 119                         m_nodeXPos[m_numNodes] = (float)xPos[v];
 120                         m_nodeYPos[m_numNodes] = (float)yPos[v];
 121                         m_nodeSize[m_numNodes] = (float)nodeSize[v];
 122                         m_avgNodeSize += nodeSize[v];
 123                         nodeIndex[v] = m_numNodes;
 124                         m_numNodes++;
 125                 }
 126                 m_avgNodeSize = m_avgNodeSize / (double)m_numNodes;
 127
 128                 edge e;
 129                 forall_edges(e, G)
 130                 {
 131                         pushBackEdge(nodeIndex[e->source()], nodeIndex[e->target()], (float)edgeLength[e]);
 132                 }
 133                 m_desiredAvgEdgeLength = m_desiredAvgEdgeLength / (double)m_numEdges;
 134         }
 135
 136         //! writes the data back to GraphAttributes
 137         /**
 138          * The function does not require to be the same Graph, only the order of nodes and edges
 139          * is important
 140          * @param GA the GraphAttributes to update
 141          */
 142         void writeTo(GraphAttributes& GA);
 143
 144         //! writes the data back to node arrays with the given coordinate type
 145         /**
 146          * The function does not require to be the same Graph, only the order of nodes and edges
 147          * is important
 148          * @param xPos the x coordinate array to update
 149          * @param yPos the y coordinate array to update
 150          */
 151         template<typename C_T>
 152         void writeTo(const Graph& G, NodeArray<C_T>& xPos, NodeArray<C_T>& yPos)
 153         {
 154                 node v;
 155                 __uint32 i = 0;
 156                 forall_nodes(v, G)
 157                 {
 158                         xPos[v] = m_nodeXPos[i];
 159                         yPos[v] = m_nodeYPos[i];
 160                         i++;
 161                 }
 162         }
 163
 164         //! returns the adjacency information for a node
 165         inline NodeAdjInfo& nodeInfo(__uint32 i) { return m_nodeAdj[i]; }
 166
 167         //! returns the adjacency information for a node
 168         inline const NodeAdjInfo& nodeInfo(__uint32 i) const { return m_nodeAdj[i];     }
 169
 170         //! returns the adjacency information for an edge
 171         inline EdgeAdjInfo& edgeInfo(__uint32 i) { return m_edgeAdj[i]; }
 172
 173         //! returns the adjacency information for an edge
 174         inline const EdgeAdjInfo& edgeInfo(__uint32 i) const { return m_edgeAdj[i];     }
 175
 176         //! returns the NodeAdjInfo array for all nodes
 177         /**
 178          * The array is 16 byte aligned
 179          */
 180         inline NodeAdjInfo* nodeInfo() { return m_nodeAdj; }
 181
 182         //! returns the NodeAdjInfo array for all nodes
 183         /**
 184          * The array is 16 byte aligned
 185          */
 186         inline const NodeAdjInfo* nodeInfo() const { return m_nodeAdj; }
 187
 188         //! returns the EdgeAdjInfo array for all edges
 189         /**
 190          * The array is 16 byte aligned
 191          */
 192         inline EdgeAdjInfo* edgeInfo() { return m_edgeAdj; }
 193
 194         //! returns the EdgeAdjInfo array for all edges
 195         /**
 196          * The array is 16 byte aligned
 197          */
 198         inline const EdgeAdjInfo* edgeInfo() const { return m_edgeAdj; }
 199
 200         //! returns the x coord array for all nodes
 201         /**
 202          * The array is 16 byte aligned
 203          */
 204         inline float* nodeXPos() { return m_nodeXPos; }
 205
 206         //! returns the x coord array for all nodes
 207         /**
 208          * The array is 16 byte aligned
 209          */
 210         inline const float* nodeXPos() const { return m_nodeXPos; }
 211
 212         //! returns the y coord array for all nodes
 213         /**
 214          * The array is 16 byte aligned
 215          */
 216         inline float* nodeYPos() { return m_nodeYPos; }
 217
 218         //! returns the y coord array for all nodes
 219         /**
 220          * The array is 16 byte aligned
 221          */
 222         inline const float* nodeYPos() const { return m_nodeYPos; }
 223
 224         //! returns the node size array for all nodes
 225         /**
 226          * The array is 16 byte aligned
 227          */
 228         inline float* nodeSize() { return m_nodeSize; }
 229
 230
 231         //! returns the node movement radius array for all nodes
 232         /**
 233          * The array is 16 byte aligned
 234          */
 235         inline float* nodeMoveRadius() { return m_nodeMoveRadius; }
 236
 237         //! returns the node size array for all nodes
 238         /**
 239          * The array is 16 byte aligned
 240          */
 241         inline const float* nodeSize() const { return m_nodeSize; }
 242
 243         //! returns the edge length array for all edges
 244         /**
 245          * The array is 16 byte aligned
 246          */
 247         inline float* desiredEdgeLength() { return m_desiredEdgeLength; }
 248
 249         //! returns the edge length array for all edges
 250         /**
 251          * The array is 16 byte aligned
 252          */
 253         inline const float* desiredEdgeLength() const { return m_desiredEdgeLength; }
 254
 255         //! returns the index of the first pair of node node
 256         inline __uint32 firstEdgeAdjIndex(__uint32 nodeIndex) const
 257         {
 258                 return nodeInfo(nodeIndex).firstEntry;
 259         };
 260
 261         //! returns the index of the next pair of curr for node a
 262         inline __uint32 nextEdgeAdjIndex(__uint32 currEdgeAdjIndex, __uint32 nodeIndex) const
 263         {
 264                 const EdgeAdjInfo& currInfo = edgeInfo(currEdgeAdjIndex);
 265                 if (currInfo.a == nodeIndex)
 266                         return currInfo.a_next;
 267                 return currInfo.b_next;
 268         }
 269
 270         //! returns the other node a is paired with in pair with the given index
 271         inline __uint32 twinNodeIndex(__uint32 currEdgeAdjIndex, __uint32 nodeIndex) const
 272         {
 273                 const EdgeAdjInfo& currInfo = edgeInfo(currEdgeAdjIndex);
 274                 if (currInfo.a == nodeIndex)
 275                         return currInfo.b;
 276                 return currInfo.a;
 277         }
 278
 279         template<typename Func>
 280         void for_all_nodes(__uint32 begin, __uint32 end, Func func)
 281         {
 282                 for(__uint32 i=begin; i <=end; i++)
 283                         func(i);
 284         }
 285
 286
 287         inline float avgDesiredEdgeLength() const { return (float)m_desiredAvgEdgeLength; }
 288
 289         inline float avgNodeSize() const { return (float)m_avgNodeSize; }
 290
 291         void transform(float translate, float scale);
 292         void centerGraph();
 293
 294 private:
 295
 296         //! internal function used by readFrom
 297         void pushBackEdge(__uint32 a, __uint32 b, float desiredEdgeLength);
 298
 299         //! internal function used allocate all arrays
 300         void allocate(__uint32 numNodes, __uint32 numEdges);
 301
 302         //! internal function used allocate all arrays
 303         void deallocate();
 304
 305         //! internal function used to clear the arrays
 306         void clear()
 307         {
 308                 for (__uint32 i=0; i < m_numNodes; i++)
 309                         nodeInfo(i).degree = 0;
 310
 311                 m_numNodes = 0;
 312                 m_numEdges = 0;
 313         }
 314
 315         //! number of nodes in the graph
 316         __uint32 m_numNodes;
 317
 318         //! number of edges in the graph
 319         __uint32 m_numEdges;
 320
 321         //! x coordinates
 322         float* m_nodeXPos;
 323
 324         //! x coordinates
 325         float* m_nodeYPos;
 326
 327         //! size of the node
 328         float* m_nodeSize;
 329
 330         //! avg node size
 331         double  m_avgNodeSize;
 332
 333         //! maximum node movement length
 334         float* m_nodeMoveRadius;
 335
 336         //! edge length
 337         float* m_desiredEdgeLength;
 338
 339         double m_currentAvgEdgeLength;
 340
 341         //! avg edge length
 342         double m_desiredAvgEdgeLength;
 343
 344         //! information about adjacent edges
 345         NodeAdjInfo* m_nodeAdj;
 346
 347         //! information about adjacent nodes
 348         EdgeAdjInfo* m_edgeAdj;
 349 };
 350
 351 } // end of namespace ogdf
 352
 353 #endif
 354