Расстояния между списками вершин (не двух вершин) в питоне - PullRequest
Новая
       16

Расстояния между списками вершин (не двух вершин) в питоне

1 голос
/ 07 марта 2019

Ранее я использовал функцию distance () в igraph, которая вычисляет расстояние между двумя узлами или двумя векторами узлов.Сейчас я пишу код на python, используя NetworkX 2.2 и пытаюсь также найти расстояние между двумя списками узлов (не двумя узлами) .

ЭтоКажется, что нет никакой функции, может сделать это в 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 и держаться подальше от проблемы потери имен вершин, возникающих при попытке получить соседей для вершин.

Ответы [ 2 ]

1 голос
/ 08 марта 2019

Вы были близки, за исключением последнего цикла, где вы должны снова выполнить итерации по спискам соседей и затем сохранить расстояния 

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]}

Вот ссылка на блокнот Google Colab скод выше.

Надеюсь, это поможет!

0 голосов
/ 07 марта 2019

Последняя строка вашего кода дает ошибку. Внутри For neighbor1 и neighbor2 обновляются в виде списка с несколькими узлами после каждой итерации, а для nx.shortest_path_length необходимо передать один исходный и один целевой узлы, а не список. Надеюсь, это поможет.

Обновление

Вот пример кода для решения вашей проблемы. graph.neighbors(node) выдаст список соседей для узла. 

 import networkx as nx
import pandas as pd
G = nx.path_graph(5)
Distance=[]
edge0=[]
neighbor0edge0=[]
neighbor1edge1=[]
edge1=[]
Output=pd.DataFrame()
for edge in G.edges():
    neighbor1=[n for n in G.neighbors(edge[0])] #neighborrs w.r.t v1
    neighbor2=[n for n in G.neighbors(edge[1])] #neighborrs w.r.t v2
    distance=[]
    for i in neighbor1:
        for j in neighbor2:
              distance.append(nx.shortest_path_length(G, source=i, target=j)) #Find distance between all the combination of neighbor1 and neighbor2
    edge0.append(edge[0])
    edge1.append(edge[1])
    Distance.append(distance)
    neighbor0edge0.append(neighbor1)
    neighbor1edge1.append(neighbor2)
Output['v1']=edge0
Output['neighborv1']=neighbor0edge0
Output['v2']=edge1
Output['neighborv2']=neighbor1edge1
Output['Distances']=Distance

Результат: - 

`v1 neighborv1  v2 neighborv2     Distances
 0        [1]   1     [0, 2]        [1, 1]
 1     [0, 2]   2     [1, 3]  [1, 3, 1, 1]
 2     [1, 3]   3     [2, 4]  [1, 3, 1, 1]
 3     [2, 4]   4        [3]        [1, 1]`
...