没有合适的资源?快使用搜索试试~ 我知道了~
可证明的快速和空间高效并行双连接性
520可证明快速且空间高效的并行双连通性0XiaojunDong加州大学河滨分校xdong038@ucr.edu0LetongWang加州大学河滨分校lwang323@ucr.edu0YanGu加州大学河滨分校ygu@cs.ucr.edu0YihanSun加州大学河滨分校yihans@cs.ucr.edu0摘要计算图的双连通分量(BCC)是一个基本的图问题。经典的并行BCC算法是Tarjan-Vishkin算法,它在具有�个顶点和�个边的图上具有�(�+�)的最优工作和对数级别的跨度。然而,Tarjan-Vishkin在实践中并不常用。我们认为原因是其空间低效(使用了�(�)的额外空间)。在实践中,现有的并行实现基于广度优先搜索(BFS)。由于BFS的跨度与图的直径成比例,现有的并行BCC实现在大直径图上性能较差,并且在许多现实世界的图上可能比顺序算法慢。我们提出了第一个具有最优工作、对数级别的跨度且空间高效的并行双连通性算法(FAST-BCC)。我们的算法基于输入图的任意生成树创建一个骨架图。然后我们使用骨架的连通性信息来计算原始输入的双连通性。我们对算法的正确性进行了仔细分析,这是非常复杂的。我们实现了FAST-BCC并将其与现有的实现进行了比较,包括GBBS、Slota和Madduri的算法以及顺序的Hopcroft-Tarjan算法。我们在一个96核的机器上对27个图进行了测试,这些图的边分布各不相同。FAST-BCC在所有图上都是最快的。平均而言(几何平均值),FAST-BCC在每个图上比最佳基准算法快3.1倍。0CCS概念:•计算理论→共享内存算法;图算法分析;并行算法。0关键词:并行算法,图算法,双连通性,连通性,图分析01 引言0PPoPP '23,2023年2月25日至3月1日,加拿大蒙特利尔©2023版权由所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35774830本作品采用知识共享署名国际4.0许可协议。10.524816 32 >32530我们的 GBBS SM'14 SEQ 我们的 GBBS SM'14 SEQ0Social0YT 5.88 4.36 3.15 1.000HH5 7.01 1.14 n 1.000OK 30.51 19.91 5.66 1.00 CH5 4.11 0.37 n 1.000LJ 17.92 11.77 n 1.00 GL2 6.24 1.64 n 1.000TW 34.21 17.42 2.40 1.00 GL5 8.53 1.44 n 1.000FT 39.26 18.93 10.22 1.00 GL10 10.59 4.31 n 1.000平均值21.23 12.75 4.57 1.00 GL15 11.88 5.91 n 1.000Web0GG 8.92 5.65 n 1.00 GL20 11.84 6.88 n 1.000SD 29.74 16.46 n 1.00 COS5 14.16 6.86 n 1.000CW 30.37 17.52 n 1.00 平均值8.68 2.42 - 1.000HL14 32.46 19.96 n 1.000SQR 18.50 1.59 10.56 1.000HL12 33.99 29.15 n 1.00 REC 12.48 0.36 3.02 1.000平均值 24.53 15.68 - 1.00 SQR' 8.06 0.85 n 1.000道路0CA 5.15 0.55 n 1.00 REC' 7.81 0.48 n 1.000美国 6.69 0.49 0.60 1.00 Chn7 11.97 0.04 0.08 1.000GE 10.77 1.43 2.44 1.00 Chn8 11.97 0.04 0.06 1.000平均值7.18 0.73 1.21 1.00 平均值11.30 0.27 0.18 1.000TOTAL MEAN 12.89 2.50 0.96 1.000平均值=几何平均数 n0图1.并行BCC算法相对于顺序Hopcroft-Tarjan算法[45]在96核(192超线程)上的加速比热图。较大/绿色表示更好。数字表示并行算法比顺序Hopcroft-Tarjan算法快多少倍(<1表示更慢)。两个基准算法来自[31,64]。完整结果见表2。0在我们的实验中,我们观察到现有的并行实现甚至在许多现实世界的图上都比顺序的Hopcroft-Tarjan算法慢(参见图1中的GBBS [31]和SM'14[64])。在本文中,我们提供了第一个空间高效(�(�)辅助空间)的并行双连通性算法,该算法具有高效的�(�+�)工作和对数级别的跨度。我们的骨架�'是基于任意生成树(AST)的。与Tarjan-Vishkin不同,我们的�'是�的子图,并且可以在�(�)辅助空间中隐式维护。关键思想是精确地识别一些围栏边,这些边指示了BCC的“边界”。在高层次上,我们将所有图边分为围栏树边,普通(非围栏)树边,返回边和交叉边。我们的骨架�'包含普通树边和交叉边。使用�(�)空间,我们可以有效地确定�中每条边的类别。在处理骨架时,我们使用输入图�,但跳过围栏和返回边。我们展示了�的BCC信息可以从�'的CC信息加上一些简单的后处理来构建。由于我们的算法基于“围栏任意生成树”,我们将我们的算法称为FAST-BCC。有关FAST-BCC的更多细节,请参见图2。我们注意到,从概念上讲,我们的算法很简单,但正确性分析非常复杂。我们实现了我们在理论上高效的FAST-BCC算法,并将其与最先进的并行基于BFS的BCC实现GBBS [31]和SM'14[64]以及顺序的Hopcroft-Tarjan算法进行了比较。我们测试了27个图,包括社交、Web、道路、�-NN和合成图,其规模和边分布差异显著。图和结果的详细信息0在表2中给出了我们的结果。我们还在图1中展示了相对运行时间,相对于顺序的Hopcroft-Tarjan进行了归一化。在具有96个核心的机器上,FAST-BCC在所有测试的图上都是最快的。我们使用几何平均数来比较多个图上的“平均”性能。由于工作效率和空间效率,我们的单核算法与Hopcroft-Tarjan相比具有竞争力(平均慢2.8倍)。对于所有类型的图(平均15-66倍自相对加速),对数对数的跨度导致良好的并行性。在直径较小的图(社交和Web图)上,虽然GBBS和SM'14也实现了良好的并行性,但FAST-BCC仍然比这两者中最好的快1.2-2.1倍,并且比顺序的Hopcroft-Tarjan快5.9-39倍。对于直径较大的图(道路,A-nn,网格和链图),现有的基于BFS的实现可能比Hopcroft-Tarjan表现更差。由于跨度较低,FAST-BCC比GBBS快1.7-295倍(平均10倍),比顺序的Hopcroft-Tarjan快4.1-18.5倍(平均9.2倍)。对于所有图形,FAST-BCC的平均速度比三个现有实现中最好的速度快3.1倍。我们的代码可以公开获取[36]。我们在本文的完整版本中提供了更多的结果和分析[37]。02. 预备知识计算模型。我们使用工作-跨度(或工作-深度)模型来分析并行算法中的分支-合并并行性,其中分支是二分支分叉[15,30],最近在许多并行算法的论文中使用[3, 10, 11, 13, 14,16-22, 33-35, 42, 43, 62,71]。我们假设一组共享公共内存的线程。一个进程可以分叉两个子软件线程以并行工作。当两个子线程都完成时,父进程继续执行。算法的工作是计算过程中指令的总数,跨度(深度)是计算中最长的一系列依赖指令的长度。如果算法的工作与最佳顺序算法的工作渐近地相同,则称该算法是工作有效的。我们可以使用随机化的工作窃取调度器[6,23]来执行计算。我们假设单位成本的原子操作compare_and_swap(A, Aold,Anew)(或CAS),它以原子方式读取由A指向的内存位置,并在当前值为Aold时将值Anew写入其中。如果成功则返回true,否则返回false。符号。给定一个无向图A = (V,E),我们使用|V|表示A的顶点数,|E|表示A的边数。diam(A)表示A的直径,A-y表示A和y之间的边。CC和BCC的定义见第1节。关节点(或割点)是一种顶点,其移除会增加CC的数量。桥(或割边)是一种边,其移除会增加CC的数量。对于一个连通图A的生成树A是一个包含没有回路的A的子图。如果A是非连通的,则生成森林的定义类似。为简单起见,我们假设A是连通的,但我们的算法和实现适用于任何图。给定一个图A和一个有根生成树540A = (V, E):输入图A = (V, E):A的生成树0A,A,A,A,A,hA,A,A,y,A,A',A',A'... ∈ A:A中的顶点0A-y ∈ E:A中的一条边A, A:A中的一个BCC0AA:A在A中的子树hA:A的BCC头0A(A):A在A中的父节点A ~ y:A中的一条树路径0A = A - y - ...:一条路径A':骨架0栅栏边:(A(A), A) ∈ E,(A, y) ∈ V,其中A ∈ V且y � V(A)0(A的子树中没有边从A(A)的子树中逃逸)0普通边:(A(A), A) ∈ E,(A(A),A)不是栅栏边,反向边,交叉边:A中的边 \V(A)的定义与通常相同。FAST-BCC中的骨架A' = (V, E'):A' ={普0表1. 本文中的符号和术语。0树A中的边是树边,如果它在A中。非树边是反向边,如果一个端点是另一个端点的祖先,否则是交叉边。图2中的第3步显示了一个示例。如果A是BFS树,则没有反向边;如果A是DFS树,则没有交叉边。我们用A ~y表示A和y之间的树路径。我们将顶点A的父节点表示为A(A),将A的子树表示为A(A)。本文中使用的符号见表1。我们在A中高概率(whp)使用A(A(A))表示至少有1-1/A-A的概率A(A(A))。Euler游览技术(ETT)。ETT是Tarjan和Vishkin在他们的BCC算法中提出的一种根据生成树的方法。后来,ETT成为顺序和并行环境中广泛使用的原语,包括计算几何[2]、图算法[5, 28,67]、维护子树或树路径和[30]等等。ETT在Tarjan-Vishkin中是必需的,因为当为图生成任意生成树(例如从CC算法)时,它没有根,因此我们没有顶点的父子信息。给定一个有�−1条边的未根化树A,ETT找到A的欧拉游览,即遍历A中的每条边恰好两次(每个方向一次)的循环。ETT首先在2�−2个有向树边上构建一个链表,并在其上运行列表排名。关于ETT的更多细节,我们将读者参考并行算法的教材[47, 58]。使用[15,44]中的半排序算法和[15]中的列表排名,ETT的工作代价是�(�)的期望工作和�(log�)的跨度whp。给定�,我们可以将任何顶点设置为�的根,并使用ETT确定边的方向。然后我们可以确定任何顶点的父节点,以及�中的边是树边、反向边还是交叉边(1工作)。03种现有的BCC算法0本节回顾了现有的BCC算法和实现。我们将使用骨架连通性框架来描述现有的BCC算法。骨架阶段从�生成一个辅助图�',然后连通性阶段在�'上计算连通性以构造�的BCC。现有的BCC算法可以根据生成骨架�'的方式进行分类。Hopcroft-Tarjan算法使用基于DFS的骨架;Tarjan-Vishkin算法基于一个0任意生成树(AST);几乎所有其他BCC算法(参见第3.3节)使用基于BFS的骨架。03.1 Hopcroft-Tarjan算法0顺序地,Hopcroft-TarjanBCC算法[45]使用深度优先搜索(DFS)树A进行A(A +A)的工作。基于A,为每个顶点分配两个标签first[∙]和low[∙]。first[A]是A中每个顶点的先序号。low[A]给出通过非树边和A本身与A ∈AA相连的任何顶点上最早(最小的先序号)的顶点。更正式0为了计算BCC(双连通分量),我们需要维护一个额外的栈。每次访问一个新的边时,将其推入栈中。当发现关节点A(A的low[A] ≥ first[A(A)])时,从栈中弹出边,直到弹出A -A(A)。这些边和相关的顶点形成一个BCC。从概念上讲,Hopcroft-Tarjan算法中的骨架是DFS树,不包含A -A(A)的“栅栏边”,当low[A] ≥first[A(A)]时。这个洞察也启发了我们的BCC算法。03.2 Tarjan-Vishkin算法0Hopcroft-Tarjan使用DFS树作为骨架,但DFS本质上是串行的,很难并行化[57]。为了并行化BCC,Tarjan-Vishkin算法[65]使用任意生成树(AST)代替DFS树。该生成树�可以通过任何并行CC算法获得。然后,该算法使用ETT(该论文中也提出了ETT)来根化树�(见第2节)。然后算法构建一个骨架�' =(�,�')并在其上运行连通性算法。我们在完整论文[37]中对�'进行了更详细的描述,在此仅简要回顾。�'中的顶点对应于�1中的边。为了确定�'中的边,该算法对每个顶点使用四个标记(first[∙],last[∙],low[∙]和high[∙])。其中,first[�]和last[�]是顶点�在欧拉游览中的第一次和最后一次出现(注意,这与Hopcroft-Tarjan中的first[∙]不同,但在概念上是等价的)。low[�]与Hopcroft-Tarjan中的定义相同,而high[�]则对称定义:0high[�] = max{�2[�] | � ∈ �且�在以�为根的子树中} �2[�] =max{{first[�]} ∪ {first[�'] | (�,�') � �}}0所有标记可以在�(� +�)的期望工作量和�(log�)的span下使用ETT计算出来。然后,Tarjan-Vishkin在�'上找到CCs以计算�的BCCs。然而,在Tarjan-Vishkin中,�'可能很大,使得算法不太实用。假设有一个高效的ETT和并行CC算法,Tarjan-Vishkin使用�(� +�)的最优期望工作量和对数级的span。然而,空间低效性阻碍了Tarjan-Vishkin的实用性,因为�'包含�(�)条边。在我们的实验中,Tarjan-Vishkin最多需要01 在后来的一篇论文[39]中,证明了�'中的顶点数可以减少到�(�),但|�'|仍然是�(�)。55011 ×比我们的FAST-BCC或GBBS多出的空间。在我们的1.5TB内存机器上,Tarjan-Vishkin在处理Clueweb图[54]时内存不足,尽管存储图仅需约300GB(详见完整版本[37]中的讨论)。大量的空间使用禁止在大规模图上在大多数多核机器上运行Tarjan-Vishkin。即使对于小图,高空间使用率也会增加内存占用和降低性能。一些现有的BCC实现(例如GBBS[31]和TV-filter[29])也被描述为Tarjan-Vishkin算法,可能是因为它们也使用了骨架连接框架。我们注意到它们的正确性依赖于基于BFS的骨架(即稀疏证书[27]),并将它们与其他几个算法一起分类。03.3 其他已有的算法/实现在Tarjan-Vishkin之前,Savage和JáJá[61]展示了一种基于矩阵乘法的并行BCC算法,其工作量为�(�3log�)。Tsin和Chin[66]提出了一种使用AST骨架的算法。它与Tarjan-Vishkin非常相似,但工作量为�(�2)。为了实现空间效率,许多后来的并行BCC算法使用了基于BFS的骨架[25, 26, 29, 31, 40, 50, 64,68]。其中许多算法使用了稀疏证书[27]的类似思想。使用BFS树的BCC要简单得多-所有非树边都是具有相同或相邻级别的两个端点的交叉边。Cong和Bader的TV-filter算法[29]使用骨架作为BFS树�,并使用�\�(�(�))的任意生成树/森林。Slota和Maduri的算法[64]和Dhulipala等人的算法[31]使用骨架作为输入图�,不包括�(�)个顶点/边。其他算法[25, 26, 40,68]使用BFS树作为骨架,并动态计算连通性。所有这些算法都具有空间效率。它们的骨架图要么具有�(�)的大小[25, 26, 29,40, 68],要么可以使用�(�)的信息隐式表示[31,64]。然而,生成BFS树的跨度与图的直径成比例,这对于直径较大的图来说效率低下。03.4 空间高效的BCC表示由于某些顶点(关节点)出现在多个BCC中(见图2),我们需要以空间高效的方式表示所有BCCs(�(�)空间)。我们在算法中使用了一种常用的表示方法[11, 31,40]。给定一棵生成树�,我们为除�的根之外的每个顶点分配一个标签,指示该顶点所在的BCC。对于具有相同标签的所有顶点,我们找到另一个称为组件头的顶点(详见第4.1节),该顶点与该标签相关联。具有相同标签和相应组件头的所有顶点形成一个BCC。图2给出了这种表示的示例。很容易看出,这种表示使用了�(�)的空间,因为我们对所有顶点有�-1个标签,并且最多有�-1个组件头。0算法1:FAST-BCC算法0输入:一个无向图� = (�, �)输出:顶点的标签�[∙],以及每个BCC的组件头01 计算�的生成森林� � 第一个CC02 使用欧拉游览技术以�为根对树进行根化 � 根化03 根据欧拉游览计算每个顶点的标签(例如low,high) � 标记04 使用满足InSkeleton(�, �) =true的边在�上进行连通性计算,计算顶点标签�[∙],并得到最后的05 并行对于所有� ∈ �且�[�] ≠ �[�(�)]的顶点进行操作06 将�[�]的组件头设置为�(�)07 函数InSkeleton(�, �) � 判断�-�是否在骨架�'中08 如果(�, �)是一条树边,则09 返回¬Fence(�, �)且¬Fence(�,�)010 否则返回 ¬Back(�, �) 且 ¬Back(�,�)011 函数Fence(�, �) � 判断树边是否为围栏边012 返回 first[�] ≤ low[�] 且 last[�] ≥ high[�]013 函数Back(�, �) � 判断非树边是否为后向边014 返回 first[�] ≤ first[�] 且 last[�] ≥ first[�]04 FAST-BCC算法在本节中,我们介绍我们的FAST-BCC算法及其分析。我们的算法是第一个既具有工作效率又具有空间效率且具有对数级span的并行BCC算法。回顾BFS-based算法是空间效率的,但是BFS本身不易并行化。Tarjan-Vishkin基于AST并且具有高度并行性,但生成骨架的空间效率低。要实现高并行性和空间效率,我们需要新颖的算法洞察力。有趣的是,我们的关键思想是重新审视顺序DFS-based的Hopcroft-Tarjan算法(第3.1节)。尽管DFS本质上是顺序的,但Hopcroft-Tarjan中的洞察力启发了我们的并行BCC算法。Hopcroft-Tarjan中的(隐式)骨架非常简单,骨架大小小(�(�))。与许多后来的并行BCC算法中基于Fact4.2组合循环的高层次思想不同,Hopcroft-Tarjan中的思想是“围栏”条件,如下所示。在计算骨架�'(DFS树)上的CC并遍历从�到�(�)的边时,如果low[�] ≥first[�(�)],则�'上的CC(�上的BCC)被称为被围栏。此条件将DFS树�划分为多个对应于�中的BCC的CC。请注意,Hopcroft-Tarjan中的�'仅包含DFS树的边,因为DFS树中没有交叉边,并且所有后向边信息都由low[∙]捕获。现在我们尝试将这个思想推广到任意生成树(AST)。直接使用Hopcroft-Tarjan中的“围栏”条件不起作用,因为我们需要处理交叉边。请注意,Hopcroft-Tarjan中的围栏边�-�(�)意味着�的子树中的顶点没有逃逸的边(即另一个端点在�(�)的子树之外)。我们也根据这个条件定义了我们的围栏边。更正式地说,我们说一个树边(�, �)其中� =�(�)是一条围栏边560如果没有边 ( �,� ) ∈ � ,使得 � ∈ � � 并且 � � � � ,直观上,� 的子树 � � 与 � �之外的其他部分“隔离”,并且只通过 � �与外部世界交互。为了得到AST的等价条件,我们借鉴Tarjan-Vishkin的思想,计算四个辅助数组 first [∙], last [∙], low [∙] 和 high [∙] 。然后,“隔离”条件变为 low [ � ] ≥first [ � ( � )] 和 high [ � ] ≤ last [ � ( � )] 。一棵非围栏树边被称为一个普通边。注意,后向边的信息已经包含在 low [∙] 和 high [∙]数组中,这些数组也用于确定围栏边。我们的算法将像Hopcroft-Tarjan一样忽略后向边,而我们的骨架 � ′ 包含普通树边和跨边。0由于我们算法的主要方法是对任意生成树进行围栏操作,所以我们将我们的算法称为FAST-BCC。我们注意到,围栏算法的高层次思想(在生成树上找到一些特殊边)在一些现有工作中也被使用[11, 31,64]。我们的骨架设计和围栏条件是第一个实现BCC问题的工作效率、对数级跨度和空间效率的方法。算法的概要见图2,伪代码见算法1。尽管我们的围栏算法很简单,但我们注意到正确性证明(第4.2节)非常复杂。04.1 算法细节 我们的FAST-BCC算法有四个步骤:First-CC(生成生成树), Rooting(使用ETT根化生成树),Tagging(计算first [∙], last [∙], �1[∙], �2[∙], low [∙], high [∙],�[∙])和Last-CC(在骨架上运行CC和后处理)。在骨架连接性框架中,前三个步骤是骨架阶段(计算骨架 � ′ ),最后一步是连通性阶段(在 � ′上运行CC以找到 �中的所有BCC)。First-CC(图2的第1步,算法1的第1行)。该步骤在 �中找到所有的CC,并生成一个生成森林 �。为了简化起见,接下来我们关注一个CC及其生成树 �,此时还未根化。如果 �包含多个CC,则可以并行处理它们。运行CC仅需要 � ( � )的辅助空间。Rooting(图2的第2步,算法1的第2行)。我们使用Eulertour技术(ETT)来根化 �,这意味着树边的方向(图2的第2步)。ETT需要 � ( � )的空间。Tagging(图2的第3步,算法1的第3行)。该步骤生成算法中使用的标签,包括 �1[∙], �2[∙], low [∙], high [∙], first [∙], last[∙](与Tarjan-Vishkin中相同,参见第3节)和父数组 �[∙]。通过循环遍历所有边并获取 �1 和 �2 数组,并应用 �的1D区间最小查询(RMQ)来计算 low [∙] 和 high [∙] 值。该步骤需要 �( � + � ) 的工作和 � ( log � )的跨度[15]。这些标签将有助于决定四种边的类型(详见下文)。所有标签数组的大小为 � ( � )。Last-CC(图2的第4步,算法1的第4-6行)。如前所述,我们的骨架图 � ′包含普通树边和跨边。由于我们算法的主要方法是对任意生成树进行围栏操作,我们将我们的算法称为FAST-BCC。我们注意到,围栏操作(在生成树上找到一些特殊边)的高层次思想也被一些现有工作所使用[11, 31,64]。我们的骨架设计和围栏条件是第一个实现BCC问题的工作效率、对数级跨度和空间效率的方法。算法的概要见图2,伪代码见算法1。尽管我们的围栏算法很简单,但我们注意到正确性证明(第4.2节)非常复杂。0为了实现空间效率,我们不显式存储 � ′ 。由于 � ′ 是 �的子图,我们可以直接使用 �,但跳过围栏边和后向边,这可以使用第3步生成的标签来确定(第7-14行)。然后,我们计算骨架 � ′上的CCs(第4行),为每个顶点分配一个标签 � [ � ](图2的第4.1步)。在引理4.11中,我们证明了如果两个顶点在 �′ 中相连,它们必须在输入图 �中是双连通的。然后,我们通过循环遍历所有围栏边(图2的第4.2步)为每个标签分配一个头(第5和6行)。对于一个围栏边 � – �( � ) ,如果 � 和 � ( � ) 有不同的标签(第5行),则 � ( � )(直观上)将 �下面的顶点与图中的其他部分隔离开来。因此,我们将 � ( � )分配为 � 的CC在 � ′中的组件头。我们在引理4.9和4.12中证明了这一步的正确性。该步骤也只需要 � ( � ) 的辅助空间,这是在 �上运行CC但跳过某些边所需要的。04.2 FAST-BCC算法的正确性0我们现在证明算法的正确性。注意,我们的算法将首先识别生成树,然后分别处理每个CC。为了简化起见,本节中我们专注于 �中的一个CC。在下文中,当我们使用关于图的生成树的概念(例如根、父节点、子节点和子树)时,我们指的是我们算法中第1步识别出的特定生成树,并用 � 表示它。回顾一下,� �表示以顶点 � 为根的子树,� ~ � 表示在 � 上从 � 到 �的路径。表1中给出了一些其他的符号约定。在一个生成树中,我们说节点 � 比节点 � 更浅(深),如果 � 比 �更靠近(更远离)根。我们将节点和顶点互换使用。我们注意到,尽管算法1很简单,但正确性证明是复杂的。我们在图2中展示了事实、引理和定理之间的关系。由于篇幅限制,事实4.1和4.2以及引理4.3到4.5的证明在全文中给出,我们主要关注反映我们新算法中一些关键思想的证明。我们首先给出一些基于定义的BCC的事实。0事实4.1. 两个BCC最多共享一个公共顶点。0事实4.2.对于图中的一个环,环上的所有顶点都在同一个BCC中。0引理4.3. 给定一个图 � ,每个BCC中的顶点 � � �也必须在一个任意生成树 � 中相互连接。0由于每个BCC � 必须在 �的生成树中是连通的,因此在该BCC中必然存在一个唯一的最浅节点。我们称这个最浅节点为BCC �的BCC头,并将其表示为 � � 。0引理4.4.每个非根BCC头都是一个关节点。关节点必须是一个BCC头。0引理4.5. 算法1中的函数InSkeleton(第7行)可以正确地跳过围栏和后向边。570图2. FAST-BCC 算法的概要和一个运行示例。四个步骤在第4.1节中详细解释。0图3.算法1的正确性证明结构。0接下来,我们展示了普通树边的一个有用属性。0引理4.6. 对于一个普通树边 � – � ,其中 � 是 � 的父节点,令 � 的父节点,则 �,�,� 是双连通的。0证明. 由于 � – � 不是一个围栏边,必须存在一条边 � – � ,使得� ∈ � � 并且 � � � � 。这个环 � ~ � – � ~ � – � – � 包含。根据事实4.2,� , � 和 � 在同一个BCC中。□0接下来,我们展示算法1可以正确地识别所有的BCC。我们将展示两个方向。首先,如果两个顶点 � 和 �是双连通的,算法1必须将它们放入一个BCC中。其次,对于算法1在找到的任意一个BCC中的任意两个顶点 � 和 �,它们必须是双连通的。0定理4.7. 对于 �, � ∈ �,如果它们是双连通的,算法1会将它们分配到同一个BCC中。0为了证明定理4.7,我们讨论两种情况: 1) � 和 �中有一个是BCC头,2) � 和 � 都不是BCC头。0引理4.8. 对于一个BCC � 和两个顶点 �, � ∈ � \ { � � },它们在′ 中是被连接的,并且在算法1中会得到相同的标签。0证明. 如果连接 � \ { � � } 的所有树边都是普通树边,� 和 � 已经在 � ′ 中连接。接下来,我们展示每条围栏边的两个端点也在 � ′中连接。为了做到这一点,我们首先对所有顶点进行排序(仅在概念上),然后找到相邻的顶点对,其中一个在 �中,另一个在 � ′中。然后,我们将这些顶点对连接起来,直到每个顶点都属于某个连通分量。我们在这个过程中遵循围栏边的定义,即 � – �是一条围栏边当且仅当 � 是 � 的父节点,� 是 � 的父节点,� � � � ,并且 � ∈ � � 。我们证明了这一连接过程将连接所有在 � ′中是连通的顶点。由于 � ′ 是 � 的子图,所以 � ′ 中的顶点也在 � 中连接。因此,� 和 � 是连通的,证毕。0在 � \ { � � } 中,按照它们在 �中的深度对顶点进行排序。然后,我们自底向上(从深到浅)归纳地显示,给定一个顶点 � ∈ �,� � ∩ �(� 在 � 中的子树)在 � ′中是连通的。基本情况是 � \{ � � }中最深的顶点。在这种情况下,它们的子树只包含一个顶点,因此它们是连通的。我们现在考虑归纳步骤——如果对于所有深度 ≥ � 的顶点,它们在 � 中的子树在 � ′中是连通的,则对于深度为 � − 1 的所有顶点,它们在 �中的子树在 � ′ 中也是连通的。考虑一个深度为 � − 1 的顶点 �∈ � \ { � � }。如果 � 在 � 中只有一个子节点 � ,那么 � – �是一条普通树边,否则 � 的子树无法逃离 � 的子树,�将是一个关节点(断开 � 和 �(�)),这与引理 4.4 矛盾。假设� 有多个子节点 � 1,...,� � 在 � 中。让 � – � 是一条不在 � ′中的栅栏边,其中 � = � � 是 � 的一个子节点。我们将证明 � 和 � 在� ′ 中仍然是连通的。由于 � 不是BCC头,�(�) 也必须在 �中。根据BCC的定义,如果我们移除 �,� 和 �(�) 仍然在 �中连通。设路径为 � = � – � 1 – � 2 –...– � � – �(�),其中 � � ∈ �,� � ≠�。我们将构造一条从 � 到 � 的路径在 � ′ 中连接 � 和 �。让 � � + 1是路径 � 中的第一个不在 � � 中的顶点。我们将使用路径 � = � 0 –� 1 – � 2 –...– � �。该路径上的所有节点的深度都 ≥�。由于归纳假设,如果一些边是反向或栅栏边,我们可以用 � ′中的路径替换它们,并将此路径表示为 � ′。然后,由于 � � + 1 � �� 与 � � ∈ � � 相连,树路径 � � ~ �上的所有边都是普通树边。因此,� 和 � 在 � ′ 中通过路径 � ′ 从 �到 � � 相连,并且通过从 � � 到 � 的树路径(所有边都在 � ′中)相连。通过归纳,� \ { � � } 中的所有顶点在 � ′中是连通的,因此在第4行之后它们都获得相同的标签。□0引理 4.9。任何BCC头都将在算法 1中正确地被标识为组件头。0证明。考虑一个BCC � 及其BCC头 � �。在 � � 的所有子节点中,�的一个子集 � 在同一个BCC � 中。考虑 � 中的任何�。我们将证明边 � – � � 在第5行中必须被正确地标识。580我们首先展示 � – � � 必须是栅栏边。如果 � � 是 � 的根,那么所有连接到 � �的树边都是栅栏边。否则,可以从引理 4.6 的逆否推断出这一点。如果 � – � �是一条普通树边,那么 �、� � 和 �(� �) 必须是双连通的,这意味着 �(� �) 也在BCC �中。这与 � � 是BCC头(BCC中最浅的节点)的假设矛盾。然后,我们证明在我们对骨架 �′ 运行CC之后。0(第4行),� � 和 � 具有不同的标签(即,� � 和 � 在 � ′中不相连)。假设存在一条路径 � 从 � 到 � � 在 � ′ 上。在 � �之前,考虑路径上的最后一个节点 �。因为 � � – �是一条栅栏边,在 � ′ 中被忽略,所以 � ≠�。我们讨论三种情况。(1) � 不在 � � 的子树 � � 中。在路径 上找到第一条边 � – �,其中 � ∈ � � � 并且 � ≠ � � � � 。由� � 的子树,树路径 � ′ = � ~ � � 只包含普通树边。设 � ′ 是路上的 � � 子节点。根据引理 4.6,� ′、� � 和 �(��)是双连通的。在这种情况下,� � – � ~ � ~ � ′ – � �是一个循环,根据事实 4.2,� ′、� � 和 � 是双连通的。事实 4.1的逆否表明 � ′、� �、� 和 �(� �) 都是双连通的,与 � �是BCC头(BCC中最浅的节点)的假设矛盾。(2)� ∈ � � �,但不是 � � 的子节点。这是不可能的,因为� – � �是一条反向边,不在 � ′ 中。(3)� 是 � �的子节点。这种情况与(1)类似。通过将先前的证明中的 � ′替换为�,我们可以得到相同的矛盾。结合所有情况可以证明,在 � ′中不存在 � � 与其子节点之间的路径,因此 �[� �] 与其子节点在 中的标签不同。□0结合引理 4.8 和 4.9,我们可以证明定理4.7。然后我们展示另一个方向——算法 1计算出的所有BCC确实是双连通的。0定理 4.10。如果算法 1 将两个顶点 � 和 �标识为同一个BCC中的顶点,则它们必须是双连通的。0类似于前一个证明,我们考虑两种情况:(1)两个顶点都不是组件头(它们在 � ′ 中相连),在引理 4.11中证明,和(2)其中一个顶点在第6行中被标识为组件头,在引理 4.12 中证明。0引理 4.11。如果骨架 � ′ 中的两个顶点 � 和 �相连,则它们是双连通的。0证明。由于 � 和 � 在 � ′ 中相连,存在一条路径 � 从 � 到 � 只使中的边。设 � 为 � = � 0 – � 1 –...– � � − 1 – � � =�。我们将展示在移除路径 � 上的任何顶点 � �,其中 1 ≤ � < �,1 和 � � + 1 仍然是连通的,这意味着 � 和 �是双连通的。我们总结了所有可能的局部结构,分为三种情况,根据 � � − 1 (和 � � + 1 )是否是 � � 的子节点在 � 中。情− 1 和 � � + 1 都是 � � 的子节点。由于 � � − 1 – � �不是栅栏边,必然存在一条边 � – �,其中 � ∈ � � � − 1,� � ��。类似地,对于 � � – � � + 1,存在一条边(� ′,� ′),其中 + 1 且 � ′ � � � �。因此,在不使用 � � 的情况下,� � − 1 和0� � + 1 仍然通过路径 � � − 1 ~ � – � ~ � ′ – � ′ ~ � � + 1相连。在这里,由于 �、� ′ � � � �,� ~ � ′ 不包含 � �。情况2:� � − 1和 � � + 1 中的一个是 � � 的子节点。不失一般性,假设 � � − 1是子节点。由于 � � − 1 – � � 不是栅栏边,必然存在一条边 � –�,其中 � ∈ � � � − 1,� � � � �。同样,由于 � � + 1 要么是 � �的父节点,要么使用交叉边与 � � 相连,� � + 1 � � ��。因此,在不使用 � � 的情况下,� � − 1 和 � � + 1 仍然通过路径 � �− 1 ~ � – � ~ � � + 1 相连。情况3:� � − 1 和 � � + 1 都不是 � �的子节点,并且它们都不在 � � �中(否则它们将通过反向边相连)。在不使用 � � 的情况下,� �− 1 和 � � + 1 仍然通过树路径 � � − 1 ~ � � + 1相连。由于在路径 �上移除任何顶点都不会断开路径,骨架中的所有顶点都是双连通的。□0证明。 首
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功