Discussion :

[razonback]

Bonjour,

Pour être direct, voila mon code :

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
17
18
19
20
21
22
23
24
25
26
27
28
 
 
void Foret ::CrossOver(int arb1, int arb2)
{
    cout << __func__<<endl;
    if( arb1 < this->bois.size() && arb2 < this->bois.size() )
    {
	Arbre * tmp1 = new Arbre;
	Arbre * tmp2 = new Arbre;
 
	tmp1 = RetourneBranche(arb1);
	tmp2 = RetourneBranche(arb2);
 
	if( tmp1 != NULL && tmp2 != NULL)
	{
	    Arbre * temp = new Arbre;
	    temp = NULL;
 
	    temp = tmp1;
	    tmp1 = tmp2;
	    tmp2 = temp;
 
	    temp = NULL;
	    delete temp;
	}
    }
    cout << "Fin " << __func__<<endl;
}

En gros, j'ai deux arbres et je voudrais qu'il se croise, c'est à dire qu'une branche de l'un devienne une branche de l'autre et inversement.
Ce que je fais marche, car quand j'affiche les pointeurs, et les attributs de mes branches, elles sont bien inversés. Mais je ne sais pas pourquoi, elles ne sont pas changés lorsque j'affiche leurs arbres.
Si vous pouviez m'éclairer...

[Invité]

Bonjour,
Je n'ai pas très bien compris votre code.
Les paramètres de la fonction (arb1 et arb2) sont des int. probablement le diamètre des branches des 2 arbres à échanger éventuellement. Mais, à quels arbres appartiennent-elles?
D'autre part, vous initialisez des pointeurs sur Arbre avec new, et vous les modifiez immédiatement après.
Dans les 2 premiers cas il ne faut pas créer un nouvel objet avec new, puisqu'ils sont censés exister, mais il faut le tester, dans le second cas vous initialisez 3 fois en suivant temp, il y en 2 de trop.

[Steph_ng8]

Tu ne sembles pas avoir bien compris ce que sont les pointeurs.
Je te conseille de bien revoir tout ça, en C s'il le faut.
http://c.developpez.com/faq/?page=pointeurs

Pour commencer, on n'utilise l'opérateur « new » que lorsqu'on a besoin d'allouer de la mémoire pour un nouvel objet, donc qui n'existe pas encore.
Là, ce n'est pas visiblement pas le cas.
Donc retire les initialisations de tes pointeurs.

Code :

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

1
2
Arbre * tmp1 = RetourneBranche(arb1);
Arbre * tmp2 = RetourneBranche(arb2);

Ensuite, étant donné que tu travailles avec des variables locales, l'échange que tu fais n'est effectif que localement à la fonction.
Alors oui, quand tu affiches les pointeurs locaux, les valeurs sont échangées, mais comme ce ne sont que des copies, dès que l'on sort de la fonction les modification ne sont pas répercutées.

