rsppfp"：一个R包，用于带禁止路径的最短路径问题的开源算法实现

SoftwareX 9（2019）265原始软件出版物“rsppfp”：一个R包，用于带禁止路径的最短路径问题Melina Vidoni Aldo Vecchietti设计与开发研究所（INGA CONICET-UTN），Avellaneda 3657，Santa Fe，Argentinaar t i cl e i nf o文章历史记录：收到2018年收到修订版，2019年1月16日接受，2019年保留字：R包最短路径禁止路径网络流a b st ra ct带禁止路径的最短路径问题（SPPFP）是原始最短路径问题的一个变体，其中约束来自一组禁止弧序列，这些禁止弧序列不能是任何可行的解决方案。虽然这个问题在学术文献中得到了解决，并且有许多应用，但是没有开源的算法实现来解决它。本文提出了“rsppfp”，一个R包，它提供了通过将SPPFP转换为传统的最短路径问题来解决SPPFP的功能。它的主要优点是具有并行处理能力，并与其他网络研究软件包具有很高的兼容性。在本文中，我们描述了“rsppfp”的设计和功能©2019作者由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本V1.0.4此代码版本使用的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2018_71法律代码许可证GPL使用Git的代码版本控制系统使用的软件代码语言、工具和服务语言：R v3.4R软件包：stringr，dumr，foreach，doParallel，igraph，tidyr编译要求，操作环境依赖R软件包：stringr，dumr，foreach，doParallel，iGraph，tidyr如果有开发人员文档/手册链接https://melvidoni.github.io/rsppfp问题支持电子邮件melinavidoni@santafe-conicet.gov.ar软件元数据当前软件版本V1.0.4此版本可执行文件的永久链接https://CRAN.R-project.org/package=rsppfp法律软件许可证GPL计算平台/操作系统Linux，Windows安装要求依赖项R包：stringr，dumr，foreach，doParallel，igraph，tidyr如果可用，请链接到用户手册-如果正式出版，请在参考列表中引用该出版物https://melvidoni.github.io/rsppfp问题支持电子邮件melinavidoni@santafe-conicet.gov.ar1. 动机和意义带禁止路径的最短路问题（SPPFP）是由Villeneuve和Desaulniers [1]提出的。On this∗通讯作者。电子邮件地址：melinavidoni@santafe-conicet.gov.ar（M.Vidoni），aldovec@santafe-conicet.gov.ar（A.Vecchietti）。https://doi.org/10.1016/j.softx.2019.03.004问题，给定图G=（N， A），其中N是节点集，A是弧集，G中还有一个禁止路径列表F，这些禁止路径不能是任何解路径的一部分在这个版本的问题中，F是事先已知的;然而，每个禁止路径可以具有不同的长度，最少有三个节点。这个问题经常出现在光网络[2]，窗口网络[3]，物流和路由[4]等。2352-7110/©2019作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx266M. Vidoni和A. Vecchietti / SoftwareX 9（2019）265=∈−∈={个∈ []==∈大多数学术建议通过将原始图G及其F转换为放大图G来解决SPPFP（N∈ F，A∈ F）使得G∈ F中的每条路都不包含任何禁止路f∈F.这种方法有两个优点：在大多数情况下，G和F在很长一段时间内保持不变。因此，转换只完成一次，并且G可以与原始图一起存储。一个新只有在G或F的罕见情况下才需要转换变化这个问题可以在G语言上使用传统的短-通过有效管理时间和资源约束的算法来测试路径。这些算法在大量的编程语言和框架中实现。因此，图。1展示了这个求解过程，使用纸符号来表示输入和输出数据。R是一个高效的统计分析和数据处理软件环境，为网络研究提供了强大的支持示例是已知的软件包，诸如igraph [5]、WGCNA[6]等。然而，据作者‘‘rsppfp’’因此，有必要将目前的SPPFP，从城市街道地图，解决最短路径问题。‘‘rsppfp’’ manipulates input and output in standard R dataframedouble等;但是，返回的图将具有字符类型的节点。这将在第1.3节中进一步讨论第二，F表示禁止路径的数据帧，其中数据帧的每一行是路径fF。路径可以有不同的长度，但未使用的列必须用NA值填充。此外，F中使用的所有节点必须是G的一部分;它们可以是任何数据类型，但它们在内部被操作为字符。列名与此数据框无关假设禁止路径涉及至少三个节点。这是因为任何两个节点的路径都是简单的弧，并且应该从G中删除，因为它们是禁止的。第三，建议对于具有c核心的计算机，此参数的最大可能值应为c1，以允许一个核心负责操作系统的功能。如果未收到值，则代码片段（1）提供了创建样本图的结构，其中F[s， u，v，t]，[u，v， y， u]。这张图可以在图中看到。二、值得注意的是，在SPPFP中，路径不能包含任何完整的fF，但可以包括作为部分的弧任何给定的禁止路径;例如，对于图中看到的图形。2，路径p[s， u，w，v， y]是可接受的：它包含在不同f F中使用的两个弧（分别为[s， u]和v，y），但它不包括任何完全禁止的路径。f-数据帧（V1 = c（“s”，“u”），V2 = c（“u”，“v”），V3 = c（“v”，“y”），V4 = c（“t”，“u”），字符串作为因子= FALSE）g-数据帧（from = c（“s”，“s”，“s”，“u”，“u”，“w”，这样，结果可以与其他联网工具一起使用。它的贡献在图中突出显示。1，同时描述求解SPPFP的过程。更重要的是，这个包中包含的算法这种配置对用户来说很简单，因为只需要输入内核的数量 。 ‘‘rsppfp’’ includes different transformation algorithms, torespond to varying constraints inside the problem; some of [七]《中国日报》“w”、“x”、“x”、“v”、“v”、“y”、“y”），to = c（“u”，“w”，“x”，“w”，“v”，“v”，“y”，“w”，“y”，“y”，“t”，“t”，“u”），成本= c（1L，1L，1L，1L，1L，1L，1L，1L，1L，1L，1L，1L），字符串作为因子= FALSE）2.2. 可用功能（一个）反向构造，转换为N的序列，返回到N，并将这些函数用于无向图。此外，图形被格式化为数据帧，转换操作图形，其中节点由其名称表示，并且弧具有未公开的属性数量。更重要的是，这些属性可以是任何类型;转换处理它们时不需要用户进行任何额外的配置。2. 软件描述“rsppfp "是一个软件包，它支持图形及其禁止路径集的转换，以便稍后与其他工具一起使用。它实现了从学术角度提出和接受的算法[1，7]。 它是用R语言写的，在GitHub存储库中可用，可以克隆或分叉。2.1. 输入数据格式主输入数据由两个不同的数据帧和一个用于并行处理的附加参数首先，G将原始图表示为弧的数据框架。弧主要表示为这两列需要位于数据框的1：2位置。每个弧可以或不可以可能有额外的属性，这是内部处理的节点名称可以是任何简单类型，例如字符、整数、“”rsppfp“”实现了两种转换算法。在这两种情况下，F必须事先已知，并且集合上的每个禁止路径可以具有不同的长度-即，包括不同数目节点。然而，禁止路径的最小长度是三个节点。值得一提的是，这些算法是不平凡的，因为其逻辑的实现并不简单。然而，本文的目的并不是描述这种逻辑，因为作者已经广泛地讨论了这种逻辑。第一个是Villeneuve和Desaulniers该算法受一个规则限制，限制为没有fi F必须是或包含另一个fj F的子路径，其中i j;意思是对于同一个图，禁止路径不能包含另一个禁止路径的子路径。这个转换过程是在一个特定的函数上实现的，它的声明可以在代码片段（2）中看到：modify_graph_vs← function（g，f，cores = 1L）{...}（二）第二种变换算法是Hsu等人开发的算法。[7]，称为反向构造。该算法与前一个算法不同，没有限制，限制禁止路径的结构。这个转换过程是在一个单独的函数中实现的。它的声明可以在代码片段（3）中看到：modify_graph_hsu← function（g，f，cores = 1L）{.}（三）作为限制，这些算法仅对有向图起作用;即，图，其中每条弧从特定节点指向··M. Vidoni和A. Vecchietti / SoftwareX 9（2019）265267={个={个={个∈图1.一、 流程图展示了一个SPPFP解决过程，并强调了“rsppfp”包的贡献。图二、 使用代码片段（1）生成的图的结构。另一个节点，并且只能在一个特定的方向上行进为了克服这个限制，这是通过复制每个弧并反转复制此功能还支持并行处理。2.3. 算法为了评估所实现的算法的性能，解决了几个说明性的例子。使用 igraph 的 www.example.com （ ） 生 成 了 总 共 27 个 图erdos.renyi.game这些图由以下值的组合产生：大小为（N）100、300、500的一组节点，大小为（F）50、250、500之间变化的禁止路径的数量，以及大小为（d）0的变化的密度。1、0.五，零。9 .第九条。在图论中，稠密图是其中弧数接近于可能弧的最大数目的图在转换这些图形时，使用R基函数system.time（）计算这些函数。代码以及生成的图形，可作为'' rsppfp ''的包的一部分这是在具有3.6 Ghz的Intel i7-4790 CPU的计算机上执行的，具有4GB RAM，使用Linux Ubuntu 16.04作为操作系统;四个核心中的三个用于所有转换。图3示出了根据电弧密度分面的测试结果。可以看出，在所有情况下，更通用的算法（Hsu值得一提的是，这是预期的行为，因为变换逻辑在禁止路径F由于其逻辑，HsuF值。2.4. 输出数据格式这两种类型的转换函数都返回一个图形G作为一个数据帧，其中每行表示一个弧。它保持268M. Vidoni和A. Vecchietti / SoftwareX 9（2019）265||||||}{}|| ||||联系我们联系我们联系我们•|{1}|||个文件夹|}∈图三. Villeneuve算法和Hsu算法在“rsppfp”中的执行时间与节点数的关系。它包括可变的禁止路径数，最多6个节点的长度，每个密度都有小平面从和到的主要列表示在原点和目的地节点方面的弧;附加列表示其他G弧的属性，如果对应。然而，不管原始图中N使用的数据类型如何这是因为新节点名称的生成遵循Villeneuve和Desaulniers的[ 1 ]提出的建议：由于两种算法都循环通过每条禁止路径上的每个节点，因此这些节点名称是通过递增地连接原始名称并由管道分割而生成的例如，对于给定的f1F f， c， p， t， n，节点以字母命名，新节点为：f c， f cp， f cp t，等等。在第二示例中，对于f2F1988、 1985、 1958、1963，其中节点为整数值，新节点名称为：1988 1985、 19881985 1958和1988 1985 1958 1963。作为该软件包允许转换具有多个属性的图，其向G的转换工作如下：第一步是定义图及其禁止路径。这在代码片段（4）中完成，其中一组禁止路径被定义为Ff1，f2，f3，f4，其中f1u，v，y，u 、 f2u，w， y， u，f3w，v，y和f4x，w，v， y， t。图形结构与图1中所示的图形结构相同。虽然这个例子是任意定义的，并且输入数据是硬编码的，但值得注意的是，输入可以从不同的源（如数据库、电子表格文件等）获得;但是，该过程超出了#1a.加载禁止路径f-数据帧（V1 = c（“u”，“u”，“w”，“x”），V2 = c（“v”，“w”，“v”，“w”），V3 = c（“y”，“y”，“y”，“v”），V4 = c（“u”，“u”，NA，“y”），V5 = c（NA，NA，NA，“t”），对于现有节点之间的弧，其属性保持不变。对于新节点之间的弧（例如，f c）和现有节点（例如，s），则弧的属性与传统节点c和s之间的原始弧对于新结点之间的弧，属性与最后一个传统结点之间的原始弧的字符串作为因子= FALSE）#1b。将图形作为弧g-数据帧（from = c（“s”，“s”，“s”，“u”，“u”，“w”，“w”，“x”、“x”、“v”、“v”、“y”、“y”），to = c（“u”，“w”，“x”，“w”，“v”，“v”，“y”，“w”，“y”，“y”，“t”，“t”，“u”），字符串作为因子= FALSE）（四）每一个新节点。例如，对于弧f c p， k m t，属性是来自原始弧{p，t}的那些属性然而，在G中计算的任何路径都使用这些名称。因此，与N个节点兼容路径必须作为向量传递，一旦读取了图形和禁止路径，就可以使用在这种情况下，一些fF的子路径是其他F。因此，该示例使用了Hsu这可以在（5）中看到：有序节点（或顶点）。与此相关，该软件包还提供了一个函数，用于获取每Ni个节点，这些节点相当于#2。将图形转换为gStargStar-modify_graph_hsu（g，f，cores =3L）（五）原始N1节点;这可以用于获得涉及所述N1节点的路径node.3. 说明性实例本节提供了一个示例来展示如何使用“rsppfp”。完整的代码可以从“rsppfp”的GitHub存储库中的examples目录和网站中访问生成的数据帧G（在代码中命名为gStar）可以转换为其他数据类型，特定于特定的库。例如，可以使用函数graph_from_data_frame（）由igraph [5]提供，用于将G转换为使用igraph最短路径功能。使用所述功能还允许绘制图表。这是针对图4所做的，图4显示了使用tkplot（）的转换图。··M. Vidoni和A. Vecchietti / SoftwareX 9（2019）265269||∈图四、修 改 后的图，产生与许的向后建设。图图4中，灰色顶点表示新节点，黑色虚线弧表示新链接。由于从这里开始，可以使用任何最短路径算法来获得所需路径。然而，由于这些算法应该应用于G_n以避免禁止路径，因此需要执行额外的步骤带着。首先，一个节点nG可以在G中有等价的节点。为例如图 节点w、x w和u w都是等价的，因为它们都表示相同的原始节点w，但是从不同的地方到达。因此，为了搜索最短路径，需要考虑起始节点朝向目的节点的所有等价。可以使用'' rsppfp ''函数get_all_nodes（）获得等价性‘‘rsppfp’’_path（），它总结了代码片段（6，7，8）的代码，简化了获得最短路径的过程，而不会引发禁止路径。但是，此功能需要安装igraph。4. 影响创建和发布“rsppfp”包的决定尽管如此，SPPFP仍然是一个未被探索的问题。更重要的是，当前的转换算法在学术期刊上发表[9]，但它们的实现并不公开。因此，本文提出了一个包，旨在带来#3。获取所有节点，其中“w”是目的地-get_all_nodes（gStar，“w”）（六）这些转换算法中的一些，在R中实现这一决定是基于R在此之后，可以应用任何最短路径函数因为-在使用igraph [5]功能的情况下，需要将gStar转换为igraph类;然后需要获得通往每个等效目的地点的最短路径，并仅保留权重较小的一个在片段（7）中可以看到这样做所需的代码：第四名。转换为igraph以使用gStar.igraph-graph_from_data_frame（gStar）第五名。找到从“s”到对应于“w”的所有N* 的最短路径sp-shortest_paths（gStar.igraph，from =“s”，to = dest，weights = gStar$weight，output =“both”）第六名。找出这些路径中的最短路径dist-vapply（sp$epath，function（path）sum（path$weight），numeric（1））shortestPath-sp$vpath[[which.min（dist）]]（七）然而，由于在G中计算的任何路径都是以项给出的，在它的N个节点中，需要解析返回到属于G的节点的最终路径。这可以使用“rsppfp”的函数parse_vpath（）来完成第七名。将带有节点的路径从N* 转换为带有节点的nity [10].此外，它是一种可以在整个研究周期中使用的语言，从获取和分析数据到甚至通过交互式网站显示数据。特别是为这类图形问题提供一个免费且易于使用的工具。构建一个包含多种转换算法的通用平台，每种算法都适合不同的需求。开源，开放的可能性，实现自己的功能纳入包。一个显著的优点是，主要贡献如下：出版了一个现成的软件包，用于将具有已知禁止路径的有向图转换为可以使用传统和有效的最短路径算法求解的图。利用R的并行处理能力，为用户提供了简单的配置。是否存在转换路径的功能，以及包• 开放源代码资源，提供添加更多内容from N parse_vpath（names（shortestPath））（八）算法，并且能够包括来自社区的贡献······270M. Vidoni和A. Vecchietti / SoftwareX 9（2019）2655. 结论本文介绍了因此，该转换过程允许在结果图上使用传统的最短路径函数。它的输入和输出数据是以原生R数据类型生成的，最大限度地提高了包更重要的是，该软件包利用了R的并行处理，为用户提供了一种简单的方式来配置其使用。已经分析了时间和资源限制，测试图可以在GitHub存储库中找到。‘‘rsppfp’’作者打算通过实现其他学术作者提供的不同解决方案来添加这些例子是SPPFP的基本版本，以及当禁止路径的集合事先不知道时的算法致谢作 者 非 常 感 谢 阿 根 廷 国 立 科 技 大 学 （ UTN ） 通 过 PIDEIUTIFE0003974TC对本文所述工作的财政支持。此外，作者赞赏地认识到匿名评审员的非凡努力，他们为提高文章的阅读和代码的质量提出了利益冲突作者声明不存在利益冲突引用[1] Villeneuve D ， Desaulniers G. 有 禁 止 路 径 的 最 短 路 问 题 。 European JOperRes2005;165（1）：97-107.http://dx.doi.org/10.1016/j.ejor.2004.01.032.[2] Ahmed M， Lubiw A.避免 禁止子 路径的最 短路径 In：Symposium ontheoretical aspects of computer science.弗赖堡，德国; 2009年。第63-74页。https://hal.archives-ouvertes.fr/STACS2009/inria-00359710网站。[3]杨海辉，陈永林。求具有等待时间的k条最短循环路在时间窗口网络中应用数学模型2006;30（5）：458网址：//dx.doi.org/10.1016/j.apm.2005.05.005网站。[4]杨 海 辉 ， 陈 永 林 。 求 交 通 灯 网 络 中 的 K 条 最 短 环 路 。 Comput Oper Res2005;32（3）：571-81. http://dx.doi.org/10.1016/j.cor.2003.08.004.[5]恰尔迪·G，内普斯·T.用于复杂网络研究的igraph软件包。InterJ Complex Syst2006;1[6] 作者：J. P. WGCNA ：一个用于加权相关网络分析的R软件包。 BMCBioinformatics 2009;9. http://dx.doi.org/10.1186/1471-2105-9-559.[7]徐成成，陈德荣，丁宏英.带禁止路的最短路问题的一个有效算法。在：国际会议上的算法和架构的并行处理。LNCS，第5574卷。台北，台湾; 2009年。第638- 650页。https://doi.org/10.1007/978-3-642-03095-6_60网站。[8] 威克姆·H Ggplot2：用于数据分析的优雅图形。第2版，瑞士：SpringerInternationalPublishing;2016 ， http://dx.doi.org/10.1111/j 。 1541-0420.2011.01616.x。[9]Guerriero F.资源受限最短路径问题综述：精确解方法。Netw Int J 2013;62（3）：183网址：//dx.doi.org/10.1002/net.21511网站。[10] 蒂普曼编程工具：R的冒险。Int Wkly J Sci 2015;517：109-10.http://dx.doi.org/10.1038/517109a网站。