?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Drop unused resource strings
[TortoiseGit.git] / ext / OGDF / src / energybased / FruchtermanReingold.cpp
blobe094e96ae3c6ed70abecd5572815cf774d3703c3
1 /*
2 * $Revision: 2552 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of class FruchtermanReingold (computation of forces).
11 *
12 * \author Stefan Hachul
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
44 #include <ogdf/internal/energybased/FruchtermanReingold.h>
45
46 #include "numexcept.h"
47 #include <ogdf/basic/Array2D.h>
48
49
50 namespace ogdf {
51
52 FruchtermanReingold::FruchtermanReingold()
53 {
54 grid_quotient(2);
55 }
56
57
58 void FruchtermanReingold::calculate_exact_repulsive_forces(
59 const Graph &G,
60 NodeArray<NodeAttributes> &A,
61 NodeArray<DPoint>& F_rep)
62 {
63 //naive algorithm by Fruchterman & Reingold
64 numexcept N;
65 node v,u;
66 DPoint f_rep_u_on_v;
67 DPoint vector_v_minus_u;
68 DPoint pos_u,pos_v;
69 DPoint nullpoint (0,0);
70 double norm_v_minus_u;
71 long node_number = G.numberOfNodes();
72 Array<node> array_of_the_nodes (node_number+1);
73 long counter = 1;
74 long i,j;
75 double scalar;
76
77 forall_nodes(v,G)
78 F_rep[v]= nullpoint;
79
80 forall_nodes(v,G)
81 {
82 array_of_the_nodes[counter]=v;
83 counter++;
84 }
85
86 for(i = 1; i<node_number;i++)
87 for(j = i+1;j<=node_number;j++)
88 {
89 u = array_of_the_nodes[i];
90 v = array_of_the_nodes[j];
91 pos_u = A[u].get_position();
92 pos_v = A[v].get_position();
93 if (pos_u == pos_v)
94 {//if2 (Exception handling if two nodes have the same position)
95 pos_u = N.choose_distinct_random_point_in_radius_epsilon(pos_u);
96 }//if2
97 vector_v_minus_u = pos_v - pos_u;
98 norm_v_minus_u = vector_v_minus_u.norm();
99 if(!N.f_rep_near_machine_precision(norm_v_minus_u,f_rep_u_on_v))
100 {
101 scalar = f_rep_scalar(norm_v_minus_u)/norm_v_minus_u ;
102 f_rep_u_on_v.m_x = scalar * vector_v_minus_u.m_x;
103 f_rep_u_on_v.m_y = scalar * vector_v_minus_u.m_y;
104 }
105 F_rep[v] = F_rep[v] + f_rep_u_on_v;
106 F_rep[u] = F_rep[u] - f_rep_u_on_v;
107 }
108 }
109
110
111 void FruchtermanReingold::calculate_approx_repulsive_forces(
112 const Graph &G,
113 NodeArray<NodeAttributes> &A,
114 NodeArray<DPoint>& F_rep)
115 {
116 //GRID algorithm by Fruchterman & Reingold
117 numexcept N;
118 List<IPoint> neighbour_boxes;
119 List<node> neighbour_box;
120 IPoint act_neighbour_box;
121 IPoint neighbour;
122 DPoint f_rep_u_on_v;
123 DPoint vector_v_minus_u;
124 DPoint nullpoint (0,0);
125 DPoint pos_u,pos_v;
126 double norm_v_minus_u;
127 double scalar;
128
129 int i,j,act_i,act_j,k,l,length;
130 node u,v;
131 double x,y,gridboxlength;//length of a box in the GRID
132 int x_index,y_index;
133
134 //init F_rep
135 forall_nodes(v,G)
136 F_rep[v]= nullpoint;
137
138 //init max_gridindex and set contained_nodes;
139
140 max_gridindex = static_cast<int> (sqrt(double(G.numberOfNodes()))/grid_quotient())-1;
141 max_gridindex = ((max_gridindex > 0)? max_gridindex : 0);
142 Array2D<List<node> > contained_nodes (0,max_gridindex, 0, max_gridindex);
143
144 for(i=0;i<= max_gridindex;i++)
145 for(j=0;j<= max_gridindex;j++)
146 {
147 contained_nodes(i,j).clear();
148 }
149
150 gridboxlength = boxlength/(max_gridindex+1);
151 forall_nodes(v,G)
152 {
153 x = A[v].get_x()-down_left_corner.m_x;//shift comput. box to nullpoint
154 y = A[v].get_y()-down_left_corner.m_y;
155 x_index = static_cast<int>(x/gridboxlength);
156 y_index = static_cast<int>(y/gridboxlength);
157 contained_nodes(x_index,y_index).pushBack(v);
158 }
159
160 //force calculation
161
162 for(i=0;i<= max_gridindex;i++)
163 for(j=0;j<= max_gridindex;j++)
164 {
165 //step1: calculate forces inside contained_nodes(i,j)
166
167 length = contained_nodes(i,j).size();
168 Array<node> nodearray_i_j (length+1);
169 k = 1;
170 forall_listiterators(node, v_it,contained_nodes(i,j))
171 {
172 nodearray_i_j[k]= *v_it;
173 k++;
174 }
175
176 for(k = 1; k<length;k++)
177 for(l = k+1;l<=length;l++)
178 {
179 u = nodearray_i_j[k];
180 v = nodearray_i_j[l];
181 pos_u = A[u].get_position();
182 pos_v = A[v].get_position();
183 if (pos_u == pos_v)
184 {//if2 (Exception handling if two nodes have the same position)
185 pos_u = N.choose_distinct_random_point_in_radius_epsilon(pos_u);
186 }//if2
187 vector_v_minus_u = pos_v - pos_u;
188 norm_v_minus_u = vector_v_minus_u.norm();
189
190 if(!N.f_rep_near_machine_precision(norm_v_minus_u,f_rep_u_on_v))
191 {
192 scalar = f_rep_scalar(norm_v_minus_u)/norm_v_minus_u ;
193 f_rep_u_on_v.m_x = scalar * vector_v_minus_u.m_x;
194 f_rep_u_on_v.m_y = scalar * vector_v_minus_u.m_y;
195 }
196 F_rep[v] = F_rep[v] + f_rep_u_on_v;
197 F_rep[u] = F_rep[u] - f_rep_u_on_v;
198 }
199
200 //step 2: calculated forces to nodes in neighbour boxes
201
202 //find_neighbour_boxes
203
204 neighbour_boxes.clear();
205 for(k = i -1;k <= i+1;k++)
206 for(l = j-1;l <= j+1;l++)
207 if ( (k>=0) && (l>=0) && (k<=max_gridindex) && (l<=max_gridindex))
208 {
209 neighbour.m_x = k;
210 neighbour.m_y = l;
211 if ((k != i) || (l != j) )
212 neighbour_boxes.pushBack(neighbour);
213 }
214
215
216 //forget neighbour_boxes that already had access to this box
217 forall_listiterators(IPoint, act_neighbour_box_it,neighbour_boxes)
218 {//forall
219 act_i = (*act_neighbour_box_it).m_x;
220 act_j = (*act_neighbour_box_it).m_y;
221 if((act_j == j+1)||((act_j == j)&&(act_i == i+1)))
222 {//if1
223 forall_listiterators(node,v_it,contained_nodes(i,j))
224 forall_listiterators(node,u_it,contained_nodes(act_i,act_j))
225 {//for
226 pos_u = A[*u_it].get_position();
227 pos_v = A[*v_it].get_position();
228 if (pos_u == pos_v)
229 {//if2 (Exception handling if two nodes have the same position)
230 pos_u = N.choose_distinct_random_point_in_radius_epsilon(pos_u);
231 }//if2
232 vector_v_minus_u = pos_v - pos_u;
233 norm_v_minus_u = vector_v_minus_u.norm();
234
235 if(!N.f_rep_near_machine_precision(norm_v_minus_u,f_rep_u_on_v))
236 {
237 scalar = f_rep_scalar(norm_v_minus_u)/norm_v_minus_u ;
238 f_rep_u_on_v.m_x = scalar * vector_v_minus_u.m_x;
239 f_rep_u_on_v.m_y = scalar * vector_v_minus_u.m_y;
240 }
241 F_rep[*v_it] = F_rep[*v_it] + f_rep_u_on_v;
242 F_rep[*u_it] = F_rep[*u_it] - f_rep_u_on_v;
243 }//for
244 }//if1
245 }//forall
246 }
247 }
248
249
250 void FruchtermanReingold::make_initialisations(double bl, DPoint d_l_c, int grid_quot)
251 {
252 grid_quotient(grid_quot);
253 down_left_corner = d_l_c; //export this two values from FMMM
254 boxlength = bl;
255 }
256
257
258 inline double FruchtermanReingold::f_rep_scalar(double d)
259 {
260 if (d > 0) {
261 return 1/d;
262
263 } else {
264 cout<<"Error FruchtermanReingold:: f_rep_scalar nodes at same position"<<endl;
265 return 0;
266 }
267 }
268
269 }//namespace ogdf
Windows Explorer Extension to Operate Git