Importance

Loading Importance Indicators...

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.

Loading the Abstract Image...

First Claim