Layout of node-link structures in space with negative curvature

Claims

What is claimed:

1. A method comprising:

obtaining layout data; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch;

using the layout data to present a first representation of the node-link structure on a display;

receiving a signal from a user; the signal indicating a change from a first display position to a second display position; the first representation including a first feature near the first display position, the first feature representing a first part of the node-link structure; and

in response to the signal, presenting a second representation of the node-link structure on the display; the second representation including a second feature representing the first part of the node-link structure, the second feature being presented near the second display position; the second representation being perceptible as a changed continuation of the first representation.

2. The method of claim 1 in which the space with negative curvature is a discrete approximation of a hyperbolic plane.

3. The method of claim 2 in which the layout data indicate, for each of the set of nodes, first and second coordinates; the first and second coordinates together indicating a position in the hyperbolic plane.

4. The method of claim 3 in which each of the first and second coordinates is between zero and one; the act of operating the processor to use the layout data to present a first representation of the node-link structure comprising:

using the layout data to obtain mapped data that indicate, for each of a subset of the set of nodes, the first and second coordinates indicated for the node by the layout data; the first coordinate indicating position along a first axis within a planar unit disk and the second coordinate indicating position along a second axis within the planar unit disk, the second axis being perpendicular to the first axis.

5. The method of claim 1 in which the node-link structure is an acyclic graph.

6. The method of claim 5 in which the node-link structure is a tree.

7. The method of claim 1 in which the branch is an exponentially growing branch.

8. The method of claim 1 in which the act of using the layout data to present a first representation of the node-link structure comprises:

using the layout data to obtain mapped data indicating positions in a region of the display for a subset of the nodes; and

using the mapped data to provide first representation data to the display, the first representation data causing presentation of the first representation in the region of the display; the first representation including, for each node in the subset, a node feature representing the node.

9. The method of claim 8 in which the act of using the layout data to obtain mapped data comprises performing projective mapping to a planar unit disk.

10. The method of claim 8 in which the act of using the layout data to obtain mapped data comprises performing conformal mapping to a planar unit disk.

11. The method of claim 10 in which the layout data indicate, for each of the mapping's subset of nodes, first and second coordinates; the first and second coordinates together indicating a position in the space with negative curvature; each of the first and second coordinates being between zero and one; the act of using the layout data to obtain mapped data comprising:

obtaining mapped data that indicate, for each of the subset of nodes, the first and second coordinates indicated for the node by the layout data; the first coordinate indicating position along a first axis within the planar unit disk and the second coordinate indicating position along a second axis within the planar unit disk, the second axis being perpendicular to the first axis.

12. The method of claim 8 in which the region of the display has a perimeter; the act of using the layout data to obtain mapped data comprising, for one of the nodes that is a child node of one of the parent nodes and that has descendant nodes:

using the layout data to map the parent node's position in the layout space to a first display position in the region of the display;

using the layout data to map the child node's position in the layout space to a second display position in the region of the display; and

if the second display position is within a minimum spacing from the perimeter of the region and, from the relation between the first and second display positions, it is unlikely that any of the descendant nodes are further than the minimum spacing from the perimeter, excluding the child node and its descendant nodes from the subset of nodes.

13. The method of claim 12 in which the region of the display is circular.

14. The method of claim 1 in which the act of presenting the first representation comprises:

obtaining first transformation data indicating a first rigid transformation of the layout space that moves the positions indicated by the layout data to first transformed positions; and

using the first transformation data to obtain first transformed position data; the first transformed position data indicating transformed positions in the layout space for parts of the node-link structure, the transformed positions having a relation to the positions indicated by the layout data equivalent to the first rigid transformation; the first transformed position data indicating a position for the first part of the node-link structure such that a feature representing the first part would be presented near the first display position;

the act of presenting a second representation comprising:

obtaining second transformation data indicating a second rigid transformation of the layout space that would move a first transformed position that maps to the first display position to a second transformed position that maps to the second display position; and

using the second transformation data to obtain second transformed position data; the second transformed position data indicating transformed positions in the layout space for parts of the node-link structure, the transformed positions having a relation to the positions indicated by the first transformed position data equivalent to the second rigid transformation; the second transformed position data indicating a position for the first part of the node-link structure such that a feature representing the first part would be presented near the second display position.

