The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
May. 27, 1997
Filed:
Dec. 13, 1994
John T Rusterholz, Roseville, MN (US);
Unisys Corporation, Blue Bell, PA (US);
Abstract
A method used by a digital computer for generating a preferred processing order of the vertices in a directed graph. The method also detects any cycles that exist in the directed graph. The vertices of the directed graph represent components of a system and the arcs represent the interrelationships between components. Each arc is defined by a vertex pair consisting of a starting vertex and an ending vertex. Each vertex is either assigned or unassigned to a processing order and marked as either a leaf vertex or a non-leaf vertex. The method includes traversing the set of arcs of the directed graph and marking the starting vertex as a non-leaf vertex for each arc whose ending vertex is unassigned, traversing the set of vertices and for each vertex that is unassigned and a leaf vertex, assigning the vertex to the processing order; and for each vertex that is unassigned and a non-leaf vertex, marking it as a leaf vertex. If unassigned vertices remain in the set of vertices and no vertices were assigned to the processing order then a cycle exists in the directed graph. These steps are repeated as long as there are vertices in the set of vertices that are unassigned and no cycle has been detected.