Discussion :

[azamharir]

salut
je dois implementer un graphe (graphe : cas général). je cherche la meilleure structure possible.
je crois que je vais utiliser celle ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
une classe noeud
{
    contient l'information du noeud (nom ...)
    un suivant de type poids* (en fait c'est une liste de poids* et suivant est 
    la tete de cette liste)
}
 
une classe poids
{
    contient un le cout ou poids (un entier ou float ..., c'est le poids d'une 
    arete)
    un frere de type poids* (en fait c'est une liste de poids* qui partent du 
    meme noeud)
    un suivant de type noeud* (c'est le noeud d'arrivée de l'arete qui possede 
    ce poids)
}

que pensez vous de cette démarche?
j'attends vos remarques, merci et à bientot

[loufoque]

boost::graph

[azamharir]

merci loufoque,
mais je prefere le programmer moi meme. en plus, c'est pour un gros graphe (reseau routiers, ... c'est des graphes à l'echelle des villes). En plus, j'ai des algorithmes à appliquer et je dois jongler entre la ram et le disque pour ne pas saturer la mémoire.
donc, utiliser boost (je crois) n'est pas une solution pour moi.
merci, et si tu as d'autres conseils, je suis preneur. @++

[Kujara]

Pas d'accord pour le coup de la liste.
Si tu a tendance a etre limité par la ram, utilise plutot un tableau de base( la liste stoque des pointeurs de plus). Par contre tu y perds grandement si tu a besoin de rajouter / enlever des noeuds.
Mais bon, si c'est pour une carte routiere,ce n'est clairement pas le cas...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
struct Node;
struct Link
{
float poids;
Node * node;
};
 
struct Node
{
Link * links;
unsigned int numLinks;
//suivit des infos supplementaires par node.
};

Remplace les links par un std::vector si tu veux, mais tu va y perdre en mémoire, pour y gagner en facilité de code ( de peu). A toi de voir.

[zais_ethael]

Remplace les links par un std::vector si tu veux, mais tu va y perdre en mémoire, pour y gagner en facilité de code ( de peu). A toi de voir.

Serais-ce une vile tentative pour inciter aux mauvaises techniques de programmation?? Tu te rends compte du faible nombre d'informations supplémentaires que rajoute un std::vector par rapport à un tableau C-style? A priori, ça rajoute uniquement un size_t (et pas un unsigned int) pour indiquer la capacité qui est d'ailleurs bien utile pour l'optimisation vitesse.

[Kujara]

Serais-ce une vile tentative pour inciter aux mauvaises techniques de programmation?? Tu te rends compte du faible nombre d'informations supplémentaires que rajoute un std::vector par rapport à un tableau C-style? A priori, ça rajoute uniquement un size_t (et pas un unsigned int) pour indiquer la capacité qui est d'ailleurs bien utile pour l'optimisation vitesse.

"sizeof(vector<int>)" 16, contre 8 pour un tableau de base + taille.
Quand on est limité par la mémoire, ça compte,surtout pour des tableaux de faible taille, genre 2 ou 3 elements, comme on risque de voir ici.

Quand au size_t, apprends que c'est soit un unsigned int, soit un unsigned __int64.

la version 64 se justifie uniquement sur architecture 64, où justement, unsigned int vaut lui aussi unsigned __int64.

Donc, j'utilise unsigned int.