Trois façons de stocker un graphe en mémoire, avantages et inconvénients

Il existe trois façons de stocker un graphique en mémoire:

1. Les nœuds comme objets et les arêtes comme pointeurs
2. Une matrice contenant tous les poids de bord entre le nœud numéroté x et le nœud y
3. Une liste d'arêtes entre les nœuds numérotés

Je sais écrire les trois, mais je ne suis pas sûr d'avoir pensé à tous les avantages et inconvénients de chacun.

Quels sont les avantages et les inconvénients de chacune de ces façons de stocker un graphe en mémoire?

Une façon de les analyser est en termes de complexité de mémoire et de temps (qui dépend de la façon dont vous souhaitez accéder au graphique).

Stockage des nœuds en tant qu'objets avec des pointeurs les uns vers les autres

• La complexité de la mémoire pour cette approche est O (n) car vous avez autant d'objets que de nœuds. Le nombre de pointeurs (vers les nœuds) requis est jusqu'à O (n ^ 2) car chaque objet nœud peut contenir des pointeurs pour jusqu'à n nœuds.
• La complexité temporelle de cette structure de données est O (n) pour accéder à un nœud donné.

Stockage d'une matrice de poids d'arête

• Ce serait une complexité mémoire de O (n ^ 2) pour la matrice.
• L'avantage de cette structure de données est que la complexité temporelle pour accéder à un nœud donné est O (1).

En fonction de l'algorithme que vous exécutez sur le graphique et du nombre de nœuds, vous devrez choisir une représentation appropriée.

Quelques autres choses à considérer:

1. Le modèle matriciel se prête plus facilement aux graphes avec des arêtes pondérées, en stockant les poids dans la matrice. Le modèle objet / pointeur devrait stocker les poids de bord dans un tableau parallèle, ce qui nécessite une synchronisation avec le tableau de pointeur.

2. Le modèle objet / pointeur fonctionne mieux avec les graphiques orientés que les graphiques non orientés car les pointeurs doivent être maintenus par paires, ce qui peut devenir non synchronisé.

La méthode des objets et des pointeurs souffre de difficultés de recherche, comme certains l'ont noté, mais elle est assez naturelle pour faire des choses comme la construction d'arbres de recherche binaires, où il y a beaucoup de structure supplémentaire.

Personnellement, j'adore les matrices de contiguïté car elles facilitent beaucoup de problèmes en utilisant des outils de la théorie algébrique des graphes. (La kième puissance de la matrice de contiguïté donne le nombre de chemins de longueur k du sommet i au sommet j, par exemple. Ajoutez une matrice d'identité avant de prendre la kième puissance pour obtenir le nombre de chemins de longueur <= k. Prenez un rang n-1 mineur du Laplacien pour obtenir le nombre d'arbres enjambeurs ... Et ainsi de suite.)

Mais tout le monde dit que les matrices de contiguïté coûtent cher en mémoire! Ils n'ont qu'à moitié raison: vous pouvez contourner ce problème en utilisant des matrices clairsemées lorsque votre graphique a peu d'arêtes. Les structures de données matricielles clairsemées font exactement le travail de garder une liste de contiguïté, mais ont toujours la gamme complète des opérations matricielles standard disponibles, vous donnant le meilleur des deux mondes.

Je pense que votre premier exemple est un peu ambigu: les nœuds comme objets et les arêtes comme pointeurs. Vous pouvez garder une trace de ceux-ci en stockant uniquement un pointeur vers un nœud racine, auquel cas accéder à un nœud donné peut être inefficace (disons que vous voulez le nœud 4 - si l'objet nœud n'est pas fourni, vous devrez peut-être le rechercher) . Dans ce cas, vous perdriez également des parties du graphique qui ne sont pas accessibles depuis le nœud racine. Je pense que c'est le cas que f64 rainbow suppose quand il dit que la complexité en temps pour accéder à un nœud donné est O (n).

Sinon, vous pouvez également conserver un tableau (ou hashmap) plein de pointeurs vers chaque nœud. Cela permet à O (1) d'accéder à un nœud donné, mais augmente un peu l'utilisation de la mémoire. Si n est le nombre de nœuds et e est le nombre d'arêtes, la complexité spatiale de cette approche serait O (n + e).

La complexité spatiale pour l'approche matricielle serait le long des lignes de O (n ^ 2) (en supposant que les arêtes sont unidirectionnelles). Si votre graphique est clairsemé, vous aurez beaucoup de cellules vides dans votre matrice. Mais si votre graphe est entièrement connecté (e = n ^ 2), cela se compare favorablement à la première approche. Comme le dit RG, vous pouvez également avoir moins d'erreurs de cache avec cette approche si vous allouez la matrice comme un morceau de mémoire, ce qui pourrait accélérer le suivi de beaucoup d'arêtes autour du graphique.

La troisième approche est probablement la plus efficace en termes d'espace dans la plupart des cas - O (e) - mais ferait de la recherche de tous les bords d'un nœud donné une tâche O (e). Je ne peux pas penser à un cas où cela serait très utile.

Jetez un œil au tableau de comparaison sur wikipedia. Cela donne une assez bonne compréhension du moment où utiliser chaque représentation de graphiques.

Il y a une autre option: les nœuds comme objets, les arêtes comme objets aussi, chaque arête étant en même temps dans deux listes doublement liées: la liste de toutes les arêtes sortant du même nœud et la liste de toutes les arêtes entrant dans le même nœud .

struct Node {
    ... node payload ...
    Edge *first_in;    // All incoming edges
    Edge *first_out;   // All outgoing edges
};

struct Edge {
    ... edge payload ...
    Node *from, *to;
    Edge *prev_in_from, *next_in_from; // dlist of same "from"
    Edge *prev_in_to, *next_in_to;     // dlist of same "to"
};

La charge mémoire est importante (2 pointeurs par nœud et 6 pointeurs par arête) mais vous obtenez

• Insertion du nœud O (1)
• Insertion d'arête O (1) (pointeurs donnés vers les nœuds "from" et "to")
• O (1) suppression d'arête (étant donné le pointeur)
• Suppression du nœud O (deg (n)) (étant donné le pointeur)
• O (deg (n)) recherche des voisins d'un nœud

La structure peut aussi représenter un graphe assez général: multigraphe orienté avec des boucles (c'est-à-dire que vous pouvez avoir plusieurs arêtes distinctes entre les deux mêmes nœuds incluant plusieurs boucles distinctes - arêtes allant de x à x).

Une explication plus détaillée de cette approche est disponible ici .

D'accord, donc si les arêtes n'ont pas de poids, la matrice peut être un tableau binaire, et l'utilisation d'opérateurs binaires peut rendre les choses vraiment très rapides dans ce cas.

Si le graphe est clairsemé, la méthode objet / pointeur semble beaucoup plus efficace. Tenir l'objet / les pointeurs dans une structure de données spécifiquement pour les amener dans un seul morceau de mémoire peut également être un bon plan, ou toute autre méthode pour les amener à rester ensemble.

La liste de contiguïté - simplement une liste de nœuds connectés - semble de loin la plus efficace en mémoire, mais probablement aussi la plus lente.

Inverser un graphe orienté est facile avec la représentation matricielle, et facile avec la liste de contiguïté, mais pas très bien avec la représentation objet / pointeur.