Si la classe Arbre dispose d'un constructeur par recopie et un opérateur d'affectation corrects (voir http://cpp.developpez.com/faq/cpp/?p...GE_affectation), ceci fonctionnera en dehors de la fonction :

Code :

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

1
2
3
Arbre temp = *tmp1;
*tmp1 = *tmp2;
*tmp2 = temp;

ou encore mieux :

Code :

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

1
2
3
4
5
#include <algorithm>
 
(...) 
 
std::swap(*tmp1, *tmp2);

Cette fois, ce sont bien les objets, et non pas leurs adresses qui sont échangées.
Mais étant donné qu'il y a duplication des objets, cela peut poser des problèmes...

Il faudrait que tu donnes plus de détails sur tes arbres, la manière dont ils sont stockés dans la forêt, etc.

Et puis, d'après ce que j'ai compris de ton code, il échange deux arbres, et non pas les branches de deux arbres...

[Chessmaster1966]

Bonjour,

Pour être direct, voila mon code :

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
17
18
19
20
21
22
23
24
25
26
27
28
 
 
void Foret ::CrossOver(int arb1, int arb2)
{
    cout << __func__<<endl;
    if( arb1 < this->bois.size() && arb2 < this->bois.size() )
    {
    Arbre * tmp1 = new Arbre;
    Arbre * tmp2 = new Arbre;
 
    tmp1 = RetourneBranche(arb1);
    tmp2 = RetourneBranche(arb2);
 
    if( tmp1 != NULL && tmp2 != NULL)
    {
        Arbre * temp = new Arbre;
        temp = NULL;
 
        temp = tmp1;
        tmp1 = tmp2;
        tmp2 = temp;
 
        temp = NULL;
        delete temp;
    }
    }
    cout << "Fin " << __func__<<endl;
}

En gros, j'ai deux arbres et je voudrais qu'il se croise, c'est à dire qu'une branche de l'un devienne une branche de l'autre et inversement.
Ce que je fais marche, car quand j'affiche les pointeurs, et les attributs de mes branches, elles sont bien inversés. Mais je ne sais pas pourquoi, elles ne sont pas changés lorsque j'affiche leurs arbres.
Si vous pouviez m'éclairer...

Ton code fait n'importe quoi !

1) Si tu veux échanger seulement les branches pourquoi échanges-tu des arbres.
2) Tu crées deux pointeurs que tu effaces immédiatement après.
3) Si ta fonction 'RetourneBranche' retourne un arbre ce n'est pas logique, elle doit retourner la branche spécifique de l'arbre que tu as passé en paramètre et en plus tu ne précises pas quelle branche tu veux échanger à moins que cela soit fait de façon aléatoire.
4) Tu passes en paramètre de "CrossOver" des int alors que cela doit être des "Arbre*"

Conclusion : Tu veux intervertir deux branches de deux arbres mais ce sont les arbres que tu échanges !

Mais si j'ai bien compris ton message de détresse tu veux seulement intervertir les branches de deux arbres alors je pense que le code que je te propose fait cela (il te restera à l'améliorer) :

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
17
18
19
20
21
22
23
 
void Foret ::CrossOver(Arbre* arb1, Arbre* arb2)
{
    cout << __func__<<endl;
    if( arb1->size() < this->bois.size() && arb2->size() < this->bois.size() )
    {
         Branche BrancheArbre1 = RetourneBranche(arb1);
            Branche BrancheArbre2 = RetourneBranche(arb2);
 
            //*** Inversion des branches. ***
 
            //La branche de l'arbre 1 devient la branche de l'arbre 2
            arb1->SupprimeBranche(BrancheArbre1);
            arb1->AjouteBranche(BrancheArbre2);
 
            //La branche de l'arbre 2 devient la branche de l'arbre 1
            arb2->SupprimeBranche(BrancheArbre2);
            arb2->AjouteBranche(BrancheArbre1);     
 
    }
    cout << "Fin " << __func__<<endl;
 
}

[razonback]

Bonjour,

Bon tout d'abord et heureusement pour moi, mon code ne fait pas n'importe quoi. La seul chose ou je suis le roi des c...ns !!! est cette allocation de m...de. Pourquoi ai je fais cela ?!?! ( je me suis déjà flagellé )

Pour ce qui est du reste vous n'avez pas trop compris la structure de mon arbre.
En fait comme un arbre peut être de hauteur 1 (juste la racine) à n, un arbre n'est qu'un ensemble d'autre arbre plus petit.

Ma création est donc récursive et je ne crée pas de d'objet de classe branche puisque je n'en ai pas, ce sont des arbres.

Voila aussi pourquoi ma fonction branche retourne un arbre. Les paramètre arb1 et arb2 ne sont que les hauteurs de la branche/ l'arbre à retourner. Mais comme c'est une branche aléatoire ... j'ai préféré ne pas mettre le code et expliquer la fonction - j'aurais du- .

