Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
1998-07-29
2002-04-23
Cuchlinski, Jr., William A. (Department: 3661)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
C707S793000
Reexamination Certificate
active
06377259
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to presenting a node-link structure in which modification occurs.
BACKGROUND AND SUMMARY OF THE INVENTION
Lamping, J. and Rao, R., “The Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchies”,
Journal of Visual Languages and Computing
, Vol. 7, 1996, pp. 33-55, disclose techniques for displaying a hierarchy in which components diminish in size as they move outwards and the number of components grows exponentially with increasing radius. The display can be smoothly transformed to change the node at the center or focus. Animated transitions between different views maintain object constancy, helping a user assimilate changes. For quick redisplay, less of a fringe is drawn, lines can be drawn rather than arcs, and text can be dropped during animation. Lamping et al., U.S. Pat. No. 5,619,632, disclose a browser that employs similar techniques for presenting a node-link structure and mention that a browser could be used in editing structures.
Matsuura, T., Taniguchi, K., Masuda, S., and Nakamura, T., “A Graph Editor for Large Trees with Browsing and Zooming Capabilities”,
Systems and Computers in Japan
, Vol. 24, No. 8, 1993, pp. 35-46, disclose a library program which allows direct manipulation of a large tree on a display. When a node or subtree is added or deleted, the data structure is updated; the layout for each node is calculated based on the graph layout algorithm, and each node and edge is redrawn. When nodes are added or deleted consecutively, a single update of the display can be performed after all the modifications have been made. A viewport includes a global view and a canvas, and updating depends on mode, which may be automatic update, partial update, or on demand update. Partial update resembles on demand update, but an intermediate display node is displayed temporarily.
Beaudet et al., U.S. Pat. No. 5,515,487, disclose selective display of portions of graphics by expanding and collapsing nodes in trees, directed acyclic graphs, and cyclic graphs. Nodes are selected for modification, all nodes connected to each selected node is assigned to a first set of nodes, and then each node is removed from the first set of nodes and assigned to a second set, together with any connected nodes that are not in the first set. The identified nodes are deleted from the display, and each node connected to a deleted node is highlighted, surrounded by an outline box, shown with outgoing arcs, or otherwise shown in a way that distinguishes collapsed nodes.
Windows NT Explorer is a program that can be used to see the hierarchy of folders on a disk drive. The hierarchy is presented as a list of items, with indentation showing which items are children of other items. Some folders are presented with plus signs (+), and if the user does a mouse click on a plus sign, more folders will be displayed. Windows NT also provides a similar program that can be used to see a hierarchy of network resources.
The invention addresses problems in presenting node-link structures that change.
A node-link structure can change in several situations. For example, if the structure is large, the data available at a given time may only define part of the structure. This may occur because data defining the complete structure has not yet arrived or because the structure is so large that memory is not large enough to hold a complete definition of it. In such cases, a partial structure is held in memory, to be changed as additional data arrives or is retrieved.
Another situation in which a node-link structure changes is when the structure is a partial version of an underlying structure. For example, the user may request that specified types of nodes or links be selected to obtain a filtered version. In response, a node-link structure is produced that omits nodes and links that are not selected by the filter criterion, allowing more space for nodes and links of interest. Or the structure can be a tree that represents an underlying directed graph (DG) structure in which there are multiple in-links to a node in the DG that in turn has children. In one approach, the DG node is represented by multiple parent nodes in the tree, each with one of the in-links, but the DG node's children are represented with only one of the parent nodes in the tree. In response to user input, the parent node with which the children are represented can change, thus changing the tree structure (but not the DG).
Also, the underlying structure may itself change. For example, it may be modified in response to processes other than the browser through which it is being viewed. Or it may be modified in response to user requests through the browser interface.
A node-link structure that changes in any of these ways is referred to herein as a “dynamic node-link structure”. This term therefore includes not only underlying node-link structures that change, but also partial versions that change or are obtained differently from an underlying node-link structure, which may itself be either static or dynamic.
The presentation techniques described by Lamping and Rao and other conventional techniques can lead to problems with structure change during presentation. Typically, a new layout must be done for at least part of the changed structure and then it must be redisplayed. Therefore, when a change occurs in a structure being presented with such techniques, there is often an abrupt or discontinuous transition to a representation of the changed structure. In some cases, layout and redisplay is so slow that a user cannot effectively interact with the changed structure. Further, layout and redisplay do not provide a way to animate the transition from the old to the new structure, which would improve the user's understanding of the transition. Therefore, many conventional presentation techniques only produce satisfactory results for static node-link structures, and are not suitable for dynamic node-link structures.
Some conventional presentation techniques can, however, animate transitions to expand or contract an item on a hierarchical list. These techniques are limited however to one modification, either an expansion or a contraction, and therefore are difficult to generalize to all transitions.
The invention alleviates problems in presenting dynamic node-link structures by providing techniques that make it easier for a user to understand a broader range of transitions. Each technique presents a sequence of representations, the first of which represents a first node-link structure and the last of which represents a second node-link structure that is a modified version of the first node-link structure. The elements shared by the first and last structures include a moving element represented by features that have different positions in the first and last representations. Between the first representation and the last representation, the techniques present at least one intermediate representation. Each representation in the sequence includes features representing a subset of the shared elements that includes the moving element. The feature representing the moving element has object constancy through the sequence of steps.
In one aspect of the invention, the second node-link structure is a modified version with at least one insertion and at least one deletion in the first node-link structure. For example, an element could be deleted from one position and inserted at another position. Therefore, techniques according to this aspect, referred to as “deletion and insertion” herein, could be used to move an element or to make more complicated changes, in cluding multiple deletions and insertions.
Each of the new deletion and insertion t techniques presents a sequence of images in which the area of an element being deleted or inserted changes, either decreasing or increasing in each successive image. At the same time, compensating area changes occur in nearby elements. If the area changes are appropriately chosen, the sequence of images will produce the impression that, in deletion, n
Lamping John O.
Rao Ramana B.
Tenev Tichomir G.
Cuchlinski Jr. William A.
Haynes Mark A.
Haynes Beffel & Wolfeld LLP
Inxight Software, Inc.
Nguyen Thu
LandOfFree
Presenting node-link structures with modification does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Presenting node-link structures with modification, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Presenting node-link structures with modification will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2877187