The distances between lists of vertices (not two vertices) in python

Question

I used previously the function distance() in igraph which computes the distance between two nodes or two vectors of nodes. Now I am writing a code in python using NetworkX 2.2 and I am trying to find also the distance between two lists of nodes (not two nodes).

It seems that there is no function can do this in NetworkX. In fact I used shortest_path_length() but it didn't work. What I am doing here is : 1. read the graph edge by edge, 2. then for each edge to select the first vertex v1 and the second vertex v2, 3. find the neighbors connected to the first vertex and also find the connected neighbors to the second vertex, 4. finally compute the distance between the neighbors of v1 and neighbors of v2.

At the end I want to get,for each edge, a vector contains the distances between the neighbors for both vertices v1 and v2. My code in 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

To do this in python, I wrote this code

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))

But I got this error which states that the neighbors are not defined as vertices since they are lists not single values

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

Is there a possibility in python to get a list for the distances between lists of of vertices, not single values, as I did in R ? Is there such a function and if not is it possible to modify the current function?

Note: I didn' use igraph-python to get the required list for two reasons: there is no such function , according to my search , in igraph and to stay away from the problem of loosing the names of vertices produced when tryinh to get neighbors for vertices.

Gambit1614 Gambit1614 · Accepted Answer · 2019-03-07T23:28:44

You were close, except in the last loop where you have to iterate over the neighbours lists again and then store the distances

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

The distance_neighbours contains the following data:

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

The ordering of the value in the last edge(3,4) is different because Python is ordering the neighbours different from how R does it. In order to make sure the behaviour is same, run the following code:

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

Now the distance_neighbors has the same output as your R code:

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

Here is the link to the Google Colab notebook with the above code.

Hope this helps!

The distances between lists of vertices (not two vertices) in python

2 Answers