Patent ID: 7861193

Claim:
A method for identifying instances of a smaller circuit in a larger circuit, both the smaller circuit and the larger circuit having a plurality of vertices, each of the plurality of vertices is one of a device or a net, the device having a Gate, a Drain, and a Source, the method being executed by a processor comprising: recursively relabeling of each of the plurality of vertices until labels of all neighboring vertices of a selected vertex are NULL, the neighboring vertices of a vertex are vertices that are directly connected to the vertex, wherein each successive iteration of the relabeling uses labels of each of the plurality of vertices after a previous iteration of the relabeling; and recursively performing circuit tracing operation starting from the selected vertex until each of the plurality of vertices in the smaller circuit is matched with one of the plurality of vertices in the larger circuit, the circuit tracing operation includes matching a label of each of the plurality of vertices neighboring the selected vertex in the smaller circuit with a label of each of the plurality of vertices in the larger circuit neighboring a vertex corresponding to the selected vertex, wherein labels at a same depth of relabeling iteration being matched, and wherein an identification of the smaller circuit in the larger circuit is performed by comparing a label of a selected vertex of the smaller circuit with a plurality of labels in the larger circuit, wherein the comparing of the label is performed after a same number of relabeling iterations has been performed on both the smaller circuit and the larger circuit.