Comment répartir les modifications dans le graphique orienté?

J'ai orienté le graphique. Le graphique peut être fortement connecté. Chaque sommet peut avoir un ensemble de n'importe quoi, par exemple des lettres. L'ensemble est modifiable par l'utilisateur.Comment répartir les modifications dans le graphique orienté?

Chaque sommet fait intersection des ensembles dans les sommets précédents (un seul pas en arrière).

Mais maintenant, il y a un problème: Lorsque je mets à jour l'ensemble d'un sommet, le changement devrait s'étendre à tous les sommets et remonter leur intersection des ensembles de sommets précédents.

Comment faire pour chaque sommet avoir une intersection correcte après la mise à jour de n'importe quel sommet? Restriction: l'algorithme doit éviter de coller à l'infini. ...

Une idée de la façon de le résoudre ?. EDIT:

Exemple - change VERTIX rouge, et il est nécessaire de se propager le changement de intersecions de tous les sommets: alt text http://img402.imageshack.us/img402/7608/beznzvuru.jpg

Source

2010-03-18 joseph

Pouvez-vous expliquer ou donner un exemple de la façon dont un sommet met à jour son ensemble en fonction de ses prédécesseurs? Une question que j'ai par exemple est: est-ce qu'un nœud aura toujours un surensemble de son ensemble initial ou peut-il perdre des éléments de l'ensemble initial? Qu'arrive-t-il aux sommets sans prédécesseur? – ziggystar

Ad1: Peu importe. L'exigence est que chaque nœud peut offrir une intersection de tous les nœuds précédents. Ad2: Rien ne se passe avec les sommets sans prédécesseur. – joseph

Vous pouvez diviser les changements dans soustractive et additifs changements. Tout ce qui est soustractif peut être retiré en un seul passage en utilisant la méthode décrite par MicSim. Tout additif, cependant, peut se propager tout au long des cycles que vous avez.

Pour les modifications supplémentaires, effectuez les mises à jour de la même manière mais ignorez les entrées qui n'ont pas encore été mises à jour. Cela vous amènera à surpeupler le graphique, car vous ne calculez pas toutes les intersections. Mais si vous revenez pour un second passage, vous nettoierez tous les changements. (Vous pourriez avoir besoin de continuer à balayer jusqu'à ce qu'il n'y ait plus de changements, je ne suis pas tout à fait sûr.)

Je suppose que si vous ne tenez pas compte de ce qui a été ajouté et de ce qui a été soustrait - seulement Il y a eu un changement - vous effectuez simplement un balayage initial où les nœuds nécessitant une mise à jour, mais non mis à jour, ne sont pas recoupés, puis continuez à balayer jusqu'à ce que tout se stabilise. Puisque l'intersection peut seulement enlever des éléments, ceci est garanti pour compléter.

Source

2010-03-18 17:02:00

On dirait un BFS ferait:

Mémorisez la l'ensemble du sommet qui a changé.
Maintenant commencer une première recherche étendue du sommet changé
Pour chaque changement de sommet adjacent correspondant défini selon l'ensemble de (1)
sommet Marquer comme visité
Répétez 1-4 pour chaque sommet adjacent jusqu'à ce qu'il n'y ait plus de sommets non vus

Votre véritable problème réside peut-être dans l'intersection des ensembles. Que vous seriez le point (3) ici. Vous devriez ajouter un exemple pour clarifier le problème.

Source

2010-03-18 16:33:42 MicSim

J'essaie de faire l'exemple en quelques minutes. Mais le problème est que certains sommets doivent être visités plus d'une fois pour le résoudre correctement. – joseph

Mais, je pense juste que certains sommets doivent être visités plus d'une fois, cela n'a pas besoin d'être vrai – joseph

+1 - cela ressemble à la route à suivre. Incidemment, pour créer une recherche d'une grande largeur, il est souvent plus facile d'avoir une file d'attente contenant des éléments sur lesquels travailler, et lorsque vous terminez un élément, ajoutez ses enfants non marqués à la file d'attente. Si vous ne pouvez pas marquer facilement les nœuds eux-mêmes, vous pouvez avoir un ensemble de hachage de "nœuds visités" que vous mettez à jour chaque fois que vous avez fini de travailler sur un nœud. La seule raison pour laquelle cela pourrait ne pas fonctionner est si vous avez besoin de plusieurs passes pour que cela fonctionne - mais cela ne devrait pas être le cas pour "intersection". –

Faites BFS comme suggéré par MicSim, arrêtez après une itération qui n'a pas modifié les sommets.

Source

2010-03-18 17:05:13

Et est mis en quarantaine que l'algorithme ne colle pas à l'infini? Et si chaque itération change un sommet? – joseph

Si chaque itération modifie un sommet, cela signifie que vos cordes dans les sommets sont soit hors limites à l'infini, soit ont atteint une sorte d'équilibre fluctuant. Ils ne peuvent pas atteindre l'infini parce que vous avez des ensembles et ils ne peuvent pas grandir sans que de nouveaux éléments uniques leur soient ajoutés. Voyons maintenant le cas de fluctuation. La fluctuation est possible si un élément est d'abord ajouté au sommet, puis après un certain nombre d'étapes est retiré du sommet. Mais une modification d'un seul sommet ne peut pas supprimer et ajouter le même élément. Donc, la fluctuation n'est pas possible. Ce n'est pas une preuve à 100%, mais ... –

Si vous utilisez la méthode que j'ai décrite (ie surpopulation initiale suivie d'un raffinement), chaque passe supplémentaire ne peut retirer que _remove_ éléments des ensembles, et comme les ensembles sont finis, ceci doit compléter dans un nombre fini de passes. –

Comment répartir les modifications dans le graphique orienté?

Répondre

Questions connexes