Comment calculer les distances globales à partir de la ou des racines les plus basses d'un graphe dirigé avec networkx

Question

Si vous regardez ce DAG (directed acyclic graph) :

Je veux créer un dict qui mappe la distance entre le(s) nœud(s) le(s) plus bas et tous les autres nœuds, ce qui est similaire à la position x (hauteur) de chaque nœud depuis le bas dans le graphique rendu. Pour ce graphique donné, ce serait :

distance_nodes_map: {
  0: {'base-zero', 'base-one'}, 
  1: {'low-b', 'low-a', 'low-c'}, 
  3: {'high-x', 'high-z', 'high-y'}, 
  2: {'mid-r', 'mid-q', 'mid-p'}, 
  4: {'super'}
}

J'ai écrit un algorithme qui a fonctionné pour le graphique ci-dessus mais j'ai ensuite testé un autre graphique et cela n'a plus fonctionné. J'ai essayé quelques algorithmes et fonctions comme shortest path ou descendants_at_distance mais je ne pense pas qu'ils soient vraiment utiles comme entrée pour calculer les distances.

Mon algorithme ne fonctionne pas par exemple pour ce graphique :

https://gist.github.com/timaschew/3b08a07243fa6f43773014ef5e705c96

Voici le gist qui contient :

• un script en python qui lit un fichier YAML, la structure des dépendances/graphes et génère un HTML avec un graphe de sirène rendu (j'ai enlevé mon algorithme pour calculer les distances d'une mauvaise manière)
• les deux graphiques qui sont montrés ici, comme un fichier YAML

Answer 1

Pseudo-code non testé car ma pause déjeuner est presque terminée :

Vous avez un arbre à plusieurs racines, avec une racine principale choisie.

1. Pour chaque racine, créer un sous-graphe composé de tous les nœuds accessibles pour cette racine.

2. En commençant par la racine principale (racine a), calculez la distance/longueur du plus court chemin vers la racine pour tous les nœuds du sous-graphe A correspondant.

3. Trouvez tous les sous-graphes qui partagent au moins un nœud avec le sous-graphe principal, et sélectionnez le sous-graphe (sous-graphe B) qui a le nœud (nœud x) avec la plus petite distance à la racine principale.

4. Calculer la distance à la Racine b pour tous les noeuds du sous-graphe B. Ajouter la distance d(noeud x, Racine a). Soustrayez la distance d(noeud x, Racine b).

5. Créer l'union des sous-graphes A et B. Répéter les étapes 3 à 5 jusqu'à ce qu'il ne reste plus de racines.

6. Soustraire la distance maximale et inverser le signe de façon à ce que la racine principale ait la plus grande distance/valeur d'ordre.

Edit :

Mon pseudo-code fonctionne (*). Je blâme l'erreur de l'utilisateur ;-)

#!/usr/bin/env python
"""
https://stackoverflow.com/q/66584661/
"""
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx

def hierarchical_layout(graph):

    longest_path = nx.algorithms.dag.dag_longest_path(graph)
    principal_root = longest_path[0]

    roots = [node for node, degree in list(graph.in_degree) if degree==0]
    subgraphs = {root : create_subgraph(graph, root) for root in roots}

    # Starting with the principal root (root a), compute the
    # longest path length to the root for all nodes in the
    # corresponding subgraph A.
    node_to_level = single_source_longest_dag_path_length(subgraphs[principal_root], principal_root)

    explored = subgraphs[principal_root]
    del subgraphs[principal_root]

    while len(explored) < len(graph):

        # Find all subgraphs that share at least one node with the
        # principal subgraph, and select the subgraph (subgraph B) that
        # has the node (node x) with the smallest distance to the
        # principal root.
        minimum_cost = np.inf
        minimum_cost_node = None
        minimum_cost_root = None
        for root, subgraph in subgraphs.items():
            for node in subgraph.nodes:
                if node in node_to_level:
                    if node_to_level[node] < minimum_cost:
                        minimum_cost = node_to_level[node]
                        minimum_cost_node = node
                        minimum_cost_root = root

        assert minimum_cost_node, "Could not find a connected subgraph."

        # Compute the distance to the root b for all nodes in subgraph
        # B. Add the distance d(node x, root a). Subtract the distance
        # d(node x, root b).
        path_lengths = [len(path) for path in nx.all_simple_paths(subgraphs[minimum_cost_root], minimum_cost_root, minimum_cost_node)]
        offset = np.max(path_lengths) - 1
        for node, distance in single_source_longest_dag_path_length(subgraphs[minimum_cost_root], minimum_cost_root).items():
            if not node in node_to_level:
                node_to_level[node] = distance + minimum_cost - offset

        # Create the union of subgraph A and B.
        explored = nx.compose(explored, subgraphs[minimum_cost_root])
        del subgraphs[minimum_cost_root]

    return node_to_level

def create_subgraph(G, node):
    # https://stackoverflow.com/a/45678930/2912349
    nodes = nx.single_source_shortest_path(G,node).keys()
    return G.subgraph(nodes)

