Quel est l'avantage de pouvoir cartographier les dépendances d'un système comme un DAG (dirigé graphique acyclique)?

Question

Si je devais organiser une collection de dépendances d'objets dans un DAG, dans quelles situations serait-ce plus souhaitable qu'une autre structure de données comme un BDD (diagramme de décision binaire)?

Answer 1

Le DAG a quelques propriétés qui sont idéales pour analyser les dépendances.

D'abord, vous pouvez facilement identifier les composants « niveau de base » de votre système. Ce sont les nœuds du DAG sans bords entrer dans eux. Connaître les couches relatives de votre système signifie que vous connaissez l'impact de refactoring. (Tout en bas de la chaîne.)

En second lieu, si vous pouvez produire un DAG vous savez que le système n'a pas inter-dépendances étranges. Cycles dans le graphe de dépendance signifie que vous avez deux composants qui reposent sur une autre - une recette pour les bugs étranges et les erreurs de construction. Chez Microsoft, nous avons utilisé un outil appelé asmmeta pour contourner ce problème.

Answer 2

Je ne suis pas très bien informé sur les diagrammes de décision binaires, mais wikipedia semble à l'autre qu'ils sont fondamentalement dirigés, acyclique, graphiques. Je connais un peu DAG. Si vous pouvez représenter votre problème en tant que DAG vous pouvez vous assurer que vous n'avez pas encore cycles (comme Chris Smith mentionné plus haut).

Un autre attribut d'un arbre de décision binaire qui peut (ou non) être pertinente ici est qu'ils sont binaires. Cependant, je ne sais pas comment vous voulez modéliser votre problème à un diagramme de décision binaire. Il semble que BDD zéro, un ou deux choix à chaque noeud. Je vais avoir du mal à voir comment je mapper les dépendances à cela. dépendances de cartographie dans un graphique font beaucoup plus de sens pour moi.

Principalement, je pense que cela dépend de ce que les algorithmes que vous voulez exécuter sur votre représentation. Si vous ne savez pas que vous avez un DAG, vous pouvez exécuter un cycle de l'algorithme de détection pour vous dire si est ou non. Si vous voulez trouver les chemins les plus courts, vous pouvez exécuter Dijkstra sur elle. Je pense que cela dépend vraiment de ce que vous voulez faire, et je sais que les choses que vous pouvez faire avec un graphique général, qui concernent principalement le prouver est un DAG. Une fois que vous avez un DAG, la plupart des choses que je voudrais établir ont été mis en place. C'est juste moi bien.

-Brian J. Stinar -