15. The method of claim 14 in which the second transformation data indicate a second rigid transformation that preserves in the second representation an orientation of features in the first representation that represent parts of the node-link structure.

16. The method of claim 15 in which the first part is a parent node with at least one child node that is related to the parent node through one link; the first transformed position data indicating positions for the parent node and for its child nodes so that the child nodes together have a first orientation with respect to the parent node; the second transformation data indicating a second rigid transformation; the second transformed position data indicating positions for the parent node and for its child nodes so that the child nodes' positions together have a second orientation with respect to the second parent node's position; the first and second orientations being approximately equal.

17. The method of claim 16 in which the node-link structure is a tree with a root node; the first part being the root node.

18. The method of claim 14 in which the first and second representations each include a region of greater spacings in which node features have nearest node spacings that are in general perceptibly greater than in other regions; the first representation including in its region of greater spacings a first parent node with at least one child node that is related to the first parent node through one link; the first transformed data indicating transformed positions for the first parent node and for its child nodes so that the child nodes together have a first orientation with respect to the first parent node in the first representation; the second representation including in its region of greater spacings a second parent node with at least one child node that is related to the second parent node through one link; the second transformation data indicating a second rigid transformation such that the second transformed position data indicate positions for the second parent node and for its child nodes so that the child nodes together have a second orientation with respect to the second parent node in the second representation; the first and second orientations being approximately equal.

19. The method of claim 1, further comprising a series of iterations in response to the signal; each iteration comprising:

presenting an intermediate representation of the node-link structure; the intermediate representation including features representing parts of the node-link structure, the features including an intermediate first part feature representing the first part; the intermediate first part feature having a position between the first display position and the second display position;

the iterations being performed such that the intermediate first part features in the intermediate representations and the second feature in the second representation are all perceptible as moved continuations of the first feature in the first representation.

20. The method of claim 1 in which the first part is a node.

21. A method of operating a machine; the machine including:

memory;

user input circuitry for providing data indicating signals from a user;

a display;

a processor connected for accessing data stored in the memory, for receiving data from the user input circuitry, and for providing data to cause presentation of images by the display; and

layout data stored in the memory; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch;

the method comprising:

operating the processor to use the layout data to provide first representation data to the display, the first representation data causing the display to present a first representation of the node-link structure;

receiving a signal from a user; the signal indicating a change from a first display position to a second display position; the first representation including a first feature near the first display position, the first feature representing a first part of the node-link structure; and

in response to the signal, operating the processor to automatically provide second representation data to the display, the second representation data causing the display to present a second representation of the node-link structure on the display; the second representation including a second feature representing the first part of the node-link structure, the second feature being presented near the second display position; the second representation being perceptible as a changed continuation of the first representation.

22. The method of claim 21 in which the user input circuitry comprises a pointer control device that controls a pointer presented on the display; the signal from the user including a button click when the pointer is at the second display position.

23. The method of claim 22 in which the signal from the user further includes an action moving the pointer to the second display position.

24. A machine comprising:

memory;

user input circuitry for providing data indicating signals from a user;

a display;

a processor connected for accessing data stored in the memory, for receiving data from the user input circuitry, and for providing data to cause presentation of images by the display;

layout data stored in the memory; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch; and

program data stored in the memory; the program data indicating instructions the processor executes; the processor, in executing the instructions:

using the layout data to provide first representation data to the display, the first representation data causing the display to present a first representation of the node-link structure;

receiving a signal from a user; the signal indicating a change from a first display position to a second display position; the first representation including a first feature near the first display position, the first feature representing a first part of the node-link structure; and

in response to the signal, automatically providing second representation data to the display, the second representation data causing the display to present a second representation of the node-link structure on the display; the second representation including a second feature representing the first part of the node-link structure, the second feature being presented near the second display position; the second representation being perceptible as a changed continuation of the first representation.

25. An article of manufacture for use in a system that includes:

memory;

a storage medium access device;

user input circuitry for providing data indicating signals from a user;

a display;

a processor connected for accessing data stored in the memory, for receiving data accessed on a storage medium by the storage medium access device, and for providing data to cause presentation of images by the display; and

layout data stored in the memory; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch;

the article of manufacture comprising:

a storage medium; and

