1 /** \file
2 * \brief Implementation of class FruchtermanReingold (computation of forces).
3 *
4 * \author Stefan Hachul
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 #include <ogdf/energybased/fmmm/FruchtermanReingold.h>
33 #include <ogdf/energybased/fmmm/common.h>
34 #include <ogdf/basic/Array2D.h>
35
36 namespace ogdf {
37 namespace energybased {
38 namespace fmmm {
39
FruchtermanReingold()40 FruchtermanReingold::FruchtermanReingold()
41 {
42 grid_quotient(2);
43 }
44
45
calculate_exact_repulsive_forces(const Graph & G,NodeArray<NodeAttributes> & A,NodeArray<DPoint> & F_rep)46 void FruchtermanReingold::calculate_exact_repulsive_forces(
47 const Graph &G,
48 NodeArray<NodeAttributes> &A,
49 NodeArray<DPoint>& F_rep)
50 {
51 //naive algorithm by Fruchterman & Reingold
52 DPoint nullpoint(0, 0);
53 int node_number = G.numberOfNodes();
54 Array<node> array_of_the_nodes(node_number + 1);
55
56 for (node v : G.nodes)
57 F_rep[v] = nullpoint;
58
59 int counter = 1;
60 for (node v : G.nodes)
61 {
62 array_of_the_nodes[counter] = v;
63 counter++;
64 }
65
66 for (int i = 1; i < node_number; i++) {
67 for (int j = i + 1; j <= node_number; j++)
68 {
69 node u = array_of_the_nodes[i];
70 node v = array_of_the_nodes[j];
71 DPoint f_rep_u_on_v = numexcept::f_rep_u_on_v(A[u].get_position(), A[v].get_position());
72 F_rep[v] += f_rep_u_on_v;
73 F_rep[u] -= f_rep_u_on_v;
74 }
75 }
76 }
77
78
calculate_approx_repulsive_forces(const Graph & G,NodeArray<NodeAttributes> & A,NodeArray<DPoint> & F_rep)79 void FruchtermanReingold::calculate_approx_repulsive_forces(
80 const Graph &G,
81 NodeArray<NodeAttributes> &A,
82 NodeArray<DPoint>& F_rep)
83 {
84 //GRID algorithm by Fruchterman & Reingold
85 List<IPoint> neighbour_boxes;
86 List<node> neighbour_box;
87 IPoint neighbour;
88 DPoint nullpoint(0, 0);
89
90 double gridboxlength;//length of a box in the GRID
91
92 //init F_rep
93 for (node v : G.nodes)
94 F_rep[v] = nullpoint;
95
96 //init max_gridindex and set contained_nodes
97
98 max_gridindex = static_cast<int> (sqrt(double(G.numberOfNodes())) / grid_quotient()) - 1;
99 max_gridindex = ((max_gridindex > 0) ? max_gridindex : 0);
100 Array2D<List<node> > contained_nodes(0, max_gridindex, 0, max_gridindex);
101
102 for (int i = 0; i <= max_gridindex; i++) {
103 for (int j = 0; j <= max_gridindex; j++)
104 {
105 contained_nodes(i, j).clear();
106 }
107 }
108
109 gridboxlength = boxlength / (max_gridindex + 1);
110 for (node v : G.nodes)
111 {
112 double x = A[v].get_x() - down_left_corner.m_x;//shift comput. box to nullpoint
113 double y = A[v].get_y() - down_left_corner.m_y;
114 int x_index = static_cast<int>(x / gridboxlength);
115 int y_index = static_cast<int>(y / gridboxlength);
116 contained_nodes(x_index, y_index).pushBack(v);
117 }
118
119 //force calculation
120
121 for (int i = 0; i <= max_gridindex; i++) {
122 for (int j = 0; j <= max_gridindex; j++) {
123 // Step1: calculate forces inside contained_nodes(i,j)
124 calculate_forces_inside_contained_nodes(F_rep, A, contained_nodes(i, j));
125
126 // Step 2: calculated forces to nodes in neighbour boxes
127
128 //find_neighbour_boxes
129
130 neighbour_boxes.clear();
131 for (int x = i - 1; x <= i + 1; x++) {
132 for (int y = j - 1; y <= j + 1; y++) {
133 if ((x >= 0) && (y >= 0) && (x <= max_gridindex) && (y <= max_gridindex))
134 {
135 neighbour.m_x = x;
136 neighbour.m_y = y;
137 if ((x != i) || (y != j))
138 neighbour_boxes.pushBack(neighbour);
139 }
140 }
141 }
142
143 //forget neighbour_boxes that already had access to this box
144 for (const IPoint &act_neighbour_box : neighbour_boxes)
145 {
146 int act_i = act_neighbour_box.m_x;
147 int act_j = act_neighbour_box.m_y;
148 if ((act_j == j + 1) || ((act_j == j) && (act_i == i + 1)))
149 {
150 for (node v : contained_nodes(i, j)) {
151 for (node u : contained_nodes(act_i, act_j))
152 {
153 DPoint f_rep_u_on_v = numexcept::f_rep_u_on_v(A[u].get_position(), A[v].get_position());
154 F_rep[v] += f_rep_u_on_v;
155 F_rep[u] -= f_rep_u_on_v;
156 }
157 }
158 }
159 }
160 }
161 }
162 }
163
164
make_initialisations(double bl,DPoint d_l_c,int grid_quot)165 void FruchtermanReingold::make_initialisations(double bl, DPoint d_l_c, int grid_quot)
166 {
167 grid_quotient(grid_quot);
168 down_left_corner = d_l_c; //export this two values from FMMM
169 boxlength = bl;
170 }
171
172 }
173 }
174 }
175