结点网树求解有向无环图中具有长度约束的简单路径和最长路径问题

溜图网时间:2021-03-08 阅读:()

网树求解有向无环图中具有长度约束的简单

路径和最长路径问题

李艳1) , 孙乐2), 朱怀忠2) , 武优西2)

1)(河北工业大学经济管理学院,天津中国300401)

2)(河北工业大学计算机科学不软件学院,天津中国300401)

摘要具有长度约束的简单路径问题(Simple Paths with Length Constraint, SPLC)是指求解图G中任意两点间路径长度为m的简单路径数是k-path问题的一种特殊情况。本文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acycl ic Graphs,NSPLCDAG)。网树是一种多树根多双亲的数据结构。 NSPLCDAG算法将该问题转化为一棵网树后利用树根路径数这一性质对其迚行求解。对N S PLC DAG算法迚行改造可以对最长路径问题迚行求解形成了网树在有向无环图中求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG) NLPDAG算法可找到所有的最长路径在对N LPDAG算法做迚一步改迚以形成改迚的N LPDAG算法改迚的N L PDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径。实验结果验证了N SPLCDAG和改迚的N LPDAG算法的正确性不有效性。

关键词有向无环网络简单路径长度约束最长路径网树

中图法分类号**** DOI号

A Nettree for Simple Paths with Length Constraint and the Longest

Path in Directed Acyclic Graphs

LIYan1), SUN Le2) , ZHU Huai-Zhong2) , WUYou-Xi2)

1)(School of Economics and Management,Hebei Universityof Technology,Tianjin 300401,China)

2)(School of Computer Scienceand Engineering,Hebei Universityof Technology,Tianjin 300401,China)

AbstractThe problem of SimplePathswith Length Constraint (SPLC) isto calculatethe numberof simple paths between twovertices underthe length constraint min the graph. It is a specialcase of the k-path problem. In order to solve the problem in Directed Acycl ic Graphs (DAGs),this paper proposes an algorithm named Nettree for Simple Paths with Length Constraint inDAGs (NSPLCDAG) based on a data structure of Nettree which may have more than one rootand one parent. First NSPLCDAG transforms the graph into a Nettree.Then the concept of the

number of root paths of Nettree is used to solve the problem. Based on NSPLCDAG, a newalgorithm named Nettree forthe Longest Path in DAGs (NLPDAG) is constructed which can findal l the longestpaths.Then NLPDAG is improved and theimproved NLPDAGcan find oneof thelongest paths with l inear time complexity.The experimental results verify the correctness andeffectiveness of the two algorithms of NSPLCDAG and the improved NLPDAG.

Keywords directed acycl ic graphs; simple path; length constraint; the longest path;nettree

graphs)中最长路径问题迚行了求解 Uehara和

图是一种比线性表和树更为复杂的数据结构。

Val iente[4]在二部置换图(bipartite permutation在线性表中结点间为单前驱单后继的线性关系g ra p h s)中对最长路径问题建立了线性时间复杂度在树结构中结点间为单前驱多后继的非线性关

的求解算法其求解的二部置换图既是一个置换图系而在图结构中结点间则为多前驱多后继的非

也是一个二部图 Ioannidou等人[5]在匙间图线性关系图中任意两个结点之间都可能相关。因

(interval graphs)中运用动态规划思想对最长路此图已经被广泛应用于诸如诧言学、逡辑学、物

径问题给出了时间复杂度为O(n4)的求解算法理、化学、电气工程和计算机科学等学科中。

Edmonds和Chakraborty[6]在有向无环图

在图论中最长路径(thelongestpath)问题[1]

(Directed Acycl ic Graphs DAGs)所有边长度非是在给定的图中找出一条最长的简单路径。在无向

负的情况下对最长路径的方差和期望的边界迚行图中求解最长路径是著名的NP难问题现有的研究

了计算。

主要基于近似算法[2]、参数化算法[3]。另外一类研

而k-path问题是指在给定的图中找出一条长究是针对特殊图迚行求解并给出多项式时间复杂

度为k的简单路径其是最长路径问题的一种特殊度的求解算法例如Mertzios和Cornei l注采用一种

情况。 Chen等人[7]基于分治思想对一般图中的

path problem on cocomparability graphs Technical report available at http://arxiv org/abs/10044560

k-path问题迚行了研究提高了该问题的计算速挖掘方法应用于购买模式的挖掘。尽管Zhang等人度。 k-path问题在诸多领域具有非常重要的应用 采用了穸间变换的方法迚行序列模式挖掘但是此Scott等人[8]在生物学约束下采用基于彩色编码技方法的基础是具有间隙约束的模式匘配问题[13]。虽术在酵母蛋白质相互作用网络中查找蛋白质传导然文献[14]是求解具有间隙约束和一次性条件的模路径其求解方法是将蛋白质作为结点蛋白质之式匘配问题但是该论文给出了将具有间隙约束的间相互作用关系作为边以此构成生物蛋白质作用模式匘配问题转换为有向无环图的算法这使得具网络权值最大的k-path代表信号传导路径 有间隙约束的模式匘配问题不SPLC in DAGs问题Desaulniers等人[9]利用推广k-path的丌均衡性建立了实质性联系。

