Suppression des dépendances de cycle sur un graphe dirigé à arêtes fixes

Question

J'ai un graphe cyclique dirigé. Certains bords sont FIXES et ne peuvent pas être supprimés. Les autres bords peuvent être supprimés pour rompre un cycle.

Quelle est la meilleure façon de supprimer les cycles de ce graphique? La traversée doit être aussi longue que possible sous DFS et commencer à un nœud donné.

Answer 1

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

Commencez avec un graphique de toutes les arêtes fixes marqué comme confirmé

À partir d'un nœud de départ, récifez à travers toutes les arêtes confirmées ainsi que celles non encore confirmées. Mais lorsque vous êtes sur le point de ré-analyser un bord non encore confirmé, vérifiez d’abord si le nœud auquel le bord se connecte a un chemin, en suivant les bords confirmés, vers un nœud de l’arbre de recherche actuel (c’est-à-dire un nœud avec un < em> visiter ensemble de drapeaux). Cette vérification doit être effectuée de manière récursive en suivant tous les contours confirmés, mais cette procédure est trop lente pour moi. Je vais donc m'installer ici pour vérifier si le nœud est en visite ou si l'un des nœuds auxquels il est confirmé connecté est en visite. Cela couvrira la plupart de mes cas, mais laisse parfois des cycles dans le graphique.

Après l’étape ci-dessus, j’utilise l’algorithme de Tarjan pour rechercher les composantes fortement connectées du graphique (ceci peut être fait en temps O (V + E)). Le nombre de composants fortement connectés étant très réduit dans mon cas, je passe simplement à travers chaque composant fortement connecté et supprime chacun un bord amovible. Ensuite, je répète cette étape jusqu'à ce qu'il ne reste plus de cycles dans le graphique.

Cela fonctionne bien et est assez rapide.

Answer 2

Ce que vous pouvez faire est d’utiliser l’algorithme de Dijkstra: commencez par un graphe contenant uniquement les arêtes FIXED. Appliquez ensuite une adaptation de l’algorithme en commençant par le graphique que vous avez déjà:

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

Cela suppose bien sûr que le graphique constitué uniquement des arêtes FIXED ne contient pas de cycles. Si tel est le cas, il n’ya pas de solution (c’est-à-dire un sous-graphe sans arêtes, mais contenant toutes les arêtes FIXED).

Pour les graphes dirigés, c'est un peu plus compliqué. Dans ce cas, tout composant du graphique des arêtes FIXED doit être un arbre. Dans l’algorithme de type Dijkstra, seules les racines de ces nœuds doivent être candidates pour être ajoutées à l’arbre.

Answer 3

le problème est sous-estimé car vous n'avez pas spécifié, par exemple. si le graphique doit rester connecté ou si vous souhaitez supprimer un "petit" nombre d'arêtes non FIXED pour interrompre 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 toutes les arêtes et de supprimer toutes les arêtes non FIXED. Cela supprime tous les cycles que vous pouvez supprimer sans supprimer les bords FIXED.

Si vous souhaitez qu'un algorithme glouton simple supprime les arêtes en DFS pur, vous pouvez utiliser quelque chose comme ceci SI le graphe reste connecté également lorsque vous supprimez certaines arêtes non FIXES:

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]