基于超图模型的软件模块自动划分

doi:10.3969/j.issn.1000-3428.2016.01.014

摘要/Abstract

摘要： 应用超图理论模型设计软件模块的自动划分算法。通过分析软件源码建立超图模型,将类抽象为超图的顶点,使多个类之间存在关联,将软件模块划分转换为超图划分问题,再利用超图模型实现对超图的划分,从而达到软件模块划分的目的。基于高内聚低耦合原则给出模块度的概念,得到优化的分割结果。以开源软件为实验数据,并与传统的划分算法hMetis进行对比,结果表明该算法的划分结果较优,验证了其合理性与有效性。

关键词: 软件模块划分, 超图建模, 超图划分, 模块度, hMetis算法

Abstract: This paper applies the hypergraph model to design automatic software module partition algorithm.Under the hypergraph modeling,each significant class extracted from the source codes of an analyzing software system is abstracted as a vertex of a hypergraph,and hyperedges are built among the classes which have relations to some extent.Then the problem of module partition is translated into a partitioning problem of a hypergraph,which can be solved by hypergraph partitioning algorithm.In order to improve the partitioning result,a new modularity function is constructed according to the cohesion states and coupling relations in and among software modules.Compared with hMetis algorithm,experimental results show that the proposed algorithm can obtain reasonable and effective module partition.

Key words: software module partition, hypergraph modeling, hypergraph partition, modularity, hMetis algorithm

中图分类号:

TP18