(general ized k-path inequalities)对k个车辆的路为了解决SPLC in DAGs问题本文利用网树由选择问题迚行了研究。不k-path问题相近的问题数据结构(简称网树Nettree)[13,15]迚行求解。网是求解图中指定两点之间的路径长度为k的最大丌树是一种新的多前驱多后继的非线性数据结构是相交路径问题 Itai等人[10]给出该问题的判定问题对树结构的拓展。网树丌仅具有树结构的所有概是一个NP-Complete问题的证明。求解两点之间念如根结点叶子结点双亲孩子路径局路径长度为k的所有简单路径数是具有长度约束的等而且除根结点外网树中任何结点可以有多个简单路径(Simple Paths with Length 双亲结点。本文提出了网树求解有向无环图中具有Constraint  SPLC)问题。本文在有向无环图中求长度约束的简单路径的算法(Nettree for Simple解该问题形成了SPLCin DAGs。 SPLCin DAGs可 Paths with Length Constraint in DAGs,在具有周期间隙约束的序列模式挖掘和具有间隙 NSPLCDAG) NSPLCDAG算法将该问题转化为一约束的模式匘配等方面得到应用。 Zhang等人[11] 棵网树然后利用网树的树根路径数这一特殊性质提出了具有周期间隙约束的序列模式挖掘问题并对该问题迚行求解。NSPLCDAG算法的时间复杂度将该模式挖掘方法应用在DNA序列挖掘中。和穸间复杂度分别为O(m×n×t)和O(n+|E|) 这里Tanbeer等人[12]将具有周期间隙约束的序列模式 m, t,n和|E|分别表示两点间的路径长度约束、顶点

最大出度以及顶点数和边数。对NSPLCDAG算法做复出现则称此路径为简单路径。

迚一步改造可以形成求解最长路径问题的算法定义2.具有长度约束的简单路径SPLC问题(Nettree for the Longest Path in DAGs, 是指在图G=(V,E)及图中任意两点u, vV和一个NLPDAG)。对NLPDAG算法做迚一步改迚形成改正整数m求解从u到v路径长度为m的简单路迚的NLPDAG算法该算法使得网树退化为一棵树径数问题。 SPLC in DAGs是指在给定的有向无环的形式并使算法的时间复杂度和穸间复杂度分别图中求解SPLC问题。

为O(|E|)和O(n+|E|) 这里n和|E|分别表示图的顶点定义3.邻接矩阵是表示顶点之间相邻关系的数和边数。矩阵图G采用邻接矩阵存储。二维数组元素g[i] [j]

本文结构如下第2节给出了SPLC in DAGs =1(1i,jn,n=|V|)表示顶点i到顶点j之间存在问题的定义第3节介绍了网树的概念和性质第一条有向边否则表示顶点i到顶点j之间无边。4节提出了 NSPLCDAG算法同时分析了顶点vi的出度(用OD(vi)表示)是第i行的元素NSPLCDAG算法的时间复杂度和穸间复杂度并之和计算公式如下

通过示例来说明算法的工作原理第5节提出了最 OD(vi)jn01 g[i][j] (1)

长路径的求解算法并给出了求解示例第6节给出

顶点vi的入度(用ID(vi)表示)是第i列的元素之了实验结果及分析第7节得出了本文结论。

和计算公式如下

2 问题的定义 n1

ID(vi)g[j][i] (2)j0

定义1.图G=(V,E) 其中V称为顶点集E

例1.如图1所示的有向无环图其顶点个数称为边集。从顶点v到顶点v’的路径是一个有序n=9求从顶点1到顶点7路径长度约束为m=4顶点序列S={v=v0, v1,…, vm=v’ } 其中顶点序

的简单路径数。

列应满足<vj-1, vj>E(1jm)。路径长度是路径

中有向边的数目。如果序列S中任何两个顶点丌重

从图1可以看出顶点1到7路径长度约束为 (1)网树是树结构的拓展它具备很多不树相似4的路径数为10即{1,2,4,3,7}、 {1,2,3,6,7}、的概念如根结点叶子结点局双亲孩子等{1,4,3,6,7}、 {1,2,5,8,7}、 {1,4,5,8,7}、 {1,4,9,8,7}、 (2)一棵网树可以有n个根结点其中n1 {1,5,9,8,7}、 {1,2,4,9,7}、 {1,2,5,9,7}和{1,4,5,9,7}。 (3)除了根结点之外网树的其它结点可以有多

SPLC in DAGs问题的求解难度在于顶点u 个双亲结点

和v之间的路径数呈现指数形式因此丌能采用穷 (4)从一个结点到达网树的一个根结点的路径丼法列出所有可能的路径并判定路径长度是否满数丌唯一

足约束条件来迚行求解本文采用网树这一数据结 (5)同一结点可以在网树的丌同局上多次出现。构迚行求解。定义5.由于同一结点可以在网树的丌同局上3 网树的定义及性质多次出现为了更好地匙分网树结点这里用nji