Au passage la forêt est un vecteur (vector) d'arbre.

Voila je crois avoir tout expliquer.

Merci en tout cas de m'avoir répondu et surtout ouvert les YEUX !

[Chessmaster1966]

Bon tout d'abord et heureusement pour moi, mon code ne fait pas n'importe quoi.

Excuse moi, j'y suis allé peut-être un peu fort.

Pour ce qui est du reste vous n'avez pas trop compris la structure de mon arbre.

J'ai compris ce qui avait à comprendre selon le peu de code et d'explication que tu as fournit.

En fait comme un arbre peut être de hauteur 1 (juste la racine) à n, un arbre n'est qu'un ensemble d'autre arbre plus petit.

Fallait-il encore le savoir !

Ma création est donc récursive et je ne crée pas de d'objet de classe branche puisque je n'en ai pas, ce sont des arbres.

Ta logique est un peu déroutante !
Tu utilises une fonction "RetourneBranche" en passant une hauteur d'arbre en argument, là Ok mais tu retournes un arbre au lieu d'une branche j'ai du mal à comprendre. Il faut nommer ses fonctions correctement. Pour moi une fonction nommée "RetourneBranche" retourne effectivement un objet "Branche".

Voila aussi pourquoi ma fonction branche retourne un arbre. Les paramètre arb1 et arb2 ne sont que les hauteurs de la branche/ l'arbre à retourner. Mais comme c'est une branche aléatoire ... j'ai préféré ne pas mettre le code et expliquer la fonction - j'aurais du- .

Pour ce qui des hauteurs d'arbre appelle un chat un chat !
Nommes tes paramètres "HauteurArbre1" par exemple cela sera plus facile à maintenir et surtout pour toi quand quelque mois plus tard du devras revoir ton code.

Au passage la forêt est un vecteur (vector) d'arbre.

Ok...une collection d'arbres.

As-tu, aujourd'hui, résolu ton problème ?

[Chessmaster1966]

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
void Foret ::CrossOver(int arb1, int arb2)
{
    cout << __func__<<endl;
    if( arb1 < this->bois.size() && arb2 < this->bois.size() )
    {
    //Effectivement ici pas d'allocation, juste la déclaration
    //des objets tmp1 et tmp2.
    Arbre * tmp1 = new Arbre;
    Arbre * tmp2 = new Arbre;
 
    //Parce que ici tu écrases les deux pointeurs sans les détruire.
    //Donc une allocation qui ne sert à rien et ralentit le système
    //surtout dans les jeux comme le tient.
 
    //Donc tu utilises la hauteur d'un arbre pour retourner l'ardre en question
    //en lui sélectionant une branche de façon aléatoire et tu stockes
    //les arbres en question respectivement dans tmp1 et tmp2.
    tmp1 = RetourneBranche(arb1);
    tmp2 = RetourneBranche(arb2);
 
    if( tmp1 != NULL && tmp2 != NULL)
    {
        //Tu fais une inversion...Ok
 
        //Là encore une allocation inutile !
        Arbre * temp = new Arbre;
        //Puisque ici tu écrases le pointeur en lui affectant 0.
        temp = NULL;
 
        temp = tmp1;
        tmp1 = tmp2;
        tmp2 = temp;
 
        temp = NULL;
 
        //???,pourquoi supprimes-tu tmp que tu à mis à 0 ?
        delete temp;
 
        //Mais après avoir fait l'inversion tu ne fait rien de tmp1 et tmp2, 
        //j'aimerai comprendre.
 
        //Donnes moi plus d'éléments parce avec ce petit bout de code et des explications je trouves
        //à mon niveau ton code un peu bizarre !!!
    }
    }
    cout << "Fin " << __func__<<endl;
}

[razonback]

Je vais essayer d'être clair et de répondre à toutes tes questions.
Déjà oui ça marche, et au passage merci à Steph_ng8 pour la fonction

Code :

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

