Method for generating a preferred processing order and for detecting cycles in a directed graph used to represent system component connectivity

A method for operating a digital computer to generate a processing order array and to detect cycles in a directed graph having an array of vertices and an array of arcs connecting pairs of vertices, each arc being defined by a starting vertex and an ending vertex, wherein the array of vertices and the array of arcs may be randomly-ordered, and wherein each vertex represents a component in a system and each are represents a logical relationship between a plurality of components in the system, each vertex being assigned or unassigned to the processing order array and being electronically marked as a leaf vertex or a non-leaf vertex, comprising the steps of operating a computer to:

• (a) initialize each vertex in the array of vertices to be unassigned to the processing order array;
• (b) electronically mark each vertex in the array of vertices as a leaf vertex;
• (c) traverse the array of arcs and electronically mark the starting vertex as a non-leaf vertex for each arc having an ending vertex that is unassigned to the processing order array;
• (d) traverse the array of vertices and for each vertex that is unassigned to the processing order array and electronically marked as a leaf vertex, assign the vertex to the processing order array, and for each vertex that is unassigned to the processing order array and electronically marked as a non-leaf vertex, electronically mark the vertex as a leaf vertex;
• (e) indicate that a cycle exists in the directed graph when there are unassigned vertices remaining in the array of vertices and no vertices were assigned to the processing order array during said step (d);
• and
• (f) repeat said steps (c)-(e) if there are vertices in the array of vertices that are unassigned to the processing order array and no cycle was indicated in said step (e).

A computer-implemented method for generating a processing order and for detecting cycles in a directed graph having an array of vertices and an array of arcs connecting pairs of vertices, wherein the array of vertices and the array of arcs may be randomly-ordered, and wherein each vertex represents a component in a system and each arc represents a logical relationship between a plurality of components in the system, each arc being defined by a starting vertex and an ending vertex, each vertex being assigned or unassigned to a position in a preliminary processing order array and being electronically marked as a leaf vertex or a non-leaf vertex, a parent vertex being the starting vertex and a corresponding child vertex being the ending vertex for any arc, comprising the steps of:

• (a) initializing a next available position in the preliminary processing order array to the first position in the preliminary processing order array;
• (b) initializing each vertex in the array of vertices to be unassigned to any position in the preliminary processing order array;
• (c) electronically marking each vertex in the array of vertices as a leaf vertex;
• (d) traversing the array of arcs and electronically marking the starting vertex as a non-leaf vertex for each arc whose ending vertex is unassigned to any position in the preliminary processing order array;
• (e) traversing the array of vertices and for each vertex that is unassigned to any position in the preliminary processing order array and electronically marked as a leaf vertex, incrementing said next available position and assigning the vertex to said next available position in the preliminary processing order array, and for each vertex that is unassigned to any position in the preliminary processing order array and electronically marked as a non-leaf vertex, electronically marking the vertex as a leaf vertex;
• (f) indicating that a cycle exists in the directed graph when there are unassigned vertices remaining in the array of vertices and no vertices were assigned positions in the preliminary processing order array during said step (e);
• (g) repeating said steps (d)-(f) if there are vertices in the array of vertices that are unassigned to any positions in the preliminary processing order array and no cycle was indicated in said step (f);
• and
• (h) generating a final processing order array from the positions of the vertices in the preliminary processing order array such that each vertex in the array of vertices will be processed in a predetermined order.

An apparatus for producing a processing order for the components in a system and for detecting recursion in the system definition, the components being represented as vertices in a directed graph, the arcs of the directed graph representing a logical relationship between selected vertices, each arc being defined by a starting vertex and an ending vertex, each vertex being assigned or unassigned to a processing order array and being marked as a leaf vertex or a non-leaf vertex, the directed graph being input to the apparatus, the apparatus comprising:

• initialization means for electronically marking each vertex as a leaf vertex which is not assigned a processing order in the processor order array;
• arc traversal means for traversing an array of arcs and for electronically marking the starting vertex as a non-leaf vertex for each arc whose ending vertex is unassigned to the processing order array;
• vertex traversal means for traversing an array of vertices and for each vertex that is unassigned to the processing order array and electronically marked as a leaf vertex, assigning that vertex to the processing order array to establish the processing order for the components in the system, and for each vertex that is unassigned to the processing order array and electronically marked as a non-leaf vertex, electronically marking that vertex as a leaf vertex in said array of vertices;
• and
• recursion detection means for detecting that recursion exists in the system when there are unassigned vertices remaining in said array of vertices and no vertices were assigned to the processing order array by said vertex traversal means.

