Je cherche une bibliothèque pour fonctionner sur des graphiques dynamiques. J'ai une simulation où je dois calculer à plusieurs reprises la longueur géodésique moyenne pour un graphique après avoir effectué des modifications dans sa structure (ajout et suppression de bords, sur un graphique non dirigé, tous les bords ont les mêmes poids).
J'utilisais un enveloppement rapide C ++ sur igraphe que j'ai fait. IGraphe est pour les graphiques statiques, donc je recalculait les distances géodésiques à partir de zéro chaque fois que j'ai changé le graphique. C'est une simulation de Monte Carlo, alors je dois faire ces millions de fois pour récupérer certaines statistiques. Ça commence à devenir réel lent.
Donc, j'ai cherché des bibliothèques avec des algorithmes pour des graphiques dynamiques, cela pourrait recalculer simplement la mise à jour de la longueur moyenne après avoir supprimé ou ajouter un bord. J'ai trouvé des papiers sur le sujet, mais je ne suis vraiment pas spécialiste (je suis juste un physicien, j'utilise simplement des graphiques sur un problème ... Je n'ai presque aucune connaissance des structures de données et des algorithmes) afin que je puisse Il a même lu les papiers, sans parler de mettre en œuvre les algorithmes.
J'ai trouvé cette bibliothèque LEDA (http://www.algorithmic-solutions.com/leda/) qui semble avoir une extension de graphique dynamique, mais il semble être hométacé (les liens à télécharger la version gratuite sont cassés) et c'est propriétaire.
Y a-t-il des alternatives? Je recherche des bibliothèques C / C ++. Peut-être que Haskell si je dois, et je suis absolument désespérément.
3 Réponses :
Y a-t-il des algorithmes pour des graphiques dynamiques à Boost? Il me semble que ce n'est que pour des graphiques statiques.
De la documentation BGL: "Il est hautement paramétré de sorte qu'il puisse être optimisé pour différentes situations: le graphique est dirigé ou non dirigé, autoriser ou interdire des bords parallèles, un accès efficace aux bordures sortantes ou aux bords intégrés, sommet rapide insertion et élimination au coût de l'espace supplémentaire aérien, etc. " Vous ne savez pas si c'est ce dont vous avez besoin ou si vous recherchez des algorithmes qui n'ont pas besoin de visiter un graphique entier pour rendre compte des changements?
Oui, je m'intéresse aux algorithmes qui peuvent calculer le changement dans le chemin géodésique plus rapide en fonction du fait que je connais le chemin géodésique avant que je puis j'ai supprimé ou ajouté un bord, comme exemple. Sur les lignes de cet article: AMS.org/mathscinet-getem?MR=2145260.
Depuis que vous faites de toute façon Monte Carlo, je suppose qu'il serait acceptable de se rapprocher de la longueur moyenne du chemin le plus court. À chaque étape, vous pouvez goûter une poignée de nœuds et signaler la longueur moyenne du chemin le plus court des chemins à partir de l'un de ces nœuds, qui a la même répartition et une autre variance raisonnable.
Alternativement, référence [3] du papier JACM que vous avez mentionné sur des chemins de mer les plus courts dynamiques est une étude expérimentale de 2004; Peut-être que les auteurs vous permettraient d'utiliser leur code.
Maintenant que j'ai un endroit pour commenter, cela pourrait être utile pour les réponses futures pour savoir comment sont denses vos graphiques.
Salut. Mes graphiques vont de la forme d'étoile à complètement connectée. :(
Serais-je introduire des biais si je suis échantillonné des nœuds en fonction de leur connectivité pour calculer la longueur du chemin AVG?
Je sais que tard, mais avez-vous regardé citron ?
Il utilise la première recherche de souffle. Dans sa diapositive, il utilise "BFS". Lemon.cs.elte.hu/pub/doc/Lemon- intro-présentation.pdf :(
Comment avez-vous résolu ce problème? Six ans plus tard, je ne trouve toujours pas de cette bibliothèque (haute performance).
Cette question était sur le sujet lorsqu'elle a été posée, mais c'est hors de sujet maintenant. En même temps ... homme, je vraiment veut une réponse à cela. Cela ferait quelque chose que je travaille sur tellement plus facile. Tant pis.