Meilleur algorithme pour détecter des cycles dans un graphe orienté


Answers

Étant donné qu'il s'agit d'une liste d'emplois, je soupçonne qu'à un moment donné, vous allez les classer dans un ordre d'exécution proposé.

Si tel est le cas, alors une implémentation de tri topologique peut dans tous les cas détecter des cycles. UNIX tsort certainement. Je pense qu'il est probable qu'il est donc plus efficace de détecter des cycles en même temps que des cycles, plutôt que dans une étape séparée.

Donc, la question pourrait devenir: «Comment puis-je le plus efficacement tsort», plutôt que «comment puis-je détecter le plus efficacement les boucles». Pour lequel la réponse est probablement "utiliser une bibliothèque", mais à défaut, l'article suivant de Wikipédia:

http://en.wikipedia.org/wiki/Topological_sorting

a le pseudo-code pour un algorithme, et une brève description d'un autre de Tarjan. Les deux ont O(|V| + |E|) complexité temporelle.

Question

Quel est l'algorithme le plus efficace pour détecter tous les cycles dans un graphe orienté?

J'ai un graphique orienté représentant une planification des travaux qui doivent être exécutés, un travail étant un nœud et une dépendance étant un bord. J'ai besoin de détecter le cas d'erreur d'un cycle dans ce graphique menant à des dépendances cycliques.




La manière la plus simple de le faire est de faire une première traversée en profondeur (DFT) du graphe .

Si le graphe a n sommets, il s'agit d'un algorithme de complexité temporelle O(n) . Puisque vous devrez éventuellement faire une DFT à partir de chaque sommet, la complexité totale devient O(n^2) .

Vous devez maintenir une pile contenant tous les sommets dans la première traversée en profondeur , le premier élément étant le nœud racine. Si vous rencontrez un élément qui est déjà dans la pile pendant la DFT, alors vous avez un cycle.




Si un graphique satisfait cette propriété

|e| > |v| - 1

alors le graphique contient au moins un cycle.




Comme vous l'avez dit, vous avez un ensemble d'emplois, il doit être exécuté dans un certain ordre. Topological sort vous donne l'ordre requis pour la planification des travaux (ou pour les problèmes de dépendance s'il s'agit d'un direct acyclic graph ). Exécutez dfs et maintenez une liste, et commencez à ajouter un noeud au début de la liste, et si vous avez rencontré un noeud déjà visité. Ensuite, vous avez trouvé un cycle dans le graphique donné.




La façon dont je le fais est de faire un tri topologique, en comptant le nombre de sommets visités. Si ce nombre est inférieur au nombre total de sommets dans le groupe de disponibilité de base de données, vous avez un cycle.




Si vous ne pouvez pas ajouter une propriété "visitée" aux noeuds, utilisez un ensemble (ou une carte) et ajoutez simplement tous les noeuds visités à l'ensemble, à moins qu'ils ne soient déjà dans l'ensemble. Utilisez une clé unique ou l'adresse des objets comme "clé".

Cela vous donne également les informations sur le nœud "racine" de la dépendance cyclique qui sera utile lorsqu'un utilisateur doit résoudre le problème.

Une autre solution consiste à essayer de trouver la prochaine dépendance à exécuter. Pour cela, vous devez avoir une pile où vous pouvez vous souvenir où vous êtes maintenant et ce que vous devez faire ensuite. Vérifiez si une dépendance est déjà sur cette pile avant de l'exécuter. Si c'est le cas, vous avez trouvé un cycle.

Bien que cela puisse sembler avoir une complexité de O (N * M) vous devez vous rappeler que la pile a une profondeur très limitée (donc N est petit) et que M devient plus petit avec chaque dépendance que vous pouvez cocher comme "exécutée" plus vous pouvez arrêter la recherche lorsque vous avez trouvé une feuille (donc vous ne devrez jamais vérifier tous les nœuds -> M sera également petit).

Dans MetaMake, j'ai créé le graphique sous la forme d'une liste de listes, puis j'ai supprimé tous les nœuds au fur et à mesure que je les exécutais, ce qui a naturellement réduit le volume de recherche. Je n'ai jamais eu à faire un contrôle indépendant, tout s'est déroulé automatiquement pendant l'exécution normale.

Si vous avez besoin d'un mode "test seulement", ajoutez simplement un drapeau "dry-run" qui désactive l'exécution des jobs réels.




J'avais implémenté ce problème dans sml (programmation impérative). Voici le contour. Trouver tous les nœuds qui ont soit un indegree ou un outdegree de 0. De tels nœuds ne peuvent pas faire partie d'un cycle (donc supprimez-les). Ensuite, supprimez tous les bords entrants ou sortants de ces nœuds. Appliquez récursivement ce processus au graphique résultant. Si à la fin vous ne vous trouvez avec aucun nœud ou bord, le graphique n'a aucun cycle, sinon il l'a fait.






Related