为图中的每个节点计算距离为n的未访问节点

Question

对于大图中的每个点,我试图创建一个列表,其中包含距离n起始节点一定距离的未访问节点的数量.示例输出是: [1,3,6] 这意味着在距离0处有起始节点本身,在距离1处有3个新的(未探测的)节点等.

如果你只有一个起点,这很容易:你只需在广度优先搜索的基础上增加一个shell计数器.当我必须为图中的每个节点执行此操作时,问题就开始了.因为我的图形很大(> 100000个节点),所以对每个点执行上述例程变得相当慢.

我首次尝试优化这个是检查节点上的列表a是否可以从所有邻居的列表构建a,但到目前为止我没有运气,部分原因是图中的周期.我希望你们中的一些人可能有一些不错的想法,也许还有一些我可以缓存的额外信息.

我的问题:如果您知道必须为每个节点执行此操作,是否有一种优化此类搜索的方法？

Answer 1

less 似乎不太可能有解决方案O(n*|V|^2)，因此这里有一个 Python 中的方法，看起来并不太糟糕。

# some basic topologies
def lineE(N): 
  return(set((i,i+1) for i in range(N-1)))

def ringE(N):
  return(lineE(N).union([(0,N-1)]))

def fullE(N):
  return(set([(i,j) for i in range(N) for j in range(i)]))

# propagate visitors from x to y
def propagate(V, curr, x, y, d):
  nexty = set()
  for cx in curr[x]:
    if not cx in V[y]["seen"]:
      V[y]["seen"].add(cx)
      V[y]["foaf"][d] = V[y]["foaf"].get(d,0) + 1
      nexty.add(cx)
  return(nexty)

# run for D iterations
def mingle(N, E, D):
  V = dict((i, {"seen":set([i]), "foaf":{0:1}}) for i in range(N))
  curr = dict((i, set([i])) for i in range(N))
  for d in range(1, min(D+1, N)):
    next = dict((i, set()) for i in range(N))
    for (h, t) in E:
      next[t] = next[t].union(propagate(V, curr, h, t, d))
      next[h] = next[h].union(propagate(V, curr, t, h, d))
    curr = next
  return(V)

尝试使用 10 个节点和距离 3，

N=10
D=3
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N)), ("full", fullE(N))]:
  V = mingle(N, E, D)
  print "\n", topology
  for v in V:
    print v, V[v]["foaf"]

我们得到

line
0 {0: 1, 1: 1, 2: 1, 3: 1}
1 {0: 1, 1: 2, 2: 1, 3: 1}
2 {0: 1, 1: 2, 2: 2, 3: 1}
3 {0: 1, 1: 2, 2: 2, 3: 2}
4 {0: 1, 1: 2, 2: 2, 3: 2}
5 {0: 1, 1: 2, 2: 2, 3: 2}
6 {0: 1, 1: 2, 2: 2, 3: 2}
7 {0: 1, 1: 2, 2: 2, 3: 1}
8 {0: 1, 1: 2, 2: 1, 3: 1}
9 {0: 1, 1: 1, 2: 1, 3: 1}

ring
0 {0: 1, 1: 2, 2: 2, 3: 2}
1 {0: 1, 1: 2, 2: 2, 3: 2}
2 {0: 1, 1: 2, 2: 2, 3: 2}
3 {0: 1, 1: 2, 2: 2, 3: 2}
4 {0: 1, 1: 2, 2: 2, 3: 2}
5 {0: 1, 1: 2, 2: 2, 3: 2}
6 {0: 1, 1: 2, 2: 2, 3: 2}
7 {0: 1, 1: 2, 2: 2, 3: 2}
8 {0: 1, 1: 2, 2: 2, 3: 2}
9 {0: 1, 1: 2, 2: 2, 3: 2}

full
0 {0: 1, 1: 9}
1 {0: 1, 1: 9}
2 {0: 1, 1: 9}
3 {0: 1, 1: 9}
4 {0: 1, 1: 9}
5 {0: 1, 1: 9}
6 {0: 1, 1: 9}
7 {0: 1, 1: 9}
8 {0: 1, 1: 9}
9 {0: 1, 1: 9}

这似乎是正确的。此外，在我的笔记本电脑上运行具有 100000 个节点的距离 100 的简单拓扑大约需要一分钟。当然，如果你有一个密集的图表（如fullE），这将会爆炸。

N=100000
D=100
for (topology, E) in [("line", lineE(N)), ("ring", ringE(N))]:
  V = mingle(N, E, D)