[1]轩 瑞,陈 磊,石海鹤*.图类算法可重用设计及其实现[J].江西师范大学学报(自然科学版),2023,(01):52-60.
　XUAN Rui,CHEN Lei,SHI Haihe*.The Reusable Design and Implementation of Graph Algorithms Family[J].Journal of Jiangxi Normal University:Natural Science Edition,2023,(01):52-60.
点击复制

图类算法可重用设计及其实现()
分享到：

《江西师范大学学报》（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2023年01期
页码:
52-60
栏目:
高可信与智能化软件
出版日期:
2023-01-25

文章信息/Info

Title:
The Reusable Design and Implementation of Graph Algorithms Family
作者:
轩 瑞; 陈 磊; 石海鹤*
(江西师范大学计算机信息工程学院,江西 南昌 330022)
Author(s):
XUAN Rui; CHEN Lei; SHI Haihe*
(School of Computer and Information Engineering,Jiangxi Normal University,Nanchang Jiangxi 330022,China)
关键词:
图算法生成;  特征模型;  可重用设计;  构件
Keywords:
graph algorithms generation;  feature model;  reusable design;  component
分类号:
TP 311
文献标志码:
A
摘要:
为了提高图算法生成效率和可靠性,该文提出一种将领域特征模型与构件组装技术相结合的可重用的图类算法开发方法.首先,通过对一族图算法的深入分析,揭示出图类算法领域的共性特征和可变特征,建立领域特征模型; 然后,分析特征之间的交互过程,设计图类算法的可重用构件,并对构件依赖关系做出描述; 最后,借助高可靠平台对算法构件进行开发,建立高可靠可重用构件库,进一步由构件组装出多种图算法,提高了图算法的开发效率和可靠性.实验表明开发出的图算法可重用构件库具有一定的实用性.
Abstract:
In order to improve the efficiency and reliability of graph algorithms generation,the reusable development method of graph algorithms that combines domain feature model and component assembly technology is proposed.First,a family of graph algorithms are analyzed to reveal the common features and variable features in the domain of graph algorithms and a domain feature model is established.Then,the interaction process between features is analyzed,the reusable components of graph algorithms are descigned and the component dependencies are described.Finally,the algorithm components with the help of PAR platform are developed,a library of highly reliable reusable components is established,and further the various graph algorithms are assembled by the components,the development efficiency and reliability of these graph algorithms are significantly improved.The experiments show that the developed reusable component library of graph algorithms has certain practicality.

参考文献/References:

