Graphe de sérialisation

Je suis à la recherche d'un algorithme simple de "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 le bon ordre au moment de la compilation. Je sais que cela doit être assez fréquent - les compilateurs de le faire tout le temps mais mon google-fu a été faible aujourd'hui. Quel est le "go-to" de l'algorithme pour cela?

InformationsquelleAutor Kieron | 2008-08-07
  1. 57

    Tri Topologique (Tiré De Wikipedia):

    Dans la théorie des graphes, un tri topologique ou
    ordre topologique d'un dirigés
    graphe acyclique (DAG) est une forme linéaire
    la commande de ses nœuds dans lequel chaque
    nœud vient avant tous les nœuds pour lesquels
    il a sortante bords. Chaque DAG
    un ou plusieurs topologique sortes.

    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)
    • Eh... copié directement sur wikipédia?
    • oui, merci de citer les sources
    • Merci. M'a aidé à la carte le fait que l'arbre des dépendances peuvent être triées à l'aide de cette méthode. 🙂
    InformationsquelleAutor Andrew Peters
  2. 1

    Je m'attends à des outils qui ont besoin de simplement à pied de l'arbre en profondeur d'abord de la manière et quand ils ont frappé une feuille, juste de processus (par exemple, la compilation) et de le supprimer du graphe (ou la marquer comme traitées, et de traiter les nœuds avec toutes les feuilles traitées comme des feuilles).

    Tant que c'est un DAG, cette simple basée sur la pile marche devrait être trivial.

    • Oui, c'est comment vous le faites. Il a appelé à une profondeur d'abord de recherche (DFS). Et à moins que vous soyez certain que vous avez un DAG, vous mustcheck pour les bords de derrière, sinon un cycle va vous envoyer dans une boucle infinie.
    InformationsquelleAutor Lily Ballard
  3. 1

    Si le graphe contient des cycles, comment peut-il exister permis d'exécution d'ordres pour vos fichiers?
    Il me semble que si le graphe contient des cycles, alors vous n'avez pas de solution, et ce
    est correctement signalée par l'algorithme ci-dessus.

    • Oui, un tri topologique n'est pas possible si un graphe contient un cycle. Cela correspond à la réalité: Si je vous demande de faire Un avant B, et B avant A, il n'y a aucun moyen que vous allez me répondre ;-).
    InformationsquelleAutor
  4. 0

    Je suis venu avec une assez naïfs algorithme récursif (pseudo-code):

    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 avec cela est qu'il a pas la capacité de détecter cyclique dépendances - il possible d'aller dans une récursion infinie (c'est à dire de débordement de pile ;-p). Le seul moyen de contourner ce que je vois serait de renverser l'algorithme récursif dans un interative un avec un manuel de la pile, et de vérifier manuellement la pile pour les éléments répétés.

    Quelqu'un a quelque chose de mieux?

    • au lieu d'utiliser un foreach un certain temps, de maintenir les deux pointeurs traversant les données, un chef de file celui qui double étapes et une fuite en celui qui seul étapes. Le premier pointeur gère le acutal résolutions et si jamais il tours, le pointeur de fuite il y a un cycle.
    InformationsquelleAutor Kieron