Structure de données pour stocker les bords d'un graphique

8

Je travaille actuellement sur ma thèse de master, et c'est sur le clustering sur les graphes. Je travaille avec une idée utilisant des fourmis pour résoudre le problème. Je travaille actuellement sur l'implémentation et je me demande exactement comment bien représenter les bords du graphique.

Chaque bord est augmenté de certaines informations telles que sa valeur de phéromone et le nombre de fois qu'une fourmi a visité ce bord. Je vais travailler avec des graphes non orientés, qui peuvent finir par être assez énormes (plus d'un million de sommets) et je me demandais quel est le moyen le plus efficace pour moi de stocker les bords et de les rechercher? Je pensais à m'en tenir à une convention et à stocker les points de terminaison en fonction de celui qui a un id de sommet inférieur pour et le plus élevé pour ( et sont les points d'extrémité du bord dans la structure de données). Mais je me demande comment pourrais-je effectuer une recherche dans ce cas?v1v2v1v2

Il y a un mappage que j'ai trouvé de la matrice d'adjacence au tableau de bord, mais cela ne fonctionne que si le graphique sous-jacent est un graphique complet. Je suis donc venu ici pour quelques suggestions sur la façon de procéder car j'ai besoin que ma recherche soit efficace alors que je ne veux pas faire exploser l'espace de stockage pour les bords car les graphiques seront énormes.

graph-theory data-structures evolutionary-computing boueux
la source
1
Votre graphique est-il clairsemé ou dense? Parce que la réponse repose sur cela.
Bartosz Przybylski
Oh, j'aurais dû le mentionner, oui, ce sont surtout des graphiques clairsemés. Fondamentalement, les graphiques avec lesquels je vais travailler représentent des réseaux du monde réel qui sont généralement clairsemés. :)
boueux
Listes d'adjacence triées?
Raphael

Réponses:

5

Si votre graphique est clairsemé, vous devez le stocker en utilisant des "listes" de contiguïté, bien que vous souhaitiez probablement quelque chose de plus efficace qu'une liste (ou peut-être pas, selon l'utilisation). C'est plus simple si vous stockez chaque bord aux deux extrémités. Cela peut être implémenté de plusieurs façons, par exemple, vous pouvez stocker toutes les données dans un grand tableau et stocker uniquement des pointeurs dans les "listes" d'adjacence.

Yuval Filmus
la source
Jusqu'à présent, j'ai utilisé une approche de liste d'adjacence où pour chaque sommet j'ai un tableau de ses voisins (chaque sommet est un objet). Cette méthode est utile car chaque fourmi connaît les voisins de chaque sommet. Mais j'ai besoin de choisir le bord à traverser ensuite, en fonction des informations sur les phéromones et d'autres données que je vais calculer. Je ne veux pas introduire de duplication donc je me demandais s'il y avait un moyen de représenter chaque bord individuellement mais être capable de les indexer efficacement en même temps, car j'aurai besoin de beaucoup de recherche pour chaque bord à chaque itération .
boueux
À titre d'exemple, voici le mappage possible aux indices du tableau de bord si le graphique était complet. Dans ce cas, nous savons déjà que la taille du tableau de bord sera n (n-1), où n est le nombre de sommets. Ainsi, traduire la matrice d'adjacence [x] [y] en index de tableau (idx) peut être la suivante: si x <= y alors idx = n * x - x * (x + 1) / 2 + (y - x - 1) else idx = n * y - y * (y + 1) / 2 + (x - y - 1) Donc, disons que bord (5,11) ou (11,5) se traduiront tous les deux dans le même index de tableau. Mais comme je ne travaille pas avec des graphiques complets, je ne peux pas penser à une cartographie.
boueux
2
Vous persistez à utiliser des structures de données qui n'ont de sens que pour les graphiques denses. Pour les graphiques clairsemés, l'approche consiste toujours à stocker, d'une manière ou d'une autre, pour chaque sommet tous les bords qui lui sont incidents. Il n'y a pas de duplication - les données ne sont stockées qu'en un seul endroit; mais il y a deux pointeurs vers les données. L'indexation rapide peut être implémentée à l'aide d'arbres de recherche, de tables de hachage, etc. Ceux-ci vous permettront d'implémenter rapidement et, espérons-le, sans surcharge d'espace. G[x][y]
Yuval Filmus