instruction data stored by the storage medium; the instruction data including data units positioned on the storage medium so that the storage medium access device can access the data units and provide the data units to the processor in a sequence; the data units, when in the sequence, indicating instructions the processor can execute; the processor, in executing the instructions:

using the layout data to provide first representation data to the display, the first representation data causing the display to present a first representation of the node-link structure;

receiving a signal from a user; the signal indicating a change from a first display position to a second display position; the first representation including a first feature near the first display position, the first feature representing a first part of the node-link structure; and

in response to the signal, automatically providing second representation data to the display, the second representation data causing the display to present a second representation of the node-link structure on the display; the second representation including a second feature representing the first part of the node-link structure, the second feature being presented near the second display position; the second representation being perceptible as a changed continuation of the first representation.

26. A method of operating a first machine that includes:

first memory;

a first connection to a network;

a first processor connected for accessing data stored in the first memory and for establishing connections with other machines over the network through the first connection; and

instruction data stored in the first memory; the instruction data indicating instructions that can be executed by a second machine, the second machine including:

second memory;

a second connection to the network;

a second processor connected for accessing data stored in the second memory and for establishing connections with other machines over the network through the second connection; and

layout data stored in the memory; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch;

the method comprising:

operating the first processor to establish a connection to the second processor over the network through the first and second connections; and

operating the first processor to transfer the instruction data over the network to the second processor so that the second processor can store the instruction data in the second memory and can execute the instructions indicated by the instruction data; the second processor, in executing the instructions indicated by the instruction data:

using the layout data to provide first representation data to the display, the first representation data causing the display to present a first representation of the node-link structure;

receiving a signal from a user; the signal indicating a change from a first display position to a second display position; the first representation including a first feature near the first display position, the first feature representing a first part of the node-link structure; and

in response to the signal, automatically providing second representation data to the display, the second representation data causing the display to present a second representation of the node-link structure on the display; the second representation including a second feature representing the first part of the node-link structure, the second feature being presented near the second display position; the second representation being perceptible as a changed continuation of the first representation.

27. A method of operating a machine; the machine including:

memory;

a processor connected for accessing data stored in the memory; and

node-link data stored in the memory; the node-link data defining a node-link structure; the node-link structure including nodes and links, each link relating at least two of the nodes;

the method comprising:

operating the processor to use the node-link data to obtain layout data; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch; and

operating the processor to use the layout data to perform two or more different mappings; each mapping obtaining mapped data; the mapped data obtained by each mapping indicating positions for a subset of the set of nodes.

28. The method of claim 27 in which the layout space is a discrete approximation of a hyperbolic plane.

29. The method of claim 28 in which the layout data indicate, for each of the set of nodes, first and second coordinates; the first and second coordinates together indicating a position in the hyperbolic plane.

30. The method of claim 27 in which the node-link structure is an acyclic graph.

31. The method of claim 30 in which the node-link structure is a tree.

32. The method of claim 27 in which the branch is an exponentially growing branch.

33. The method of claim 27 in which the branch includes a parent node that is the top level node, the parent node having two or more child nodes at a first lower level; the act of operating the processor to use the node-link data to obtain layout data comprising:

obtaining parent node data indicating, for the parent node, a parent position and a parent wedge in the layout space; the parent wedge having a vertex at the parent position; the parent wedge being a part of the layout space between two rays extending from the vertex; and

using the parent node data to obtain child node data for each of the child nodes; each child node's child node data indicating, for the child node, a child position in the layout space; each of the child positions being approximately along an arc that is within the parent wedge, the arc being part of a circle that is centered at the vertex.

34. The method of claim 33 in which the parent wedge has a wedge angle formed by the two rays at the vertex; the wedge angle being less than 360.degree.; each child node's child node data indicating, for the child node, a child wedge; each child node's child wedge having a vertex at the node's child position, the child wedge being a part of the parent wedge between two rays extending from the vertex, the two rays forming an angle approximately equal to the wedge angle at the vertex; the child wedges not overlapping.