swap(*tmp1,*tmp2);

Je ne la connaissais pas.

Ensuite, le code final est donc le suivant, avec en prime la fonction RetourneBranche :

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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
void Foret ::CrossOver(unsigned int arb1,unsigned  int arb2)
{
    cout << __func__<<endl;
    if( arb1 < this->bois.size() && arb2 < this->bois.size() )
    {
	Arbre * tmp1;
	Arbre * tmp2;
 
	tmp1 = RetourneBranche(arb1);
	tmp2 = RetourneBranche(arb2);
 
	if( tmp1 != NULL && tmp2 != NULL)
	{
	    qDebug() << tmp1;
	    swap(*tmp1,*tmp2);
	}
    }
    cout << "Fin " << __func__<<endl;
}
 
 
Arbre * Foret ::RetourneBranche(unsigned int cas)
{
    cout << __func__<< endl;
    int level = rand()%this->bois[cas]->hauteur + 1;
    int enf = 0, cpt = 0;
 
    Arbre* tmp;
    tmp = this->bois[cas];
 
    while(tmp->nb_children != 0 && cpt < level)
    {
	enf = rand()%(tmp->nb_children);
	tmp = tmp->enfants[enf];
	cpt++;
    }
 
    tmp->Affiche();
    cout << __func__<<endl;
    return tmp;
}

En fait, mes variables arb1 et arb2 sont les numéros des arbres de ma collection d'arbre ou forêt. Je m'excuse d'ailleurs car j'avais dit que c'étaient des hauteurs, chose absurde pour mon programme.

Comme tu peux le voir dans ma fonction RetourneBranche(int arbre1), elle renvoie un sous "arbre" présent dans mon arbre arbre1 (paramètre de ma fonction).
Je l'ai appelé de cette manière car elle retourne une "branche" de mon arbre complet, mais c'est tout de même un arbre.
Tu seras d'accord avec moi si je te dis qu'un arbre de hauteur n, c'est aussi 2 arbres de hauteur n/2 mis bout à bout, etc... C'est plus simple de le créer de manière récursive, d'où cette méthode.

Et ensuite pour le plus de précision sur ce que j'en fait, je n'en ai pas vraiment puisque je ne fait rien d'autre avec. Je prends juste 2 branches et je les intervertis.

Voila ce que je peux dire. Si tu as d'autres questions car je me suis mal expliqué, ce qui est fort possible!!, n'hésite pas.
Et merci pour tes réponses.

[Steph_ng8]

Petites précisions concernant l'emploi de std::swap.

Le code de cette fonction est quelque chose comme ça :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
#include <algorithm>
 
namespace std
{
    template <typename T>
    void swap(T& a, T& b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }
}

Autrement dit, elle utilise le constructeur par recopie (une fois) et l'opérateur d'affectation (deux fois) (et une fois le destructeur…).
Ce qui veut dire que la classe doit être assignable.
C'est pour cela que je disais qu'il y a duplication des objets.

Mais rien n'empêche de redéfinir cette fonction d'échange pour ses propres besoins :

Code :

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

1
2
3
4
5
6
7
8
namespace std
{
    void swap(UnType& a, UnType& b)
    {
        // Le code qui va bien…
        (...)
    }
}

En fait, je ne suis pas totalement sûr qu'il soit nécessaire de la définir dans l'espace de nom std, surtout si on n'utilise pas le comportement par défaut.

Une convention, du moins utilisée pour les conteneurs, est de définir une fonction membre swap qui fait l'échange entre l'objet lié et celui passé en paramètre ; la fonction non-membre se contente alors d'appeler cette fonction membre.

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
void UnType::swap(UnType& x)
{
    // Le code qui va bien…
    (...)
}
 
//*****************//
 
namespace std
{
    void swap(UnType& a, UnType& b)
    {
        return a.swap(b);
    }
}

[Steph_ng8]

