Node-link data defining a graph and a tree within the graph

• US 6,108,698 A
• Filed: 07/29/1998
• Issued: 08/22/2000
• Est. Priority Date: 07/29/1998
• Status: Expired due to Term

• Current Assignee: SAP America Incorporated (SAP SE)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Shinsato, Harold J. Jr., Lamping, John O., Rao, Ramana B., Tenev, Tichomir G.
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/124,338
• Time in Patent Office: 755 Days
• Field of Search: 709/220, 709/221, 709/222, 709/252, 709/253, 345/356, 345/357
• US Class Current: 709/220
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Node-link data defining a graph also include tree defining data. The node-link data with the tree defining data further define a tree within the graph. The tree defining data indicate a set of elements in the graph that are represented in the tree. Each of a subset of elements in the set is represented more than once in the tree. For at least one element in the subset, the tree defining data indicate which representations of the element have descendants in the tree and which representations have none. The tree defining data can, for example, be expansion flags for links in the graph that are in the set of elements, with each links expansion flag indicating whether the link'"'"'s to-node is expanded or contracted in the tree. In response to each of a series of expand and contract signals from a user, an iteration can modify the tree defining data and use it to present a representation of the graph with the indicated node expanded or contracted as requested.

Claims

1. A method of obtaining node-link data;

the method comprising;

(A) obtaining node-link data defining a graph;

in which (A) comprises;

obtaining tree defining data that are included in the node-link data;

the node-link data with the tree defining data further defining a tree within the graph;

the tree defining data indicating a set of elements in the graph that are represented in the tree;

a subset of elements in the set being represented more than once in the tree;

for at least one element in the subset, the tree defining data indicating which representations of the element have descendants in the tree and which representations of the element have no descendants in the tree.

2. The method of claim 1 in which the tree defining data comprise expansion/contraction data indicating, for each link in the set of elements, whether the link'"'"'s to-node is expanded or contracted.

3. The method of claim 2 in which the expansion/contraction data include, for each link in the set of elements, a flag indicating whether the link'"'"'s to-node is expanded or contracted.

4. The method of claim 3 in which the expansion/contraction data include, for the incoming links of each node in the set of elements, at most one link with a flag indicating that the node is expanded.

5. The method of claim 1 in which the tree defining data indicate at most one representation of the element in the tree that has descendants, all other representations of the element in the tree having no descendants.

6. The method of claim 1 in which (A) further comprises a series of iterations, each iteration obtaining respective tree defining data.

7. The method of claim 6 in which each iteration comprises:

receiving a navigation signal from a user;

responding to the navigation signal by obtaining the iteration'"'"'s tree defining data; and

using the node-link data including the iteration'"'"'s tree defining data to present a representation of the graph.

8. The method of claim 7 in which the navigation signal is an expand signal or a contract signal.

9. The method of claim 8 in which the navigation signal further indicates a node feature in the representation presented in the preceding iteration, the node feature representing a node in the graph, the representation further including a link feature leading to the node feature, the link feature representing an incoming link to the node in the graph.

10. The method of claim 9 in which the navigation signal is an expand signal, the act of obtaining the iteration'"'"'s tree defining data comprising:

modifying the previous iteration'"'"'s tree defining data to indicate that the incoming link represented by the link feature is expanded and that all other incoming links to the node in the graph are contracted.

11. The method of claim 9 in which the navigation signal is a contract signal, the act of obtaining the iteration'"'"'s tree defining data comprising:

modifying the previous iteration'"'"'s tree defining data to indicate that the incoming link represented by the link feature is contracted.

12. The method of claim 9 in which the node feature includes an indication of whether the node it represents is expanded or contracted in the tree.

13. A system for obtaining node-link data, the system comprising:

a processor for obtaining node-link data defining a graph;

the processor, in obtaining the node-link data, obtaining tree defining data that are included in the node-link data;

the node-link data with the tree defining data further defining a tree within the graph;

the tree defining data indicating a set of elements in the graph that are represented in the tree;

a subset of elements in the set being represented more than once in the tree;

for at least one element in the subset, the tree defining data indicating which representations of the element have descendants in the tree and which representations of the element have no descendant in the tree.

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

a storage medium access device; and

a processor connected for receiving data accessed on a storage medium by the storage medium access device;

the article of manufacture comprising;

a storage medium; and

instruction data stored by the storage medium;

the instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, obtaining node-link data defining a graph;

the processor, in obtaining the node-link data, obtaining tree defining data that are included in the node-link data;

the node-link data with the tree defining data further defining a tree within the graph;

the tree defining data indicating a set of elements in the graph that are represented in the tree;

a subset of elements in the set being represented more than once in the tree;

for at least one element in the subset, the tree defining data indicating which representations of the element have descendants in the tree and which representations of the element have no descendants in the tree.

15. A method of transferring data between first and second machines over a network, the second machine including memory and a processor connected for accessing the memory;

the memory being for storing instruction data;

the method comprising;

establishing a connection between the first and second machines over the network; and

operating the first and second machines to transfer instruction data from the first machine to the memory of the second machine;

the instruction data indicating instructions the processor can execute;

the processor, in executing the instructions, obtaining node-link data defining a graph;

the processor, in obtaining the node-link data, obtaining tree defining data that are included in the node-link data;

the node-link data with the tree defining data further defining a tree within the graph;

the tree defining data indicating a set of elements in the graph that are represented in the tree;

a subset of elements in the set being represented more than once in the tree;

for at least one element in the subset, the tree defining data indicating which representations of the element have descendants in the tree and which representations of the element have no descendants in the tree.