Sérialisation graphique

Je cherche 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 veux trouver l’ordre correct au moment de la compilation. Je sais que cela doit être une chose assez commune à faire – les compilateurs le font tout le temps – mais mon google-fu a été faible aujourd’hui. Quel est l’algorithme “go-to” pour cela?

Tri topologique (extrait de Wikipedia):

Dans la théorie des graphes, un sorting topologique ou un ordre topologique d’un graphe acyclique dirigé (DAG) est un ordre linéaire de ses nœuds dans lequel chaque nœud vient avant tous les nœuds auxquels il a des bords sortants. Chaque DAG a un ou plusieurs types 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) 

Je m’attendrais à ce que les outils qui en ont besoin marchent simplement dans l’arbre en profondeur et quand ils frappent une feuille, traitez-la simplement (comstackz) et retirez-la du graphique (ou marquez-la comme traitée et traitez toutes les feuilles). transformé en feuilles).

Tant que c’est un DAG, cette simple marche par stack doit être sortingviale.

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

Je suis venu avec un algorithme récursif assez naïf (pseudocode):

 Map> source; // map of each object to its dependency list List 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 faire l’object d’une récursion infinie (c’est-à-dire un débordement de stack ;-p). Le seul moyen que je puisse voir serait de retourner l’algorithme récursif dans un algorithme interactif avec une stack manuelle, et de vérifier manuellement la stack pour les éléments répétés.

Quelqu’un a quelque chose de mieux?