[Conception] Quelle structure pour lier des chemins et des arcs ?

Hello,

Je travaille avec un réseau, donc j'ai des sommets, des arcs, des chemins formés d'arcs, etc... J'aimerai pouvoir stocker de l'information qui lie les chemins et les arcs (principe de la matrice link_path qui contient un 1 en position [i][j] si l'arc i est dans le chemin j et 0 sinon), mais je ne peux pas me permettre de stocker la matrice entière, elle a plein de zéros et c'est trop gros. (pour un ordre de grandeur, j'ai plus de 4000 arcs et autour des 50000 chemins).

J'ai besoin :

- de pouvoir facilement savoir si un chemin passe par un arc donné
- de pouvoir facilement savoir à quels chemins un arc donné appartient, et quels sont les arcs formant un chemin donné
- de pouvoir facilement supprimer un chemin
- de pouvoir facilement (voire automatiquement ) supprimer les arcs qui font partie d'exactement les mêmes chemins

J'ai pensé à utiliser les map pour que les doublons se suppriment automatiquement, mais je dois mette la liste des chemins comme clé pour qu'ils suppriment les doublons, et ensuite c'est difficile d'accéder à un arc en particulier vu que la clé est sur les chemins.

toutes vos idées ou commentaires sont les bienvenus !

Et ben une structure de graphe non. Pour éviter de stocker une énorme matrice, tu peux peut être utiliser l'adjacency_list de la BGL.

Mon probleme est que je travaille sur le lien entre les arcs et les chemins, et non entre les sommets et les arcs. En fait je n'ai meme pas les sommets a disposition. L'inconvenient est qu'alors qu'un arc n'appartient qu a deux sommets, il peut appartentir a plein de chemins.

Je vais essayer deux objets, arcs et chemins, qui contiendront chacun une liste des identifiants de l'autre type (chaque arc a un id et une liste d'id pour tous les chemins auxquels il appartient). Ca stocke tous les 1 a double, mais pas les 0. vu que ma matrice est creuse, ca devrait valoir la peine je pense.Ca reprend le principe de l'adjacent_list.

Salut,

Et, pour te faciliter un peu la tache, si tu inversait la réflexion :question:

Tu pourrait envisager, par exemple, que chaque chemin soit responsable du fait de garder une liste cohérente de ses points de passage...

Il te "suffirait" dés lors, de lui poser "gentiment" la question "passe tu par le point (machin)", à laquelle il te répondrait "oui", ou "non", et le tour serait joué...

Maintenant, La forme précise que doit prendre cette liste de points de passages et la logique que tu mettra en œuvre pour la maintenir cohérente dépendront fortement du reste du problème...