Existe-t-il un algorithme approprié pour résoudre le problème de suppression des contours?

Question

Il existe un graphe orienté (pas nécessairement connecté) dont un ou plusieurs nœuds sont distingués en tant que sources. Tout nœud accessible depuis l'une des sources est considéré comme "allumé". Supposons maintenant que l’un des bords soit supprimé. Le problème est de déterminer les nœuds qui étaient allumés et qui ne le sont plus.

Je présume que l’on pourrait envisager une analogie comme un système électrique urbain.

Answer 1

Il s'agit d'un "accessibilité des graphes dynamiques". problème. Le document suivant devrait être utile:

Un algorithme d'accessibilité entièrement dynamique pour les graphes dirigés avec un temps de mise à jour presque linéaire. Liam Roditty, Uri Zwick. Théorie de l'informatique , 2002.

Ceci donne un algorithme avec O (m * sqrt (n)) - mises à jour de temps ( amorti ) et O (sqrt (n)) - requêtes de temps sur un graphe éventuellement cyclique (où m est le nombre d'arêtes et n le nombre de nœuds). Si le graphique est acyclique, vous pouvez améliorer les requêtes de mises à jour O (m) ( amorties ) et O (n / log n).

Il est toujours possible de faire mieux que cela en raison de la structure spécifique de votre problème ou en échangeant de l'espace contre du temps.

Answer 2

Si au lieu de simplement "lit" ou "non allumé" vous conserveriez un ensemble de nœuds à partir desquels un nœud est alimenté ou allumé et considérez un nœud avec un ensemble vide comme "non allumé". et un nœud avec un ensemble non vide défini comme "allumé", puis la suppression d'un bord impliquerait simplement la suppression du nœud source de l'ensemble du nœud cible.

EDIT: J'ai oublié ceci: Et si vous supprimez le dernier nœud éclairé de l'ensemble, parcourez les bords et supprimez le nœud que vous venez de "laisser éteint". à partir de leur ensemble (et éventuellement à partir de là aussi, etc.)

EDIT2 (reformulation pour tafa): Tout d’abord, j’ai mal interprété la question initiale et je pensais qu’elle indiquait que, pour chaque nœud, il était déjà connu d’être allumé ou éteint, ce qui, comme je le relis maintenant, n’a pas été mentionné.

Cependant, si pour chaque nœud de votre réseau vous stockez un ensemble contenant les nœuds sur lesquels il était éclairé, vous pouvez facilement parcourir le graphique à partir du bord supprimé et corriger les références allumées / non éclairées. Ainsi, par exemple, si nous avons les nœuds A, B, C, D comme ceci: (tentative boiteuse d’art ascii)

A -> B >- D
 \-> C >-/

Ensuite, au nœud A, vous stockeriez qu’elle était une source (et donc allumée toute seule), et dans B et C, vous les stockeriez allumées par A, et en D, vous mémorisiez qu’elle était allumée par les deux A et C.

Dites ensuite que nous supprimons le bord de B en D: En D, nous supprimons B de la liste des sources allumées, mais il reste allumé car il est toujours allumé par A. Ensuite, supprimons le bord de A à C après que: A est retiré de l'ensemble de C, et donc C n'est plus allumé. Nous continuons ensuite à traverser les arêtes provenant de C et retirons C de l'ensemble de D qui n'est plus éclairé. Dans ce cas, nous avons terminé, mais si l'ensemble était plus grand, nous passerions simplement à D.

Cet algorithme ne visitera jamais que les nœuds directement affectés par la suppression ou l'ajout d'un bord, et en tant que tel (à l'exception du stockage supplémentaire nécessaire sur chaque nœud), il devrait être proche de l'optimum.

Answer 3

Est-ce votre devoir?

La solution la plus simple consiste à créer une DFS ( http://fr.wikipedia.org/ wiki / Depth-first_search ) ou un système BFS ( http: //en.wikipedia. org / wiki / Breadth-first_search ) sur le graphique d'origine à partir des nœuds sources. Cela vous donnera tous les noeuds allumés d'origine.

Supprimez maintenant le bord en question. Refaites le DFS. Vous pouvez voir les nœuds qui restent allumés.

Affiche les noeuds qui apparaissent dans le premier ensemble mais pas le second.

C’est un algorithme asymptotiquement optimal, puisque vous faites deux DFS (ou BFS) qui prennent O (n + m) fois et espace (où n = nombre de nœuds, m = nombre d’arêtes), qui dominent la complexité. Vous avez besoin d'au moins o (n + m) temps et espace pour lire l'entrée. L'algorithme est donc optimal.

Maintenant, si vous souhaitez supprimer plusieurs arêtes, ce serait intéressant. Dans ce cas, nous parlerions de structures de données dynamiques. Est-ce ce que vous vouliez?

EDIT: compte tenu des commentaires:

• pas connecté n'est pas un problème, car les nœuds dans les composants connectés inaccessibles ne seront pas atteints pendant la recherche
• il existe un moyen intelligent de faire le DFS ou le BFS à partir de tous les nœuds à la fois (je décrirai le BFS). Il suffit de les mettre tous au début sur la pile / la file d'attente.

Pseudo-code pour un système BFS qui recherche tous les nœuds accessibles depuis l'un des nœuds de départ:

Queue q = [all starting nodes]
while (q not empty)
{
   x = q.pop()
   forall (y neighbour of x) {
      if (y was not visited) {
         visited[y] = true
         q.push(y)
      }
   }
}

Remplacez la file d'attente par une pile et vous obtenez une sorte de DFS.

Answer 4

Quelle est la taille et la connectivité des graphes? Vous pouvez stocker tous les chemins des noeuds sources vers tous les autres noeuds et rechercher des noeuds où tous les chemins menant à ce noeud contiennent l'un des bords supprimés.

EDIT: étendre un peu cette description

Faites un DFS à partir de chaque noeud source. Gardez une trace de tous les chemins générés vers chaque nœud (en tant qu’arêtes et non de sommets; nous avons donc besoin de connaître uniquement les arêtes impliquées, et non leur ordre, pour pouvoir utiliser un bitmap). Conservez pour chaque nœud le nombre de chemins entre la source et le nœud.

Maintenant, parcourez les chemins. Supprimez tout chemin contenant le (s) bord (s) supprimé (s) et décrémentez le compteur pour ce nœud. Si un compteur de nœud est décrémenté à zéro, il était allumé et ne l’est plus.

Answer 5

Je conserverais les informations des nœuds sources connectés sur les bords lors de la construction du graphique (par exemple, si le bord a une connectivité avec les sources S1 et S2, sa liste de sources contient S1 et S2) et crée les nœuds avec les informations de bords d'entrée et de sortie. Lorsqu'une arête est supprimée, mettez à jour les arêtes de sortie du nœud cible de cette arête en prenant en compte les arêtes d'entrée du nœud. Et parcourez tous les nœuds cibles des arêtes mises à jour en utilisant DFS ou BFS. (Dans le cas d'un graphique de cycle, envisagez un marquage). Lors de la mise à jour du graphique, il est également possible de trouver des nœuds sans aucun bord disposant d'une connexion source (nœuds non allumés). Cependant, cela pourrait ne pas être une bonne solution, si vous souhaitez supprimer plusieurs arêtes en même temps, car cela peut entraîner le déplacement sur plusieurs arêtes, encore et encore.