Renvoie la contribution des nœuds sources dans le graphe orienté NetworkX

Question

J'ai un graphe NetworkX dirigé qui relie les nœuds d'alimentation entre eux par des arêtes, pour lesquelles les valeurs d'attributs de capacité sont définies.

Je suis intéressé par l'obtention d'une liste de noeuds racine lorsque je spécifie un noeud source/puits. je parviens à obtenir un arbre en utilisant la profondeur première méthode de recherche nx.dfs_tree(G, sink node)

Cependant, je voudrais:

• obtenir une liste de tous les noeuds source et leur contribution globale dans l'approvisionnement du nœud de puits.

Answer 1

Si par contribution globale d'un nœud source dans l'approvisionnement du nœud de puits vous dire la somme de la capacité de chaque bord dans le plus court chemin entre la source et l'évier, puis:

contributions = nx.shortest_path_length(G, target=sink_node, weight='capacity') 
paths = nx.shortest_path(G, target=sink_node, weight='capacity') 
intermediary_nodes = set() 
for node in paths: 
    intermediary_nodes.update(paths[node][1:]) 
sources = [(node, contribution) for node, contribution in contributions.items() if node not in intermediary_nodes] 

fera le travail . Où sources est une liste de 2-tuples du genre (source, contribution globale). Les nœuds non contribuant sont ignorés.