Patent ID: 7913209

Claim:
A method for determining a basis for a plurality of cycles within a directed graph, comprising: inputting a specification of the directed graph, the directed graph modeling a circuit and including a plurality of nodes that represent circuit elements of the circuit and including a plurality of edges that represent connections between the circuit elements and that are each directed from one to another of the nodes; performing, using a processor, a first depth-first search of the directed graph, wherein nodes and edges visited in the first depth-first search form a tree, and wherein the first depth-first search classifies each of the edges of the directed graph to have a type that is one of a within-tree type for an edge within the tree, a forward type for an edge skipping forward along the tree, a back type for an edge directed back along the tree, or a cross type for an edge between two subtrees of the tree; performing a second depth-first search of the directed graph that determines a respective first cycle for each of the edges of the back type, wherein the respective first cycle is a cycle of the edge of the back type and at least one edge of the within-tree type; performing a third depth-first search of the directed graph that determines a respective second cycle for each of the edges of the cross type included a cycle, wherein the respective second cycle is a cycle of the edge of the cross type and a plurality of edges of the within-tree, back, or cross types; and outputting the basis that specifies each of the respective first cycles and each of the respective second cycles.