Il est vrai que la manière la plus simple de représenter un arbre est de le faire de manière récursive, en le voyant comme une racine et un ensemble de sous-arbres (éventuellement vide).

Par contre, pour moi une branche c'est en quelque sorte un chemin entre la racine et une feuille particulière.
Bon, on peut être plus souple et ne pas partir de la racine et/ou ne pas s'arrêter à une feuille.
Disons un chemin entre deux nœuds.
Alors on peut effectivement considérer qu'une branche est un arbre, mais un arbre unaire ; autrement dit, une liste…

Du coup, je vois mal comment on peut échanger des branches de deux arbres différents.
Tu es sûr que ce ne sont pas des sous-arbres que tu veux échanger ?
D'après ton dernier code, c'est l'impression que j'ai, en tout cas…

[razonback]

Bah si, mais comme pour moi des branches sont des sous-arbres...
En gros, on ne voit pas la branche de la même façon, c'est tout.

[Invité]

Bonjour,
On n'est pas vraiment sur un site d'agriculture, donc, les termes employés ont bien souvent un caractère de comparaison, exclusivement.
En matière de listes, il y a deux types principaux
1- les arborescences univoques: un objet peut avoir plusieurs descendants, et un objet qulconque ne peut avoir qu'un seul ascendant direct
2- les graphes, un objet peut avoir plusieurs descendants ET plusieurs ascendants.
Donc, que représente votre problème? Autrement dit que cherchez-vous à faire?

[razonback]

Rien, le topic est résolu.
Et personnellement, jamais entendu arbres univoques... Plutôt ABR (arbres binaires de recherches ) ou d'autres structures dans le genre

[Joel F]

En fait, je ne suis pas totalement sûr qu'il soit nécessaire de la définir dans l'espace de nom std, surtout si on n'utilise pas le comportement par défaut.

la mettre dans le namespace des objets swappé suffit pour y accéder par ADL.

[Steph_ng8]

ADL ???

[Goten]

Koenig's lookup ou Argument dependant lookup.

Ce qui fait que

std::cout << "foo";

compile.

[Steph_ng8]

...

[Goten]

L'opérateur est trouvé par ADL ... Si y'avait pas alors le compilo te dirait que y'a pas d'opérateur << compatible dans le namespace globale..

[Steph_ng8]

Hum… Ok…

[3DArchi]

Cf ici : Argument-dependent name lookup
Imagine ce code :

Code :

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

1
2
3
4
5
6
7
8
9
10
namespace mon_ns
{
   void fonction(int){}
}
 
int main()
{
   fonction(0);
   return 0;
}

Ce code ne compile pas car fonction est définie dans l'espace de nom mon_ns et il n'existe pas de fonction dans l'espace de nom global. Tu es obligé de préciser comme suit :

Code :

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

1
2
3
4
5
6
7
8
9
10
namespace mon_ns
{
   void fonction(int){}
}
 
int main()
{
   mon_ns::fonction(0);
   return 0;
}

Maintenant changeons un peu le code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
namespace mon_ns
{
   struct my_struct
   {};
   void fonction(my_struct){}
}
 
int main()
{
   fonction(mon_ns::my_struct());
   return 0;
}

Ça compile ? Ça compile pas ? Magique ! Ça compile ! Pourquoi ? Grâce au Argument-dependent name lookup (ou Koenig lookup). L'idée est de dire que lorsque le compilateur cherche la fonction fonction, il la cherche non seulement dans l'espace de nom courant (le premier cas) mais il injecte aussi l'espace de nom des arguments. Ce qui fait que l'on peut appeler fonction(mon_ns::my_struct()) sans préciser que fonction est dans l'espace de nom mon_ns.

C'est comme l'indique Goten grâce à ce principe que la ligne std::cout<<"truc"; compile alors que l'opérateur << est défini dans l'espace de nom std. Sans ce principe, on aurait du écrire : std::operator<<(std::cout,"truc") Bien moins sexy