Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Structure de donnéees pour un gros graphe orienté peu dense
Bonjour,
J'essaie de modéliser un réseau urbain et pour se faire j'utilise un graphe orienté dont le nombre de sommets peut atteindre max 80000. Chaque sommet ne peut être connecté qu'à max 8 autres sommets.
Hors de question d'utiliser une matrice d'adjacence car celle-ci contiendrait max 80000 x 80000 = 6400000000 éléments.
Pensez vous que la liste d'adjacence soit la structure de données la plus adaptée à mon besoin ?
Je vais te retourner la question : tu exclues la matrice d'adjacence, ok, normal.
Tu hésites entre une liste d'adjacence et quoi ?
J'hésitais avec la liste d’arêtesEnvoyé par tbc92
Ok,
Liste d'adjacence = pour chaque sommet, la liste des arêtes partant de ce sommet.
Liste des arêtes = toutes les arêtes, 'en vrac'.
Toutes les arêtes en vrac, sans outil pour trouver rapidement les arêtes partant d'un sommet ou arrivant à un sommet, c'est pas terrible.
Peut-être 2 listes d'adjacence, une pour avoir les arêtes partant d'un sommet, et l'autre pour avoir les arêtes arrivant à un sommet.
Cette organisation ralentit les temps de mise à jour, mais ici, il n'y a pas de mise à jour, juste une initialisation. Et ça peut être très utile d'avoir ces 2 listes.
Dans les années 80/90, j'avais fait des choses de ce genre.
Certes, depuis, l'informatique a bien évolué.
merci beaucoup pour ta réponse détaillée
Une représentation qui marche encore assez bien dans ce cas (si ton graphe est statique, sans mises à jour), c'est stocker les arêtes : un vecteur pour des origines, un autre pour les destinations, avec un tri sur l'origine. Si tu as des mises à jour, tu devrais insérer des arêtes en plein milieu des vecteurs, ce n'est pas génial et, surtout, ça change les indices des arêtes (ce qui rend plus difficile le stockage de données annexes, comme des poids). Exemple d'implémentation : https://github.com/google/or-tools/b...ph.h#L394-L467.
Autre solution possible : stocker le graphe sous la forme d'une matrice avec leurs poids, mais creuse. Problème : tu ne peux pas stocker une arête avec un poids nul. Exemple d'implémentation : https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl.
Tu indiques un très bon élément avec le fait que ton graphe est creux ; ensuite, que veux-tu en faire, de ce graphe ?
Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.
Créer des applications graphiques en Python avec PyQt5
Créer des applications avec Qt 5.
Pas de question d'ordre technique par MP !
Merci pour ces autres pistes
Répondre avec citation
Partager