J'ai utilisé précédemment la fonction distance() dans igraph qui calcule la distance entre deux nœuds ou deux vecteurs de nœuds. Maintenant, j'écris un code en python en utilisant NetworkX 2.2 et j'essaie de trouver aussi la distance entre deux listes de nœuds (pas deux nœuds).

Il semble qu'aucune fonction ne puisse le faire dans NetworkX. En fait j'ai utilisé shortest_path_length() mais cela n'a pas fonctionné. Ce que je fais ici c'est : 1. lire le graphe arête par arête, 2. puis pour chaque arête sélectionner le premier sommet v1 et le deuxième sommet v2, 3. trouver les voisins connectés au premier sommet et aussi trouver les voisins connectés au deuxième sommet, 4. enfin calculer la distance entre les voisins de v1 et les voisins de v2.

À la fin, je veux obtenir, pour chaque arête, un vecteur contenant les distances entre les voisins pour les deux sommets v1 et v2. Mon code en 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

Pour faire cela en python, j'ai écrit ce 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))

Mais j'ai eu cette erreur qui indique que les voisins ne sont pas définis comme des sommets car ce sont des listes et non des valeurs uniques

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

Existe-t-il une possibilité en python d'obtenir une liste des distances entre les listes de sommets, pas des valeurs uniques, comme je l'ai fait dans R ? Existe-t-il une telle fonction et sinon est-il possible de modifier la fonction actuelle ?

Remarque: je n'ai pas utilisé igraph-python pour obtenir la liste requise pour deux raisons: il n'y a pas de telle fonction, selon ma recherche, dans igraph et pour éviter le problème de perdre les noms de sommets produits en essayant d'obtenir des voisins pour les sommets.

1
Noah16 7 mars 2019 à 19:43

2 réponses

Meilleure réponse

Vous étiez proche, sauf dans la dernière boucle où vous devez à nouveau parcourir les listes de voisins puis stocker les 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

La distance_voisins contient les données suivantes :

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

L'ordre de la valeur dans le dernier bord (3,4) est différent car Python trie les voisins différemment de la façon dont R le fait. Afin de vous assurer que le comportement est le même, exécutez le code suivant :

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

Maintenant, le distance_neighbors a la même sortie que votre code 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]}

Voici le lien vers le bloc-notes Google Colab avec le code ci-dessus.

J'espère que cela t'aides!

1
Mohammed Kashif 7 mars 2019 à 23:28

Dernière ligne de votre code donnant l'erreur. À l'intérieur de For neighbor1 et neighbor2 mis à jour sous forme de liste avec plusieurs nœuds après chaque itération et pour nx.shortest_path_length vous devez transmettre une seule source et un seul nœud cible, pas une liste . J'espère que ça aide.

Mettre à jour

Voici un exemple de code pour résoudre votre problème. graph.neighbors(node) donnera une liste de voisins pour le nœud.

 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

Résultat:-

`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]`
0
kumar navneet 7 mars 2019 à 18:43