Comment affecter des "niveaux" aux sommets d'un graphe orienté acyclique?

Question

J'ai un graphique dirigé acyclique. Je voudrais assigner des niveaux à chaque sommet d'une manière qui garantit que si le bord (v1, v2) est dans le graphique, alors niveau (v1)> niveau (v2). Je voudrais aussi que si le niveau (v1) = niveau (v3) à chaque fois (v1, v2) et (v3, v2) sont dans le graphique. De plus, les niveaux possibles sont discrets (aussi bien les prendre pour des nombres naturels). Le cas idéal serait ce niveau (v1) = niveau (v2) + 1 quand (v1, v2) est dans le graphique et il n'y a pas d'autre chemin de v1 à v2, mais parfois cela n'est pas possible avec les autres contraintes - Par exemple, considérons un graphe sur cinq sommets avec les arêtes (a, b) (b, d) (d, e) (a, c) (c, e).
Est-ce que quelqu'un connaît un algorithme décent pour résoudre ce problème? Mes graphiques sont assez petits (| V | < = 25 ou plus), donc je n'ai pas besoin de quelque chose qui flambe rapidement - la simplicité est plus importante. Ma pensée jusqu'ici est de simplement trouver un élément au moins, assigner le niveau 0, trouver tous les parents, leur attribuer le niveau 1, et résoudre les contradictions en ajoutant +0.5 aux sommets appropriés, mais cela semble assez horrible.

Aussi, je reçois le sentiment qu'il pourrait être utile de supprimer tous les bords "implicites" (c.-à-remove (V1, V3) si le graphe contient à la fois (v1, v2) et (v2, v3).

Answer 1

Je pense que laisser le niveau de v la longueur du chemin le plus long dirigé de v pourrait bien fonctionner pour vous en Python.

# the level of v is the length of the longest directed path from v 
def assignlevel(graph, v, level): 
    if v not in level: 
     if v not in graph or not graph[v]: 
      level[v] = 0 
     else: 
      level[v] = max(assignlevel(graph, w, level) + 1 for w in graph[v]) 
    return level[v] 

g = {'a': ['b', 'c'], 'b': ['d'], 'd': ['e'], 'c': ['e']} 
l = {} 
for v in g: 
    assignlevel(g, v, l) 
print l 

sortie:

{'a': 3, 'c': 1, 'b': 2, 'e': 0, 'd': 1} 

Answer 2

vous pouvez utiliser une sorte topologique attribuer un numéro unique à chaque ver tex avec la propriété que vous voulez De même, vous pouvez parcourir les nœuds dans l'ordre topologique et affecter max (parents) + 1