Suppression des dépendances de cycle sur un graphe orienté avec bords fixes

Question

J'ai un graphe cyclique dirigé. Certains bords sont FIXES et ne peuvent pas être supprimés. Les autres bords peuvent être retirés pour rompre un cycle. Quelle est la meilleure façon de supprimer les cycles dans ce graphique?

La traversée doit être aussi importante qu'un DFS possible et commencer à un nœud donné.

Answer 1

I utilisé l'algorithme suivant pour résoudre mon problème:

Commencez avec un graphique de tous les bords fixes Marquée comme confirmé

d'un noeud de départ, récursif à travers tous les bords confirmés ainsi que ceux qui n'ont pas encore été confirmés. Mais lorsque vous êtes sur le point de recopier une arête non encore confirmée, vérifiez d'abord si le nœud vers lequel pointe le contour a un chemin, en suivant les arêtes confirmées, jusqu'à un nœud dans l'arbre de recherche actuel (par exemple un nœud avec visite ensemble de drapeaux). Cette vérification doit être faite récursivement en suivant tous les bords confirmés mais c'est trop lent pour moi donc je vais m'installer ici juste pour vérifier si le noeud est en train de visiter ou si l'un des noeuds auquel il est confirmé est en train de visiter. Cela couvrira la plupart de mes cas mais laissera occasionnellement des cycles dans le graphique.

Après l'étape précédente, j'utilise l'algorithme de Tarjan pour trouver les composants fortement connectés restant dans le graphique (cela peut être fait en temps O (V + E)).Le nombre de composants fortement connectés sera très petit dans mes cas alors je vais juste passer par chaque composant fortement connecté et enlever un bord amovible chacun. Ensuite, je répète cette étape jusqu'à ce qu'il ne reste plus de cycles dans le graphique.

Cela fonctionne très bien et est assez rapide.

Answer 2

Ce que vous pouvez faire est d'utiliser l'algorithme de Dijkstra: commencez avec un graphique contenant seulement les bords FIXES. Appliquez ensuite une adaptation de l'algorithme en commençant par le graphique déjà existant:

1. Commencez par le noeud de départ et tous les arêtes FIXES du composant du noeud de départ. Supposons que c'est un arbre.
2. Ajoutez le nœud le plus proche de l'arborescence.
3. Ajoutez également des arêtes FIXES dans le composant du noeud que vous venez d'ajouter.
4. Si tous les nœuds sont dans l'arborescence, fin. Sinon, passez à l'étape 4.

Ceci, bien sûr, suppose que le graphique constitué uniquement des bords FIXES ne contient pas de cycles. Si c'est le cas, il n'y a pas de solution (c'est-à-dire, un sous-graphe sans bords, mais contenant tous les bords FIXES).

Pour les graphes orientés, c'est un peu plus compliqué. Dans ce cas, tout composant du graphique des arêtes FIXES doit être un arbre. Dans l'algorithme de Dijkstra, seules les racines de ces nœuds devraient être des candidats à ajouter à l'arbre.

Answer 3

le problème est sous-estimé car vous n'avez pas spécifié, par ex. si le graphe doit rester connecté, ou si vous voulez supprimer un "petit" nombre d'arêtes non-FIXES pour casser tous les cycles, ou si vous avez vraiment besoin du nombre minimum global d'arêtes non FIXES à supprimer.

Si le graphique n'a pas besoin de rester connecté, il suffit de parcourir tous les bords et de supprimer tous ceux qui ne sont pas FIXES. Cela supprime tous les cycles que vous pouvez supprimer sans enlever les bords FIXES.

Si vous voulez un algorithme glouton simple pour enlever les arêtes qui est DFS pur, vous pouvez utiliser quelque chose comme cela si le graphique reste également connecté lorsque vous supprimez certaines des arêtes non FIXE:

proc recurse(vertex n, vertex_set ns) 
    if (n appers_in ns) // it is a cycle 
    return BREAK_CYCLE 
    else for (e in list_outgoing_edges_from(n)) 
    np = e.destination 
    result = recurse(np, add_to_set(ns, np)) 
    if (result == BREAK_CYCLE) 
     if (e.FIXED) 
     return BREAK_CYCLE 
     else 
     [remove e from the graph] 
     return RETRY 
     else if (result == RETRY) 
     return recurse(n, ns) 
    return FINISHED 

if (recurse (your_initial_node, empty_vertex_set())) 
    [graph contains a cycle through only FIXED edges] 
else 
    [the reachable component from initial_node has no longer cycles]