def single_source_longest_dag_path_length(graph, s):
    # from AlaskaJoslin's comment to https://stackoverflow.com/a/60978007/2912349
    dist = dict.fromkeys(graph.nodes, -float('inf'))
    dist[s] = 0
    topo_order = nx.topological_sort(graph)
    for n in topo_order:
        for s in graph.successors(n):
            if dist[s] < dist[n] + 1:
                dist[s] = dist[n] + 1
    return dist

if __name__ == '__main__':

    # edge_list = [
    #     ("n10", "n11"),
    #     ("n11", "n12"),
    #     ("n12", "n13"),
    #     ("n13", "n14"),
    #     ("n20", "n21"),
    #     ("n20", "n14"),
    #     ("n21", "n22"),
    #     ("n22", "n23"),
    #     ("n30", "n23"),
    #     ("n30", "n31"),
    #     ("n31", "n32"),
    # ]

    edge_list = [
        ("low-a", "base-one"),
        ("low-c", "base-zero"),
        ("low-c", "base-one"),
        ("mid-p", "low-b"),
        ("mid-p", "low-c"),
        ("mid-q", "low-a"),
        ("high-x", "mid-p"),
        ("high-y", "mid-p"),
        ("high-y", "base-zero"),
        ("high-z", "mid-q"),
        ("high-z", "mid-r"),
        ("high-z", "base-one"),
        ("super", "high-x"),
    ]

    graph = nx.DiGraph()
    graph.add_edges_from(edge_list)

    node_to_level = hierarchical_layout(graph)

    # reverse output format
    distance_nodes_map = dict()
    max_distance = np.max(list(node_to_level.values()))
    for node, distance in node_to_level.items():
        reversed_distance = max_distance - distance
        if reversed_distance in distance_nodes_map:
            distance_nodes_map[reversed_distance].add(node)
        else:
            distance_nodes_map[reversed_distance] = set([node])

    # print(distance_nodes_map)
    for ii, nodes in sorted(distance_nodes_map.items())[::-1]:
        print(f"{ii} : {nodes}")

Rendement :

    # 4 : {'super'}
    # 3 : {'high-x', 'high-y', 'high-z'}
    # 2 : {'mid-p', 'mid-r', 'mid-q'}
    # 1 : {'low-a', 'low-b', 'low-c'}
    # 0 : {'base-one', 'base-zero'}

(*) "soustraire la distance d(nœud x, Racine b)" impliquait naturellement la le plus long longueur du chemin entre le nœud x et la racine b. Évidemment.

Answer 2

Vous recherchez un algorithme qui dessine un graphe en couches. Il existe de nombreux algorithmes différents, et vous devez choisir celui qui répond le mieux à vos besoins (par exemple, consultez l'article suivant Une technique pour dessiner des graphes dirigés par Gansner et al. ).

Un grand nombre de ces algorithmes sont déjà mis en œuvre dans Graphviz (un très célèbre et puissant logiciel de visualisation de graphiques). Une fois que vous l'avez installé, il est assez simple de calculer le résultat que vous recherchez ( G est votre graphe acyclique dirigé construit en utilisant networkx.DiGraph ):

from networkx.drawing.nx_agraph import graphviz_layout

def get_distance_nodes_map(G):
    pos = graphviz_layout(G, prog='dot')
    coor = sorted({y for k, (x, y) in pos.items()})
    kmap = dict(zip(coor, range(len(coor))))
    distance_nodes_map = {level: set() for level in kmap.values()}
    for k, (x, y) in pos.items():
        distance_nodes_map[kmap[y]].add(k)
    return distance_nodes_map

Voici quelques exemples utilisant les données que vous avez fournies :

>>> from networkx import DiGraph
>>> from pprint import PrettyPrinter
>>> pp = PrettyPrinter()
>>> G1 = DiGraph()
>>> G1.add_edges_from([('super', 'high-x'), ('high-x', 'mid-p'),
...                    ('mid-p', 'low-b'), ('mid-p', 'low-c'),
...                    ('low-c', 'base-zero'), ('low-c', 'base-one'),
...                    ('high-y', 'mid-p'), ('high-y', 'base-zero'),
...                    ('high-z', 'base-one'), ('high-z', 'mid-r'),
...                    ('high-z', 'mid-q'), ('mid-q', 'low-a'),
...                    ('low-a', 'base-one')])
>>> pp.pprint(get_distance_nodes_map(G1))
{0: {'base-one', 'base-zero'},
 1: {'low-a', 'low-b', 'low-c'},
 2: {'mid-p', 'mid-r', 'mid-q'},
 3: {'high-y', 'high-x', 'high-z'},
 4: {'super'}}
>>> G2 = DiGraph()
>>> G2.add_edges_from([('n10', 'n11'), ('n11', 'n12'), ('n12', 'n13'),
...                    ('n13', 'n14'), ('n20', 'n14'), ('n20', 'n21'),
...                    ('n21', 'n22'), ('n22', 'n23'), ('n30', 'n23'),
...                    ('n30', 'n31'), ('n31', 'n32')])
>>> pp.pprint(get_distance_nodes_map(G2))
{0: {'n32'},
 1: {'n31', 'n23'},
 2: {'n30', 'n22'},
 3: {'n21', 'n14'},
 4: {'n13', 'n20'},
 5: {'n12'},
 6: {'n11'},
 7: {'n10'}}