1 /** \file
2 * \brief Splits and packs the components of a Graph
3 *
4 * \author Gereon Bartel
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32
33 #include <ogdf/packing/ComponentSplitterLayout.h>
34 #include <ogdf/packing/TileToRowsCCPacker.h>
35 #include <ogdf/graphalg/ConvexHull.h>
36 //used for splitting
37 #include <ogdf/basic/simple_graph_alg.h>
38 #include <ogdf/basic/GraphCopy.h>
39
40
41 namespace ogdf {
42
ComponentSplitterLayout()43 ComponentSplitterLayout::ComponentSplitterLayout()
44 {
45 m_packer.reset(new TileToRowsCCPacker);
46 m_targetRatio = 1.f;
47 m_border = 30;
48 }
49
50
call(GraphAttributes & GA)51 void ComponentSplitterLayout::call(GraphAttributes &GA)
52 {
53 // Only do preparations and call if layout is valid
54 if (m_secondaryLayout)
55 {
56 //first we split the graph into its components
57 const Graph& G = GA.constGraph();
58
59 NodeArray<int> componentNumber(G);
60 int numberOfComponents = connectedComponents(G, componentNumber);
61 if (numberOfComponents == 0) {
62 return;
63 }
64
65 // intialize the array of lists of nodes contained in a CC
66 Array<List<node> > nodesInCC(numberOfComponents);
67
68 for(node v : G.nodes)
69 nodesInCC[componentNumber[v]].pushBack(v);
70
71 // Create copies of the connected components and corresponding
72 // GraphAttributes
73 GraphCopy GC;
74 GC.createEmpty(G);
75
76 EdgeArray<edge> auxCopy(G);
77
78 for (int i = 0; i < numberOfComponents; i++)
79 {
80 GC.initByNodes(nodesInCC[i],auxCopy);
81 GraphAttributes cGA(GC, GA.attributes());
82 //copy information into copy GA
83 for(node v : GC.nodes)
84 {
85 cGA.width(v) = GA.width(GC.original(v));
86 cGA.height(v) = GA.height(GC.original(v));
87 cGA.x(v) = GA.x(GC.original(v));
88 cGA.y(v) = GA.y(GC.original(v));
89 }
90 // copy information on edges
91 if (GA.has(GraphAttributes::edgeDoubleWeight)) {
92 for (edge e : GC.edges) {
93 cGA.doubleWeight(e) = GA.doubleWeight(GC.original(e));
94 }
95 }
96 m_secondaryLayout->call(cGA);
97
98 //copy layout information back into GA
99 for(node v : GC.nodes)
100 {
101 node w = GC.original(v);
102 if (w != nullptr)
103 {
104 GA.x(w) = cGA.x(v);
105 GA.y(w) = cGA.y(v);
106 if (GA.has(GraphAttributes::threeD)) {
107 GA.z(w) = cGA.z(v);
108 }
109 }
110 }
111 }
112
113 // rotate component drawings and call the packer
114 reassembleDrawings(GA, nodesInCC);
115 }
116 }
117
118 // geometry helpers
119
120 /* copied from multilevelgraph
121 //moves point set average to origin
122 void moveToZero()
123 {
124 // move Graph to zero
125 double avg_x = 0.0;
126 double avg_y = 0.0;
127 for(node v : getGraph().nodes) {
128 avg_x += x(v);
129 avg_y += y(v);
130 }
131 avg_x /= getGraph().numberOfNodes();
132 avg_y /= getGraph().numberOfNodes();
133 for(node v : getGraph().nodes) {
134 x(v, x(v) - avg_x);
135 y(v, y(v) - avg_y);
136 }
137 }
138 */
139
atan2ex(double y,double x)140 double atan2ex(double y, double x)
141 {
142 double angle = atan2(y, x);
143
144 if (x == 0)
145 {
146 if (y >= 0) {
147 angle = 0.5 * Math::pi;
148 } else {
149 angle = 1.5 * Math::pi;
150 }
151 }
152
153 if (y == 0)
154 {
155 if (x >= 0)
156 {
157 angle = 0.0;
158 } else {
159 angle = Math::pi;
160 }
161 }
162
163 return angle;
164 }
165
166 //TODO: Regard some kind of aspect ration (input)
167 //(then also the rotation of a single component makes sense)
reassembleDrawings(GraphAttributes & GA,const Array<List<node>> & nodesInCC)168 void ComponentSplitterLayout::reassembleDrawings(GraphAttributes& GA, const Array<List<node> > &nodesInCC)
169 {
170 int numberOfComponents = nodesInCC.size();
171
172 Array<IPoint> box;
173 Array<IPoint> offset;
174 Array<DPoint> oldOffset;
175 Array<double> rotation;
176 ConvexHull CH;
177
178 // rotate components and create bounding rectangles
179
180 //iterate through all components and compute convex hull
181 for (int j = 0; j < numberOfComponents; j++)
182 {
183 //todo: should not use std::vector, but in order not
184 //to have to change all interfaces, we do it anyway
185 std::vector<DPoint> points;
186
187 //collect node positions and at the same time center average
188 // at origin
189 double avg_x = 0.0;
190 double avg_y = 0.0;
191 for (node v : nodesInCC[j])
192 {
193 DPoint dp(GA.x(v), GA.y(v));
194 avg_x += dp.m_x;
195 avg_y += dp.m_y;
196 points.push_back(dp);
197 }
198 avg_x /= nodesInCC[j].size();
199 avg_y /= nodesInCC[j].size();
200
201 //adapt positions to origin
202 int count = 0;
203 //assume same order of vertices and positions
204 for (node v : nodesInCC[j])
205 {
206 //TODO: I am not sure if we need to update both
207 GA.x(v) = GA.x(v) - avg_x;
208 GA.y(v) = GA.y(v) - avg_y;
209 points.at(count).m_x -= avg_x;
210 points.at(count).m_y -= avg_y;
211
212 count++;
213 }
214
215 // calculate convex hull
216 DPolygon hull = CH.call(points);
217
218 double best_area = std::numeric_limits<double>::max();
219 DPoint best_normal;
220 double best_width = 0.0;
221 double best_height = 0.0;
222
223 // find best rotation by using every face as rectangle border once.
224 for (DPolygon::iterator iter = hull.begin(); iter != hull.end(); ++iter) {
225 DPolygon::iterator k = hull.cyclicSucc(iter);
226
227 double dist = 0.0;
228 DPoint norm = CH.calcNormal(*k, *iter);
229 for (const DPoint &z : hull) {
230 double d = CH.leftOfLine(norm, z, *k);
231 if (d > dist) {
232 dist = d;
233 }
234 }
235
236 double left = 0.0;
237 double right = 0.0;
238 norm = CH.calcNormal(DPoint(0, 0), norm);
239 for (const DPoint &z : hull) {
240 double d = CH.leftOfLine(norm, z, *k);
241 if (d > left) {
242 left = d;
243 }
244 else if (d < right) {
245 right = d;
246 }
247 }
248 double width = left - right;
249
250 Math::updateMax(dist, 1.0);
251 Math::updateMax(width, 1.0);
252
253 double area = dist * width;
254
255 if (area <= best_area) {
256 best_height = dist;
257 best_width = width;
258 best_area = area;
259 best_normal = CH.calcNormal(*k, *iter);
260 }
261 }
262
263 if (hull.size() <= 1) {
264 best_height = 1.0;
265 best_width = 1.0;
266 best_area = 1.0;
267 best_normal = DPoint(1.0, 1.0);
268 }
269
270 double angle = -atan2(best_normal.m_y, best_normal.m_x) + 1.5 * Math::pi;
271 if (best_width < best_height) {
272 angle += 0.5f * Math::pi;
273 double temp = best_height;
274 best_height = best_width;
275 best_width = temp;
276 }
277 rotation.grow(1, angle);
278 double left = hull.front().m_x;
279 double top = hull.front().m_y;
280 double bottom = hull.front().m_y;
281 // apply rotation to hull and calc offset
282 for (DPoint tempP : hull) {
283 double ang = atan2(tempP.m_y, tempP.m_x);
284 double len = sqrt(tempP.m_x*tempP.m_x + tempP.m_y*tempP.m_y);
285 ang += angle;
286 tempP.m_x = cos(ang) * len;
287 tempP.m_y = sin(ang) * len;
288
289 if (tempP.m_x < left) {
290 left = tempP.m_x;
291 }
292 if (tempP.m_y < top) {
293 top = tempP.m_y;
294 }
295 if (tempP.m_y > bottom) {
296 bottom = tempP.m_y;
297 }
298 }
299 oldOffset.grow(1, DPoint(left + 0.5 * static_cast<double>(m_border), -1.0 * best_height + 1.0 * bottom + 0.0 * top + 0.5 * (double)m_border));
300
301 // save rect
302 int w = static_cast<int>(best_width);
303 int h = static_cast<int>(best_height);
304 box.grow(1, IPoint(w + m_border, h + m_border));
305 }
306
307 offset.init(box.size());
308
309 // call packer
310 m_packer->call(box, offset, m_targetRatio);
311
312 int index = 0;
313 // Apply offset and rebuild Graph
314 for (int j = 0; j < numberOfComponents; j++)
315 {
316 double angle = rotation[index];
317 // apply rotation and offset to all nodes
318
319 for (node v : nodesInCC[j])
320 {
321 double x = GA.x(v);
322 double y = GA.y(v);
323 double ang = atan2(y, x);
324 double len = sqrt(x*x + y*y);
325 ang += angle;
326 x = cos(ang) * len;
327 y = sin(ang) * len;
328
329 x += static_cast<double>(offset[index].m_x);
330 y += static_cast<double>(offset[index].m_y);
331
332 x -= oldOffset[index].m_x;
333 y -= oldOffset[index].m_y;
334
335 GA.x(v) = x;
336 GA.y(v) = y;
337 }
338
339 index++;
340 }
341
342 //now we center the whole graph again
343 //TODO: why?
344 #if 0
345 const Graph& G = GA.constGraph();
346 for(node v : G.nodes)
347 MLG.moveToZero();
348 #endif
349 }
350
351 }
352