Patent US5450535A successfully refreshed from Google Patents.
US5450535A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Graphs employing clusters
Assignee: AT&T Inc
•
Filing: 1993-09-24
•
Granted: 1995-09-12
•
Expires: 2013-09-24
Abstract
Abstract Techniques for automatically laying out directed graphs with clusters of nodes and free nodes. The techniques produce pictorial representations of the graphs in which a node in a cluster and a free node may belong to the same rank in the graph and nodes belonging to more than one cluster may belong to the same rank. The techniques have been added to the well-known DOT system for laying out directed graphs, and include a recursive technique for ranking nodes of the graph, a technique for ordering nodes within ranks which collapses subclusters into skeletons when the nodes within a cluster are ordered, and a technique for positioning the nodes after they have been ranked and ordered which obtains the x coordinates for the nodes by producing an auxiliary graph which is in effect the original graph "turned on its side" and assigning ranks to the nodes in the auxiliary graph.
Inventors
- 👤 Stephen C. North
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 07:07
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/26
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
151 words
A method of using a computer system to automatically draw a directed graph, the directed graph and clusters therein being made up of free nodes which do not belong to contained clusters and bound nodes which do, the method including a step of assigning ranks to the nodes and the method being improved in that the step of assigning ranks comprises: recursively performing on the directed graph and the contained clusters contained therein steps including assigning relative ranks to each contained cluster, collapsing each contained cluster into a virtual node, and assigning relative ranks to the free nodes and virtual nodes; and on completion of the recursive steps, assigning absolute ranks to all nodes, with the rank of a free node within a cluster being determined by the absolute rank of the virtual node into which the cluster was collapsed and the relative rank of the free node within the cluster.
Claim 2
Independent Claim
151 words
A method of using a computer system to automatically draw a directed graph, the directed graph and clusters therein being made up of free nodes which do not belong to contained clusters and bound nodes which do, the method including a step of assigning ranks to the nodes and the method being improved in that the step of assigning ranks comprises: recursively performing on the directed graph and the contained clusters contained therein steps including assigning relative ranks to each contained cluster, collapsing each contained cluster into a virtual node, and assigning relative ranks to the free nodes and virtual nodes; and on completion of the recursive steps, assigning absolute ranks to all nodes, with the rank of a free node within a cluster being determined by the absolute rank of the virtual node into which the cluster was collapsed and the relative rank of the free node within the cluster.
Claim 3
Independent Claim
119 words
A method of using a computer system to automatically draw a directed graph of nodes which includes subgraphs grouped in clusters, the method including a step of assigning ranks to the nodes and the method being improved in that the step of assigning ranks to the nodes comprises: assigning a relative rank to each contained node or cluster contained in the graph or cluster which is relative to the graph or cluster which immediately contains the contained node or cluster; and assigning an absolute rank to each node or cluster which is determined from the absolute rank of the graph or cluster which immediately contains the contained node or cluster and the relative rank of the node or cluster.
Claim 4
Independent Claim
119 words
A method of using a computer system to automatically draw a directed graph of nodes which includes subgraphs grouped in clusters, the method including a step of assigning ranks to the nodes and the method being improved in that the step of assigning ranks to the nodes comprises: assigning a relative rank to each contained node or cluster contained in the graph or cluster which is relative to the graph or cluster which immediately contains the contained node or cluster; and assigning an absolute rank to each node or cluster which is determined from the absolute rank of the graph or cluster which immediately contains the contained node or cluster and the relative rank of the node or cluster.
Claim 5
Dependent Claim
48 words
The method set forth in claim 2 wherein: the step of assigning a relative rank is done by recursively performing steps including assigning relative ranks to each contained cluster; collapsing each contained cluster into a virtual node; and assigning relative ranks to the free nodes and virtual nodes.
Claim 6
Dependent Claim
33 words
The method set forth in claim 3 further comprising the step of: replacing edges whose endpoints are in contained clusters with a virtual node with edges connecting the virtual node to the endpoints.
Claim 7
Dependent Claim
43 words
The method set forth in claim 2 further comprising the step of: in each collapsed cluster, establishing ports for edges having endpoints in nodes belonging to the collapsed cluster corresponding to the relative ranks of the nodes which are endpoints of the edges.
Claim 8
Independent Claim
78 words
A method of using a computer system to automatically draw a directed graph of nodes which includes subgraphs grouped in clusters, the method including a step of ordering the nodes within a rank the method being improved in that the step of ordering the nodes within the rank comprises: collapsing each contained cluster immediately contained in the rank into a representation of the entire cluster; and ordering the nodes within the rank by treating the representations as nodes.
Claim 9
Independent Claim
78 words
A method of using a computer system to automatically draw a directed graph of nodes which includes subgraphs grouped in clusters, the method including a step of ordering the nodes within a rank the method being improved in that the step of ordering the nodes within the rank comprises: collapsing each contained cluster immediately contained in the rank into a representation of the entire cluster; and ordering the nodes within the rank by treating the representations as nodes.
Claim 10
Dependent Claim
72 words
The method set forth in claim 6 wherein the step of assigning ranks to the nodes further comprises the steps of: for each collapsed cluster, expanding the collapsed cluster while collapsing any contained cluster; ordering the nodes immediately contained in the expanded cluster together with the collapsed contained cluster; and reordering the nodes immediately contained in the expanded cluster and the other nodes in the rank as required for the expanded cluster,
Claim 11
Dependent Claim
32 words
The method set forth in claim 7 wherein: the step of reordering is such that a node in an expanded cluster does not change places with a node outside the expanded cluster.
Claim 12
Dependent Claim
26 words
The method set forth in claim 7 wherein: the step of expanding the collapsed cluster is performed recursively for each cluster contained in the collapsed cluster.
Claim 13
Independent Claim
61 words
The method set forth in any of claims 7, 8, or 9 wherein: the step of ordering the nodes within the rank, ordering the nodes immediately contained in the expanded cluster, or reordering the nodes immediately contained in the expanded cluster includes a step which determines how to reorder the nodes and any immediately-contained collapsed cluster to reduce crossings of edges.
Claim 14
Dependent Claim
60 words
The method set forth in claim 10 wherein: the step which determines how to reorder the nodes includes the steps of: assigning weighted constraint costs to the edges which include costs derived from internal ranks of nodes inside subclusters and determining the reordering by solving a series of linear programs to determine an ordering which minimizes the total constraint costs.
Claim 15
Independent Claim
188 words
A method of using a computer system to automatically draw a directed graph of nodes which include subgraphs grouped in clusters, the method having steps comprising: assigning ranks to the nodes, to the subgraphs, and to the nodes contained in the subgraphs; and ordering the nodes within the ranks in order to reduce the number of edges in the graph which cross other edges therein and the method having the improvement comprising: in the step of assigning ranks to the nodes, the steps of: assigning a relative rank to each node or cluster which is relative to the graph or cluster which immediately contains the node or cluster, and assigning an absolute rank to each node or cluster which is determined from the absolute rank of the graph or cluster which immediately contains the node or cluster and the relative rank of the node or cluster; and in the step of ordering the nodes within the ranks, the steps of: collapsing each cluster immediately contained in the rank into a representation of the entire cluster, and ordering the nodes within the rank by treating the representations as nodes.
Claim 16
Independent Claim
188 words
A method of using a computer system to automatically draw a directed graph of nodes which include subgraphs grouped in clusters, the method having steps comprising: assigning ranks to the nodes, to the subgraphs, and to the nodes contained in the subgraphs; and ordering the nodes within the ranks in order to reduce the number of edges in the graph which cross other edges therein and the method having the improvement comprising: in the step of assigning ranks to the nodes, the steps of: assigning a relative rank to each node or cluster which is relative to the graph or cluster which immediately contains the node or cluster, and assigning an absolute rank to each node or cluster which is determined from the absolute rank of the graph or cluster which immediately contains the node or cluster and the relative rank of the node or cluster; and in the step of ordering the nodes within the ranks, the steps of: collapsing each cluster immediately contained in the rank into a representation of the entire cluster, and ordering the nodes within the rank by treating the representations as nodes.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-11 | 1999-03-13 | 1999-09-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-11 | 2003-03-13 | 2003-09-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-11 | 2007-03-13 | 2007-09-12 | $7700.00 | Window Closed / Lapsed |