6 * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class ArrayGraph.
12 * \author Martin Gronemann
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
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
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.
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.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
43 #ifndef OGDF_ARRAY_GRAPH_H
44 #define OGDF_ARRAY_GRAPH_H
46 #include <ogdf/basic/GraphAttributes.h>
50 //! struct which keeps information aboout incident edges (16 bytes)
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
59 //! struct which keeps information about an edge (16 bytes)
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
73 ArrayGraph(__uint32 maxNumNodes
, __uint32 maxNumEdges
);
74 ArrayGraph(const GraphAttributes
& GA
, const EdgeArray
<float>& edgeLength
, const NodeArray
<float>& nodeSize
);
77 //! returns the number of nodes
79 * \return the number of nodes
81 inline __uint32
numNodes() const { return m_numNodes
; }
83 //! returns the number of nodes
85 * \return the number of nodes
87 inline __uint32
numEdges() const { return m_numEdges
; }
89 //! updates an array graph from GraphAttributes with the given edge lenghts and node sizes and creates the edges;
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
95 void readFrom(const GraphAttributes
& GA
, const EdgeArray
<float>& edgeLength
, const NodeArray
<float>& nodeSize
);
97 //! updates an array graph with the given positions, edge lenghts and node sizes and creates the edges
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
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
)
111 NodeArray
<__uint32
> nodeIndex(G
);
115 m_desiredAvgEdgeLength
= 0;
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
;
126 m_avgNodeSize
= m_avgNodeSize
/ (double)m_numNodes
;
131 pushBackEdge(nodeIndex
[e
->source()], nodeIndex
[e
->target()], (float)edgeLength
[e
]);
133 m_desiredAvgEdgeLength
= m_desiredAvgEdgeLength
/ (double)m_numEdges
;
136 //! writes the data back to GraphAttributes
138 * The function does not require to be the same Graph, only the order of nodes and edges
140 * @param GA the GraphAttributes to update
142 void writeTo(GraphAttributes
& GA
);
144 //! writes the data back to node arrays with the given coordinate type
146 * The function does not require to be the same Graph, only the order of nodes and edges
148 * @param xPos the x coordinate array to update
149 * @param yPos the y coordinate array to update
151 template<typename C_T
>
152 void writeTo(const Graph
& G
, NodeArray
<C_T
>& xPos
, NodeArray
<C_T
>& yPos
)
158 xPos
[v
] = m_nodeXPos
[i
];
159 yPos
[v
] = m_nodeYPos
[i
];
164 //! returns the adjacency information for a node
165 inline NodeAdjInfo
& nodeInfo(__uint32 i
) { return m_nodeAdj
[i
]; }
167 //! returns the adjacency information for a node
168 inline const NodeAdjInfo
& nodeInfo(__uint32 i
) const { return m_nodeAdj
[i
]; }
170 //! returns the adjacency information for an edge
171 inline EdgeAdjInfo
& edgeInfo(__uint32 i
) { return m_edgeAdj
[i
]; }
173 //! returns the adjacency information for an edge
174 inline const EdgeAdjInfo
& edgeInfo(__uint32 i
) const { return m_edgeAdj
[i
]; }
176 //! returns the NodeAdjInfo array for all nodes
178 * The array is 16 byte aligned
180 inline NodeAdjInfo
* nodeInfo() { return m_nodeAdj
; }
182 //! returns the NodeAdjInfo array for all nodes
184 * The array is 16 byte aligned
186 inline const NodeAdjInfo
* nodeInfo() const { return m_nodeAdj
; }
188 //! returns the EdgeAdjInfo array for all edges
190 * The array is 16 byte aligned
192 inline EdgeAdjInfo
* edgeInfo() { return m_edgeAdj
; }
194 //! returns the EdgeAdjInfo array for all edges
196 * The array is 16 byte aligned
198 inline const EdgeAdjInfo
* edgeInfo() const { return m_edgeAdj
; }
200 //! returns the x coord array for all nodes
202 * The array is 16 byte aligned
204 inline float* nodeXPos() { return m_nodeXPos
; }
206 //! returns the x coord array for all nodes
208 * The array is 16 byte aligned
210 inline const float* nodeXPos() const { return m_nodeXPos
; }
212 //! returns the y coord array for all nodes
214 * The array is 16 byte aligned
216 inline float* nodeYPos() { return m_nodeYPos
; }
218 //! returns the y coord array for all nodes
220 * The array is 16 byte aligned
222 inline const float* nodeYPos() const { return m_nodeYPos
; }
224 //! returns the node size array for all nodes
226 * The array is 16 byte aligned
228 inline float* nodeSize() { return m_nodeSize
; }
231 //! returns the node movement radius array for all nodes
233 * The array is 16 byte aligned
235 inline float* nodeMoveRadius() { return m_nodeMoveRadius
; }
237 //! returns the node size array for all nodes
239 * The array is 16 byte aligned
241 inline const float* nodeSize() const { return m_nodeSize
; }
243 //! returns the edge length array for all edges
245 * The array is 16 byte aligned
247 inline float* desiredEdgeLength() { return m_desiredEdgeLength
; }
249 //! returns the edge length array for all edges
251 * The array is 16 byte aligned
253 inline const float* desiredEdgeLength() const { return m_desiredEdgeLength
; }
255 //! returns the index of the first pair of node node
256 inline __uint32
firstEdgeAdjIndex(__uint32 nodeIndex
) const
258 return nodeInfo(nodeIndex
).firstEntry
;
261 //! returns the index of the next pair of curr for node a
262 inline __uint32
nextEdgeAdjIndex(__uint32 currEdgeAdjIndex
, __uint32 nodeIndex
) const
264 const EdgeAdjInfo
& currInfo
= edgeInfo(currEdgeAdjIndex
);
265 if (currInfo
.a
== nodeIndex
)
266 return currInfo
.a_next
;
267 return currInfo
.b_next
;
270 //! returns the other node a is paired with in pair with the given index
271 inline __uint32
twinNodeIndex(__uint32 currEdgeAdjIndex
, __uint32 nodeIndex
) const
273 const EdgeAdjInfo
& currInfo
= edgeInfo(currEdgeAdjIndex
);
274 if (currInfo
.a
== nodeIndex
)
279 template<typename Func
>
280 void for_all_nodes(__uint32 begin
, __uint32 end
, Func func
)
282 for(__uint32 i
=begin
; i
<=end
; i
++)
287 inline float avgDesiredEdgeLength() const { return (float)m_desiredAvgEdgeLength
; }
289 inline float avgNodeSize() const { return (float)m_avgNodeSize
; }
291 void transform(float translate
, float scale
);
296 //! internal function used by readFrom
297 void pushBackEdge(__uint32 a
, __uint32 b
, float desiredEdgeLength
);
299 //! internal function used allocate all arrays
300 void allocate(__uint32 numNodes
, __uint32 numEdges
);
302 //! internal function used allocate all arrays
305 //! internal function used to clear the arrays
308 for (__uint32 i
=0; i
< m_numNodes
; i
++)
309 nodeInfo(i
).degree
= 0;
315 //! number of nodes in the graph
318 //! number of edges in the graph
331 double m_avgNodeSize
;
333 //! maximum node movement length
334 float* m_nodeMoveRadius
;
337 float* m_desiredEdgeLength
;
339 double m_currentAvgEdgeLength
;
342 double m_desiredAvgEdgeLength
;
344 //! information about adjacent edges
345 NodeAdjInfo
* m_nodeAdj
;
347 //! information about adjacent nodes
348 EdgeAdjInfo
* m_edgeAdj
;
351 } // end of namespace ogdf