(译)Proxies for Shortest Path and Distance Queries

这篇paper是马帅老师发在TKDE 2016的一篇paper。这篇paper主要的思路就是选取原图的一部分代理点(proxies)来保存原图的距离信息,来进一步加快最短路查询的速度。本文主要是翻译这篇paper以及对这篇paper的理解,细节性的东西请移步马老师的论文。

图的基本定义:

cut-node: 对于图中的一个点,如果把这个点移除会增加原图联通分支的数量,那么我们称这个点为cut-node。

BCC(bi-connectted components): 如果一个子图的边集中,任何两条边都落在同一个cycle中的话,我们称这样的子图为BCC。文章中的例子可以注意到,如果只有一条边的子图也可以算是一个BCC,因为没有两条边,所以上述的条件也是满足的,是一个特殊的例子。

代理点的定义:(Routing proxies)

当一个点u满足下列三个条件时,我们称这样的点为一个点集A的代理点:

  1. 对于$A$中的任何一个点,都可以到达$A$中其他的任何点。(保证连通性
  2. 对于$A$中除了代理点u以外的任何点$v$,$v$的邻居也在$A$当中。(保证邻居都在$A$当中,但是并不要求代理点的邻居都在$A$当中)
  3. $|A|$的大小不超过一个阈值$T$。($A$如果太大,选的代理点代理的范围太大,那么这样的代理意义就不是太大)

代理区域(DRA)

对于某个代理点$u$,可以代理多个点集$A_1,A_2,A_3,\ldots,A_n$,我们把所有代理的点集合并在一起称为一个代理区域(DRA)。每个$A_i$代表DRA的一个分量,这里需要注意二者的区别。

最大代理点(Maximal Proxies)

我们称一个代理点u是极大的当没有其他的代理点$u'$的DRA比$u$的DRA更大。

关于DRA的几个性质:

  1. 如果没有第三个大小条件限制的话,图中每个点$u$都是原图的一个极大代理点,而且每个点的代理区域DRA都恰好是$u$所属的联通分支。
  2. 任何代理点在原图都有唯一的DRA。
  3. 如果点$u$在$u’$的DRA中的话,那么$u$的DRA是$u’$的DRA的子集。如果$u’$和$u$不在彼此的DRA中的话,那么$u’$和$u$的DRA交集为空。
  4. 对于$u$的DRA中的两点$v$和$v’$,他们在$u$的DRA中的最短路径或者最短距离和在原图当中的是一致的。
  5. 对于两个代理点$x$和$y$,以及$x$的DRA中的点$v$,$y$的DRA中的点$u$,$path(v,u)=path(v,x)+path(x,y)+path(y,u)$,这里的$path(v,u)$表示$v$和$u$之间的最短距离。

DRA的计算:

根据DRA的第5条性质,我们知道剩下的核心就是如何快速的计算DRA。

首先介绍一下BCC的几个性质。

1. 如果一个代理点v所在的联通分支H的点集的数量大于阈值T,那么这样的点v是原图的一个cut-node。(用反证法,如果点v不是一个cut-node,那么移除v不会增加原图的连通分支数量,对于v的DRA Av中至少存在一个邻居节点u,u可以到达H中的任何点,否则移除v就会增加连通分量。那么根据Av的定义,Av的数量就大于阈值。矛盾。)
2. 如果一个BCC的点集的数量大于T,那么这个BCC中的任何一个点都是平凡的代理点。

BC-SKETCH Graph: BC-SKETCH Graph 是一个二分图。二分图一边的点是BC点,每个点表示一个BCC,另一边是cut-node。当如果一个cut-node属于某个BCC,那么久在对应的cut-node和代表该BCC的点之间连接一条边,形成一个二分图,这个二分图就是BC-SKETCH图。

BC-SKETCH Graph 是一棵树。(反证法,如果有环$B_1v_1B_2v_2\ldots v_nB_1$,那么存在一个回路,那么移除任何一个cut-node都不会增加联通分支数量,与假设矛盾)
计算DRA的算法:

查找图中所有的cut-nodes和BCC。可以在线性时间内完成。(自己想了一个方法:线性时间查找一个图中的所有node-cut点分割)
根据BC-SKETCH的性质,建立BC-SKETCH图的时间复杂度是$|V|-1$
计算DRA和最大代理点。当有了BC-SKETCH图以后,将图中的BC nodes和cut-node不断融合在一起。
利用DRA计算最短路径问题:

预处理:

1. 计算出DRA中每个点与对应的代理点的最短路/最短距离。
2. 计算出代理点和代理点的最短路/最短距离。

最短路径查询path(s,t):

如果$s$和$t$同属于代理点$u$的DRA的一个分支的话,那么在该分支内计算最短路即可。
如果$s$和$t$同属于代理点$u$的DRA的不同分支的话,那么$path(s,t)=path(s,u)/path(u,t)$。
如果$s$属于代理点$v$的DRA,$t$属于代理点$u$的DRA,那么$path(s,t)=path(s,v)/path(v,u)/path(u,t)$
我们这里不过多的区分最短路径和最短距离的问题,是因为这两个问题是等价的。最短路径返回的结果是一条路径,最短距离是返回源点和终点的距离。马老师的文章里面阐述得更加仔细,把路径和距离的性质单独罗列出来,可以详细看文章里面提的。