35. The method of claim 33 in which the branch includes descendant nodes at lower levels below the first lower level, each descendant node being related to first or second ones of the children nodes through one or more links; more of the descendant nodes at one of the lower levels below the first lower level being related to the first child node than to the second child node so that if the descendant nodes were uniformly spaced, the descendant nodes related to the first child node would occupy a larger angle than the descendant nodes related to the second children node; each child node's child node data indicating, for the child node, a child wedge; each child node's child wedge having a vertex at the node's child position, the child wedge being a part of the parent wedge between two rays extending from the child wedge's vertex, the two rays forming a wedge angle at the child wedge's vertex; the wedge angle of each child node's child wedge depending on the angle that would be occupied by descendant nodes related to the child node, the first child node having a larger wedge angle than the second child node; the child wedges of the child nodes not overlapping.

36. The method of claim 33 in which the parent node of the branch is the root node of a tree; the two rays being identical so that the parent wedge includes all of the space with negative curvature.

37. The method of claim 33 in which adjacent child positions are equally separated along the arc by the base spacing.

38. A machine comprising:

memory;

a display;

a processor connected for accessing data stored in the memory and for providing data to cause presentation of images by the display;

node-link data stored in the memory; the node-link data defining a node-link structure that includes nodes and links, each link relating at least two of the nodes; and

program data stored in the memory; the data program indicating instructions the processor executes; the processor, in executing the instructions:

using the node-link data to obtain layout data; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch; and

using the layout data to perform two or more different mappings; each mapping obtaining mapped data; the mapped data obtained by each mapping indicating positions for a subset of the set of nodes.

39. An article of manufacture for use in a machine that includes:

memory;

a storage medium access device;

a display;

a processor connected for accessing data stored in the memory, for receiving data accessed on a storage medium by the storage medium access device, and for providing data to cause presentation of images by the display; and

node-link data stored in the memory; the node-link data defining a node-link structure that includes nodes and links, each link relating at least two of the nodes;

the article of manufacture comprising:

a storage medium; and

instruction data stored by the storage medium; the instruction data including data units positioned on the storage medium so that the storage medium access device can access the data units and provide the data units to the processor in a sequence; the data units, when in the sequence, indicating instructions the processor can execute; the processor, in executing the instructions:

using the node-link data to obtain layout data; the layout data indicating positions in a layout space for parts of a node-link structure; the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch; and

using the layout data to perform two or more different mappings; each mapping obtaining mapped data; the mapped data obtained by each mapping indicating positions for a subset of the set of nodes.

40. A method of operating a first machine that includes:

first memory;

a first connection to a network;

a first processor connected for accessing data stored in the first memory and for establishing connections with other machines over the network through the first connection; and

instruction data stored in the first memory; the instruction data indicating instructions that can be executed by a second machine, the second machine including:

second memory;

a second connection to the network;

a second processor connected for accessing data stored in the second memory and for establishing connections with other machines over the network through the second connection; and

node-link data stored in the second memory; the node-link data defining a node-link structure that includes nodes and links, each link relating at least two of the nodes;

the method comprising:

operating the first processor to establish a connection to the second processor over the network through the first and second connections; and

operating the first processor to transfer the instruction data over the network to the second processor so that the second processor can store the instruction data in the second memory and can execute the instructions indicated by the instruction data; the second processor, in executing the instructions indicated by the instruction data:

using the node-link data to obtain layout data; the layout data indicating positions in a layout space for parts of a node-link structure;

the layout space being a space with negative curvature; the node-link structure including nodes and links, each link relating at least two of the nodes; the layout data indicating positions in the layout space for a set of the nodes; the set of nodes forming a branch that includes two or more levels of nodes including a top level and at least one lower level, the top level including a top level node and the lower levels including lower level nodes, each node at each lower level having a parent node at a next higher level to which the node is related through one link; for each of a set of two or more parent nodes, the layout data indicating:

a parent position in the layout space for the parent node; and

child positions that lie approximately along a circle in the layout space for a number of lower level nodes that share the parent node, the parent position being approximately at the center of the circle; the number of lower level nodes being two or more; adjacent child positions along the circle being separated by approximately a base spacing;

the circles having radii that, together, approximate a function that increases slowly with number of lower level nodes such that the radii and spacings between adjacent child positions along circles are all approximately uniform within the branch; and

using the layout data to perform two or more different mappings; each mapping obtaining mapped data; the mapped data obtained by each mapping indicating positions for a subset of the set of nodes.