收藏切换
A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards
收藏切换
Xinguo Deng1, Xinhong Zhang1, Jiarui Chen1, *, Qinghai Liu2, 3, Chuandong Chen4
Journal of Computer Research and Development | 2025, 62(8) : 1948 - 1961
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(8): 1948-1961
• Computer Architecture •
A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards
Full
Xinguo Deng1, Xinhong Zhang1, Jiarui Chen1, *, Qinghai Liu2, 3, Chuandong Chen4
Affiliations
  • 1College of Computer and Data Science, Fuzhou University, Fuzhou 350108
  • 2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108
  • 3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024
  • 4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108
  • born in 1975. PhD, associate professor. His main research interest includes electronic design automation

    born in 1998. Master. His main research interest includes electronic design automation

    born in 1981. PhD, associate professor. His main research interest includes electronic design automation

    born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

    born in 1982. PhD, associate professor. His main research interest includes electronic design automation

About Author:

born in 1975. PhD, associate professor. His main research interest includes electronic design automation

born in 1998. Master. His main research interest includes electronic design automation

born in 1981. PhD, associate professor. His main research interest includes electronic design automation

born in 1982. PhD, professor. Member of CCF. His main research interests include graph theory and its application, combinatorial optimization, and electronic design automation

born in 1982. PhD, associate professor. His main research interest includes electronic design automation

Published: 2025-08-01 doi: 10.7544/issn1000-1239.202440069
Outline
收藏切换

Routing is considered as an essential component in the design of printed circuit board (PCB). Current existing PCB designs mostly rely on the process results from electronic design automation tools, and traditional automatic routing research often focuses on the only general bus routing without considering bus groups to be determined during the routing process. Due to the absence of general bus grouping, there may be situations where there are more nets in one group than in the other groups, resulting in larger line width and line clearance occupied by this group when compared with other bus groups in the original bus routing, thereby posing new challenges to effective and efficient routing. To overcome this drawback, we focus on studying PCB group routing. In this study, a group routing algorithm based on a weighted directed graph is proposed. A Hanan grid graph is constructed, containing the only merged edges and their adjacent relationships. Following this, a weighted directed graph is developed using the merged edge information to represent the routing resources on the circuit board. For routing planning, a heuristic search algorithm equipped with multi-wire avoidance features is utilized. The routing situations are then classified into several potential scenarios, with each considered separately, to accomplish detailed routing and obtain a final result of group routing. Results from experiments demonstrate that 100% routability is consistently achieved by using the algorithm on complex industrial examples that have been previously tested, and that the design rule constraints of all benchmark industrial PCB cases are not violated.

electronic design automation (EDA)  /  printed circuit board  /  group routing  /  weighted directed graph  /  path planning
邓新国, 张鑫泓, 陈家瑞, 刘清海, 陈传东. 一种基于带权有向图的印刷电路板群组布线算法. 计算机研究与发展, 2025 , 62 (8) : 1948 -1961 . DOI: 10.7544/issn1000-1239.202440069
Xinguo Deng, Xinhong Zhang, Jiarui Chen, Qinghai Liu, Chuandong Chen. A Weighted Directed Graph-Based Algorithm for Group Routing in Printed Circuit Boards[J]. Journal of Computer Research and Development, 2025 , 62 (8) : 1948 -1961 . DOI: 10.7544/issn1000-1239.202440069
Year 2025 volume 62 Issue 8
97
39
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202440069
  • Receive Date:2024-02-04
  • Online Date:2026-11-10
  • Published:2025-08-01
Article Data
Affiliations
History
  • Received:2024-02-04
  • Revised:2025-02-07
  • Accepted:2025-03-03
Affiliations
    1College of Computer and Data Science, Fuzhou University, Fuzhou 350108
    2Center for Discrete Mathematics, Fuzhou University, Fuzhou 350108
    3Fujian Science & Technology Innovation Laboratory for Optoelectronic Information of China, Fuzhou 350024
    4College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440069
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT