Changeset 4068 for trunk/sources/HeuristicLab.ExtLibs/HeuristicLab.Netron/3.0.2672.12446/Netron.Diagramming.Core-3.0.2672.12446/Layout/ForceDirectedLayout.cs
- Timestamp:
- 07/22/10 00:44:01 (14 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/sources/HeuristicLab.ExtLibs/HeuristicLab.Netron/3.0.2672.12446/Netron.Diagramming.Core-3.0.2672.12446/Layout/ForceDirectedLayout.cs
r2768 r4068 1 1 using System; 2 using System.Diagnostics; 2 using System.Collections.Generic; 3 using System.ComponentModel; 4 using System.Drawing; 3 5 using Netron.Diagramming.Core.Analysis; 4 6 using Netron.Diagramming.Core.Layout.Force; 5 using System.Drawing; 6 using System.Collections.Generic; 7 using System.Text; 8 using System.Windows.Forms; 9 using System.ComponentModel; 10 11 namespace Netron.Diagramming.Core 12 { 13 /// <summary> 14 /// <para>Layout that positions graph elements based on a physics simulation of 15 /// interacting forces; by default, nodes repel each other, edges act as 16 /// springs, and drag forces (similar to air resistance) are applied. This 17 /// algorithm can be run for multiple iterations for a run-once layout 18 /// computation or repeatedly run in an animated fashion for a dynamic and 19 /// interactive layout.</para> 20 /// 21 /// <para>The running time of this layout algorithm is the greater of O(N log N) 22 /// and O(E), where N is the number of nodes and E the number of edges. 23 /// The addition of custom force calculation modules may, however, increase 24 /// this value.</para> 25 /// 26 /// <para>The <see cref="ForceSimulator"/> used to drive this layout 27 /// can be set explicitly, allowing any number of custom force directed layouts 28 /// to be created through the user's selection of included 29 /// <see cref="Force"/> components. Each node in the layout is 30 /// mapped to a <see cref="ForceItem"/> instance and each edge 31 /// to a <see cref="Spring"/> instance for storing the state 32 /// of the simulation. See the <see cref="Force"/> namespace for more.</para> 33 /// </summary> 34 class ForceDirectedLayout : LayoutBase 35 { 36 #region Fields 37 private ForceSimulator m_fsim; 38 private long m_lasttime = -1L; 39 private long m_maxstep = 50L; 40 private bool m_runonce; 41 private int m_iterations = 100; 42 private bool mEnforceBounds; 43 BackgroundWorker worker; 44 protected INode referrer; 45 46 protected String m_nodeGroup; 47 protected String m_edgeGroup; 48 private Dictionary<string, ForceItem> Pars; 49 #endregion 50 51 #region Properties 52 public long MaxTimeStep 53 { 54 get { return m_maxstep; } 55 set { m_maxstep = value; } 56 } 57 58 public ForceSimulator getForceSimulator 59 { 60 get { return m_fsim; } 61 set { m_fsim = value; } 62 } 63 64 public int Iterations 65 { 66 get { return m_iterations; } 67 set 68 { 69 if (value < 1) 70 throw new ArgumentException("The amount of iterations has to be bigger or equal to one."); 71 m_iterations = value; 72 } 73 } 74 75 76 77 #endregion 78 79 #region Constructor 80 ///<summary> 81 ///Default constructor 82 ///</summary> 83 public ForceDirectedLayout(IController controller) 84 : base("ForceDirected Layout", controller) 85 { 86 87 } 88 #endregion 89 90 #region Methods 91 /// <summary> 92 /// Handles the DoWork event of the worker control. 93 /// </summary> 94 /// <param name="sender">The source of the event.</param> 95 /// <param name="e">The <see cref="T:System.ComponentModel.DoWorkEventArgs"/> instance containing the event data.</param> 96 private void worker_DoWork(object sender, DoWorkEventArgs e) 97 { 98 this.Controller.View.Suspend(); 99 Init(); 100 Layout(); 101 this.Controller.View.Resume(); 102 } 103 /// <summary> 104 /// Runs this instance. 105 /// </summary> 106 public override void Run() 107 { 108 Run(2000); 109 } 110 111 /// <summary> 112 /// Runs the specified time. 113 /// </summary> 114 /// <param name="time">The time.</param> 115 public override void Run(int time) 116 { 117 worker = new BackgroundWorker(); 118 worker.DoWork += new DoWorkEventHandler(worker_DoWork); 119 worker.RunWorkerAsync(time); 120 } 121 122 /// <summary> 123 /// Stops this instance. 124 /// </summary> 125 public override void Stop() 126 { 127 if (worker != null && worker.IsBusy) 128 worker.CancelAsync(); 129 } 130 ///<summary> 131 /// Get the mass value associated with the given node. Subclasses should 132 /// override this method to perform custom mass assignment. 133 /// @param n the node for which to compute the mass value 134 /// @return the mass value for the node. By default, all items are given 135 /// a mass value of 1.0. 136 ///</summary> 137 protected float getMassValue(INode n) 138 { 139 return 1.0f; 140 } 141 142 ///<summary> 143 /// Get the spring length for the given edge. Subclasses should 144 /// override this method to perform custom spring length assignment. 145 /// @param e the edge for which to compute the spring length 146 /// @return the spring length for the edge. A return value of 147 /// -1 means to ignore this method and use the global default. 148 ///</summary> 149 protected float getSpringLength(IEdge e) 150 { 151 return -1.0F; 152 } 153 154 ///<summary> 155 /// Get the spring coefficient for the given edge, which controls the 156 /// tension or strength of the spring. Subclasses should 157 /// override this method to perform custom spring tension assignment. 158 /// @param e the edge for which to compute the spring coefficient. 159 /// @return the spring coefficient for the edge. A return value of 160 /// -1 means to ignore this method and use the global default. 161 ///</summary> 162 protected float getSpringCoefficient(IEdge e) 163 { 164 return -1.0F; 165 } 166 167 private bool Init() 168 { 169 170 mEnforceBounds = false; 171 m_runonce = true; 172 m_fsim = new ForceSimulator(); 173 174 m_fsim.AddForce(new NBodyForce()); 175 m_fsim.AddForce(new SpringForce()); 176 m_fsim.AddForce(new DragForce()); 177 178 this.Graph = this.Model as IGraph; 179 180 if (Graph == null) 181 throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'"); 182 183 //Graph.ClearSpanningTree(); 184 //Graph.MakeSpanningTree(LayoutRoot as INode); 185 186 187 if (Graph.Nodes.Count == 0) 188 return false; 189 if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections 190 return false; 191 192 Pars = new Dictionary<string, ForceItem>(); 193 194 foreach (INode node in Nodes) 195 { 196 Pars.Add(node.Uid.ToString(), new ForceItem()); 197 } 198 return true; 199 } 200 201 /// <summary> 202 /// Updates the node positions. 203 /// </summary> 204 private void UpdateNodePositions() 205 { 206 double x1 = 0, x2 = 0, y1 = 0, y2 = 0; 207 208 if (Bounds != null) 209 { 210 x1 = Bounds.X; y1 = Bounds.Top; 211 x2 = Bounds.Right; y2 = Bounds.Bottom; 212 } 213 214 // update positions 215 foreach (INode item in Nodes) 216 { 217 218 ForceItem fitem = Pars[item.Uid.ToString()]; 219 if (item.IsFixed) 220 { 221 // clear any force computations 222 fitem.Force[0] = 0.0f; 223 fitem.Force[1] = 0.0f; 224 fitem.Velocity[0] = 0.0f; 225 fitem.Velocity[1] = 0.0f; 226 227 if (Double.IsNaN(item.X)) 228 { 229 setX(item, referrer, 0.0D); 230 setY(item, referrer, 0.0D); 231 } 232 continue; 233 } 234 235 double x = fitem.Location[0]; 236 double y = fitem.Location[1]; 237 //do we need to check the bounding constraints 238 if (mEnforceBounds && Bounds != null) 239 { 240 241 double hw = item.Rectangle.Width / 2; 242 double hh = item.Rectangle.Height / 2; 243 if (x + hw > x2) x = x2 - hw; 244 if (x - hw < x1) x = x1 + hw; 245 if (y + hh > y2) y = y2 - hh; 246 if (y - hh < y1) y = y1 + hh; 247 } 248 249 // set the actual position 250 setX(item, referrer, x); 251 setY(item, referrer, y); 252 } 253 } 254 255 ///<summary> 256 /// Reset the force simulation state for all nodes processed by this layout. 257 ///</summary> 258 public void Reset() 259 { 260 foreach (INode item in Nodes) 261 { 262 ForceItem fitem = Pars[item.Uid.ToString()]; 263 if (fitem != null) 264 { 265 fitem.Location[0] = (float)item.X; 266 fitem.Location[1] = (float)item.Y; 267 fitem.Force[0] = fitem.Force[1] = 0; 268 fitem.Velocity[0] = fitem.Velocity[1] = 0; 269 } 270 } 271 m_lasttime = -1L; 272 } 273 274 /// <summary> 275 /// Loads the simulator with all relevant force items and springs. 276 /// </summary> 277 /// <param name="fsim"> the force simulator driving this layout.</param> 278 protected void InitializeSimulator(ForceSimulator fsim) 279 { 280 //TODO: some checks here...? 281 282 float startX = (referrer == null ? 0f : (float)referrer.X); 283 float startY = (referrer == null ? 0f : (float)referrer.Y); 284 startX = float.IsNaN(startX) ? 0f : startX; 285 startY = float.IsNaN(startY) ? 0f : startY; 286 if (Nodes != null && Nodes.Count > 0) 287 { 288 foreach (INode item in Nodes) 289 { 290 ForceItem fitem = Pars[item.Uid.ToString()]; 291 fitem.Mass = getMassValue(item); 292 double x = item.X; 293 double y = item.Y; 294 fitem.Location[0] = (Double.IsNaN(x) ? startX : (float)x); 295 fitem.Location[1] = (Double.IsNaN(y) ? startY : (float)y); 296 fsim.addItem(fitem); 297 } 298 } 299 if (Edges != null && Edges.Count > 0) 300 { 301 foreach (IEdge e in Edges) 302 { 303 INode n1 = e.SourceNode; 304 if (n1 == null) continue; 305 ForceItem f1 = Pars[n1.Uid.ToString()]; 306 INode n2 = e.TargetNode; 307 if (n2 == null) continue; 308 ForceItem f2 = Pars[n2.Uid.ToString()]; 309 float coeff = getSpringCoefficient(e); 310 float slen = getSpringLength(e); 311 fsim.addSpring(f1, f2, (coeff >= 0 ? coeff : -1.0F), (slen >= 0 ? slen : -1.0F)); 312 } 313 } 314 } 315 private void Layout() 316 { 317 // perform different actions if this is a run-once or 318 // run-continuously layout 319 if (m_runonce) 320 { 321 PointF anchor = new PointF(Bounds.Width / 2F, Bounds.Height / 2F); 322 foreach (INode node in Nodes) 323 { 324 setX(node, null, anchor.X); 325 setY(node, null, anchor.Y); 326 } 327 m_fsim.Clear(); 328 long timestep = 1000L; 329 330 InitializeSimulator(m_fsim); 331 332 for (int i = 0; i < m_iterations; i++) 333 { 334 // use an annealing schedule to set time step 335 timestep *= Convert.ToInt64(1.0 - i / (double)m_iterations); 336 long step = timestep + 50; 337 // run simulator 338 m_fsim.RunSimulator(step); 339 // debugging output 340 //if (i % 10 == 0 ) {Trace.WriteLine("iter: "+i);} 341 } 342 UpdateNodePositions(); 343 } 344 else 345 { 346 // get timestep 347 if (m_lasttime == -1) 348 m_lasttime = DateTime.Now.Ticks * 10 - 20; 349 long time = DateTime.Now.Ticks * 10;//how many milliseconds since the human race started to count things 350 long timestep = Math.Min(m_maxstep, time - m_lasttime); 351 m_lasttime = time; 352 353 // run force simulator 354 m_fsim.Clear(); 355 InitializeSimulator(m_fsim); 356 m_fsim.RunSimulator(timestep); 357 UpdateNodePositions(); 358 } 359 //if ( frac == 1.0 ) { 360 // reset(); 361 //} 362 } 363 #endregion 364 365 } 7 8 namespace Netron.Diagramming.Core { 9 /// <summary> 10 /// <para>Layout that positions graph elements based on a physics simulation of 11 /// interacting forces; by default, nodes repel each other, edges act as 12 /// springs, and drag forces (similar to air resistance) are applied. This 13 /// algorithm can be run for multiple iterations for a run-once layout 14 /// computation or repeatedly run in an animated fashion for a dynamic and 15 /// interactive layout.</para> 16 /// 17 /// <para>The running time of this layout algorithm is the greater of O(N log N) 18 /// and O(E), where N is the number of nodes and E the number of edges. 19 /// The addition of custom force calculation modules may, however, increase 20 /// this value.</para> 21 /// 22 /// <para>The <see cref="ForceSimulator"/> used to drive this layout 23 /// can be set explicitly, allowing any number of custom force directed layouts 24 /// to be created through the user's selection of included 25 /// <see cref="Force"/> components. Each node in the layout is 26 /// mapped to a <see cref="ForceItem"/> instance and each edge 27 /// to a <see cref="Spring"/> instance for storing the state 28 /// of the simulation. See the <see cref="Force"/> namespace for more.</para> 29 /// </summary> 30 class ForceDirectedLayout : LayoutBase { 31 #region Fields 32 private ForceSimulator m_fsim; 33 private long m_lasttime = -1L; 34 private long m_maxstep = 50L; 35 private bool m_runonce; 36 private int m_iterations = 100; 37 private bool mEnforceBounds; 38 BackgroundWorker worker; 39 protected INode referrer; 40 41 protected String m_nodeGroup; 42 protected String m_edgeGroup; 43 private Dictionary<string, ForceItem> Pars; 44 #endregion 45 46 #region Properties 47 public long MaxTimeStep { 48 get { return m_maxstep; } 49 set { m_maxstep = value; } 50 } 51 52 public ForceSimulator getForceSimulator { 53 get { return m_fsim; } 54 set { m_fsim = value; } 55 } 56 57 public int Iterations { 58 get { return m_iterations; } 59 set { 60 if (value < 1) 61 throw new ArgumentException("The amount of iterations has to be bigger or equal to one."); 62 m_iterations = value; 63 } 64 } 65 66 67 68 #endregion 69 70 #region Constructor 71 ///<summary> 72 ///Default constructor 73 ///</summary> 74 public ForceDirectedLayout(IController controller) 75 : base("ForceDirected Layout", controller) { 76 77 } 78 #endregion 79 80 #region Methods 81 /// <summary> 82 /// Handles the DoWork event of the worker control. 83 /// </summary> 84 /// <param name="sender">The source of the event.</param> 85 /// <param name="e">The <see cref="T:System.ComponentModel.DoWorkEventArgs"/> instance containing the event data.</param> 86 private void worker_DoWork(object sender, DoWorkEventArgs e) { 87 this.Controller.View.Suspend(); 88 Init(); 89 Layout(); 90 this.Controller.View.Resume(); 91 } 92 /// <summary> 93 /// Runs this instance. 94 /// </summary> 95 public override void Run() { 96 Run(2000); 97 } 98 99 /// <summary> 100 /// Runs the specified time. 101 /// </summary> 102 /// <param name="time">The time.</param> 103 public override void Run(int time) { 104 worker = new BackgroundWorker(); 105 worker.DoWork += new DoWorkEventHandler(worker_DoWork); 106 worker.RunWorkerAsync(time); 107 } 108 109 /// <summary> 110 /// Stops this instance. 111 /// </summary> 112 public override void Stop() { 113 if (worker != null && worker.IsBusy) 114 worker.CancelAsync(); 115 } 116 ///<summary> 117 /// Get the mass value associated with the given node. Subclasses should 118 /// override this method to perform custom mass assignment. 119 /// @param n the node for which to compute the mass value 120 /// @return the mass value for the node. By default, all items are given 121 /// a mass value of 1.0. 122 ///</summary> 123 protected float getMassValue(INode n) { 124 return 1.0f; 125 } 126 127 ///<summary> 128 /// Get the spring length for the given edge. Subclasses should 129 /// override this method to perform custom spring length assignment. 130 /// @param e the edge for which to compute the spring length 131 /// @return the spring length for the edge. A return value of 132 /// -1 means to ignore this method and use the global default. 133 ///</summary> 134 protected float getSpringLength(IEdge e) { 135 return -1.0F; 136 } 137 138 ///<summary> 139 /// Get the spring coefficient for the given edge, which controls the 140 /// tension or strength of the spring. Subclasses should 141 /// override this method to perform custom spring tension assignment. 142 /// @param e the edge for which to compute the spring coefficient. 143 /// @return the spring coefficient for the edge. A return value of 144 /// -1 means to ignore this method and use the global default. 145 ///</summary> 146 protected float getSpringCoefficient(IEdge e) { 147 return -1.0F; 148 } 149 150 private bool Init() { 151 152 mEnforceBounds = false; 153 m_runonce = true; 154 m_fsim = new ForceSimulator(); 155 156 m_fsim.AddForce(new NBodyForce()); 157 m_fsim.AddForce(new SpringForce()); 158 m_fsim.AddForce(new DragForce()); 159 160 this.Graph = this.Model as IGraph; 161 162 if (Graph == null) 163 throw new InconsistencyException("The model has not been set and the Graph property is hence 'null'"); 164 165 //Graph.ClearSpanningTree(); 166 //Graph.MakeSpanningTree(LayoutRoot as INode); 167 168 169 if (Graph.Nodes.Count == 0) 170 return false; 171 if (Graph.Edges.Count == 0) //this layout is base on embedded springs in the connections 172 return false; 173 174 Pars = new Dictionary<string, ForceItem>(); 175 176 foreach (INode node in Nodes) { 177 Pars.Add(node.Uid.ToString(), new ForceItem()); 178 } 179 return true; 180 } 181 182 /// <summary> 183 /// Updates the node positions. 184 /// </summary> 185 private void UpdateNodePositions() { 186 double x1 = 0, x2 = 0, y1 = 0, y2 = 0; 187 188 if (Bounds != null) { 189 x1 = Bounds.X; y1 = Bounds.Top; 190 x2 = Bounds.Right; y2 = Bounds.Bottom; 191 } 192 193 // update positions 194 foreach (INode item in Nodes) { 195 196 ForceItem fitem = Pars[item.Uid.ToString()]; 197 if (item.IsFixed) { 198 // clear any force computations 199 fitem.Force[0] = 0.0f; 200 fitem.Force[1] = 0.0f; 201 fitem.Velocity[0] = 0.0f; 202 fitem.Velocity[1] = 0.0f; 203 204 if (Double.IsNaN(item.X)) { 205 setX(item, referrer, 0.0D); 206 setY(item, referrer, 0.0D); 207 } 208 continue; 209 } 210 211 double x = fitem.Location[0]; 212 double y = fitem.Location[1]; 213 //do we need to check the bounding constraints 214 if (mEnforceBounds && Bounds != null) { 215 216 double hw = item.Rectangle.Width / 2; 217 double hh = item.Rectangle.Height / 2; 218 if (x + hw > x2) x = x2 - hw; 219 if (x - hw < x1) x = x1 + hw; 220 if (y + hh > y2) y = y2 - hh; 221 if (y - hh < y1) y = y1 + hh; 222 } 223 224 // set the actual position 225 setX(item, referrer, x); 226 setY(item, referrer, y); 227 } 228 } 229 230 ///<summary> 231 /// Reset the force simulation state for all nodes processed by this layout. 232 ///</summary> 233 public void Reset() { 234 foreach (INode item in Nodes) { 235 ForceItem fitem = Pars[item.Uid.ToString()]; 236 if (fitem != null) { 237 fitem.Location[0] = (float)item.X; 238 fitem.Location[1] = (float)item.Y; 239 fitem.Force[0] = fitem.Force[1] = 0; 240 fitem.Velocity[0] = fitem.Velocity[1] = 0; 241 } 242 } 243 m_lasttime = -1L; 244 } 245 246 /// <summary> 247 /// Loads the simulator with all relevant force items and springs. 248 /// </summary> 249 /// <param name="fsim"> the force simulator driving this layout.</param> 250 protected void InitializeSimulator(ForceSimulator fsim) { 251 //TODO: some checks here...? 252 253 float startX = (referrer == null ? 0f : (float)referrer.X); 254 float startY = (referrer == null ? 0f : (float)referrer.Y); 255 startX = float.IsNaN(startX) ? 0f : startX; 256 startY = float.IsNaN(startY) ? 0f : startY; 257 if (Nodes != null && Nodes.Count > 0) { 258 foreach (INode item in Nodes) { 259 ForceItem fitem = Pars[item.Uid.ToString()]; 260 fitem.Mass = getMassValue(item); 261 double x = item.X; 262 double y = item.Y; 263 fitem.Location[0] = (Double.IsNaN(x) ? startX : (float)x); 264 fitem.Location[1] = (Double.IsNaN(y) ? startY : (float)y); 265 fsim.addItem(fitem); 266 } 267 } 268 if (Edges != null && Edges.Count > 0) { 269 foreach (IEdge e in Edges) { 270 INode n1 = e.SourceNode; 271 if (n1 == null) continue; 272 ForceItem f1 = Pars[n1.Uid.ToString()]; 273 INode n2 = e.TargetNode; 274 if (n2 == null) continue; 275 ForceItem f2 = Pars[n2.Uid.ToString()]; 276 float coeff = getSpringCoefficient(e); 277 float slen = getSpringLength(e); 278 fsim.addSpring(f1, f2, (coeff >= 0 ? coeff : -1.0F), (slen >= 0 ? slen : -1.0F)); 279 } 280 } 281 } 282 private void Layout() { 283 // perform different actions if this is a run-once or 284 // run-continuously layout 285 if (m_runonce) { 286 PointF anchor = new PointF(Bounds.Width / 2F, Bounds.Height / 2F); 287 foreach (INode node in Nodes) { 288 setX(node, null, anchor.X); 289 setY(node, null, anchor.Y); 290 } 291 m_fsim.Clear(); 292 long timestep = 1000L; 293 294 InitializeSimulator(m_fsim); 295 296 for (int i = 0; i < m_iterations; i++) { 297 // use an annealing schedule to set time step 298 timestep *= Convert.ToInt64(1.0 - i / (double)m_iterations); 299 long step = timestep + 50; 300 // run simulator 301 m_fsim.RunSimulator(step); 302 // debugging output 303 //if (i % 10 == 0 ) {Trace.WriteLine("iter: "+i);} 304 } 305 UpdateNodePositions(); 306 } else { 307 // get timestep 308 if (m_lasttime == -1) 309 m_lasttime = DateTime.Now.Ticks * 10 - 20; 310 long time = DateTime.Now.Ticks * 10;//how many milliseconds since the human race started to count things 311 long timestep = Math.Min(m_maxstep, time - m_lasttime); 312 m_lasttime = time; 313 314 // run force simulator 315 m_fsim.Clear(); 316 InitializeSimulator(m_fsim); 317 m_fsim.RunSimulator(timestep); 318 UpdateNodePositions(); 319 } 320 //if ( frac == 1.0 ) { 321 // reset(); 322 //} 323 } 324 #endregion 325 326 } 366 327 }
Note: See TracChangeset
for help on using the changeset viewer.