Subgraph Search Algorithm For A Circuit Design And Realization

Under the severe market competition, electronic companies have to develop new circuit design methods that help companies to reuse design of circuit, improve design efficiency and quality of circuit, shorten design cycle and deal with increasing design complexity. In PCB design field, there is a type of circuit design subgraph search technology that can help electronic companies to reuse PCB design, and then improve efficiency and quality of PCB design.The paper studies circuit design subgraph search algorithm and puts forward a new search algorithm that bases on circuit character .The new search algorithm makes use of depth first search and recursion idea, and valuable information included in circuit NETLIST, which regards connection of pins in selected module circuit as basic map unit, and searches in two levels, namely symbol level and pin level. It also thinks over complexity of circuit graph and uses some effective optimization methods which improve search speed of basic map unit, for example temporary component map table frequent component strategy and basic map unit first select strategy. Optimization methods reduce remarkably search time and advance search preciseness of algorithm.The algorithm is one of main research objects of EDA research department in a communication equipment manufacture company, and it is certificated by some experts in the company, meanwhile it has put in for patent.