[1] NEEDHAM M,HODLER A E.Graph algorithms: practical examples in Apache Spark and Neo4j [M].Sevastopol:O'Reilly Media Incorporated,2019.
[2] HAVELIWALA T H.Topic-sensitive pagerank:a context-sensitive ranking algorithm for web search [J].IEEE Transactions on Knowledge and Data Engineering,2003,15(4):784-796.
[3] MISLOVE A,MARCON M,GUMMADI K P,et al.Measurements and analysis of online social networks [EB/OL].[2022-08-11].https://doi.org.10.1145/1298306.1298311.
[4] 王兆慧,沈华伟,曹婍,等.图分类研究综述 [J].软件学报,2022,33(1):171-192.
[5] FLEURQUIN P.Systemic propagation of delays in the air-transportation network [EB/OL].[2022-08-19].http://digital.csic.es/bitstream/10261/134152/1/air-transportation_network_Fleurquin.pdf.
[6] DATAFUNTALK.图算法在斗鱼反作弊中的实践 [EB/OL].[2021-07-08].https://www.infoq.cn/article/NhX7CKcIbT3cVmY08Nrr.
[7] VILLENEUVE D,DESAULNIERS G.The shortest path problem with forbidden paths [J].European Journal of Operational Research,2005,165(1):97-107.
[8] MAGZHAN K,JANI H M.A review and evaluations of shortest path algorithms [J].International Journal of Scientific & Technology Research,2013,2(6):99-104.
[9] 张天明,徐一恒,蔡鑫伟,等.时态图最短路径查询方法 [J].计算机研究与发展,2022,59(2):362-375.
[10] 杨保国.基于OpenCL的最短路径图算法实现 [J].实验科学与技术,2017,15(1):57-59,76.
[11] 王佳敏,吴海燕.基于Prim算法的农村公路布局重要度最大树的求解与应用 [J].公路,2019,64(6):162-166.
[12] CLEOPHAS L,KOURIE D G,PIETERSE V,et al.Correcness-by-construction ∧ taxonomiesdeep comprehension of algorithm families [EB/OL].[2022-09-13].https://wur.on.worldcat.org/discovery.
[13] 张承龙,曹华伟,王国波,等.面向高通量计算机的图算法优化技术 [J].计算机研究与发展,2020,57(6):1152-1163.
[14] BEIRANVAND A,CUFFE P.A topological sorting approach to identify coherent cut-sets within power grids [J].IEEE Transactions on Power Systems,2020,35(1):721-730.
[15] 黄阳,周旭,杨志邦,等.基于缓存的时变道路网最短路径查询算法 [J].计算机研究与发展,2022,59(2):376-389.
[16] NEDUNURI S,COOK W R,SMITH D R.Theory and tecniques for synthesizing a family of graph algrithms [EB/OL].[2022-06-17].https://arxiv.org/abs/1207.0869v1.
[17] REIF J H,SCHERLIS W L.Deriving efficient graph algorithms [M]∥DERSHOWITZ N.Verification:theory and practice.Berlin:Springer-Verlog,2003:645-681.
[18] RUSSLING M.A general scheme for breadth-first graph traversal [M]∥MÖLLER B.Mathematics of program construction.Berlin:Springer-Verlog,1995:380-398.
[19] TARJAN R E.A unified approach to path problems [J].Journal of the Association for Computing Machinery,1981,28(3):577-593.
[20] MORIHATA A,MATSUZAKI K,TAKEICHI M.Write it recursively:a generic framework for optimal path quires [C]∥ICFP'08:Proceedings of the 13th ACM SIGPLAN International Conference on Functional Programming,September 20-28,2008,Victoria BC Canada.New York:Association for Computing Machinery,2008:169-178.
[21] XUE Jinyun.Developing the generic path algorithmic program and its instantiations using PAR method [EB/OL].[2022-08-17].https://www.researchgate.net/publication/285841454_PAR_method_and_its_supporting_platform.
[22] XUE Jinyun.PAR method and its supporting platform[EB/OL].[2022-08-17].https://www.researchgate.net/publication/285841454_PAR_method_and_its_supporting_platform.
[23] 谢武平,薛锦云.Radl算法到Apla程序的生成系统 [J].计算机研究与发展,2014,51(4):856-864.
[24] XUE Jinyun.Two new strategies for developing loop invariants and their applications [J].Journal of Computer Science and Technology,1993,8(2):147-154.
[25] 石海鹤,薛锦云.基于PAR的排序算法自动生成研究 [J].软件学报,2012,23(9):2248-2260.
[26] 薛锦云.程序设计方法 [M].北京:高等教育出版社,2001.
[27] 张伟,梅宏.一种面向特征的领域模型及其建模过程 [J].软件学报,2003,14(8):1345-1356.
[28] CZARNECKI K,EISENECKER U W.Generative programming:methods,tools,and applications [M].Boston:Addision Wesley Publishing Co.,2000.

相似文献/References:

[1]鄢梦恬,石海鹤.基于构件的若干图算法开发和生成[J].江西师范大学学报(自然科学版),2016,40(06):635.
　YAN Mengtian,SHI Haihe.Components-Based Graph Algorithms Development and Generation[J].Journal of Jiangxi Normal University:Natural Science Edition,2016,40(01):635.

备注/Memo

备注/Memo:
收稿日期:2022-10-25
基金项目:国家自然科学基金(62062039)和江西省自然科学基金(20212BAB202017)资助项目.
通信作者:石海鹤(1979—),女,江西乐平人,教授,博士,主要从事形式化方法、软件工程和生物信息学的研究.E-mail:haiheshi@jxnu.edu.cn
更新日期/Last Update: 2023-01-25