An apparatus for producing a processing order for the components in a system and for detecting recursion in the system definition, the components being represented as vertices in a directed graph, the arcs of the directed graph representing a logical relationship between selected vertices, each arc being defined by a starting vertex and an ending vertex, each vertex being assigned or unassigned to a processing order array and being electronically marked as a leaf vertex or a non-leaf vertex, the directed graph being input to the apparatus, the apparatus comprising:

• initialization means for initially marking each vertex as a leaf vertex which is unassigned to the processing order array;
• arc traversal means for traversing an array of arcs and for electronically marking the starting vertex as a non-leaf vertex for each arc having an ending vertex that is unassigned to the processing order array;
• vertex traversal means for traversing an array of vertices and for each vertex that is unassigned to the processing order array and electronically marked as a leaf vertex, assigning the vertex to the processing order array whereby the processing order is established for the components in the system, and for each vertex that is unassigned to the processing order array and electronically marked as a non-leaf vertex, electronically marking the vertex as a leaf vertex;
• and
• recursion detection means coupled to said arc traversal means and said vertex traversal means for detecting that recursion exists in the system when there are unassigned vertices remaining in said array of vertices and no vertices were assigned to the processing order array by said vertex traversal means.

For use with a data base storing representations of electronic components, selected hierarchical ones of the electronic components being defined as an interconnection of one or more associated ones of the electronic components, wherein each of the selected hierarchical ones of the electronic components is defined as a parent component and each of the associated ones of the electronic components is defined as an associated child component, the data base further storing a representation of a circuit design comprising the interconnection of included ones of the electronic components, a method for determining a final predetermined processing order of the included ones of the electronic components and for determining whether a recursion exists wherein an included one of the electronic components is a selected hierarchical one of the electronic components defined as a circuit design containing that selected hierarchical one of the electronic components, comprising the steps of:

• (a) designating each of the included ones of the electronic components as being an entry in an unordered list of components and having a first predetermined designation indicative of not being a selected hierarchical one of the electronic components;
• (b) marking each of the parent components in said unordered list of components with a second predetermined designation if the parent component in said unordered list of components has an associated child component in said unordered list of components, said second predetermined designation indicative of said marked parent component being defined as an interconnection of one or more other ones of the electronic components in said unordered list of components;
• (c) assigning each component in said unordered list of components which is designated with said first predetermined designation to a processing order, and removing said component from said unordered list of components;
• (d) assigning said first predetermined designation to each component in said unordered list which is designated with said second predetermined designation;
• (e) indicating that a recursion exists if components remain in said unordered list of components and no component was assigned to said processing order in said step (c);
• (f) repeating said steps (b) through (e) if there are components in said unordered list of components and no recursion was indicated in said step (e);
• (g) generating the final predetermined processing order from said processing order.

For use with a data base storing representations of electronic components, selected hierarchical ones of the electronic components being defined as an interconnection of one or more associated ones of the electronic components, wherein each of the selected hierarchical ones of the electronic components is defined as a parent component and each of the associated ones of the electronic components is defined as an associated child component, the data base further storing a representation of a hierarchical circuit design comprising the interconnection of included ones of the electronic components, an apparatus for determining a final predetermined processing order of the included ones of the electronic components and for determining whether a recursion exists wherein an included one of the electronic components is a selected hierarchical one of the electronic components defined as a circuit design containing that selected hierarchical one of the electronic components, the apparatus comprising:

• initialization means for designating each of the included ones of the electronic components as being an entry in an unordered list of components and as having a first predetermined designation indicative of said designated electronic component not being one of the selected hierarchical ones of the electronic components;
• first processing means for designating each of the parent components in said unordered list of components with a second predetermined designation if the parent component in said unordered list of components has an associated child component in said unordered list of components;
• second processing means for assigning each component in said unordered list of components which is designated with said first predetermined designation to a processing order, and removing said assigned component from said unordered list of components, and for further assigning said first predetermined designation to each component in said unordered list which is designated with said second predetermined designation;
• and
• recursion detection means for detecting that a recursion exists if components remain in said unordered list of components and no component was assigned to said processing order by said second processing means.