Comment trouver tous les chemins à travers un ensemble de nœuds donnés dans un DAG?

Question

J'ai une liste d'éléments (nœuds bleus ci-dessous) qui sont classés par les utilisateurs de mon application. Les catégories elles-mêmes peuvent être regroupées et classées elles-mêmes.

La structure résultante peut être représentée sous la forme d'un graphe orienté acyclique (DAG) où les éléments sont des puits au bas de la topologie du graphique et les catégories les plus importantes sont des sources. Notez que même si certaines catégories peuvent être bien définies, beaucoup d’entre elles seront définies par l’utilisateur et risquent d’être très compliquées.

Exemple:

_{(source: theuprightape.net )}

Sur cette structure, je souhaite effectuer les opérations suivantes:

• rechercher tous les éléments (puits) situés sous un nœud particulier (tous les éléments en Europe)
• recherche tous les chemins (le cas échéant) qui passent par tout un ensemble de n nœuds (tous les éléments envoyés via SMTP à partir de example.com)
• trouve tous les nœuds situés sous un ensemble de nœuds (intersection: aliments brun goyish)

La première semble assez simple: commencez au nœud, suivez tous les chemins possibles vers le bas et récupérez les éléments. Cependant, existe-t-il une approche plus rapide? Se souvenir des nœuds que j'ai déjà traversés aide probablement à éviter les répétitions inutiles, mais existe-t-il d'autres optimisations?

Comment puis-je m'occuper du second? Il semble que la première étape consisterait à déterminer la hauteur de chaque nœud de l’ensemble, de manière à déterminer à quel (s) point (s) de départ, puis à rechercher tous les chemins en dessous de ceux qui incluent le reste de l’ensemble. Mais est-ce la meilleure (ou même une bonne) approche?

Les algorithmes de traversée de graphes répertoriés dans Wikipedia semblent tous être concernés par la recherche d'une nœud ou la route la plus courte ou la plus efficace entre deux nœuds. Je pense que les deux ne sont pas ce que je veux, ou est-ce que je ne vois pas comment cela s'applique à mon problème? Où d'autre devrais-je lire?

Answer 1

Il me semble qu’il s’agit essentiellement de la même opération pour les 3 questions. Vous demandez toujours "Tous les X sous le (s) noeud (s) Y, où X est de type Z". Tout ce dont vous avez besoin est un mécanisme générique pour "localiser tous les nœuds sous le nœud" (résout Q3), puis vous pouvez filtrer les résultats pour "nodetype = sink" (résout Q1). Pour Q2, vous avez le point de départ (votre groupe de noeuds) et votre point de fin (tout puits inférieur au point de départ), de sorte que votre ensemble de solutions comprend tous les chemins du noeud de départ spécifié au puits. Je suggérerais donc que ce que vous avez fondamentalement est un arbre, et que des algorithmes de base de traversée des arbres seraient la solution.

Answer 2

Malgré le fait que votre graphique soit acyclique, les opérations que vous citez me rappellent des aspects similaires de l’analyse de graphe de contrôle. Il existe un riche ensemble d’algorithmes basés sur la domination . Par exemple, votre troisième opération me rappelle les frontières de la domination informatique; Je pense que cet algorithme fonctionnerait directement si vous introduisiez temporairement & entry; entry " et " quitter " nœuds. Le nœud d’entrée connecte le "groupe de nœuds donné" et les noeuds de sortie connectent les puits.

Voir aussi les algorithmes de base de Robert Tarjan.