NetworkX: poids de bord en tant que valeur calculée

Question

Je veux mettre en œuvre un algorithme de chemin le plus court avec la bibliothèque NetworkX. Dans mon cas, ma fonction de poids dérive la valeur des autres attributs de bord. Parce que le poids est une valeur calculée, je ne veux pas stocker comme un attribut supplémentaire pour éviter la complication par exemple mettre à jour la valeur lorsque les autres attributs changent. NetworkX de API algorithme , cependant, semble être le poids nécessitant une clé de données de pointe.

Alors je me demandais s'il est possible de ne pas stocker la valeur? Mon cas idéal serait de spécifier une fonction de poids personnalisé à l'algorithme.

Answer 1

Le paramètre n'a pas besoin d'être une clé dans le dictionnaire d'attributs de bord. Vous devez donc définir un attribut de bord dans le dictionnaire à utiliser comme un poids. Vous pouvez attribuer ceux d'une simple boucle avant de calculer le chemin le plus court (et si vous voulez les supprimer plus tard).

Sinon, vous pouvez modifier le code de l'algorithme de Dijkstra pour calculer votre poids des autres attributs de bord. En supposant que vous avez un graphique (pas un multigraphe) est un changement d'une ligne. Mettez votre formule de poids en ligne 231 https://networkx.lanl.gov/trac /browser/networkx/networkx/algorithms/shortest_paths/weighted.py#L231

vw_dist = dist[v] + edgedata.get(weight,1)

Answer 2

Vous pouvez calculer la valeur de poids paresseusement, mais le présenter comme si elle était un attribut, en utilisant les propriétés. Par exemple:

class Edge(object):

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def get_z(self):
        return self.x + self.y

    z = property(get_z)


e = Edge(3,4)
print e.z

Ici e.z semble être une valeur réelle stockée, un attribut de l'objet Edge. Mais ce n'est pas - il est calculé sur la demande. Il vous reste à écrire votre code de mise à jour, dans la méthode get_z, mais l'avantage ici est que vous n'avez pas à vous soucier de la mise à jour d'une valeur concrète à chaque fois que le changement des propriétés dépendantes. Au lieu de cela, vous ne calculez quand il est demandé.

Il serait facile d'étendre cet exemple à des valeurs de cache, si vous étiez préoccupé par de nombreux accès de z inutiles causant des calculs potentiellement coûteux. Le getter vérifierait une table de consultation avant de faire le calcul. Ceci est juste memoization .