没有合适的资源?快使用搜索试试~ 我知道了~
软件影响9(2021)100083原始软件出版物tinygarden -用于测试生成树Manuel Dubinskya,César Massrib,Gabriel TaubincaIngeniería en Informática,Departamento de Tecnología y Administración,Universidad Nacional de Avellaneda,ArgentinabDepartamento de Matemática,Universidad de CAECE,CABA,Argentinac美国罗德岛州普罗维登斯布朗大学工程学院A R T I C L E I N F O保留字:图生成树基本循环基A B标准生成树是图论中的基本对象。任意图的生成树集的大小可以非常大。这种限制阻碍了它的分析。然而,有趣的模式可以出现在小案件。在这篇文章中,我们介绍tinygarden,一个java软件包,用于验证假设,测试属性和从任意图的生成树集中代码元数据当前代码版本1.0用于此代码版本的代码/存储库的永久链接https://github.com/SoftwareImpacts/SIMPAC-2021-47可再生胶囊的永久链接https://codeocean.com/capsule/9539109/tree/v1法律代码许可证MIT使用git的代码版本控制系统使用Java的软件代码语言、工具和服务编译要求、操作环境依赖性jdk如果可用,链接到开发人员文档/手册https://github.com/manudubinsky/tinygarden/wiki问题支持电子邮件mdubinsky@undav.edu.ar1. 介绍图论是离散数学的一个历史悠久且完善的领域。图是某个领域中实体之间成对关系的抽象模型。一个图=(,)由组成 - 一套(或)(或)(,)(或)(。每个节点是代表一个实体的点,每条边是连接两个节点的线。例如,我们可以通过将节点与每个人相关联并将两个节点与边连接(如果对应的人是朋友)来对社交网络中的友谊关系进行建模。设���=(���,���)为图中的图形。1.一、一个子图′=(′,′)是一个图,使得′,′������������这样���, 包含了所有的端点的边缘在"“。 的路径��� =(���1,���������...,)是的连续边缘的序列(见图1)。2)的情况。一个循环���是一个非空的路径,其中唯一重复的节点是第一个和最后一个(见图。 3)。我们说G是连通的,如果每对节点之间至少有一条路。 树是没有圈的连通图。 最后,生成树������是一个包含所有节点的树���(见图1)。4).生成树在优化[1]、网络设计[2]、VLSI互连[3]、聚类[4]、复杂性理论[5]、图不变量[6]、基本循环基[7]以及应用科学和理论科学的许多领域都任意图的生成树集可以非常大[8]。 此限制可防止探索整个集合。然而,有算法生成图的所有生成树[9本文中的代码(和数据)已由Code Ocean认证为可复制:(https://codeocean.com/)。更多关于生殖器的信息徽章倡议可在https://www.elsevier.com/physical-sciences-and-engineering/computer-science/journals上查阅。∗ 通讯作者。电子邮件地址:mdubinsky@undav.edu.ar(M. Dubinsky)。https://doi.org/10.1016/j.simpa.2021.100083接收日期:2021年4月26日;接收日期:2021年5月6日;接受日期:2021年5月10日2665-9638/©2021作者。由Elsevier B.V.出版。这是一篇开放获取的文章,使用CC BY许可证(http://creativecommons.org/licenses/by/4.0/)。可在ScienceDirect上获得目录列表软件影响杂志 首页:www.journals.elsevier.com/software-impactsM. 杜宾斯基角Massri和G.Taubin软件影响9(2021)1000832Fig. 1. 图的例子图二. 一个路径的例子。图三. 一个循环的例子。见图4。 生成树的例子。2. 软件描述tinygarden包是一组自包含的java类,它支持探索给定图的生成树集。它实现了Matsui算法[11]来生成它。结构很简单。SpanningTreesMatsui类组织了整个过程。两个类层次结构的自定义后代:收集器和处理器被顺序调用以处理每个生成树。收集器对于整个集合的全局分析非常有用,例如,计算具有特定属性的生成树的数量。另一方面,处理器对于本地任务很有用,例如生成特定生成树的精美打印版本该软件包还实现了帮助类,如Graph,Sparse- Matrix,UnionFind等。由于Graph可以基于包含其关联矩阵的文本文件构建,因此它可以与着名的图形软件nauty[123. 限制和改进tinygarden包的范围仅限于特定的图论问题。最重要的限制是可以处理的实例的大小;设想探索最多9个节点的所有非同构图的生成树集。因此,两项重要的改进将是:• Matsui算法的分布式实现:为了处理更大的图。• 计算生成树集大小[13]:处理与规定阈值相比大小该软件包的第一个版本最近公布。目前只被作者使用4. 影响tinygarden包是一个工具,用于验证假设,测试属性,并从任意图的生成树集中发现模式。据我们所知,这是唯一具有这些功能的工具。在[14]中,我们介绍了mstci问题,tinygarden包被证明在寻找与完全图的交数有关的模式方面是有效的,这导致了它的主要结果,并设置了一个 这是一个重要的工具,以评估一个元启发式算法的图集成[15]。我们目前正在使用它来测试一种算法,以便找到一个好的解决方案MSTCI的问题。该软件包可用于分析一般问题,即:列出一个图的最小直径的生成树,以及携带 统计分析,即:计算固定数目节点的图相对于具有最短总路径长度的生成树的分布[5]。基于我们的软件包,可以从统计的角度分析几个NP难题,例如图5显示了8个节点图的最小基本周期基(或最小FCB)[16]的分布。这些信息可以用来实现近似或启发式算法,以找到这些问题的好的解决方案竞合利益作者声明,他们没有已知的竞争性财务利益或个人关系,可能会影响本文报告的工作致谢Massri教授得到了Instituto de Investigaciones Matemáticas '' Luis A.Santaló’’, UBA, CONICET, CABA,Taubin教授得到了美国国家科学基金会的部分资助,资助号为IIS-1717355。M. 杜宾斯基角Massri和G.Taubin软件影响9(2021)1000833引用图五、8 个 节 点 的 图 的 最小FCB的 分 布 (左)。最小FCB相对于边数的聚合关系(右)。[9]R.读吧,R.E. Tarjan,Bounds on backtrack algorithms for listing cycles,paths,and spanning trees,Networks 5(3)(1975)237http://dx.doi.org/10.1002/[1]B. Wu,K.赵,生成树与优化问题,《离散数学及其应用》,CRC出版社,2004年,网址https://books.google。 com.ar/books? id=SI82UzzyVN8C。[2]D. Eppstein, Spanning Trees and Spectrometry, in:J.- R. Sack ,J.Urrutia( Eds. ) , 《 计 算 几 何 手 册 》 , 北 荷 兰 , 阿 姆 斯 特 丹 , 2000 年 , 页 。425http://dx.doi.org/10.1016/B978-044482537-7/50010-3//www.sciencedirect.com/science/article/pii/B9780444825377500103( 第 9章)。[3] 琼孔湖他,C.- K. Koh,P.H. Madden,VLSI互连布局的性能优化,集成21(1http://dx.doi.org/10。1016/s0167-9260(96)00008-9。[4]L. Rokach,聚类算法的调查,在:数据挖掘和知识发现手册,Springer US,2009年,pp. 269 http://dx.doi.org/10。1007/978-0-387-09823-4_14。[5]M. Garey, D. Johnson , Computers and Intractability: A Guide To the TheoryofNP-Completeness,Macmillan,New York,1979,p. 三百四十[6]W. Tutte , 色 多 项 式 理 论 的 一 个 贡 献 , 加 拿 大 。6 ( 1954 )80http://dx.doi.org/10.4153/cjm-1954-010-9[7]T.卡维塔角Liebchen,K. Mehlhorn, D. 米海尔河Rizzi,T. Ueckerdt,K.A.Zweig,图表征中的循环基,算法,复杂性和应用,Comp. Sci. Rev. 3(4)(2009)199http://dx.doi.org/10.1016/[8]A. Cayley,A Theorem on Trees,Q. J. 纯应用数学23(1889)376net.1975.5.3.237。[10]H.N. Gabow,E.W. Myers,寻找有向图和无向图的所有生成树,SIAMJ. Comput。7(3)(1978)280http://dx.doi.org/10.1137/[11]T. Matsui,Algorithms for Finding All the Spanning Trees in Undirected Graphs,Department of Mathematical Engineering and Information Physics , Faculty ofEngineering,University of Tokyo(1993),1993,URLhttps://www.keisu.t.u-tokyo.ac.jp/data/1993/METR93-08.pdf.[12]B.D. McKay , A. 图 的 同 构 , II , J 。 符 号 计 算 。 60 ( 2014 )94http://dx.doi.org/10.1016/j.jsc.2013.09.003[13]G. Kirchhoff,Ueber die Auflösuung der格列春根,aufwelche人贝derUntersuchung der linearen Vertheilung galvanischer Ströme geführt wird,Ann.Phys. Chem. 148 ( 12 ) ( 1847 ) 497 http://dx.doi.org/10.1002/andp.18471481202,URLhttps://doi.org/10.1002/andp.18471481202。[14]M. 杜 宾 斯 基 角 马 斯 里 湾 Taubin , Minimum Spanning Tree Cycle Intersectionproblem,Discrete Appl. Math. 294(2021)152http://dx.doi.org/10.1016/[15]M.杜宾斯基角Massri,F. Asteasuain,Una metaclisística GRASP para in- tegraciónen grafos,in:XV Simposio Pastino de Investigación Operativa,(SIO)-JAIIO46 ( Córdoba , 2017 ) , 2017 , pp.36http://sedici.unlp.edu 。ar/handle/10915/66445(西班牙语)。[16]N. Deo,MS Krishnomoorthy,G. Prabhu,在图中生成基本圈的算法,ACM Trans.数学软件8(1)(1982)26
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功