Computer graphics processing and selective visual display system – Computer graphics processing – Graph generating
Reexamination Certificate
2000-11-21
2004-10-05
Brier, Jeffery (Department: 2672)
Computer graphics processing and selective visual display system
Computer graphics processing
Graph generating
Reexamination Certificate
active
06801200
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to data structures, and more particularly to visual representations of relationships among data structures.
COPYRIGHT NOTICE/PERMISSION
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright© 1997, Microsoft Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
Diagrams are frequently used to enable human beings to comprehend complex relationships between items, such as data base records or computer programming objects. The relationships are usually visually represented as lines (connectors) drawn between nodes that represent the items. When a diagram is small (approximately 10 nodes or less), a user can easily arrange the diagram by hand to be readable. However, larger diagrams make hand-placement of nodes a tedious, non-trivial, time-consuming task. Although diagrams are most valuable when dealing with hundreds of nodes and hundreds of connectors, the value is severely diminished when the user has to manipulate the nodes and connectors to make the diagram understandable.
Therefore, there have been many attempts to develop a computer application that lays out diagrams in a way that is both quick and very easy to read. However, all of the currently available applications fail to entirely address the problem from both the standpoints of speed and resulting readability.
For example, using seventy-two nodes and over one hundred connectors, Vision® by Visio Corp. requires approximately thirty seconds to create a diagram, related nodes are not clustered together, and the nodes are so densely packed together that the resulting diagram is not easily readable by a human being. Erwin™ by LogicWorks, Inc. lays out the same number of nodes and connectors in approximately ten seconds, but also does not cluster related nodes. Graphing software from Tom Sawyer Software is faster than Erwin™ but outputs a diagram that is also difficult to read because related nodes are not clustered and because the nodes are dispersed over a wide area, making the connectors excessively long.
Therefore, the need for a layout application that creates a node and connector diagram that is easily understood and quickly created.
SUMMARY OF THE INVENTION
The above-mentioned shortcomings, disadvantages and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
A rectilinear layout system creates a diagram (graph) from information about items (nodes) and relationships among the items, such as the information which defines data bases, computer networks, and object based systems. The rectilinear layout system designates one of the items as a focus node and partitions the remaining items into clusters (sub-graphs) of related nodes. Multiple location groups are created that are relative to the focus node for the graph and each sub-graph is assigned to a location group. The rectilinear layout system then plots a location for each node in each of the sub-graphs by recursively iterating through the sub-graphs, designating a focus node for each sub-graph, creating lower level sub-graphs, and assigning the lower level sub-graphs to location groups relative to the corresponding focus node until a lower level sub-graph contains only a single node. At that point, the rectilinear layout system plots the single node on to a layout surface for the lower level sub-graph and returns up a level. Once all nodes in a sub-graph have been plotted, the rectilinear layout system routes connectors among the nodes to represent the relationship among the nodes. The rectilinear layout system continues its recursive functions until all sub-graphs have been laid out. The rectilinear layout system then plots absolute coordinates for the focus node for the graph, the nodes of the sub-graphs, and the connectors within the sub-graphs, and creates connectors among the focus node for the graph and the appropriate nodes of the sub-graphs.
In one aspect of the invention, the item with the most relationships is designated as the focus node, with the size of the node used to represent the item in the graph used as a tie-breaker. The style of the graph is dependent on which of the different location groups are used and the order in which sub-graphs are assigned to them. Potential connector routes for previously plotted nodes are also taken into account when assigning a sub-graph to a location group. Data structures used to manage the nodes and connectors at various levels of sub-graphs are also described.
In a further aspect of the invention, eight software modules are described which implement the rectilinear layout system in the Microsoft Database Designer system.
The rectilinear layout system addresses the problem of readability of a complex diagram by selecting the focus nodes for the various levels based on the maximum number of nodal relationships, thereby clustering related nodes together. Positioning the focus nodes at the center of the corresponding layout surface makes the related nodes easier to locate and the connections among the nodes easier to navigate.
The rectilinear layout system also addresses the performance issues common in other graphing solutions. The rectilinear layout system employs a unique two-block procedure to position a node or a sub-graph around its focus without costly backtracking, i.e., making two passes through the information defining the nodes and relationships, and in the second pass repositions the nodes that have been already positioned in the first pass. The first block of the rectilinear layout system recursively partitions the graph and valid candidate locations for the node/sub-graph are calculated. In the second block of the rectilinear layout system, the graph is recursively constructed by calculating the actual x-y coordinates for the node/sub-graph on the valid locations.
Furthermore, performance is improved because connector routing is completely localized at each sub-graph level since there is no connection between two non-focus nodes at different sub-graph levels. This makes it possible to eliminate line crossing at each sub-graph level without having to re-route connectors that have already been routed, thus avoiding the costly routing backtracking present in other systems.
As a result, the graphs produced by the rectilinear layout system have several beneficial characteristics. A graph contains one or more clusters of nodes in which the nodes are usually grouped closer relative to each other than nodes in different clusters, thus visually indicating their close relationships and correlating the relationships with the nodes. The benefits of this characteristic are most obvious when dealing with complex diagrams as the relationships in such diagrams are much clearer when laid out with the rectilinear layout system. Each cluster in a graph contains one focus node with distinct syntactic or semantic features and the clusters are positioned in such a way that they can be easily located and navigated by a human being. Finally, nodes and sub-graphs within a cluster can be positioned symmetrically around the focus node, which aids in the understanding of the connectivity within clusters.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.
REFERENCES:
patent: 5321816 (1994-06-01), Rogan
patent: 5684807 (1997-11-01), Bianchini, Jr.
patent: 5808615 (1998-09-01), Hi
Budzianowski Shoshanna K.
Ling Xiaoning
Prakriya Mahesh
Amini Javid
Brier Jeffery
Microsoft Corporation
Woodcock & Washburn LLP
LandOfFree
Layout of data structures based on relationships between the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Layout of data structures based on relationships between the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Layout of data structures based on relationships between the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3266688