Bonjour à tous,

Je cherche à modéliser un graph et j'ai choisi de stocker dans une list  list_Arrete des pointeurs qui pointent vers des list. Ces dernières contiennent l'ensemble des nœuds (leur identifiants en fait, mais peu importe) qui sont connectés à un nœud donnés.

Comme c'est pas très clair, voilà un exemple

Dans la 1er case de list_Arrete, il y a un pointeur qui pointe vers une autre liste contenant (2,3,5) par exemple. Cela veut dire que le nœud 1 est lié aux 2,3 et 5e nœud de mon graph.

La liste des nœuds est stockée un parallèle dans une autre list  list_Noeud. C'est un peu bizarre mais nécessaire dans le projet global.

Dans le code, j'ai une fonction get_voisins

list<int> get_voisins(int ID){
   k=find_index(ID); //trouve dans la liste list_Noeud la position du noeud avec l'ID voulu
   list<list<int>*>::iterator it = this->list_Arrete.begin();
   advance(it,k);
   return *(*it);
}

En théorie, *it donne le pointeur dans list_Arrete et donc **it devrait donner la liste pointé par ce pointeur.

Sauf que si la liste pointée (**it) n'est pas vide, mon programme ne marche pas. Il stoppe juste à l'appel de la fonction get_voisins.

Pour info, quand je crée un noeud avec ses arretes, je fais

void ajouter_noeud(int ID, list<int> listVoisin){
   Node* n(0);
   n = new Node(ID);

  this->list_Noeud.push_back(n);
  list<int>* LI(&listVoisin);
  this->list_Arrete.push_back(LI);
}

Voilà en gros où j'en suis. La gestion de synchronisation des deux listes est faites ailleurs, ça marche bien.

Le problème est que si lalistfournie lors de la création du nœud n'est pas vide, le programme s'arrete aquand j'appelle get_voisins (ça ne plante pas, juste que ça ne passe pas à la suite). Avez vous une idée de ce que je fais mal? Je suis assez nouveau en C++ et la gestion des pointeurs, et encore plus des pointeurs de pointeurs de list est assez dur.

D'avance merci

.
.

.

Une petite question supplémentaire mais qui pourrait m'aider

Quelle différence entre :

Type * nom(0);
nom = new Type(arg1,arg2 ...);

// et 

Type nom(arg1, arg2, ...);

-
Edité par Ezor 20 octobre 2017 à 14:47:23

Salut,

En théorie, un graph n'est qu'un ensemble de neuds, et le point de départ est également un neud. Donc tu ne devrais pas avoir à manipuler une liste au départ, cela montre qu'il te manque un noeud "racine".

Tes noeuds peuvent contenir n'importe quoi, tant qu'ils garantissent la descendance (ou ascendance) et la navigation entre les noeuds.

PS: oublie les pointeurs, c'est pire que jouer à la roulette russe avec 6 balles dans le barillet.

******* EDIT ******* 

Quelle différence entre :

Type * nom(0);
nom = new Type(arg1,arg2 ...);
 
// et 
 
Type nom(arg1, arg2, ...);

Dans le premier cas, nom est un pointeur et on n'a pas accès directement à l'objet pointé?

Dans le 1er cas, tu fais une allocation dynamique, la mémoire est allouée sur le tas.
Dans le second, la memoire est allouée sur la pile, et de façon automatique.

Outre la syntaxe qui change legerement lorsque l'on veut acceder au fonction ou données membre, les allocations dynamiques posent beaucoup de problèmes (exception, responsabilité, durée de vie ect ...) dont tu n'as probablement pas conscience à l'heure actuelle (faute de les avoir déja appris).
Tant que tu ne maitrisera pas les pointeurs et tout ce qu'ils impliquent, évite les.

-
Edité par Deedolith 20 octobre 2017 à 14:56:59

Merci pour ta réponse rapide.

Dans mon cas, je n'ai pas forcément de noeud, le graph peu être vide, donc pas de racine. Ou ne pas être connexe. En gros, les racines c'est pour les arbres, et moi je veux un graph.

Je sais que les pointeurs c'est galères, mais là je dois le faire comme ça. Une idée?

-
Edité par Ezor 20 octobre 2017 à 14:58:19

Ezor a écrit:

Merci pour ta réponse rapide.

Dans mon cas, je n'ai pas forcément de noeud, le graph peu être vide, donc pas de racine. Ou ne pas être connexe. En gros, les racines c'est pour les arbres, et moi je veux un graph.

Pour moi, arbre, graph, c'est la même chose, chaque noeud maintient en interne une liste de noeuds, et l'un comme l'autre peux être vide.
PS: La "racine" peut être purement fonctionnelle (ou virtuelle), et n'avoir de signification que pour la gestion interne du graph.
J'admet que mon interpretation peut differer de la tienne.

Ezor a écrit:

mais là je dois le faire comme ça.

disons que ça sera plus simple.

Mais je vais changer pour quelque chose de plus simple, avec des noeuds qui contiennent une liste d'identifiant (mais ça ne marche pas non plus, pourtant le code est bien plus simple )

Je pense que j'ai un problème avec les passages par valeurs / références qui fait que mes finctions restent pour le moment sans effet !

Pour les graph, effectiviement, j'avais plus en tête le concept mathématique de graph, et toi le coté info, où on peut effectivement définir une racine dans tous les cas.

-
Edité par Ezor 20 octobre 2017 à 16:32:34

Une solution classique pour représenter un graphe est la liste d'adjacence, concrètement on définit une identification unique pour chaque sommet si un sommet  d'identifiant x et un sommet d'identifiant y sont tels que x=y alors c'est le même sommet. Typiquement, ça revient à les numéroter, mais on peut imaginer d'autres méthodes d'identification qui respectent ce critère. Ensuite on définit la notion de successeur direct en disant que y est successeur direct de x si il existe une arrête du graphe qui va de x à y. Pour représenter notre graphe il suffit alors de construire une liste de paires, le premier élément de la paire est un sommet du graphe, le second est la liste des identifiants de ses successeurs directs. En identifiant les sommets par un numéro on va former une structure assez simple:

Chaque sommet sera représenté par un std::pair<int,std::list<int>> et on pourra représenter le graphe complet au moyen d'un conteneur associatif comme par exemple un std::map<int,std::list<int>>. Avec ce type de représentation on voit plusieurs avantages:

• C'est plutôt facile à parcourir
• C'est plutôt facile à construire
• C'est plutôt facile à maintenir
• On n'a pas besoin de se traîner des pointeurs avec toute la panoplie de problèmes qu'ils ne manqueront pas d'engendrer.

Ces avantages vont faire qu'on va pouvoir se focaliser sur les algorithmes, plutôt que sur de la vulgaire gestion de la mémoire.

Il y a un autre avantage non négligeable, on peut assez facilement l'abstraire, ce qui va permettre de changer assez facilement la représentation interne du graphe pour permettre d'implanter facilement des optimisations, sans changer les algorithmes de traitement, cet aspect va également permettre facilement de travailler sur des graphes valués avec un minimum de modifications.

merci pour cette réponse très complète. Ça semble être une bonne solution vu comme ça. Je vais tester ça au plus vite (dès que j'aurai réglé ce problème qui fait que mes fonctions n'ont pas d'effet :(  . Je 'y perd).

-
Edité par Ezor 23 octobre 2017 à 10:56:31