魏小凤,胡继承,罗永恩. 基于超图模型的软件模块自动划分[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2016.01.014.

WEI Xiaofeng,HU Jicheng,LUO Yong’en. Automatic Software Module Partition Based on Hypergraph Model[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2016.01.014.

http://www.ecice06.com/CN/Y2016/V42/I1/71

参考文献

参考文献［1］Shaw M,Garlan D.Software Architecture:Perspectives on an Emerging Discipline［M］.New Jersey,USA:Prentice Hall,1996. ［2］Jan B.Software Architecture:The Next Step［C］//Proceedings of the 1st European Workshop on Software Architecture.Berlin,Germany:Springer,2004:194-199 ［3］李兵,马于涛,刘婧,等.软件系统的复杂网络研究进展［J］.力学进展,2008,38(6):805-814. ［4］Liu Fuyun,Song Sujing.Research on Module Division Method Based on Complex Network Theory［C］//Proceedings of the 5th International Conference on Semantics,Knowledge and Grid.Washington D.C.,USA:IEEE Press,2009:432-433. ［5］何明东,熊建斌,李振坤.基于复杂网络的软件开发方法研究［J］.计算机技术与发展,2011,21(6):59-62. ［6］Teng Xiaoyan,Zhang Taijia.Module Partition Method Based on Hybrid Fuzzy Clustering［C］//Proceedings of 2010 International Conference on Mechatronics and Automation.Washington D.C.,USA:IEEE Press,2010:333-338. ［7］Shi Junyou,Tao Qingbin.Research on a Genetic Algorithm for Solving Module Partition Problem［C］//Proceedings of the 6th International Conference on Natural Computation.Washington D.C.,USA:IEEE Press,2010:4215-4218. ［8］Doval D,Mancoridis S,Mitchell B S.Automatic Clustering of Software Systems Using a Genetic Algorithm［C］//Pro-ceedings of IEEE Conference on Software Technology and Engineering Practice.Washington D.C.,USA:IEEE Press,1999:73-81. ［9］Kumari A C,Srinivas K,Gupta M P.Software Module Clu-stering Using a Hyper-heuristic Based Multi-objective Genetic Algorithm［C］//Proceedings of the 3rd International Advance Computing Conference.Washington D.C.,USA:IEEE Press,2013:813-818. ［10］Yang Yanan,Miao Jinghong,Wang Zhongwei.Research on Module Division Method for Product Based on FCM Clustering Algorithm［C］//Proceedings of 2011 Inter-national Conference on Control,Automation and Systems Engineering.Washington D.C.,USA:IEEE Press,2011:1-4. ［11］Kiarash M,Harman M,Hierons R M.A Multiple Hill Climbing Approach to Software Module Clustering［C］//Proceedings of International Conference on Software Maintenance.Washington D.C.,USA:IEEE Press,2003:315-324. ［12］Mitchell B S,Mancoridis S.On the Automatic Modulari-zation of Software Systems Using the Bunch Tool［J］.IEEE Transactions on Software Engineering,2006,32(3):193-208. ［13］Santonu S,Kak A C,Rama G M.Metrics for Measuring the Quality of Modularization of Large-scale Object-oriented Software［J］.IEEE Transactions on Software Engineering,2008,34(5):700-720. ［14］Schlkopf B,Platt J,Hofmann T.Learning with Hyper-graphs:Clustering,Classification,and Embedding［M］//Schlkopf B,Platt J,Hofmann T.Advances in Neural Infor-mation Processing Systems 19:Proceedings of the 2006 Con- ference.Massachusetts,USA:MIT Press,2007:1601-1608. ［15］Karypis G,Aggarwal R,Kumar V,et al.Multilevel Hypergraph Partitioning:Application in VLSI Domain［J］.IEEE Transactions on Very Large Scale Integration(VLSI) Systems,1999,7(1):69-79. ［16］Mobasher B,Jain N,Han E,et al.WebMining:Pattern Discovery from World Wide Web Transactions,TR96-050［R］.Minneapolis,USA:Department of Computer Science,University of Minnesota,1996. ［17］Alpert C J,Kahng A B.Recent Directions in Netlist Partitioning:A Survey［J］.Integration,the VLSI Journal,1995,19(1/2):1-81. ［18］Karypis G,Kumar V.hMETIS,A Hypergraph Partitioning Package(Version 1.5.3),#98-036［R］.Minneapolis,USA:Department of Computer Science & Engineering Army HPC Research,University of Minnesota,1998. ［19］卢玥,曹建文.超图多级划分算法框架及对划分结果的多阶段优化［J］.计算进工程与设计,2009,30(4):800-804. ［20］Sukainah H,Oxley A.A Coupling and Cohesion Metrics Suite for Object-oriented Software［C］//Proceedings of International Conference on Computer Technology and Development.Washington D.C.,USA:IEEE Press,2009:421-425. ［21］Ulrich M.External Memory BFS on Undirected Graphs with Bounded Degree［C］//Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms.［S.l.］:Society for Industrial and Applied Mathematics,2001:87-88. ［22］Powell M L,Kleiman S R,Barton S,et al.SunOS Multi-thread Architecture［C］//Proceedings of USENIX Winter Conference.Dallas,USA:USENIX,1991:339-372. ［23］Richards G,Lebresne S,Burg B,et al.An Analysis of the Dynamic Behavior of JavaScript Programs［C］//Pro-ceedings of 2010 ACM SIGPLAN Conference on Progaram-ming Language Design and Implemention.New York,USA:ACM Press,2010:1-12. ［24］Hartigan J A,Wong M A.Algorithm AS 136:A k-means Clustering Algorithm［J］.Journal of the Royal Statistical Society:Series C(Applied Statistics),1979,28(1):100-108. 编辑金胡考

[1]	林强强, 涂山山, 刘濛, 肖创柏. 异构蜂窝网络中基于社区检测的跟踪区域规划方案[J]. 计算机工程, 2019, 45(7): 134-139.
[2]	丁明珠,马英红,李云. 基于相似度指标的社团划分算法[J]. 计算机工程, 2019, 45(2): 195-201.
[3]	王泽华, 柯新生. 基于Coclus联合聚类与非负矩阵分解的推荐算法[J]. 计算机工程, 2019, 45(11): 68-73,80.
[4]	罗永恩,胡继承,徐茜. 基于超图的多模态关联特征处理方法[J]. 计算机工程, 2017, 43(1): 226-230.
[5]	阙建华. 社交网络中基于近似因子的自适应社区检测算法[J]. 计算机工程, 2016, 42(5): 134-138,145.
[6]	章亮,姚世军,陈楚湘. 基于多层粒子群的社团发现算法[J]. 计算机工程, 2016, 42(10): 207-212.
[7]	袁铭. 基于多标度曲线的股市网络构造及其社区挖掘[J]. 计算机工程, 2015, 41(4): 60-64,76.
[8]	董雨辰,刘琰,罗军勇,张进. 基于支持向量机的炒作微博识别方法[J]. 计算机工程, 2015, 41(3): 7-14.
[9]	吴蔚蔚,刘功申,黄晨. 基于相似度的社团划分算法[J]. 计算机工程, 2015, 41(11): 67-72,83.
[10]	张梁梁,冯径,胡谷雨. 基于压缩感知的社团结构深度学习方法[J]. 计算机工程, 2014, 40(9): 190-195.
[11]	罗明伟，姚宏亮，李俊照，王浩. 一种基于节点相异度的社团层次划分算法[J]. 计算机工程, 2014, 40(1): 275-279.
[12]	叶慧, 李旻. 基于组合模型的局部搜索弱社团结构发现算法[J]. 计算机工程, 2012, 38(17): 56-58,62.
[13]	任永功, 孙宇奇, 吕朕. 一种基于局部信息的社区发现方法[J]. 计算机工程, 2011, 37(7): 12-14,23.
[14]	刘微, 张大为, 嵇敏, 谢福鼎. 基于共享邻居数的社团结构发现算法[J]. 计算机工程, 2011, 37(6): 172-174.
[15]	王林, 戴冠中, 赵焕成. 一种新的评价社区结构的模块度研究[J]. 计算机工程, 2010, 36(14): 227-229.

选择文件类型/文献管理软件名称

选择包含的内容