Patent ID: 11966682
Assignee: INTERNATIONAL BUSINESS MACHINES CORPORATION
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A method comprising:
creating, using at least one hardware processor, a constraint graph for a candidate routing solution, wherein each node in the constraint graph represents a position of an end of a metal shape and each arc in the constraint graph represents a design rule constraint between two of the nodes of the constraint graph;
computing, using the at least one hardware processor, a solution graph for at least a portion of the constraint graph using a shape processing algorithm;
checking, using the at least one hardware processor, the solution graph for design rule violations to generate one or more violation graphs, wherein each arc in the violation graph represents a design rule constraint between two of the nodes of the violation graph;
generating, using the at least one hardware processor, a constraint window and a selection of one or more arcs for at least one of the violation graphs; and
revising, using the at least one hardware processor, the candidate routing solution based on one or more violated design rules corresponding to at least one of the selected arcs within the constraint window.