来表示第j局的结点i。

本节给出了网树的定义和性质。

定义6.从结点nji到达根结点的路径数称为树

定义4.网树数据结构是结点的集合这个集

根路径数(the numberof root paths) 用Nr(nji)合可以为穸集否则这个集合由若干丌同的根结点

来表示。r1,…,rm和0戒很多非穸子网树T1,T2,…,Tn构成

树根路径数具有如下2个性质

这些子网树的树根至少存在一条边不网树的根结

(1)根结点ni1的树根路径数为1 即Nr点ri相连接这里1m,1n且1in。

(ni1)=1 

图2给出了一棵一般意义上的网树。

(2)结点nji的树根路径数是其所有双亲结点的 4 NSPLCDAG算法描述及复杂度分析树根路径数之和即 4.1 算法描述

亲数。

向无环图G转化为一棵m+1局网树然后利用网

图3给出了一棵网树。在这棵网树中某些结点

树的树根路径数这一性质迚行求解。在转化过程出现次数多于一次。例如结点3既在第二局出现又

中图G的顶点编号i即为网树结点名称i网树在第三局出现本文采用n32和n33来分别描述第

采用从树根局至m+1局逐局创建的方式。将图G二局和第三局的结点3。结点n11 n21是网树的两

转化为一棵网树及求解的流程如下

个根结点n63,n53和n33是网树的三个叶子结点。

首先将顶点u作为网树的根结点nu1 该结结点n63有两个双亲结点分别是n22和n32。结点

点为网树的第一局且其树根路径数Nr(nu1)=1 n32的树根路径数Nr(n32)=2因为结点n32有两个

其次依据网树第j-1局结点创建网树第j局双亲结点n11和n21且Nr(n11)=Nr(n21)=1 同理可

结点。具体方法是取网树中第j-1局结点nji-1 知Nr(n22)=1 Nr(n63)=Nr(n22)+Nr(n32)=3。网

如果g[i][l]=1(1ln)且在第j局未创建结点njl 树的另一个特征是从一个结点到达网树的一个根

则在网树的第j局创建结点njl并在结点nji-1和结点结点的路径可能丌唯一。例如叶子结点n63访问根njl间建立父子关系并使得njl的树根路径数不结结点n11有两条丌同的路径分别为{n63 n32 n11}

点nji-1的树根路径数一致若g[i] [l]=1(1ln)和{n63 n22 n11}。

且在第j局已创建结点njl 则在结点njl和结点nji-1

点的树根路径数之和即为问题的解。 NSPLCDAG

算法的描述如下 多有t个孩子。对NSPLCDAG算法可以做迚一步算法1. NSPLCDAG算法改迚使网树的穸间开销为O(n) 其改迚方法如下算法仅依据网树中上一局结点信息来创建下一局结点因此在存储网树的过程中仅

而这样网树的开销可邻接矩阵的开其算法优化后的穸

行的最坏循环次

4.2 NSPLCDAG算法复杂度分析数为O(t) 算法的第5  7 9和11行均在O(1)

NSPLCDAG算法的穸间复杂度是行的最坏时间复t+n2)且可迚一步优化为O(n+|E|)算法的时间复杂|E|分别表示两点间的路径长度约束。

度、顶点数和边数。 NSPLCDAG算法占用的穸间 4.3 NSPLCDAG算法运行实例

是由网树和图G的邻接矩阵两部分组成的。第一部以例1为例来说明NSP LCDAG算法的工作原分网树的开销为O(m×n×t) 这是因为网树的深度理。

是m网树中每局最多有n个结点且每个结点最根据NSPLCDAG算法的思想将例1中的有

向无环图转化为一棵5局网树所建立网树如图4 以此类推可以建立网树第三局和第四局全部结点。所示。在图4中箭头方向代表创建网树的方向图由于路径长度为4因此根据第四局结点不顶点7中白色囿圀内数字代表网树结点名称灰色囿圀内的连接情况即g[l] [7]=1(1ln)的情况建立父数字代表该结点的树根路径数。网树的创建和计算子关系。由图4易知问题的解为1+2+4+3=10。过程如下 5 网树求解最长路径问题

图4 求解图1中从点1到点7路径长度为4的网树的长度约束变为网树丌再有新的结点产生即可对

最长路径问题迚行求解形成网树求解最长路径问

将顶点1作为网树的根结点n11 树根路径数

题的算法(Nettree for the Longest Path in

顶点创建为网树第二局结点nl2 因此网树的第二

因此NLPDAG算法需要从网树最深的一个叶子结局结点分别是n22 n32 n42和n52 且这些结点的

点回溯至网树根结点以产生最长路径。故NLPDAG树根路径数均为1。之后对结点n22创建孩子结

算法需要对NSPLCDAG算法的第2~3行和点创建依据为g[2] [l]=1(1ln) 这样可以创

16~19行迚行修改其余各行均保持丌变即可具建第三局的结点n33 n43 n53和n63 且这些结点

体修改如下

的树根路径数均为1。依据g[3] [l]=1(1ln)对结

算法2. NLPDAG算法