Parallel reduction and context-sensitive incremental update method for large-scale wiring harness topology

doi:10.11996/JG.j.2095-302X.2026040820

Abstract

Abstract:

The evolution of automotive electrical/electronic architectures increases the design complexity of wiring harness systems and creates bottlenecks in validation efficiency. Traditional graph traversal algorithms also face the challenges of high computational overhead and the lack of real-time feedback in large-scale harness routing and frequent local modifications. To address these challenges, an efficient computing framework based on Reserved Graph Grammar (RGG) was proposed. This framework utilized the two-layer node structure of RGG to establish a wiring harness topology model and proposed a “global topology collapse” strategy. By defining parallel reduction rules, the physical graph was efficiently transformed into a logical connection graph, reducing the algorithmic complexity from O(N²) to O(N). Experimental results showed that in the static routing scenario, this algorithm achieved a speedup ratio of 30.89 times in a 32-thread environment, with a parallel efficiency of 96.5%. Compared with the Contraction Hierarchies (CH) static acceleration algorithm, RGG reduced memory usage by approximately 50% and supported incremental updating. For dynamic design changes, a context-sensitive incremental update mechanism was introduced. In the scenarios of attribute update and topology modification, the performance advantage of incremental update became more significant as the wiring harness scale increased: when the number of nodes increased from 100 to 5 000, the speedup ratio of attribute update increased from 543 times to 4.1×10⁴ times, and the speedup ratio of topology update increased from 3.8 times to 2.2×10² times. Compared with the Ramalingam dynamic shortest path algorithm, RGG provided more stable update time and supported topology modification. Additionally, correctness verification showed that the results of this algorithm were completely consistent with those of the traditional Dijkstra algorithm (MAE=0, R²=1.0), ensuring the complete retention of physical attributes. A low-level engine with both high fidelity and real-time responsiveness was thereby provided for the analysis of ultra-large-scale wiring harnesses.

Key words: reserved graph grammar, topological collapse, parallel reduction, context-sensitive, incremental updating

CLC Number:

TP391
U463.6

LI Kai, LIU Shaohua, HE Zihao, LIU Kangfan, ZHOU Silong. Parallel reduction and context-sensitive incremental update method for large-scale wiring harness topology[J]. Journal of Graphics, 2026, 47(4): 820-833.

Figures/Tables 14

Fig. 1 RGG node structure

Fig. 2 A set of RGG production formulas

Fig. 3 An RGG derivation process

Fig. 4 Series merge rule

Fig. 5 Branch compression rules

Fig. 6 Step-by-step schematic diagram of global topological collapse

Table 1 Comparison between Contraction Hierarchies and the method proposed in this paper

对比维度	Contraction Hierarchies	本文方法
预处理目标	构建层次化索引结构	构建归约图与依赖树
节点排序	全局启发式排序	无需排序
动态更新	需重新预计算	支持增量更新
属性传递	不保留中间属性	完整保留物理属性
空间开销	O(NlogN)额外空间	O(N)依赖树空间

Table 2 Statistical characteristics of data for wire harness diagrams of different sizes

节点数	端口数	端口比例/%	度为2节点比例/%	分支点数量	树深度	归约压缩率/%
100	39	39.0	34.0	27	29	34.0
500	188	37.6	35.8	133	67	35.8
1 000	363	36.3	37.7	260	100	37.7
2 000	700	35.0	39.0	521	120	39.0
5 000	1 853	37.1	36.3	1 333	260	36.3

Fig. 7 Double logarithmic coordinate graph of the execution time for the topological collapse of Dijkstra and RGG at all ports

Fig. 8 Experimental results of RGG global topology collapse and CH algorithm comparison

Table 3 Comparison of incremental update performance of wiring diagrams of different sizes

节点数	属性加速比	拓扑加速比
100	5.43×10²	3.78×10⁰
500	2.63×10³	3.29×10¹
1 000	4.58×10³	7.22×10¹
2 000	1.56×10⁴	2.43×10²
5 000	4.10×10⁴	2.21×10²

Fig. 9 Shows the comparative experimental results of RGG context-sensitive update and Ramalingam dynamic shortest path

Fig. 10 Analysis of the parallel scalability of the Global Topology Collapse Algorithm

Fig. 11 The comparison result between the true value and the path length calculated by RGG

References 24

