METHOD OF ANIMATING TRANSITIONS AND STABILIZING NODE MOTION DURING DYNAMIC GRAPH NAVIGATION

• US 20050180330A1
• Filed: 02/17/2005
• Published: 08/18/2005
• Est. Priority Date: 02/17/2004
• Status: Abandoned Application

• Current Assignee: Touchgraph LLC
• Original Assignee: Touchgraph LLC
• Inventors: Shapiro, Alexander
• Application Number:
  US10/906,396
• Publication Number:
  US 20050180330A1
• Time in Patent Office: Days
• US Class Current: 370/241
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

In a system and method for arranging a graph according to a Force-Directed Layout algorithm, a node-set transition in the graph may be animated by iteratively reducing or increasing an impact value of one node on another node, and a velocity of a node may be reduced in proportion the to the degree of its non-directional movement.

Claims

1. A method for animating a node-set transition from a first set of nodes to a second set of nodes in a graph arranged according to a Force-Directed Layout algorithm, the animation, comprising:

at least one of;

iteratively diminishing, in accordance with a transition-state of a first node of the graph, an impact value of the first node on a second node of the graph; and

iteratively increasing, in accordance with a transition-state of a third node of the graph, an impact value of the third node on the second node.

2. The method of claim 1, wherein during the increase, the impact value of the third node is initially 0, and during the diminishment, the impact value of the first node is reduced to 0.

3. The method of claim 1, wherein:

the impact value of the first node on the second node is diminished one of (a) upon a condition that the first node is removed from the graph during the transition and the second node is not removed from the graph during the transition, and (b) upon a condition that the first node is removed from the graph during the transition, even if the second node is removed from the graph during the transition; and

the impact value of the third node on the second node is increased one of (a) upon a condition that the third node is added to the graph during the transition and the second node is not added to the graph during the transition, and (b) upon a condition that the third node is added to the graph during the transition, even if the second node is added to the graph during the transition.

4. The method of claim 3, wherein:

a first amount by which the impact value is increased during an iteration and a second amount by which the impact value is decreased during the iteration are adjustable; and

the first and second amounts are determined by factors including a length of time to complete the iteration.

5. The method of claim 1, wherein coordinates of nodes that are removed from the graph are retained in memory.

6. The method of claim 5, wherein during an addition to the graph of a previously-removed node, the previously-removed node is initially placed in its previous location in the graph.

7. The method of claim 1, wherein the animation is visually represented by changes in at least one of color and transparency.

8. A method of setting a velocity of a node of a graph, the graph arranged according to a Force-Directed Layout algorithm, comprising:

reducing the velocity from an initial value in proportion to a degree of the node'"'"'s non-directional movement.

9. The method of claim 8, wherein the reduction of the velocity includes:

calculating a measure of a length of a path traveled by the node over at least one iteration as a path distance;

calculating a lateral displacement of the node over the at least one iteration;

calculating a noise value based on a comparison of the path distance to a magnitude of the lateral displacement; and

reducing the velocity of the node based on the noise value.

10. The method of claim 9, wherein:

each of the lateral displacement and the path distance for the node is calculated as a function of a time series of the node'"'"'s velocity vectors from successive iterations;

the lateral displacement is calculated based on a smoothing function of the velocity vectors; and

the path distance is calculated based on a smoothing function of the magnitudes of the velocity vectors.

11. The method of claim 10, wherein, for each of the lateral displacement calculation and the path distance calculation, less weight is given to a velocity vector of a first iteration than to a velocity vector of a second iteration that is more recent than the first iteration.

12. The method of claim 10, wherein:

the lateral displacement is calculated according to one of a moving average, a weighed moving average, a moving sum, a weighed moving sum, an exponential moving average, and an exponential moving sum; and

the path distance is calculated according to one of a moving average, a weighed moving average, a moving sum, a weighed moving sum, an exponential moving average, and an exponential moving sum.

13. The method of claim 10, wherein:

a lateral displacement for a current iteration is calculated based on a combination of a stored value of a lateral displacement of an immediately preceding iteration and the velocity vector of the current iteration;

the path distance for the current iteration is calculated based on a combination of a stored value of a path distance of the immediately preceding iteration and the velocity vector of the current iteration.

14. The method of claim 9, wherein the noise value is calculated based on one of (a) a ratio of the path distance to the magnitude of the lateral displacement and (b) a difference between the path distance and the magnitude of the lateral displacement.

15. The method of claim 8, wherein the reduction is ceased in response to at least one of (a) a user interaction, and (b) a programmatically determined setting.

16. An article of manufacture comprising a computer-readable medium having stored thereon instructions adapted to be executed by a processor, the instructions which, when executed, define a method for animating a node-set transition from a first set of nodes to a second set of nodes in a graph arranged according to a Force-Directed Layout algorithm (FDLA), the method comprising:

at least one of;

iteratively diminishing, in accordance with a transition-state of a first node of the graph, an impact value of the first node on a second node of the graph; and

iteratively increasing, in accordance with a transition-state of a third node of the graph, an impact value of the third node on the second node.