Sérialisation de graphiques

Question

Je recherche un algorithme simple pour « sérialiser » un graphe orienté.En particulier, j'ai un ensemble de fichiers avec des interdépendances sur leur ordre d'exécution, et je souhaite trouver le bon ordre au moment de la compilation.Je sais que cela doit être une chose assez courante à faire - les compilateurs le font tout le temps - mais mon google-fu est faible aujourd'hui.Quel est l'algorithme de prédilection pour cela ?

Answer 1

Tri topologique (De Wikipédia) :

Dans la théorie des graphiques, un type topologique ou une commande topologique d'un graphique acyclique dirigé (DAG) est un ordre linéaire de ses nœuds dans lesquels chaque nœud s'approche de tous les nœuds auxquels il a des bords sortants.Chaque Dag a une ou plusieurs sortes topologiques.

Pseudo-code :

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)

Answer 2

Je m'attendrais à ce que les outils qui en ont besoin parcourent simplement l'arbre en profondeur et lorsqu'ils touchent une feuille, la traitent simplement (par ex.compiler) et supprimez-le du graphique (ou marquez-le comme traité et traitez les nœuds avec toutes les feuilles traitées comme des feuilles).

Tant qu'il s'agit d'un DAG, cette simple marche basée sur la pile devrait être triviale.

Answer 3

Si le graphique contient des cycles, comment peut-il exister des ordres d'exécution autorisés pour vos fichiers ?Il me semble que si le graphique contient des cycles, vous n'avez pas de solution, et cela est rapporté correctement par l'algorithme ci-dessus.

Answer 4

J'ai mis au point un algorithme récursif assez naïf (pseudocode) :

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

Le plus gros problème est qu'il n'a pas la capacité de détecter les dépendances cycliques - il peut entrer dans une récursion infinie (c'est-à-dire un débordement de pile ;-p).La seule solution que je puisse voir serait de transformer l'algorithme récursif en un algorithme interactif avec une pile manuelle et de vérifier manuellement la pile pour les éléments répétés.

Quelqu'un a quelque chose de mieux ?