python - python中顶点列表(不是两个顶点)之间的距离

Question

我之前使用过函数distance()在 igraph 中，它计算两个节点或两个节点向量之间的距离。现在我正在使用 NetworkX 2.2 在 python 中编写代码我还试图找到两个节点列表之间的距离(不是两个节点)。

NetworkX 中似乎没有函数可以做到这一点。事实上我用了 shortest_path_length()但没有成功。我在这里做的是:1.逐边读取图，2.然后为每条边选择第一个顶点v1和第二个顶点v2，3.找到连接到第一个顶点的邻居，并找到连接的邻居到第二个顶点，4。最后计算 v1 的邻居和 v2 的邻居之间的距离。

最后我想得到，对于每条边，一个向量包含顶点 v1 和 v2 的邻居之间的距离。我的 R 代码

library(igraph)
graph<-matrix(c(4,3,4,1,4,2,3,2,3,1),ncol=2,byrow=TRUE)
g<-graph.data.frame(d = graph, directed = FALSE)

v1<-c()
v2<-c()
n1<-list()
n2<-list()
distance<-list()
distance.bt.neighbors<-list()

for(edge in 1:length(E(g))){
  v1[edge]<-ends(graph = g, es = edge)[1]
  v2[edge]<-ends(graph = g, es = edge)[2]
  n1<-neighbors(g,v1[edge],mode=c("all"))
  n2<-neighbors(g,v2[edge],mode=c("all"))
  distance[[edge]]<-distances(g, v = n1, to = n2, mode = c("all"))
  distance.bt.neighbors[[edge]]<-c(distance[[edge]])
                           }
distance.bt.neighbors
[[1]]
[1] 1 1 1 1 0 2 1 2 0

[[2]]
[1] 1 1 1 0 1 1

[[3]]
[1] 1 1 1 0 1 1

[[4]]
[1] 0 1 1 1 1 1

[[5]]
[1] 0 1 1 1 1 1

为了在 python 中做到这一点，我编写了这段代码

import os
import igraph
import numpy as np
import networkx as nx

os.chdir('Desktop')

graph = nx.read_edgelist("attempt") # the file attempt contains the same data as in the R code.

neighbor1 = []
neighbor2 = []
distance = []

for edge in list(graph.edges):
  neighbor1.append(list(graph.neighbors(edge[0])))
  neighbor2.append(list(graph.neighbors(edge[1])))
  distance.append(nx.shortest_path_length(graph, source=neighbor1, target= neighbor2))

但是我收到了这个错误，它指出邻居没有定义为顶点，因为它们是列表而不是单个值

Traceback (most recent call last):
File "<stdin>", line 4, in <module>
File "/home/abdelrahman/anaconda/lib/python3.7/site-packages/networkx/algorithms/shortest_paths/generic.py", line 312, in shortest_path_length
p = nx.bidirectional_shortest_path(G, source, target)
File "/home/abdelrahman/anaconda/lib/python3.7/site-packages/networkx/algorithms/shortest_paths/unweighted.py", line 223, in bidirectional_shortest_path
raise nx.NodeNotFound(msg.format(source, target))
networkx.exception.NodeNotFound: Either source [['3', '4']] or target [['1', '2']] is not in G

在 python 中是否有可能获取顶点列表之间的距离列表，而不是单个值，就像我在 R 中所做的那样？有没有这样的功能，如果没有可以修改当前的功能吗？

注意:我没有使用 igraph-python 来获取所需的列表有两个原因:根据我的搜索，igraph 中没有这样的函数，并且避免尝试时丢失生成的顶点名称的问题获取顶点的邻居。

Answer 1

你很接近，除了在最后一个循环中，你必须再次迭代邻居列表，然后存储距离

import numpy as np
import networkx as nx

# Since I didn't have your data, I simply recreated from your R code
graph = nx.Graph()
for i in range(1, 5):
  graph.add_node(i)

for x,y in [(4, 3), (4, 1), (4, 2), (3, 2), (3, 1)]:
  graph.add_edge(x, y)

# print(graph.edges())
# Output EdgeView([(4, 3), (4, 1), (4, 2), (3, 2), (3, 1)])

distance_neighbors = {}

for edge in list(graph.edges):
  neighbor1 = tuple(graph.neighbors(edge[0]))
  neighbor2 = tuple(graph.neighbors(edge[1]))

  distance_list = []
  for v1 in neighbor1:
    for v2 in neighbor2:
      distance_list.append(nx.shortest_path_length(graph, source=v1, target=v2))
  distance_neighbors[edge] = distance_list

distance_neighbours 包含以下数据:

{(1, 3): [0, 1, 1, 1, 1, 1],
 (1, 4): [1, 1, 1, 0, 1, 1],
 (2, 3): [0, 1, 1, 1, 1, 1],
 (2, 4): [1, 1, 1, 0, 1, 1],
 (3, 4): [1, 1, 1, 1, 2, 0, 1, 0, 2]}

最后一条边 (3,4) 中的值的顺序不同，因为 Python 对邻居的排序方式与 R 的方式不同。 为了确保行为相同，请运行以下代码:

import os

import numpy as np
import networkx as nx

# Since I didn't have your data, I simply recreated from your R code
graph = nx.Graph()
for i in range(1, 5):
  graph.add_node(i)

for x,y in [(4, 3), (4, 1), (4, 2), (3, 2), (3, 1)]:
  graph.add_edge(x, y)

# print(graph.edges())
# Output EdgeView([(4, 3), (4, 1), (4, 2), (3, 2), (3, 1)])

distance_neighbors = {}

for edge in list(graph.edges):
  # Just sort the neighbours list in reverse order
  neighbor1 = tuple(sorted(graph.neighbors(edge[0]), reverse=True))
  neighbor2 = tuple(sorted(graph.neighbors(edge[1]), reverse=True))

  distance_list = []
  for v1 in neighbor1:
    for v2 in neighbor2:
      distance_list.append(nx.shortest_path_length(graph, source=v1, target=v2))
  distance_neighbors[edge] = distance_list

现在 distance_neighbors 具有与 R 代码相同的输出:

{(1, 3): [0, 1, 1, 1, 1, 1],
 (1, 4): [1, 1, 1, 0, 1, 1],
 (2, 3): [0, 1, 1, 1, 1, 1],
 (2, 4): [1, 1, 1, 0, 1, 1],
 (3, 4): [1, 1, 1, 1, 0, 2, 1, 2, 0]}

这是link to the Google Colab notebook与上面的代码。

希望这有帮助!