[1]	BLOSTEIN D, FAHMY H, GRBAVEC A. Issues in the practical use of graph rewriting[C]// The 5th International Workshop on Graph Grammars and their Application to Computer Science. Cham: Springer, 1994: 38-55.
[2]	ROSEN B K. Tree-manipulating systems and Church-Rosser theorems[J]. Journal of the ACM, 1973, 20(1): 160-187. DOI URL
[3]	ZOU Y, ZENG X Q, LIU Y F. Context computation for implicit context-sensitive graph grammars: algorithms and complexities[J]. Journal of Visual Language and Computing, 2019, 2019(1): 15-28. DOI URL
[4]	VOSS C, PETZOLD F, RUDOLPH S. Graph transformation in engineering design: an overview of the last decade[J]. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 2023, 37: e5. DOI URL
[5]	KOLBECK L, VILGERTSHOFER S, ABUALDENIEN J, et al. Graph rewriting techniques in engineering design[J]. Frontiers in Built Environment, 2022, 7: 815153. DOI URL
[6]	WANG X Y, LIU Y F, ZHANG K. A graph grammar approach to the design and validation of floor plans[J]. The Computer Journal, 2020, 63(1): 137-150.
[7]	FU W T, EFTEKHARIAN A A, CAMPBELL M I. Automated manufacturing planning approach based on volume decomposition and graph-grammars[J]. Journal of Computing and Information Science in Engineering, 2013, 13(2): 021010. DOI URL
[8]	EHEIM M, KAISER D, WEIL R. On automation along the automotive wire harness value chain[C]// Stuttgart Conference on Automotive Production on Advances in Automotive Production Technology-Theory and Application: Stuttgart Conference on Automotive Production. Cham: Springer, 2021: 178-186.
[9]	CHANG S K. Visual languages: a tutorial and survey[C]// The 5th Interdisciplinary Workshop on Informatics and Psychology on Visualization in Programming. Cham: Springer, 1986: 1-23.
[10]	REKERS J, SCHÜRR A. Defining and parsing visual languages with layered graph grammars[J]. Journal of Visual Languages & Computing, 1997, 8(1): 27-55.
[11]	ZHANG D Q, ZHANG K, CAO J N. A context-sensitive graph grammar formalism for the specification of visual languages[J]. The Computer Journal, 2001, 44(3): 186-200. DOI URL
[12]	RAMALINGAM G, REPS T. An incremental algorithm for a generalization of the shortest-path problem[J]. Journal of Algorithms, 1996, 21(2): 267-305. DOI URL
[13]	YANG L W, LI P, QIAN S, et al. Path planning technique for mobile robots: a review[J]. Machines, 2023, 11(10): 980. DOI URL
[14]	GEISBERGER R, SANDERS P, SCHULTES D, et al. Contraction hierarchies: faster and simpler hierarchical routing in road networks[C]// The 7th International Workshop on Experimental Algorithms. Cham: Springer, 2008: 319-333.
[15]	HOSSAIN S, QUDDUS H A, CEVAHIR Z, et al. Optimized and routed wiring harness based on zonal clustering concept using AI in the automotive industry[J]. IEEE Access, 2025, 13: 137417-137435. DOI URL
[16]	GAON T, GABAY Y, WEISS COHEN M. Optimizing electric vehicle routing efficiency using K-means clustering and genetic algorithms[J]. Future Internet, 2025, 17(3): 97. DOI URL
[17]	EHRIG H, PFENDER M, SCHNEIDER H J. Graph-grammars: an algebraic approach[C]// The 14th Annual Symposium on Switching and Automata Theory. New York: IEEE Press, 1973: 167-180.
[18]	LÖWE M. Algebraic approach to single-pushout graph transformation[J]. Theoretical Computer Science, 1993, 109(1/2): 181-224. DOI URL
[19]	PLUMP D. Critical pairs in term graph rewriting[C]// The 19th International Symposium on Mathematical Foundations of Computer Science. Cham: Springer, 1994: 556-566.
[20]	KOENIG S, LIKHACHEV M. D*lite[C]// The 8th National Conference on Artificial Intelligence. Palo Alto: AAAI, 2002: 476-483.
[21]	NEWMAN M H A. On theories with a combinatorial definition of “equivalence”[J]. Annals of Mathematics, 1942, 43(2): 223-243. DOI URL
[22]	KARYPIS G, KUMAR V. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 1988, 20(1): 359-392. DOI URL
[23]	BLUMOFE R D, LEISERSON C E. Scheduling multithreaded computations by work stealing[J]. Journal of the ACM, 1999, 46(5): 720-748. DOI URL
[24]	AMDAHL G M. Validity of the single processor approach to achieving large scale computing capabilities[C]// Spring Joint Computer Conference. New York: ACM, 1967: 483-485.