Réseau Pythonx : Est-ce que le floyd_warshall_numpy fonctionne correctement ?

Question

Quelqu'un peut-il confirmer que l'implémentation de la méthode floyd_warshall_numpy de networkx 2.5 est incorrecte ?

Le code à reproduire est le suivant :

G = nx.balanced_tree(2, 3)
print(G.nodes())
print(nx.shortest_path(G, 2, 13))
print(nx.floyd_warshall_numpy(G, [2, 8, 13]))

Mon résultat est le suivant

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[2, 6, 13]
[[ 0. inf inf]
 [inf  0. inf]
 [inf inf  0.]] 

Je m'attendais à ce que les distances non inf soient calculées pour toutes les paires de nœuds [2, 8, 13] car le chemin le plus court existe entre toutes ces paires. Il me semble que cette implémentation essaie d'une manière ou d'une autre de trouver le chemin dans un sous-graphe.

nx.floyd_warshall_numpy(G)

fonctionne correctement pour tous les nœuds. Je trouve que la documentation n'est pas intuitive ici. https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.shortest_paths.dense.floyd_warshall_numpy.html#networkx.algorithms.shortest_paths.dense.floyd_warshall_numpy

Answer 1

J'ai regardé le code source, et ce qui se passe, c'est que l'algorithme ne considère que les chemins qui impliquent les nœuds que vous lui avez donnés.

Donc, puisqu'il n'y a pas de chemin entre 2 et 8 qui inclue seulement les noeuds 2, 8 et 13, il retourne inf .

Je ne suis pas sûr de la meilleure façon de le corriger - s'il est préférable de mettre à jour la documentation ou la méthode.

Answer 2

Je pense que votre code voulait dire print(nx.floyd_warshall_numpy(G, [2, 6, 13])) avec un ensemble de nœuds [2, 6, 13] au lieu de [2, 8, 13] . Est-ce exact ?

G = nx.balanced_tree(2, 3) 
print(G.nodes()) 
print(nx.shortest_path(G, 2, 13)) 
print(nx.floyd_warshall_numpy(G, [2, 6, 13]))                                                                         

Produit

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[2, 6, 13]
[[0. 1. 2.]
 [1. 0. 1.]
 [2. 1. 0.]]

Answer 3

Je crois que le problème est l'explication de liste de contrôle dans la documentation. Basé sur la documentation :
nodelist (liste, facultatif) - Les lignes et les colonnes sont ordonnées par les nœuds de nodelist. Si nodelist est None, l'ordre est produit par G.nodes(). Mais il n'est pas mentionné que la nodelist modifie réellement le graphe. Il crée un autre graphe en utilisant les noeuds de la liste de noeuds.

Supposons que votre graphique comporte 4 nœuds [1,2,3,4] mais que vous définissez la liste des nœuds comme étant [2,3,4]. En lisant la documentation, vous pensez que la fonction calculera la matrice de distance entre les nœuds 2, 3 et 4 du graphique original. Cependant, il semble qu'elle supprime le nœud 1 du graphe (modifiant techniquement le graphe d'origine) et calcule ensuite la matrice de distance entre les nœuds 2, 3 et 4. Cela peut être problématique si le nœud 1 relie les nœuds 2 et 3.

Exemple de graphique avec 4 nœuds

Dist_Mat=nx.algorithms.shortest_paths.dense.floyd_warshall_numpy(G,[1,2,3,4])  
print(Dist_Mat)  
[[0. 1. 1. 1.]
 [1. 0. 2. 2.]
 [1. 2. 0. 2.]
 [1. 2. 2. 0.]]

Dist_Mat=nx.algorithms.shortest_paths.dense.floyd_warshall_numpy(G,[2,3,4])  
print(Dist_Mat)
[[ 0. inf inf]
 [inf  0. inf]
 [inf inf  0.]]

veuillez trouver le code ci-dessous

import networkx as nx
import matplotlib.pyplot as plt
import nxviz as nv
G=nx.Graph()
G.add_node(1)
G.nodes[1]['N']=10
G.add_nodes_from([(2,{'N':20}),3,4])
G.add_edge(1,2)
G.edges[1,2]['E']=120
G.add_edges_from([(1,3,{'E':130}),(1,4)])
G.nodes()
pos = {0: (0, 0),
       1: (1, 0),
       2: (0, 1),
       3: (1, 1),
       4: (0.5, 2.0)}
print(G.nodes(data=True))
print(G.edges(data=True))
nx.draw(G, pos, with_labels=True, font_weight='bold')
FIG=nv.CircosPlot(G,node_size=1)
FIG.draw();plt.show()

Dist_Mat=nx.algorithms.shortest_paths.dense.floyd_warshall_numpy(G,[1, 2,3,4])
print(Dist_Mat)
Dist_Mat=nx.algorithms.shortest_paths.dense.floyd_warshall_numpy(G,[2,3,4])
print(Dist_Mat)