1 | using System;
|
---|
2 | using System.Collections.Generic;
|
---|
3 | using System.Text;
|
---|
4 | using System.Drawing;
|
---|
5 | using System.Threading;
|
---|
6 | using System.ComponentModel;
|
---|
7 | using Netron.Diagramming.Core.Analysis;
|
---|
8 | namespace Netron.Diagramming.Core
|
---|
9 | {
|
---|
10 | /// <summary>
|
---|
11 | /// <para>Layout instance implementing the Fruchterman-Reingold algorithm for
|
---|
12 | /// force-directed placement of graph nodes. The computational complexity of
|
---|
13 | /// this algorithm is quadratic [O(n^2)] in the number of nodes, so should
|
---|
14 | /// only be applied for relatively small graphs, particularly in interactive
|
---|
15 | /// situations.</para>
|
---|
16 | ///
|
---|
17 | /// <para>This implementation was ported from the implementation in the
|
---|
18 | /// <a href="http://jung.sourceforge.net/">JUNG</a> framework.</para>
|
---|
19 | /// </summary>
|
---|
20 | class FruchtermanReingoldLayout : LayoutBase
|
---|
21 | {
|
---|
22 | #region Fields
|
---|
23 | private double forceConstant;
|
---|
24 | private double temp;
|
---|
25 | private int maxIter = 300;
|
---|
26 |
|
---|
27 | protected int m_fidx;
|
---|
28 | private Random rnd;
|
---|
29 | private static double EPSILON = 0.000001D;
|
---|
30 | private static double ALPHA = 0.1D;
|
---|
31 |
|
---|
32 | Dictionary<string, Params> Pars;
|
---|
33 | double width;
|
---|
34 | double height;
|
---|
35 | BackgroundWorker worker;
|
---|
36 | #endregion
|
---|
37 |
|
---|
38 | #region Constructor
|
---|
39 | ///<summary>
|
---|
40 | ///Default constructor
|
---|
41 | ///</summary>
|
---|
42 | public FruchtermanReingoldLayout(IController controller)
|
---|
43 | : base("FruchtermanReingold Layout", controller)
|
---|
44 | {
|
---|
45 | }
|
---|
46 | #endregion
|
---|
47 |
|
---|
48 | #region Methods
|
---|
49 |
|
---|
50 | /// <summary>
|
---|
51 | /// Inits the calculational state
|
---|
52 | /// </summary>
|
---|
53 | private bool Init()
|
---|
54 | {
|
---|
55 | this.Graph = this.Model as IGraph;
|
---|
56 |
|
---|
57 | if (Graph == null)
|
---|
58 | throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'");
|
---|
59 |
|
---|
60 | //this.LayoutRoot = this.Controller.Model.LayoutRoot;//could be null if not set in the GUI
|
---|
61 | //Graph.ClearSpanningTree();
|
---|
62 | //Graph.MakeSpanningTree(LayoutRoot as INode);
|
---|
63 |
|
---|
64 | Pars = new Dictionary<string, Params>();
|
---|
65 | if (Nodes.Count == 0)
|
---|
66 | return false;
|
---|
67 | if (Edges.Count == 0) //this layout is base on embedded springs in the connections
|
---|
68 | return false;
|
---|
69 |
|
---|
70 | width = (double)Bounds.Width;
|
---|
71 | height = (double)Bounds.Height;
|
---|
72 | rnd = new Random();
|
---|
73 |
|
---|
74 |
|
---|
75 | temp = width / 10;
|
---|
76 | forceConstant = 0.75 * Math.Sqrt(height * width / Nodes.Count);
|
---|
77 |
|
---|
78 | // initialize node positions
|
---|
79 |
|
---|
80 |
|
---|
81 | double scaleW = ALPHA * width / 2;
|
---|
82 | double scaleH = ALPHA * height / 2;
|
---|
83 | Params par;
|
---|
84 | double[] loc;
|
---|
85 | foreach (INode node in Nodes)
|
---|
86 | {
|
---|
87 | loc = new double[2];
|
---|
88 | loc[0] = Center.X + rnd.NextDouble() * scaleW;
|
---|
89 | loc[1] = Center.Y + rnd.NextDouble() * scaleH;
|
---|
90 | par = new Params(loc, new double[2]);
|
---|
91 | Pars.Add(node.Uid.ToString(), par);
|
---|
92 | }
|
---|
93 | return true;
|
---|
94 | }
|
---|
95 |
|
---|
96 | /// <summary>
|
---|
97 | /// Runs this instance.
|
---|
98 | /// </summary>
|
---|
99 | public override void Run()
|
---|
100 | {
|
---|
101 | width = this.Bounds.Width;
|
---|
102 | height = this.Bounds.Height;
|
---|
103 | Run(1000);
|
---|
104 |
|
---|
105 |
|
---|
106 | }
|
---|
107 | /// <summary>
|
---|
108 | /// Stops this instance.
|
---|
109 | /// </summary>
|
---|
110 | public override void Stop()
|
---|
111 | {
|
---|
112 | if (worker != null && worker.IsBusy)
|
---|
113 | worker.CancelAsync();
|
---|
114 | }
|
---|
115 | /// <summary>
|
---|
116 | /// Runs the layout for a specified time.
|
---|
117 | /// </summary>
|
---|
118 | /// <param name="time">The time.</param>
|
---|
119 | public override void Run(int time)
|
---|
120 | {
|
---|
121 | if (Init())
|
---|
122 | {
|
---|
123 |
|
---|
124 | worker = new BackgroundWorker();
|
---|
125 | worker.DoWork += new DoWorkEventHandler(worker_DoWork);
|
---|
126 | worker.RunWorkerAsync(time);
|
---|
127 |
|
---|
128 | }
|
---|
129 |
|
---|
130 | }
|
---|
131 |
|
---|
132 | /// <summary>
|
---|
133 | /// Handles the DoWork event of the worker control.
|
---|
134 | /// </summary>
|
---|
135 | /// <param name="sender">The source of the event.</param>
|
---|
136 | /// <param name="e">The <see cref="T:System.ComponentModel.DoWorkEventArgs"/> instance containing the event data.</param>
|
---|
137 | void worker_DoWork(object sender, DoWorkEventArgs e)
|
---|
138 | {
|
---|
139 | //this.Controller.View.Suspend();
|
---|
140 | DateTime start = DateTime.Now;
|
---|
141 | while (DateTime.Now < start.AddMilliseconds((int)e.Argument))
|
---|
142 | {
|
---|
143 | RunStep();
|
---|
144 |
|
---|
145 | }
|
---|
146 | //this.Controller.View.Resume();
|
---|
147 | UpdateShapes();
|
---|
148 |
|
---|
149 | RunAnimation();
|
---|
150 | }
|
---|
151 |
|
---|
152 | private void RunAnimation()
|
---|
153 | {
|
---|
154 |
|
---|
155 | }
|
---|
156 |
|
---|
157 | /// <summary>
|
---|
158 | /// Runs a single step.
|
---|
159 | /// </summary>
|
---|
160 | private void RunStep()
|
---|
161 | {
|
---|
162 |
|
---|
163 | for (int curIter = 0; curIter < maxIter; curIter++)
|
---|
164 | {
|
---|
165 |
|
---|
166 | // Calculate repulsion
|
---|
167 | foreach (INode node in Nodes)
|
---|
168 | {
|
---|
169 | if (node.IsFixed) continue;
|
---|
170 | CalculateRepulsion(node);
|
---|
171 | }
|
---|
172 |
|
---|
173 | // Calculate attraction
|
---|
174 | foreach (IEdge edge in Edges)
|
---|
175 | {
|
---|
176 | CalculateAttraction(edge);
|
---|
177 | }
|
---|
178 |
|
---|
179 | foreach (INode node in Nodes)
|
---|
180 | {
|
---|
181 | if (node.IsFixed) continue;
|
---|
182 | CalculatePositions(node);
|
---|
183 | }
|
---|
184 |
|
---|
185 | CoolDown(curIter);
|
---|
186 |
|
---|
187 |
|
---|
188 | }
|
---|
189 |
|
---|
190 |
|
---|
191 | }
|
---|
192 |
|
---|
193 | private void UpdateShapes()
|
---|
194 | {
|
---|
195 | int x, y;
|
---|
196 | lock (Nodes)
|
---|
197 | lock (Pars)
|
---|
198 | {
|
---|
199 | foreach (INode node in Nodes)
|
---|
200 | {
|
---|
201 | x = Convert.ToInt32(Pars[node.Uid.ToString()].loc[0]) - node.Rectangle.X;
|
---|
202 | y = Convert.ToInt32(Pars[node.Uid.ToString()].loc[1]) - node.Rectangle.Y;
|
---|
203 | //if (node.Rectangle.X + x < width - node.Rectangle.Width - 10 && node.Rectangle.X + x > 10 && node.Rectangle.Y + y < height - node.Rectangle.Height - 10 && node.Rectangle.Y + y > 10)
|
---|
204 | node.MoveBy(new Point(x, y));
|
---|
205 | }
|
---|
206 | }
|
---|
207 | }
|
---|
208 |
|
---|
209 | #region Calculations
|
---|
210 | public void CalculatePositions(INode n)
|
---|
211 | {
|
---|
212 | Params np = Pars[n.Uid.ToString()];
|
---|
213 |
|
---|
214 |
|
---|
215 | double deltaLength = Math.Max(EPSILON, Math.Sqrt(np.disp[0] * np.disp[0] + np.disp[1] * np.disp[1]));
|
---|
216 |
|
---|
217 | double xDisp = np.disp[0] / deltaLength * Math.Min(deltaLength, temp);
|
---|
218 |
|
---|
219 | if (Double.IsNaN(xDisp))
|
---|
220 | {
|
---|
221 | System.Diagnostics.Trace.WriteLine("Oops, the layout resulted in a NaN problem.");
|
---|
222 | return;
|
---|
223 | }
|
---|
224 |
|
---|
225 | double yDisp = np.disp[1] / deltaLength * Math.Min(deltaLength, temp);
|
---|
226 |
|
---|
227 | np.loc[0] += xDisp;
|
---|
228 | np.loc[1] += yDisp;
|
---|
229 |
|
---|
230 |
|
---|
231 | // don't let nodes leave the display
|
---|
232 | double borderWidth = width / 50.0;
|
---|
233 | double x = np.loc[0];
|
---|
234 | if (x < borderWidth)
|
---|
235 | {
|
---|
236 | x = borderWidth + rnd.NextDouble() * borderWidth * 2.0;
|
---|
237 | }
|
---|
238 | else if (x > (width - borderWidth))
|
---|
239 | {
|
---|
240 | x = width - borderWidth - rnd.NextDouble() * borderWidth * 2.0;
|
---|
241 | }
|
---|
242 |
|
---|
243 | double y = np.loc[1];
|
---|
244 | if (y < borderWidth)
|
---|
245 | {
|
---|
246 | y = borderWidth + rnd.NextDouble() * borderWidth * 2.0;
|
---|
247 | }
|
---|
248 | else if (y > (height - borderWidth))
|
---|
249 | {
|
---|
250 | y = height - borderWidth - rnd.NextDouble() * borderWidth * 2.0;
|
---|
251 | }
|
---|
252 |
|
---|
253 | np.loc[0] = x;
|
---|
254 | np.loc[1] = y;
|
---|
255 | }
|
---|
256 |
|
---|
257 | /// <summary>
|
---|
258 | /// Calculates the attraction or tension on the given edge.
|
---|
259 | /// </summary>
|
---|
260 | /// <param name="edge">The edge.</param>
|
---|
261 | public void CalculateAttraction(IEdge edge)
|
---|
262 | {
|
---|
263 | INode n1, n2;
|
---|
264 | Params n1p = new Params();
|
---|
265 | Params n2p = new Params();
|
---|
266 | if (edge.SourceNode != null)
|
---|
267 | {
|
---|
268 | n2 = edge.SourceNode;
|
---|
269 | n2p = Pars[n2.Uid.ToString()];
|
---|
270 | };
|
---|
271 | if (edge.TargetNode != null)
|
---|
272 | {
|
---|
273 | n1 = edge.TargetNode;
|
---|
274 | n1p = Pars[n1.Uid.ToString()];
|
---|
275 | };
|
---|
276 |
|
---|
277 |
|
---|
278 |
|
---|
279 | double xDelta = n1p.loc[0] - n2p.loc[0];
|
---|
280 | double yDelta = n1p.loc[1] - n2p.loc[1];
|
---|
281 |
|
---|
282 | double deltaLength = Math.Max(EPSILON, Math.Sqrt(xDelta * xDelta + yDelta * yDelta));
|
---|
283 | double force = (deltaLength * deltaLength) / forceConstant;
|
---|
284 |
|
---|
285 | if (Double.IsNaN(force))
|
---|
286 | {
|
---|
287 | System.Diagnostics.Trace.WriteLine("Oops, the layout resulted in a NaN problem.");
|
---|
288 | return;
|
---|
289 | }
|
---|
290 |
|
---|
291 | double xDisp = (xDelta / deltaLength) * force;
|
---|
292 | double yDisp = (yDelta / deltaLength) * force;
|
---|
293 |
|
---|
294 | n1p.disp[0] -= xDisp; n1p.disp[1] -= yDisp;
|
---|
295 | n2p.disp[0] += xDisp; n2p.disp[1] += yDisp;
|
---|
296 | }
|
---|
297 |
|
---|
298 | public void CalculateRepulsion(INode node)
|
---|
299 | {
|
---|
300 | Params np = Pars[node.Uid.ToString()];
|
---|
301 | np.disp[0] = 0.0; np.disp[1] = 0.0;
|
---|
302 |
|
---|
303 | foreach (INode n2 in Nodes)
|
---|
304 | {
|
---|
305 |
|
---|
306 | Params n2p = Pars[n2.Uid.ToString()];
|
---|
307 | if (n2.IsFixed) continue;
|
---|
308 | if (node != n2)
|
---|
309 | {
|
---|
310 | double xDelta = np.loc[0] - n2p.loc[0];
|
---|
311 | double yDelta = np.loc[1] - n2p.loc[1];
|
---|
312 |
|
---|
313 | double deltaLength = Math.Max(EPSILON, Math.Sqrt(xDelta * xDelta + yDelta * yDelta));
|
---|
314 |
|
---|
315 | double force = (forceConstant * forceConstant) / deltaLength;
|
---|
316 |
|
---|
317 | if (Double.IsNaN(force))
|
---|
318 | {
|
---|
319 | System.Diagnostics.Trace.WriteLine("Oops, the layout resulted in a NaN problem.");
|
---|
320 | return;
|
---|
321 | }
|
---|
322 |
|
---|
323 | np.disp[0] += (xDelta / deltaLength) * force;
|
---|
324 | np.disp[1] += (yDelta / deltaLength) * force;
|
---|
325 | }
|
---|
326 | }
|
---|
327 | }
|
---|
328 |
|
---|
329 | private void CoolDown(int curIter)
|
---|
330 | {
|
---|
331 | temp *= (1.0 - curIter / (double)maxIter);
|
---|
332 | }
|
---|
333 | #endregion
|
---|
334 |
|
---|
335 |
|
---|
336 | /// <summary>
|
---|
337 | /// Paramter blob to temporarily keep working data of one node.
|
---|
338 | /// </summary>
|
---|
339 | struct Params
|
---|
340 | {
|
---|
341 | public double[] loc;
|
---|
342 | public double[] disp;
|
---|
343 |
|
---|
344 | public Params(double[] loc, double[] disp)
|
---|
345 | {
|
---|
346 | this.loc = loc;
|
---|
347 | this.disp = disp;
|
---|
348 | }
|
---|
349 |
|
---|
350 |
|
---|
351 | }
|
---|
352 |
|
---|
353 |
|
---|
354 | #endregion
|
---|
355 |
|
---|
356 | }
|
---|
357 | }
|
---|