Source code: giny/util/SpringEmbeddedLayouter.java
1 package giny.util;
2
3 import giny.model.*;
4 import giny.view.*;
5 import java.awt.geom.Point2D;
6 import java.util.Iterator;
7 import java.util.List;
8 import java.util.ArrayList;
9
10 /**
11 * An implementation of Kamada and Kawai's spring embedded layout algorithm.
12 */
13 public class SpringEmbeddedLayouter{
14
15 public static final int DEFAULT_NUM_LAYOUT_PASSES =
16 2;
17 public static final double DEFAULT_AVERAGE_ITERATIONS_PER_NODE =
18 20.0;
19
20 public static final double[] DEFAULT_NODE_DISTANCE_SPRING_SCALARS =
21 new double[] { 1.0, 1.0 };
22 public static final double DEFAULT_NODE_DISTANCE_STRENGTH_CONSTANT =
23 15.0;
24 public static final double DEFAULT_NODE_DISTANCE_REST_LENGTH_CONSTANT =
25 200.0;
26 public static final double DEFAULT_DISCONNECTED_NODE_DISTANCE_SPRING_STRENGTH =
27 .05;
28 public static final double DEFAULT_DISCONNECTED_NODE_DISTANCE_SPRING_REST_LENGTH =
29 2500.0;
30
31 public static final double[] DEFAULT_ANTICOLLISION_SPRING_SCALARS =
32 new double[] { 0.0, 1.0 };
33 public static final double DEFAULT_ANTICOLLISION_SPRING_STRENGTH =
34 100.0;
35
36 protected int numLayoutPasses =
37 DEFAULT_NUM_LAYOUT_PASSES;
38 protected double averageIterationsPerNode =
39 DEFAULT_AVERAGE_ITERATIONS_PER_NODE;
40
41 protected double[] nodeDistanceSpringScalars =
42 DEFAULT_NODE_DISTANCE_SPRING_SCALARS;
43 protected double nodeDistanceStrengthConstant =
44 DEFAULT_NODE_DISTANCE_STRENGTH_CONSTANT;
45 protected double nodeDistanceRestLengthConstant =
46 DEFAULT_NODE_DISTANCE_REST_LENGTH_CONSTANT;
47 protected double disconnectedNodeDistanceSpringStrength =
48 DEFAULT_DISCONNECTED_NODE_DISTANCE_SPRING_STRENGTH;
49 protected double disconnectedNodeDistanceSpringRestLength =
50 DEFAULT_DISCONNECTED_NODE_DISTANCE_SPRING_REST_LENGTH;
51 protected double[][] nodeDistanceSpringStrengths;
52 protected double[][] nodeDistanceSpringRestLengths;
53
54 protected double[] anticollisionSpringScalars =
55 DEFAULT_ANTICOLLISION_SPRING_SCALARS;
56 protected double anticollisionSpringStrength =
57 DEFAULT_ANTICOLLISION_SPRING_STRENGTH;
58
59 protected GraphView graphView;
60 protected int nodeCount;
61 protected int edgeCount;
62 protected int layoutPass;
63
64
65 public SpringEmbeddedLayouter ( GraphView graph_view ) {
66 setGraphView( graph_view );
67 initializeSpringEmbeddedLayouter();
68 }
69
70 public void setGraphView ( GraphView new_graph_view ) {
71 graphView = new_graph_view;
72 } // setGraphView( GraphView )
73
74 public GraphView getGraphView () {
75 return graphView;
76 } // getGraphView()
77
78 protected void initializeSpringEmbeddedLayouter () {
79 // Do nothing.
80 // TODO: Something?
81 } // initializeSpringEmbeddedLayouter()
82
83 public void doLayout () {
84 // initialize the layouting.
85 nodeCount = graphView.getNodeViewCount();
86 edgeCount = graphView.getEdgeViewCount();
87
88
89
90 // Stop if all nodes are closer together than this euclidean distance.
91 // TODO: Why is this an appropriate threshold?
92 double euclidean_distance_threshold =
93 ( 0.5 * ( nodeCount + edgeCount ) );
94
95 // Stop if the potential energy doesn't go down anymore.
96 double potential_energy_percent_change_threshold = .001;
97
98 int num_iterations = ( int )
99 ( ( nodeCount * averageIterationsPerNode ) / numLayoutPasses );
100
101 List partials_list = createPartialsList();
102 PotentialEnergy potential_energy = new PotentialEnergy();
103 Iterator node_views_iterator;
104 NodeView node_view;
105 PartialDerivatives partials;
106 PartialDerivatives furthest_node_partials = null;
107 double current_progress_temp;
108 double setup_progress = 0.0;
109 for( layoutPass = 0; layoutPass < numLayoutPasses; layoutPass++ ) {
110
111 setupForLayoutPass();
112
113 //System.out.println( " DO Layout Pass " );
114
115 // initialize this layout pass
116 potential_energy.reset();
117 partials_list.clear();
118
119 // Calculate all node distances. Keep track of the furthest.
120 node_views_iterator = graphView.getNodeViewsIterator();
121 while( node_views_iterator.hasNext() ) {
122 node_view = ( NodeView )node_views_iterator.next();
123
124 //System.out.println( "Calculate Partials for: "+node_view.getGraphPerspectiveIndex() );
125
126 partials = new PartialDerivatives( node_view );
127 calculatePartials(
128 partials,
129 null,
130 potential_energy,
131 false
132 );
133 partials_list.add( partials );
134 if( ( furthest_node_partials == null ) ||
135 ( partials.euclideanDistance >
136 furthest_node_partials.euclideanDistance )
137 ) {
138 // //System.out.println( "P: "+furthest_node_partials.euclideanDistance+" E: "+partials.euclideanDistance );
139 furthest_node_partials = partials;
140 }
141 }
142
143 // Until num_iterations, or the furthest node is not-so-fur, move the
144 // furthest node towards where it wants to be.
145 for( int iterations_i = 0;
146 ( ( iterations_i < num_iterations ) &&
147 ( furthest_node_partials.euclideanDistance >=
148 euclidean_distance_threshold ) );
149 iterations_i++
150 ) {
151 // TODO: REMOVE
152 //System.out.println( "At iteration " + layoutPass + ":" + iterations_i + ", furthest_node_partials is " + furthest_node_partials + "." );
153 furthest_node_partials =
154 moveNode( furthest_node_partials, partials_list, potential_energy );
155 } // End for each iteration, attempt to minimize the total potential
156 // energy by moving the node that is furthest from where it should be.
157 } // End for each layout pass
158 } // doLayout()
159
160 /**
161 * Called at the beginning of each layoutPass iteration.
162 */
163 protected void setupForLayoutPass () {
164 setupNodeDistanceSprings();
165 } // setupForLayoutPass()
166
167 protected void setupNodeDistanceSprings () {
168 // We only have to do this once.
169 if( layoutPass != 0 ) {
170 return;
171 }
172
173 nodeDistanceSpringRestLengths = new double[ nodeCount ][ nodeCount ];
174 nodeDistanceSpringStrengths = new double[ nodeCount ][ nodeCount ];
175
176 if( nodeDistanceSpringScalars[ layoutPass ] == 0.0 ) {
177 return;
178 }
179
180 //IntNodeDistances ind = new IntNodeDistances( graphView.getGraphPerspective().getNodeIndicesArray(), null, graphView.getGraphPerspective() );
181
182 NodeDistances ind = new NodeDistances( graphView.getGraphPerspective().nodesList(), null, graphView.getGraphPerspective() );
183 int[][] node_distances = ( int[][] )ind.construct();
184
185 if( node_distances == null ) {
186 return;
187 }
188
189 // TODO: A good strength_constant is the characteristic path length of the
190 // graph. For now we'll just use nodeDistanceStrengthConstant.
191 double node_distance_strength_constant = nodeDistanceStrengthConstant;
192
193 // TODO: rest_length_constant can be chosen to scale the whole graph.
194 // To make it the size of the current view, try
195 // rest_length_constant = Math.sqrt( ( ( graphView.getViewRect().width / graphView.getViewRect.height() ) / 4 ) / graphView.getGraphDiameter() );
196 // To make it bigger, try
197 // rest_length_constant = graphView.averageEdgeLength();
198 // To make it smaller, try
199 // rest_length_constant = Math.sqrt( ( graphView.getViewRect().width * graphView.getViewRect.height() ) / graphView.getGraphDiameter() );
200 // For now we'll just use nodeDistanceRestLengthConstant.
201 double node_distance_rest_length_constant = nodeDistanceRestLengthConstant;
202
203 // Calculate the rest lengths and strengths based on the node distance data
204 for( int node_i = 0; node_i < nodeCount; node_i++ ) {
205 for( int node_j = ( node_i + 1 ); node_j < nodeCount; node_j++ ) {
206
207
208 //System.out.println( "APSP: node_i: "+node_i+ " node_j: "+ node_j+" == "+node_distances[ node_i ][node_j ] );
209
210 if( node_distances[ node_i ][ node_j ] == Integer.MAX_VALUE ) {
211 nodeDistanceSpringRestLengths[ node_i ][ node_j ] =
212 disconnectedNodeDistanceSpringRestLength;
213 //System.out.println( "disconnectedNodeDistanceSpringRestLength 1: "+ disconnectedNodeDistanceSpringRestLength );
214 } else {
215 nodeDistanceSpringRestLengths[ node_i ][ node_j ] =
216 ( node_distance_rest_length_constant *
217 node_distances[ node_i ][ node_j ] );
218 //System.out.println( " ELSE 1: "+nodeDistanceSpringRestLengths[ node_i ][ node_j ] );
219 }
220 // Mirror over the diagonal.
221 nodeDistanceSpringRestLengths[ node_j ][ node_i ] =
222 nodeDistanceSpringRestLengths[ node_i ][ node_j ];
223
224 if( node_distances[ node_i ][ node_j ] == Integer.MAX_VALUE ) {
225 nodeDistanceSpringStrengths[ node_i ][ node_j ] =
226 disconnectedNodeDistanceSpringStrength;
227 } else {
228 nodeDistanceSpringStrengths[ node_i ][ node_j ] =
229 ( node_distance_strength_constant /
230 ( node_distances[ node_i ][ node_j ] *
231 node_distances[ node_i ][ node_j ] )
232 );
233 }
234 // Mirror over the diagonal.
235 nodeDistanceSpringStrengths[ node_j ][ node_i ] =
236 nodeDistanceSpringStrengths[ node_i ][ node_j ];
237
238
239 }
240
241 }
242 // currentProgress has been increased by ( nodeCount * nodeCount ).
243
244 } // setupNodeDistanceSprings()
245
246 /**
247 * If partials_list is given, adjust all partials (bidirectional) for the
248 * current location of the given partials and return the new furthest node's
249 * partials. Otherwise, just adjust the given partials (using the
250 * graphView's nodeViewsIterator), and return it. If reversed is true then
251 * partials_list must be provided and all adjustments made by a non-reversed
252 * call (with the same partials with the same graphNodeView at the same
253 * location) will be undone.
254 * Complexity is O( #Nodes ).
255 */
256 protected PartialDerivatives calculatePartials (
257 PartialDerivatives partials,
258 List partials_list,
259 PotentialEnergy potential_energy,
260 boolean reversed
261 ) {
262
263 partials.reset();
264
265 NodeView node_view = partials.getNodeView();
266 int node_view_index = node_view.getGraphPerspectiveIndex() - 1;
267 double node_view_radius = node_view.getWidth();
268 double node_view_x = node_view.getXPosition();
269 double node_view_y = node_view.getYPosition();
270
271
272 //System.out.println( "index: "+node_view_index+" x: "+node_view_x+" y:" +node_view_y );
273
274 PartialDerivatives other_node_partials = null;
275 NodeView other_node_view;
276 int other_node_view_index;
277 double other_node_view_radius;
278
279 PartialDerivatives furthest_partials = null;
280
281 Iterator iterator;
282 if( partials_list == null ) {
283 iterator = graphView.getNodeViewsIterator();
284 } else {
285 iterator = partials_list.iterator();
286 }
287 double delta_x;
288 double delta_y;
289 double euclidean_distance;
290 double euclidean_distance_cubed;
291 double distance_from_rest;
292 double distance_from_touching;
293 double incremental_change;
294 while( iterator.hasNext() ) {
295 if( partials_list == null ) {
296 other_node_view = ( NodeView )iterator.next();
297 } else {
298 other_node_partials = ( PartialDerivatives )iterator.next();
299 other_node_view = other_node_partials.getNodeView();
300 }
301
302
303
304 //System.out.println( "Node_View: "+ (node_view.getGraphPerspectiveIndex() - 1 ));
305 //System.out.println( "Other_Node_View: "+ (other_node_view.getGraphPerspectiveIndex() - 1 ) );
306
307 if ( node_view.getGraphPerspectiveIndex() - 1 == other_node_view.getGraphPerspectiveIndex() - 1 ) {
308 //System.out.println( "Nodes are the same. " );
309 continue;
310 }
311
312 other_node_view_index = other_node_view.getGraphPerspectiveIndex() - 1;
313 other_node_view_radius = other_node_view.getWidth();
314
315 delta_x = ( node_view_x - other_node_view.getXPosition() );
316 delta_y = ( node_view_y - other_node_view.getYPosition() );
317
318 //System.out.println( "Delta's Calculated: "+delta_y+ " "+delta_x );
319
320 euclidean_distance =
321 Math.sqrt( ( delta_x * delta_x ) + ( delta_y * delta_y ) );
322 euclidean_distance_cubed = Math.pow( euclidean_distance, 3 );
323
324
325 //System.out.println( "Euclidean_Distance: "+euclidean_distance+" Euclidean_Distance_Cubed: "+euclidean_distance_cubed );
326
327 distance_from_touching =
328 ( euclidean_distance -
329 ( node_view_radius + other_node_view_radius ) );
330
331 //System.out.println( "Distance_From_Touching: "+distance_from_touching );
332
333 incremental_change =
334 ( nodeDistanceSpringScalars[ layoutPass ] *
335 ( nodeDistanceSpringStrengths[ node_view_index ][ other_node_view_index ] *
336 ( delta_x -
337 (
338 ( nodeDistanceSpringRestLengths[ node_view_index ][ other_node_view_index ] *
339 delta_x ) /
340 euclidean_distance
341 )
342 )
343 )
344 );
345
346 //System.out.println( "Incremental_Change: "+incremental_change );
347
348 if( !reversed ) {
349 partials.x += incremental_change;
350 }
351 if( other_node_partials != null ) {
352 incremental_change =
353 ( nodeDistanceSpringScalars[ layoutPass ] *
354 ( nodeDistanceSpringStrengths[ other_node_view_index ][ node_view_index ] *
355 ( -delta_x -
356 (
357 ( nodeDistanceSpringRestLengths[ other_node_view_index ][ node_view_index ] *
358 -delta_x ) /
359 euclidean_distance
360 )
361 )
362 )
363 );
364 if( reversed ) {
365 other_node_partials.x -= incremental_change;
366 } else {
367 other_node_partials.x += incremental_change;
368 }
369 }
370 if( distance_from_touching < 0.0 ) {
371 incremental_change =
372 ( anticollisionSpringScalars[ layoutPass ] *
373 ( anticollisionSpringStrength *
374 ( delta_x -
375 (
376 ( ( node_view_radius + other_node_view_radius ) *
377 delta_x ) /
378 euclidean_distance
379 )
380 )
381 )
382 );
383 if( !reversed ) {
384 partials.x += incremental_change;
385 }
386 if( other_node_partials != null ) {
387 incremental_change =
388 ( anticollisionSpringScalars[ layoutPass ] *
389 ( anticollisionSpringStrength *
390 ( -delta_x -
391 (
392 ( ( node_view_radius + other_node_view_radius ) *
393 -delta_x ) /
394 euclidean_distance
395 )
396 )
397 )
398 );
399 if( reversed ) {
400 other_node_partials.x -= incremental_change;
401 //System.out.println( "Other_Node_Partials (-): "+other_node_partials.x );
402 } else {
403 other_node_partials.x += incremental_change;
404 //System.out.println( "Other_Node_Partials (+): "+other_node_partials.x );
405 }
406 }
407 }
408 incremental_change =
409 ( nodeDistanceSpringScalars[ layoutPass ] *
410 ( nodeDistanceSpringStrengths[ node_view_index ][ other_node_view_index ] *
411 ( delta_y -
412 (
413 ( nodeDistanceSpringRestLengths[ node_view_index ][ other_node_view_index ] *
414 delta_y ) /
415 euclidean_distance
416 )
417 )
418 )
419 );
420
421 //System.out.println( "Incremental_Change: "+incremental_change );
422
423 if( !reversed ) {
424 partials.y += incremental_change;
425 }
426 if( other_node_partials != null ) {
427 incremental_change =
428 ( nodeDistanceSpringScalars[ layoutPass ] *
429 ( nodeDistanceSpringStrengths[ other_node_view_index ][ node_view_index ] *
430 ( -delta_y -
431 (
432 ( nodeDistanceSpringRestLengths[ other_node_view_index ][ node_view_index ] *
433 -delta_y ) /
434 euclidean_distance
435 )
436 )
437 )
438 );
439 if( reversed ) {
440 other_node_partials.y -= incremental_change;
441 } else {
442 other_node_partials.y += incremental_change;
443 }
444 }
445 if( distance_from_touching < 0.0 ) {
446 incremental_change =
447 ( anticollisionSpringScalars[ layoutPass ] *
448 ( anticollisionSpringStrength *
449 ( delta_y -
450 (
451 ( ( node_view_radius + other_node_view_radius ) *
452 delta_y ) /
453 euclidean_distance
454 )
455 )
456 )
457 );
458 if( !reversed ) {
459 partials.y += incremental_change;
460 }
461 if( other_node_partials != null ) {
462 incremental_change =
463 ( anticollisionSpringScalars[ layoutPass ] *
464 ( anticollisionSpringStrength *
465 ( -delta_y -
466 (
467 ( ( node_view_radius + other_node_view_radius ) *
468 -delta_y ) /
469 euclidean_distance
470 )
471 )
472 )
473 );
474 if( reversed ) {
475 other_node_partials.y -= incremental_change;
476 } else {
477 other_node_partials.y += incremental_change;
478 }
479 }
480 }
481
482 incremental_change =
483 ( nodeDistanceSpringScalars[ layoutPass ] *
484 ( nodeDistanceSpringStrengths[ node_view_index ][ other_node_view_index ] *
485 ( 1.0 -
486 (
487 ( nodeDistanceSpringRestLengths[ node_view_index ][ other_node_view_index ] *
488 ( delta_y * delta_y )
489 ) /
490 euclidean_distance_cubed
491 )
492 )
493 )
494 );
495 //System.out.println( "Incremental_Change: "+incremental_change );
496
497 if( reversed ) {
498 if( other_node_partials != null ) {
499 other_node_partials.xx -= incremental_change;
500 }
501 } else {
502 partials.xx += incremental_change;
503 if( other_node_partials != null ) {
504 other_node_partials.xx += incremental_change;
505 }
506 }
507 if( distance_from_touching < 0.0 ) {
508 incremental_change =
509 ( anticollisionSpringScalars[ layoutPass ] *
510 ( anticollisionSpringStrength *
511 ( 1.0 -
512 (
513 ( ( node_view_radius + other_node_view_radius ) *
514 ( delta_y * delta_y )
515 ) /
516 euclidean_distance_cubed
517 )
518 )
519 )
520 );
521 if( reversed ) {
522 if( other_node_partials != null ) {
523 other_node_partials.xx -= incremental_change;
524 }
525 } else {
526 partials.xx += incremental_change;
527 if( other_node_partials != null ) {
528 other_node_partials.xx += incremental_change;
529 }
530 }
531 }
532 incremental_change =
533 ( nodeDistanceSpringScalars[ layoutPass ] *
534 ( nodeDistanceSpringStrengths[ node_view_index ][ other_node_view_index ] *
535 ( 1.0 -
536 (
537 ( nodeDistanceSpringRestLengths[ node_view_index ][ other_node_view_index ] *
538 ( delta_x * delta_x )
539 ) /
540 euclidean_distance_cubed
541 )
542 )
543 )
544 );
545
546 //System.out.println( "Incremental_Change: "+incremental_change );
547
548 if( reversed ) {
549 if( other_node_partials != null ) {
550 other_node_partials.yy -= incremental_change;
551 }
552 } else {
553 partials.yy += incremental_change;
554 if( other_node_partials != null ) {
555 other_node_partials.yy += incremental_change;
556 }
557 }
558 if( distance_from_touching < 0.0 ) {
559 incremental_change =
560 ( anticollisionSpringScalars[ layoutPass ] *
561 ( anticollisionSpringStrength *
562 ( 1.0 -
563 (
564 ( ( node_view_radius + other_node_view_radius ) *
565 ( delta_x * delta_x )
566 ) /
567 euclidean_distance_cubed
568 )
569 )
570 )
571 );
572 if( reversed ) {
573 if( other_node_partials != null ) {
574 other_node_partials.yy -= incremental_change;
575 }
576 } else {
577 partials.yy += incremental_change;
578 if( other_node_partials != null ) {
579 other_node_partials.yy += incremental_change;
580 }
581 }
582 }
583 incremental_change =
584 ( nodeDistanceSpringScalars[ layoutPass ] *
585 ( nodeDistanceSpringStrengths[ node_view_index ][ other_node_view_index ] *
586 ( ( nodeDistanceSpringRestLengths[ node_view_index ][ other_node_view_index ] *
587 ( delta_x * delta_y )
588 ) /
589 euclidean_distance_cubed
590 )
591 )
592 );
593
594 //System.out.println( "Incremental_Change: "+incremental_change );
595
596 if( reversed ) {
597 if( other_node_partials != null ) {
598 other_node_partials.xy -= incremental_change;
599 }
600 } else {
601 partials.xy += incremental_change;
602 if( other_node_partials != null ) {
603 other_node_partials.xy += incremental_change;
604 }
605 }
606 if( distance_from_touching < 0.0 ) {
607 incremental_change =
608 ( anticollisionSpringScalars[ layoutPass ] *
609 ( anticollisionSpringStrength *
610 (
611 ( ( node_view_radius + other_node_view_radius ) *
612 ( delta_x * delta_y )
613 ) /
614 euclidean_distance_cubed
615 )
616 )
617 );
618 if( reversed ) {
619 if( other_node_partials != null ) {
620 other_node_partials.xy -= incremental_change;
621 }
622 } else {
623 partials.xy += incremental_change;
624 if( other_node_partials != null ) {
625 other_node_partials.xy += incremental_change;
626 }
627 }
628 }
629
630 distance_from_rest =
631 ( euclidean_distance -
632 nodeDistanceSpringRestLengths[ node_view_index ][ other_node_view_index ]
633 );
634 incremental_change =
635 ( nodeDistanceSpringScalars[ layoutPass ] *
636 ( ( nodeDistanceSpringStrengths[ node_view_index ][ other_node_view_index ] *
637 ( distance_from_rest * distance_from_rest )
638 ) /
639 2
640 )
641 );
642
643 //System.out.println( "Distance_From_Rest: "+distance_from_rest+" Incremental_Change: "+incremental_change );
644
645 if( reversed ) {
646 if( other_node_partials != null ) {
647 potential_energy.totalEnergy -= incremental_change;
648 }
649 } else {
650 potential_energy.totalEnergy += incremental_change;
651 if( other_node_partials != null ) {
652 potential_energy.totalEnergy += incremental_change;
653 }
654 }
655 if( distance_from_touching < 0.0 ) {
656 incremental_change =
657 ( anticollisionSpringScalars[ layoutPass ] *
658 ( ( anticollisionSpringStrength *
659 ( distance_from_touching * distance_from_touching )
660 ) /
661 2
662 )
663 );
664 if( reversed ) {
665 if( other_node_partials != null ) {
666 potential_energy.totalEnergy -= incremental_change;
667 }
668 } else {
669 potential_energy.totalEnergy += incremental_change;
670 if( other_node_partials != null ) {
671 potential_energy.totalEnergy += incremental_change;
672 }
673 }
674 }
675 if( other_node_partials != null ) {
676 other_node_partials.euclideanDistance =
677 Math.sqrt( ( other_node_partials.x * other_node_partials.x ) +
678 ( other_node_partials.y * other_node_partials.y ) );
679 if( ( furthest_partials == null ) ||
680 ( other_node_partials.euclideanDistance >
681 furthest_partials.euclideanDistance )
682 ) {
683 furthest_partials = other_node_partials;
684 }
685 }
686
687 }
688
689 if( !reversed ) {
690 partials.euclideanDistance =
691 Math.sqrt( ( partials.x * partials.x ) +
692 ( partials.y * partials.y ) );
693 }
694
695 if( ( furthest_partials == null ) ||
696 ( partials.euclideanDistance >
697 furthest_partials.euclideanDistance )
698 ) {
699 furthest_partials = partials;
700 }
701
702 //System.out.println( "Furthest_Partials: "+furthest_partials );
703
704 return furthest_partials;
705 } // calculatePartials( PartialDerivatives, List, PotentialEnergy, boolean )
706
707 /**
708 * Move the node with the given partials and adjust all partials in the given
709 * List to reflect that move, and adjust the potential energy too.
710 * @return the PartialDerivatives of the furthest node after the move.
711 */
712 protected PartialDerivatives moveNode (
713 PartialDerivatives partials,
714 List partials_list,
715 PotentialEnergy potential_energy
716 ) {
717 NodeView node_view = partials.getNodeView();
718
719 PartialDerivatives starting_partials = new PartialDerivatives( partials );
720 calculatePartials(
721 partials,
722 partials_list,
723 potential_energy,
724 true
725 );
726 simpleMoveNode( starting_partials );
727 return
728 calculatePartials(
729 partials,
730 partials_list,
731 potential_energy,
732 false
733 );
734 } // moveNode( PartialDerivatives, List, PotentialEnergy )
735
736 protected void simpleMoveNode (
737 PartialDerivatives partials
738 ) {
739 NodeView node_view = partials.getNodeView();
740 double denomenator =
741 ( ( partials.xx * partials.yy ) -
742 ( partials.xy * partials.xy ) );
743 double delta_x =
744 (
745 ( ( -partials.x * partials.yy ) -
746 ( -partials.y * partials.xy ) ) /
747 denomenator
748 );
749 double delta_y =
750 (
751 ( ( -partials.y * partials.xx ) -
752 ( -partials.x * partials.xy ) ) /
753 denomenator
754 );
755
756 // REMOVE
757 //System.out.println( "moving node \"" + node_view + "\" to ( " + ( node_view.getXPosition() + delta_x ) + ", " + ( node_view.getYPosition() + delta_y ) + " )." );
758
759 // TODO: figure out movement
760 //node_view.setXPosition(
761 // node_view.getXPosition() + delta_x
762 //);
763 //node_view.setYPosition(
764 // node_view.getYPosition() + delta_y
765 //);
766
767 Point2D p = node_view.getOffset();
768 node_view.setOffset( p.getX() + delta_x, p.getY() + delta_y );
769
770 } // simpleMoveNode( PartialDerivatives )
771
772 protected List createPartialsList () {
773 return new ArrayList();
774 } // createPartialsList()
775
776 class PartialDerivatives {
777 protected NodeView nodeView;
778 public double x;
779 public double y;
780 public double xx;
781 public double yy;
782 public double xy;
783 public double euclideanDistance;
784
785 public PartialDerivatives ( NodeView node_view ) {
786 nodeView = node_view;
787 }
788
789 public PartialDerivatives ( PartialDerivatives copy_from ) {
790 nodeView = copy_from.getNodeView();
791 copyFrom( copy_from );
792 }
793
794 public void reset () {
795 x = 0.0;
796 y = 0.0;
797 xx = 0.0;
798 yy = 0.0;
799 xy = 0.0;
800 euclideanDistance = 0.0;
801 } // reset()
802
803 public NodeView getNodeView () {
804 return nodeView;
805 } // getNodeView()
806
807 public void copyFrom ( PartialDerivatives other_partial_derivatives ) {
808 x = other_partial_derivatives.x;
809 y = other_partial_derivatives.y;
810 xx = other_partial_derivatives.xx;
811 yy = other_partial_derivatives.yy;
812 xy = other_partial_derivatives.xy;
813 euclideanDistance = other_partial_derivatives.euclideanDistance;
814 } // copyFrom( PartialDerivatives )
815
816 public String toString () {
817 return "PartialDerivatives( \"" + getNodeView() + "\", x=" + x + ", y=" + y + ", xx=" + xx + ", yy=" + yy + ", xy=" + xy + ", euclideanDistance=" + euclideanDistance + " )";
818 } // toString()
819
820 } // inner class PartialDerivatives
821
822 class PotentialEnergy {
823
824 public double totalEnergy = 0.0;
825
826 public void reset () {
827 totalEnergy = 0.0;
828 } // reset()
829
830 } // class PotentialEnergy
831
832 } // class SpringEmbeddedLayouter