大规模线束拓扑并行归约与上下文敏感增量更新方法

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

摘要/Abstract

摘要：

针对汽车电子电气架构演进带来的线束系统设计复杂度提升及验证效率瓶颈，以及传统图遍历算法在处理大规模线束寻径和频繁局部变更时面临计算开销大、难以实时反馈的挑战，提出了一种基于保留图文法(RGG)的高效计算框架。本框架利用RGG的双层节点结构建立线束拓扑模型，并提出“全局拓扑塌缩”策略，通过定义的并行归约规则将物理图高效转换为逻辑连接图，将算法复杂度从O(N²)降低至O(N)。实验结果表明，在静态寻径场景下，该算法在32线程环境下实现了30.89倍的加速比，并行效率达96.5%。与CH静态加速算法相比，RGG内存占用降低约50%且具有增量更新能力。针对动态设计变更，引入上下文敏感的增量更新机制，在属性更新与拓扑修改场景下，增量更新的性能优势随线束规模增大而愈发显著：当节点数从100增至5 000时，属性更新加速比从543倍提升至4.1×10⁴倍，拓扑更新加速比从3.8倍提升至2.2×10²倍。与Ramalingam动态最短路径算法相比，RGG更新时间更稳定且支持拓扑修改。此外，正确性验证显示该算法与传统Dijkstra算法结果完全一致(MAE=0，R²=1.0)，确保了物理属性的完整保留。本研究为超大规模线束分析提供了兼具高保真度与实时响应能力的底层引擎。

关键词: 保留图文法, 拓扑塌缩, 并行归约, 上下文敏感, 增量更新

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

中图分类号:

TP391
U463.6

李凯, 刘绍华, 何梓豪, 刘康凡, 周思龙. 大规模线束拓扑并行归约与上下文敏感增量更新方法[J]. 图学学报, 2026, 47(4): 820-833.

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.

图/表 14

图1 RGG结点结构

Fig. 1 RGG node structure

图2 一组RGG产生式

Fig. 2 A set of RGG production formulas

图3 一个RGG推导过程

Fig. 3 An RGG derivation process

图4 串联合并规则

Fig. 4 Series merge rule

图5 分支压缩规则

Fig. 5 Branch compression rules

图6 全局拓扑塌缩分步示意图

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

表1 Contraction Hierarchies与本文方法对比

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

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

表2 不同规模线束图的数据特征统计

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

图7 全端口对Dijkstra与RGG拓扑塌缩执行时间的双对数坐标图

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

图8 RGG全局拓扑塌缩与CH算法对比实验结果

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

表3 不同规模下线束图的增量更新性能对比

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²

图9 RGG上下文敏感更新与Ramalingam动态最短路径算法对比实验结果

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

图10 全局拓扑塌缩算法的并行可扩展性分析

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

图11 真值与RGG计算路径长度的对比结果

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

参考文献 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.