structure de données C++ efficace à considérer dans ce cas

Question

Salutations code-gourous! J'écris un algorithme qui relie, par exemple node_A de Region_A avec node_D de Region_D. (node_A et node_D ne sont que des entiers). Il pourrait y avoir 100k + de tels nœuds. Supposons que le segment de droite entre A et D passe par plusieurs autres régions, B, C, Z. Il y aura un maximum de 20 régions entre ces deux nœuds. Chaque région a ses propres propriétés qui peuvent varier en fonction de la connexion A-D. Je veux y accéder à un moment ultérieur.

Je cherche une bonne structure de données (peut-être un conteneur STL) qui peut contenir cette information pour une connexion particulière.

Par exemple, pour la connexion A - DI veulent stocker:

node_A, 
node_D, 
crosssectional area (computed elsewhere) , 
regionB, 
regionB_thickness, 
regionB other properties, 
regionC, .... 

Les données peuvent être double, int, string et pourrait aussi être un tableau/vecteur etc.

1. Première J'ai envisagé de créer des structures ou des classes pour regionB, regionC etc. Mais, pour chaque connexion A-D, certaines propriétés comme l'épaisseur de la région traversée par cette connexion sont différentes. Il y aura seulement 3 ou 4 choses différentes que je dois stocker concernant une région. Quelle structure de données devrais-je considérer ici (n'importe quel conteneur STL comme un vecteur?) Pourriez-vous en suggérer une? (apprécierait un extrait de code)

2. Pour accéder à une connexion entre les noeuds A-D, je veux utiliser int node_A (un index). Cela signifie probablement que j'ai besoin d'utiliser un hashmap ou une structure de données similaire. Quelqu'un peut-il s'il vous plaît suggérer une bonne structure de données en C++ qui peut efficacement contenir ce genre de données pour la connexion A -D décrite ci-dessus? (apprécierait un extrait de code)

merci!

MISE À JOUR pour certaines raisons, je ne peux pas utiliser pkgs comme coup de pouce. Voulez-vous savoir si je peux utiliser des bibliothèques de STL

Answer 1

Vous devriez essayer de regrouper les choses lorsque vous le pouvez. Vous pouvez regrouper les informations sur chaque région avec quelque chose comme ce qui suit:

class Region_Info { 
    Region *ptr; 
    int thickness; 
    // Put other properties here. 
}; 

Ensuite, vous pouvez créer plus facilement une structure de données pour votre segment de ligne, peut-être quelque chose comme ce qui suit:

class Line_Segment { 
    int node_A; 
    int node_D; 
    int crosssectional_area; 
    std::list<Region_Info>; 
}; 

Si vous êtes limité à seulement 20 régions, une liste devrait fonctionner correctement. Un vecteur est aussi bien si vous préférez.

Answer 2

Avez-vous pris en compte un tableau d'adjacence pour chaque nœud, qui stocke les nœuds auxquels il est connecté, ainsi que d'autres données?

D'abord, définir un noeud

class Node 
{ 
    int id_; 
    std::vector<AdjacencyInfo> adjacency_; 

} 

Lorsque la AdjacencyInfo de classe peut stocker les données myriade dont vous avez besoin. Vous pouvez remplacer le vecteur par un hashmap avec l'ID du noeud comme clé si la vitesse de recherche est un problème. Pour un accès sophistiqué, vous pouvez surcharger l'opérateur [] si c'est une exigence essentielle.

Ainsi, à titre d'exemple

class Graph 
{ 
    std::map<int, Node> graph_; 
} 

Answer 3

boost a une bibliothèque graphique: boost.graph. Vérifiez s'il est utile dans votre cas.

Answer 4

Eh bien, comme tout le monde l'a remarqué, c'est un graphique. La question est, est-ce un graphe clairsemé ou dense? Il y a généralement deux façons de graphiques représentant (plus, mais vous aurez besoin probablement de considérer ces deux):

• matrice contiguïté
• liste contiguïté

Une matrice de contiguïté est essentiellement un NxN matrice qui stocke tous les nœuds dans la première ligne et colonne, et les données de connexion (arêtes) comme des cellules, de sorte que vous pouvez indexer les arêtes par des sommets. Désolé si mon anglais est nul, pas ma langue maternelle. Quoi qu'il en soit, vous ne devriez considérer la matrice d'adjacence que si vous avez un graphe dense, et que vous avez besoin de trouver des connexions de nœud -> bord -> très rapidement. Cependant, itérer à travers les voisins ou ajouter/supprimer des sommets dans une matrice d'adjacence est lent, le premier nécessitant N itérations, et le second redimensionnant le tableau/vecteur que vous utilisez pour stocker la matrice.

Votre autre option consiste à utiliser une liste d'adjacence. Fondamentalement, vous avez une classe qui représente un nœud, et une qui représente un bord, qui stocke toutes les données pour ce bord, et deux pointeurs qui pointent vers les nœuds auxquels il est connecté. La classe de noeud a une collection de quelque sorte (une liste fera), et garde la trace de tous les bords auxquels elle est connectée. Ensuite, vous aurez besoin d'une classe de gestionnaire, ou tout simplement un tas de fonctions qui fonctionnent sur vos nœuds. L'ajout/la connexion de nœuds est trivial dans ce cas, car il s'agit d'une liste de voisins ou de bords connectés. Cependant, il est plus difficile d'itérer sur tous les bords. Cette structure est plus flexible que la matrice d'adjacence et c'est mieux pour les graphes clairsemés. Je ne suis pas sûr d'avoir entièrement compris votre question, mais si je l'ai fait, je pense que vous feriez mieux d'avoir une matrice d'adjacence, vous avez l'impression d'avoir un graphe dense avec beaucoup de nœuds interconnectés et seulement besoin de connexion Info.

Wikipédia a un bon article sur les graphiques en tant que structure de données, ainsi que de bonnes références et liens, et trouver des exemples ne devrait pas être difficile. J'espère que cela aide:
Link