Meilleur algorithme pour détecter les cycles dans un graphique dirigé

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

J'ai un graphique dirigé représentant un calendrier 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 conduisant à des dépendances cycliques.

L'algorithme des composants fortement connectés de Tarjan a une O(|E| + |V|)complexité temporelle.

Pour d'autres algorithmes, voir Composants fortement connectés sur Wikipédia.

Étant donné qu'il s'agit d'un calendrier de travaux, je soupçonne qu'à un moment donné, vous allez les trier dans un ordre d'exécution proposé.

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

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

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 une O(|V| + |E|)complexité temporelle.

La façon la plus simple de le faire est de faire une première traversée en profondeur (DFT) du graphique .

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

Vous devez conserver une pile contenant tous les sommets dans la première traversée de profondeur actuelle , son 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.

Selon le lemme 22.11 de Cormen et al., Introduction to Algorithms (CLRS):

Un graphe orienté G est acyclique si et seulement si une recherche en profondeur d'abord de G ne donne aucun bord arrière.

Cela a été mentionné dans plusieurs réponses; ici, je vais également fournir un exemple de code basé sur le chapitre 22 de CLRS. Le graphique d'exemple est illustré ci-dessous.

Le pseudo-code de CLRS pour la recherche en profondeur d'abord se lit comme suit:

Dans l'exemple de la figure 22.4 du CLRS, le graphique se compose de deux arbres DFS: l'un composé des nœuds u , v , x et y et l'autre des nœuds w et z . Chaque arbre contient un bord arrière: un de x à v et un autre de z à z (une auto-boucle).

La réalisation clé est qu'un bord arrière est rencontré lorsque, dans la DFS-VISITfonction, tout en itérant sur les voisins vde u, un nœud est rencontré avec la GRAYcouleur.

Le code Python suivant est une adaptation du pseudocode de CLRS avec une ifclause ajoutée qui détecte les cycles:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

Notez que dans cet exemple, le timepseudocode de CLRS n'est pas capturé car nous ne sommes intéressés que par la détection des cycles. Il existe également du code standard pour construire la représentation de liste d'adjacence d'un graphique à partir d'une liste d'arêtes.

Lorsque ce script est exécuté, il imprime la sortie suivante:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Ce sont exactement les bords arrière de l'exemple de la figure 22.4 du CLRS.

Commencez avec un DFS: un cycle existe si et seulement si un back-edge est découvert pendant DFS . Ceci est prouvé à la suite du théorème du chemin blanc.

À mon avis, l'algorithme le plus compréhensible pour détecter le cycle dans un graphe orienté est l'algorithme de coloration du graphe.

Fondamentalement, l'algorithme de coloration du graphique parcourt le graphique d'une manière DFS (Depth First Search, ce qui signifie qu'il explore complètement un chemin avant d'explorer un autre chemin). Lorsqu'il trouve un bord arrière, il marque le graphe comme contenant une boucle.

Pour une explication approfondie de l'algorithme de coloration des graphiques, veuillez lire cet article: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

De plus, je fournis une implémentation de la coloration des graphes en JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Si vous ne pouvez pas ajouter une propriété "visitée" aux nœuds, utilisez un ensemble (ou une carte) et ajoutez simplement tous les nœuds 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 seront utiles 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 rappeler où vous êtes maintenant et ce que vous devez faire ensuite. Vérifiez si une dépendance existe 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 (vous n'avez donc jamais à vérifier chaque nœud -> M sera petit aussi).

Dans MetaMake, j'ai créé le graphique sous forme de liste de listes, puis supprimé tous les nœuds au fur et à mesure que je les exécutais, ce qui a naturellement réduit le volume de recherche. En fait, je n'ai jamais eu à effectuer de vérification indépendante, tout s'est produit automatiquement lors de l'exécution normale.

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

Il n'y a pas d'algorithme qui puisse trouver tous les cycles dans un graphe orienté en temps polynomial. Supposons que le graphe dirigé ait n nœuds et que chaque paire de nœuds ait des connexions entre elles, ce qui signifie que vous avez un graphe complet. Donc, tout sous-ensemble non vide de ces n nœuds indique un cycle et il y a 2 ^ n-1 nombre de ces sous-ensembles. Il n'existe donc pas d'algorithme de temps polynomial. Supposons donc que vous ayez un algorithme efficace (non stupide) qui peut vous indiquer le nombre de cycles dirigés dans un graphique, vous pouvez d'abord trouver les composants connectés forts, puis appliquer votre algorithme sur ces composants connectés. Puisque les cycles n'existent qu'à l'intérieur des composants et non entre eux.

J'avais implémenté ce problème en sml (programmation impérative). Voici le plan. Trouvez tous les nœuds qui ont un degré ou un degré de 0. Ces nœuds ne peuvent pas faire partie d'un cycle (supprimez-les donc). Supprimez ensuite tous les bords entrants ou sortants de ces nœuds. Appliquer récursivement ce processus au graphique résultant. Si à la fin vous ne vous retrouvez avec aucun nœud ou bord, le graphique n'a pas de cycles, sinon il en a.

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 DAG, vous avez un cycle.

/mathpro/16393/finding-a-cycle-of-fixed-length J'aime cette solution la meilleure spécialement pour 4 longueurs :)

L'assistant physique dit également que vous devez faire O (V ^ 2). Je crois que nous n'avons besoin que de O (V) / O (V + E). Si le graphique est connecté, DFS visitera tous les nœuds. Si le graphique a des sous-graphiques connectés, chaque fois que nous exécuterons un DFS sur un sommet de ce sous-graphique, nous trouverons les sommets connectés et n'aurons pas à les considérer pour la prochaine exécution du DFS. Par conséquent, la possibilité de courir pour chaque sommet est incorrecte.

Si DFS trouve une arête qui pointe vers un sommet déjà visité, vous y avez un cycle.

Comme vous l'avez dit, vous avez défini des tâches, elles doivent être exécutées dans un certain ordre. Topological sortétant donné 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 dfset maintenez une liste, et commencez à ajouter un nœud au début de la liste, et si vous avez rencontré un nœud qui est déjà visité. Ensuite, vous avez trouvé un cycle dans un graphique donné.

Si un graphique satisfait cette propriété

|e| > |v| - 1

alors le graphique contient au moins sur le cycle.