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

Question

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

J'ai un graphe orienté représentant un programme de travaux à exécuter, un travail étant un nœud et une dépendance, une arête. J'ai besoin de détecter le cas d'erreur d'un cycle dans ce graphique menant à des dépendances cycliques.

Answer 1

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

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

Answer 2

É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, la mise en œuvre de la tri topologique peut dans tous les cas, détecter les cycles. UNIX tsort le fait certainement. Je pense qu'il est donc probablement plus efficace de détecter les cycles en même temps que le transfert, plutôt que dans une étape séparée.

La question pourrait donc devenir: "Comment puis-je transférer le plus efficacement possible", plutôt que "Comment détecter le plus efficacement possible les boucles". Pour laquelle la réponse est probablement "utiliser une bibliothèque", mais à défaut de l'article Wikipedia 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 complexité temporelle O (| V | + | E |) .

Answer 3

Commencez par un DFS: un cycle existe si et seulement si un bord arrière est découvert au cours de DFS . Ceci est prouvé à la suite du théorème du chemin blanc.

Answer 4

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

Si le graphique a des sommets n , 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 conserver une pile contenant tous les sommets de la première traversée de profondeur actuelle , son premier élément étant le nœud racine. Si vous rencontrez un élément qui se trouve déjà dans la pile pendant la TFD, vous avez un cycle.

Answer 5

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

En gros, l’algorithme de coloration du graphique parcourt le graphique d’une manière DFS (recherche approfondie en premier, ce qui signifie qu’il explore complètement un chemin avant d’en explorer un autre). Lorsqu'il trouve un bord arrière, il indique que le graphique contient une boucle.

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

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

Answer 6

Si vous ne parvenez pas à ajouter un " visité " propriété des 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 en tant que "clé".

Ceci vous donne également les informations sur la " racine " noeud 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 rappeler 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 présenter une complexité de O (N * M), vous devez vous rappeler que la profondeur de la pile est très limitée (N est donc petit) et que M devient plus petit à chaque dépendance que vous pouvez le cocher ; exécuté " De plus, vous pouvez arrêter la recherche lorsque vous avez trouvé une feuille (de sorte que vous jamais ne vérifiiez jamais tous les noeuds - > M sera également petit).

Dans MetaMake, j'ai créé le graphique sous forme de liste de listes, puis supprimé tous les nœuds au fur et à mesure de leur exécution, ce qui a naturellement réduit le volume de recherche. Je n'ai jamais eu à exécuter de contrôle indépendant, tout s'est passé automatiquement lors de l'exécution normale.

Si vous avez besoin d'un "test uniquement" " mode, il suffit d'ajouter un " dry-run " drapeau qui désactive l'exécution des travaux réels.

Answer 7

Il n’existe aucun algorithme permettant de trouver tous les cycles d’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 les unes aux autres, ce qui signifie que vous avez un graphe complet. Ainsi, tout sous-ensemble non vide de ces n nœuds indique un cycle et il existe 2 ^ n-1 nombre de ces sous-ensembles. Donc, aucun algorithme de temps polynomial n'existe.     Supposons donc que vous ayez un algorithme efficace (non stupide) qui puisse vous indiquer le nombre de cycles dirigés dans un graphe. Vous pouvez d’abord rechercher les composants connectés forts, puis appliquer votre algorithme sur ces composants connectés. Comme les cycles n'existent que dans les composants et non entre eux.

Answer 8

Si DFS trouve un bord qui pointe vers un sommet déjà visité, vous avez un cycle à cet endroit.

Answer 9

Selon le lemme 22.11 de Cormen et al., Introduction aux algorithmes (CLRS):

  

Un graphe orienté G est acyclique si et seulement si une recherche de profondeur en premier par G ne produit pas de 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. L'exemple de graphique est illustré ci-dessous.

Le pseudo-code de CLRS pour la recherche en profondeur d'abord est libellé comme suit:

Dans l'exemple de la figure 22.4 du CLRS, le graphique est constitué de deux arborescences DFS: l'une composée de 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 (un boucle).

La réalisation essentielle est qu'un bord arrière est rencontré lorsque, dans la fonction DFS-VISIT , en itérant sur les voisins v de u , un nœud est rencontré avec la couleur GREY .

Le code Python suivant est une adaptation du pseudocode du CLRS avec une clause if 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 discovered and 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 temps du pseudocode de CLRS n'est pas capturé, car nous ne sommes intéressés que par la détection de cycles. Il existe également un code standard permettant de construire la représentation de la liste de contiguïté d’un graphique à partir d’une liste d’arêtes.

Lorsque ce script est exécuté, il affiche le résultat suivant:

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 de CLRS.

Answer 10

Pour ce faire, je fais 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.

Answer 11

J'avais implémenté ce problème dans sml (programmation impérative). Voici le contour. Trouvez tous les nœuds qui ont un indegree ou outdegree 0. Ces 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 graphe résultant. Si à la fin, aucun nœud ni arête ne vous reste, le graphique n'a aucun cycle, sinon il en existe.

Answer 12

https://mathoverflow.net/questions/16393/finding-a-cycle -de-longueur-fixe 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 avons seulement besoin de O (V) / O (V + E). Si le graphique est connecté, DFS visitera tous les nœuds. Si le graphe contient des sous-graphes connectés, chaque fois que nous exécutons un DFS sur un sommet de ce sous-graphe, nous trouverons les sommets connectés et ne les prendrons pas en compte lors de la prochaine exécution du DFS. Par conséquent, la possibilité de courir pour chaque sommet est incorrecte.

Answer 13

Comme vous l'avez dit, vous avez un ensemble de tâches qui doivent être exécutées dans un certain ordre. Tri topologique en fonction de l'ordre requis pour la planification des travaux (ou pour les problèmes de dépendance s'il s'agit d'un graphe acyclique direct ). Exécutez dfs , gérez une liste et commencez à ajouter un nœud au début de la liste, et si vous rencontrez un nœud déjà visité. Ensuite, vous avez trouvé un cycle dans un graphe donné.

Answer 14

Si un graphe satisfait cette propriété

|e| > |v| - 1

alors le graphique contient au moins un cycle.