Aide au design d'une classe Graph souple et extensible

Bonjour, ce fil fait suite à un précédent fil intitulé Héritage, template, généralisation et particularisation. Comment s'organiser proprement ? et concerne peu ou prou la même thématique au travers d'un exemple (cf titre).

Dans ce premier post, je pose quelques définitions afin qu'on essaie de parler le même langage.

Un graphe (type Graph) est une collection de noeuds (type Node).
Un noeud est la composition d'une Valeur(type Val) et d'une collection de liens vers d'autres noeuds.
Un lien (type Link) pointe vers un noeud et peu comporter un drapeau (type Flag).

Un graphe doit pouvoir être parcouru :
- via les liens, en largeur (type BFiterator) , en profondeur (type DFiterator).
- transversalement (type Titerator).
- autrement...

J'aimerais organiser le choses de manière à ce que ce type Graph offre facilement la possibilité de faire a peu près tout ce qu'on peut imaginer faire sur un graphe.

N.B. : Je n'attends (surtout) pas que vous me donniez une réponse toute cuite, je cherche à élaborer une méthode. J'attends des critiques, des objections, et des conseils méthodiques.

Bon, tout d'abord, il faut distinguer les types paramètres des types a implémenter.

Les types paramètres : Val et Flag.
Tous les autres sont à implémenter.

Dans l'idéal, le type Node ne dépend que de Val et le type Link que de Flag.
Toujours dans l'idéal, ces considérations devraient êtres transparentes pour le Graph, seulement les Itérateurs devraient s'en soucier.

Organisation 1
Si je reste sur ce point de vue il me semble logique d'avoir quelque chose comme ca (je ne mets que des 'déclarations').

Code:

---

1 2 3 4 5 6 7 8

class Node_ ; class Link_ ; template<class Val> class Node : public Node_ { Val val; collection_de(Link_*);} template <> class Node<void> : public Node_ {collection_de(Link*_);} template<class Flag> class Link : public Link_{ Flag flag ; Node_* pointedNode; } template<> class Link<void> : public Link_ {Node_* pointedNode;} class Graph{collection_de(Node_*)};

---

Ca m'a l'air d'être l'organisation la plus 'générale' mais j'ai plusieurs problèmes avec ça (certainement liés à ma connaissance partielle du langage) :
P1) Le graphe aura certainement besoin d'accès aux valeurs et au flags mais par contre n'aura accès qu'à l'interface de Node_ et Link_ qui elles n'ont pas accès au flags et valeurs...
P2) 'Beaucoup' d'héritage mais si cette question ne porte que sur un problème de performance, disons que je suis prêt à passer l'éponge.

Tentative de résolution de P1

Se résoudre à ce que Graph ne soit pas si indépendant que ca de Flag et Val.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

template<Val> struct Node_ { typedef Val::valtype valtype; virtual valtype getValue() const = 0; }; //+ Des tas de spécialisations eurk   template<Flag> struct Link_ { typedef Flag::flagtype flagtype; virtual flagtype getFlag() const = 0; }; //+ Re Eurk   template<class Val, class Flag> class Node : public Node_<Val> { Val val; collection_de(Link_<Flag>*); public : valtype getValue() const; }; /* Mega Re Eurk /* template <class Flag> class Node<void> : public Node_ {collection_de(Link_<Flag>*);} */   /* Traitement du même genre pour l'ex class Link */ template<class Val, class Flag> class Graph{collection_de(Node_<Val,Flag>*)};

---

Maintenant la dépendance est trop forte... tout a l'heure l'utilisateur pouvait mettre n'importe quels types Val et Flag dans un même graphe mais le graphe ne pouvait avoir accès ni aux valeurs ni aux flags.
Maintenant le graphe a accès aux valeurs et aux flags mais l'utilisateur ne peut mettre à la fois qu'un seul type Val et Flag.

Je vais relire Présentation des classes de Traits et de Politiques en C++ et voir si je trouve mieux.

Ok, j crois que j'ai un truc.... je montre juste pour Node parce que c'est déjà assez tordu comme ca (a mon gout).

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

template<class T> struct typeinfo { // Fournit des types typedef T type; const static T TypicVal = T(); }; //+ spécialisations   template<class T> struct virtualget { // *Fournit une fonction virtuelle à Node_ pour le type T. protected : virtual typeinfo<T>::type getVal(const typeinfo<T>::type&) {return typeinfo::TypicVal;} //histoire que la fonction ne soit pas pure, }; //le mieux serait peut etre que cette fonction provoque une erreur a l'execution... // le parametre de getVal est 'fictif', seulement utile pour la sélection de la surcharge.     template<int n, class T, class ...Args> struct typerval : public typerval<n-1,Args...> {}; //structure vide tant que le parametre int n'est pas nul template<class T, class ...Args> struct typerval<0, T, Args...> : public typeinfo<T> {typedef typeinfo<T>::type valuetype;} // Quand le parametre int est nul, on place un typedef sur le n-ieme type   template<class... Args> class Node_; // pré déclaration de Node_ template<> class Node_<> {}; // cas de zéro paramètres template<class T, class ... Args> class Node_ : public virtualget<T>, Node_<Args...> {}; //Dote Node_ d'une fonction virtuelle non pure (voir *) pour chaque type possible.   template class Node<int n, class... Args); // pré déclaration de Node template<> class Node<int n> : public Node_<> {} // Cas d'aucun type. template<int n, class T, class ... Args> class Node : public Node_<T, Args...>, typerval<n,T, Args...> {private : valuetype val; protected : valuetype getval() const {return getValue(val);}}; //

---

L'idée étant que graph maintienne une collection de Node_<Type0,Type1,Type2>* dont chaque Node<0, Type0, Type1, Type2>, Node<1,Type0,Type1,Type2>, Node<2,Type0,Type1,Type2> dérive avec sa propre surcharge valide de getVal.
Je dois dire que la simple idée de rajouter les flags me donne envie de pleurer :ptdr:

Puisqu'il est question de méthode, j'ai l'impression de m'en éloigner avec les deux posts précédents...
Peut-être qu'après avoir séparé les types paramètres et les types à implémenter vaut-il mieux se demander à qui appartient quoi ?
Il semble évident que si l'on parle des objets, un graphe possède des noeuds qui eux même ont des liens.

Mais lorsqu'on parle des types ?
Quels types possèdent quels autres ?
Qu'est ce que çà peut bien signifier d'ailleurs ?

En terme de code, la relation de possession à l'air de s'exprimer assez clairement...
un type possède tous ses membres statiques.

Code:

---

1 2 3 4 5 6

class A { // Le type A : static int unEntierA = 0; // - possède la variable unEntierA int unEntierB; // - ne possède pas unEntierB, propriété d'un objet de type A. class B{}; // - possède le type B };

---

La question précédente reste entière... si vous avez des idées sur comment déterminer qu'un certain type doit (ou pas) appartenir à un autre, je suis plus que preneur.

Citation:

---

Envoyé par BaygonV

Organisation 1
Si je reste sur ce point de vue il me semble logique d'avoir quelque chose comme ca (je ne mets que des 'déclarations').

Code:

---

1 2 3 4 5 6 7 8

class Node_ ; class Link_ ; template<class Val> class Node : public Node_ { Val val; collection_de(Link_*);} template <> class Node<void> : public Node_ {collection_de(Link*_);} template<class Flag> class Link : public Link_{ Flag flag ; Node_* pointedNode; } template<> class Link<void> : public Link_ {Node_* pointedNode;} class Graph{collection_de(Node_*)};

---

P2) 'Beaucoup' d'héritage mais si cette question ne porte que sur un problème de performance, disons que je suis prêt à passer l'éponge.

---

Ce n'est pas vraiment une question de performance, à quoi sert l'héritage ici ? (cf mon post précédent sur ton ancien thread).
Peux-tu le justifier ?

Citation:

---

Envoyé par BaygonV

Code:

---

1 2 3 4

virtual typeinfo<T>::type getVal(const typeinfo<T>::type&) {return typeinfo::TypicVal;} //histoire que la fonction ne soit pas pure, }; //le mieux serait peut etre que cette fonction provoque une erreur a l'execution... // le parametre de getVal est 'fictif', seulement utile pour la sélection de la surcharge.

---

---

Pour avoir une fonction virtuelle non pure, mais sans réelle implémentation, tu peux faire

Code:

---

1 2	virtual typeinfo<T>::type getVal(const typeinfo<T>::type&) const { throw 1; } // ou n'importe quel type d'exception, // attention à la cont-correctness aussi, un getter se doit d'être const

---

Mais si la méthode n'a pas d'implémentation, alors elle doit etre virtuelle pure.

edit : oui, je n'aime pas l'héritage, et je m'assure que ce soit la meilleure solution avant de l'utiliser à chaque fois.

Oui, il me semble que je peux justifier l'héritage :
Comme tu le dis dans ta réponse :

Citation:

---

Envoyé par Iradrille

L'héritage serait utile seulement si tu as besoin d'avoir un graphe avec des noeuds différents dans le même graphe.

---

Or ici oui, je veux pouvoir mettre des noeuds de types différents (ou pas) dans mon graphe.
J'ai dans l'idée que cette classe Graph puisse être utilisée pour construire... un AST par exemple ? Il me semble que dans ce cas là on peut bien s'attendre à ce qu'il y ait des objets de plusieurs types dans le graphe mais effectivement tous les types que l'on peut introduire dans le graphe sont connus a la compilation.

Tu confonds les données que va porter le graphe et la représentation du graphe en lui-même. C'est exactement pareil pour les conteneurs de la STL, les std::vector ne s'occupe pas des données qu'ils contiennent, et si l'utilisateur veut stocker des données hétérogènes, c'est son problème. Ce n'est pas dans la représentation du graphe que tu dois réaliser le type erasure mais dans les données elles-mêmes. Si tu veux qu'un noeud ait plusieurs types alors tu feras une classe de base et les données que transporteront le noeud hériteront de cette classe. Voir aussi Boost.Variant si une relation d'héritage n'est pas utile.

Ok, donc je ne met un seul type de valeur de noeud et un seul type de flag et je laisse l'utilisateur se débrouiller ?
J'ai l'impression que c'est moins pratique (pour l'utilisateur) mais je vais y réfléchir.

En attendant, j'ai passé un moment à faire des factorisations et pondre ce chef d oeuvre ;

Code:

---

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 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104

/////////////////////////////////////////////////////////////////// template<typename T, typename U> // struct is_same : std::false_type { }; // Teste // l'égalité de deux types template<typename T> // struct is_same<T, T> : std::true_type { }; // // template<typename T, typename U> // constexpr bool eqTypes() { return is_same<T, U>::value; } // /////////////////////////////////////////////////////////////////// // template<class T> struct typeinfo { //Un type info rudimentaire... typedef T type; // static const T typic = T(); // }; // /////////////////////////////////////////////////////////////////// // template<class... Arg> struct CountArg; // // Compte les arguments du template template<class T, class... Arg> struct CountArg<T,Arg...> // { // static const int count = 1+CountArg<Arg...>::count; // }; // // template<> struct CountArg<> // { // static const int count = 0; // }; // /////////////////////////////////////////////////////////////////// // template<class... Arg> struct type_vector; // Un vecteur de types template<> struct type_vector<> {}; // // template<class T, class... Arg> struct type_vector { // typedef T type; // typedef type_vector<Arg...> next; // typedef type_vector<T,Arg...> begin; // typedef type_vector<> end; // }; // /////////////////////////////////////////////////////////////////// // template<int n, class v> struct selector { // Selectionne le type situé à l'index n dans le vecteur v typedef selector<n-1,v::next>::at at; // typedef at::next next; // typedef v::end end; // typedef selector<n-1,v::next>::type type; // }; // template<class v> struct selector<0,v> { // typedef v::begin at; // typedef v::end end; // typedef v::type type; // typedef v::next next; // }; // /////////////////////////////////////////////////////////////////// template<int n, class v> struct slicer { // Découpe un vecteur en deux vecteurs à l'indice n typedef struct { // typedef v::type type; // typedef v::begin begin; // typedef v::next next; // typedef selector<n,v>::at end; // } first ; // typedef struct { // typedef selector<n,v>::type type; // typedef selector<n,v>::at begin; // typedef selector<n,v>::next next; // typedef v::end end; // } second ; // }; // //////////////////////////////////////////////////////////////////////////////////////////////////// // template<int n, class... Arg> class Graph { // //////////////////////////////////////////////////////////////////////////////////////////////////// typedef slicer<n,typevector<Arg...>>::first NodeTypes ; // Vecteur de types de Valeurs // typedef slicer<n,typevector<Arg...>>::second FlagTypes ; // Vecteur de types de Flags // //////////////////////////////////////////////////////////////////////////////////////////////////// /* //   * Générateur de classe de base //   */ // // // template <class v, template<class> class I, bool f = eqTypes<v::begin,v::end>()> class base_gen : // public base_gen< v::begin::next, I , eqTypes<v::begin::next, v::end>()>, I<v> {}; // template<class v, template<class> class I> class base_gen<v,I,false> {}; // //////////////////////////////////////////////////////////////////////////////////////////////////// /* Dispatche les fonctions virtuelles pour la future Node_ */ // template<class v> class base_node_disp { // public : // virtual typename v::begin::type getVal(const typename v::begin::type & t) const {throw 1;} // virtual void setVal(const typename v::begin::type & t) const {throw 1;} // }; // //////////////////////////////////////////////////////////////////////////////////////////////////// /* Dispatche les fonctions virtuelles pour la future Link_ */ // template<class v> class base_link_disp { // public : // virtual typename v::begin::type getFlag(const typename v::begin::type & t) const {throw 1;} // virtual void setFlag(const typename v::begin::type & t) const {throw 1;} // }; // ////////////////////////////////////////////////////////////////////////////////////////////////////                                                                                                 typedef base_gen<NodeTypes,base_node_disp> Node_; typedef base_gen<FlagTypes,base_link_disp> Link_;   };

---

Je n'ai trouvé que l'héritage (désolé Iradrille) pour inclure les fonctions virtuelles dans les classes de bases, connaissez vous d'autres moyens ?

Donc si je comprends bien finalement c est beaucoup plus simple que tout ce que j ai pu imaginer jusqu a present. Je parametre le type de valeur et le type de flag je fais les specialisations qui vont bien au cas ou ces types soient void et basta. Finalement je dois avouer que c est ce qu on m a dit depuis longtemps... mais bon j suis parfois têtu ou bête (au choix).
L'avantage de tout ca c est que j aurai au moins appris a trouver une autre source de factorisation via les template.
Je reviens dans la semaine avec ma classe Graph toute belle et surement d'autres questions.
Merci.

Je reviens à la charge pour vous demander si j'ai bien compris la situation :

1. La solution qui consiste à dire je ne mets que deux paramètres, un pour le type des valeurs de noeuds et un pour les types des valeurs de flag n'a-t-elle pas le désavantage de dire à l utilisateur "certes tu peux mettre le type que tu veux en jouant sur l'héritage mais tu vas payer cette souplesse à l'exécution" ?
2. Celle que j'ai commencée à imaginer était partie pour 'juste' éviter à l'utilisateur de faire ce travail de dérivation puisqu'en interne elle-même fabrique des classes dérivées et joue sur des fonctions virtuelles.
3. Il serait donc certainement plus malin de faire en sorte qu'en interne il n'y ait pas d'héritage, ou plus précisément, pas de fonction virtuelle. Tant qu'à jouer avec des templates variadiques autant que l'embrouillamini serve à pondre un truc efficace.
4. Est ce que c'est déjà ce que fait la bibliothéque de graphes de Boost ? (j'imagine que oui)
   Je vais tenter de chercher la réponse moi même mais honnêtement, pour avoir déjà farfouillé dans la std j'ai l'impression d'être particulièrement anti-doué dans le domaine de la 'lecture de code'.

Du coup je reviens sur une question que j'ai déjà posé dans ce fil mais qui pour l'instant n'a pas de réponse :
Dans le dernier code que j'ai posté, j'utilise de multiples dérivations successives pour 'insérer' des versions de fonctions (virtuelles dans ce cas...) dans une classe finale.
Est ce que c'est la façon standard de faire les choses ou est ce que je fais de manière maladroite un truc que 'tout le monde sait faire' de manière plus propre ?

Citation:

---

Envoyé par BaygonV

Je reviens à la charge pour vous demander si j'ai bien compris la situation :
La solution qui consiste à dire je ne mets que deux paramètres, un pour le type des valeurs de noeuds et un pour les types des valeurs de flag n'a-t-elle pas le désavantage de dire à l utilisateur "certes tu peux mettre le type que tu veux en jouant sur l'héritage mais tu vas payer cette souplesse à l'exécution" ?

---

Tout ce que tu fais "caché" à l'intérieur de ta classe Graphe, l'utilisateur peut le faire à l'extérieur donc la rapidité ou la souplesse n'a rien à voir. Je vois que tu nous a pondu une solution en jouant avec la méta-programmation (au moins tu auras appris ça :D) mais c'est beaucoup trop compliqué pour ce que tu cherches à faire et ça n'apporte rien à l'utilisateur, je dirais même que ta classe sera plus dur à utiliser. Ça revient au même que d'avoir un std::vector<int, char>, autant faire std::vector<boost::variant<int, char>>, ça laisse même à l'utilisateur le choix d'utiliser une variante ou l'héritage. En plus, il y a des bugs de méta-programmation dans ton implem, par exemple considère ça : Graph<1, int, int, int, char>, il faudrait que les types soient ajouté dans un "set", (ce qui existe dans Boost.MPL). Finalement, encore une chose, je suppose que c'est pour l’entraînement mais quasi toutes les structures de méta-prog que tu montres dans ton code existent déjà dans la std (en C++11) ou dans Boost.MPL.

Citation:

---

Envoyé par BaygonV

Celle que j'ai commencée à imaginer était partie pour 'juste' éviter à l'utilisateur de faire ce travail de dérivation puisqu'en interne elle-même fabrique des classes dérivées et joue sur des fonctions virtuelles.

---

Dans tous les cas, met toi à la place de l'utilisateur, si il veut que ses différentes classes héritent d'une classe de base, il y a certainement une raison, comme utiliser le polymorphisme autre part, tu prives à l'utilisateur d'ajouter sa propre classe de base et ses propres méthodes virtuelles.

Citation:

---

Envoyé par BaygonV

Il serait donc certainement plus malin de faire en sorte qu'en interne il n'y ait pas d'héritage, ou plus précisément, pas de fonction virtuelle. Tant qu'à jouer avec des templates variadiques autant que l'embrouillamini serve à pondre un truc efficace.

---

Comme dit avant, les templates variadiques ne sont pas utiles ici.

Citation:

---

Envoyé par BaygonV

Est ce que c'est déjà ce que fait la bibliothéque de graphes de Boost ? (j'imagine que oui)
Je vais tenter de chercher la réponse moi même mais honnêtement, pour avoir déjà farfouillé dans la std j'ai l'impression d'être particulièrement anti-doué dans le domaine de la 'lecture de code'.

---

La bibliothèque de Boost fait plutôt ce que je raconte (elle ne s'occupe pas des données contenues mais seulement de la représentation du graphe). Elle est assez compliqué à comprendre et à utiliser (du moins quand on commence) car elle fournit de nombreux points de variation (tu peux paramétrer tout ce que tu veux). Sans lire le code source, lit la documentation, ça sera déjà ça ;-)

Citation:

---

Envoyé par BaygonV

Du coup je reviens sur une question que j'ai déjà posé dans ce fil mais qui pour l'instant n'a pas de réponse :
Dans le dernier code que j'ai posté, j'utilise de multiples dérivations successives pour 'insérer' des versions de fonctions (virtuelles dans ce cas...) dans une classe finale.
Est ce que c'est la façon standard de faire les choses ou est ce que je fais de manière maladroite un truc que 'tout le monde sait faire' de manière plus propre ?

---

Il n'y a pas l'implémentation de base_gen mais, une fois de plus, je pense que cette solution alambiqué est seulement issue du mauvais design initial. Et honnêtement, je ne comprend ce que fait ta classe et à quoi ça sert.

Pour l'instant la classe ne fait rien :)
C'est moi qui la fait et plutôt mal on dirait.
Et oui c'est pour l'entrainement, et tenter de comprendre des trucs qui ont manifestement du mal à rentrer dans ma tête de mule.

Citation:

---

Envoyé par Trademark

Tout ce que tu fais "caché" à l'intérieur de ta classe Graphe, l'utilisateur peut le faire à l'extérieur donc la rapidité ou la souplesse n'a rien à voir.

---

Oui c'est bien ce que j'ai compris maintenant, à ce moment là je me disais qu'au moins ca pouvait faire gagner du temps mais bon...

Citation:

---

Envoyé par Trademark

Je vois que tu nous a pondu une solution en jouant avec la méta-programmation (au moins tu auras appris ça :D)

---

Oui et franchement je trouve ca plutôt fascinant bien que la syntaxe euh... dure dure quand même.

Citation:

---

Envoyé par Trademark

En plus, il y a des bugs de méta-programmation dans ton implem, par exemple considère ça : Graph<1, int, int, int, char>,

---

J'ai bien pensé à ca et à moins que je ne me trompe, pour l'instant, il n'y aura qu'une seule fonction virtuelle getFlag(const char&) reprise de fille en fille dans ce cas.
Tu as cependant raison sur le fait que la répétition des types pourra sans doute poser problème lorsque (travail pas fait dans le code présenté avant) j'aurai du tenter de proposer des types de Liens plus concrets dans la suite.

Citation:

---

Envoyé par Trademark

Finalement, encore une chose, je suppose que c'est pour l’entraînement mais quasi toutes les structures de méta-prog que tu montres dans ton code existent déjà dans la std (en C++11) ou dans Boost.MPL.

---

.
Oui c'est pour l'entrainement et je ne prétends pas (et de très loin) inventer un truc tout nouveau, seulement tout est nouveau pour moi en ce moment (j'ai pour la première fois installé un compilateur sur mon pc il y a... 2 mois) et sans manipuler moi même je ne pense pas arriver à utiliser des outils plus performants.

Citation:

---

Envoyé par Trademark

Dans tous les cas, met toi à la place de l'utilisateur, si il veut que ses différentes classes héritent d'une classe de base, il y a certainement une raison, comme utiliser le polymorphisme autre part, tu prives à l'utilisateur d'ajouter sa propre classe de base et ses propres méthodes virtuelles.

---

Oui et effectivement, je n'arrive pas bien à me mettre à sa place, cependant, rien ne l'empêche de déclarer un seul type et de faire ce que tu dis (pas dans la version actuelle qui n'a rien de finie comme tu l'as bien remarqué).

Citation:

---

Envoyé par Trademark

Comme dit avant, les templates variadiques ne sont pas utiles ici.

---

Ca par contre, j'ai du mal à le croire dans le contexte de ce que j'ai voulu faire.

Citation:

---

Envoyé par Trademark

La bibliothèque de Boost fait plutôt ce que je raconte (elle ne s'occupe pas des données contenues mais seulement de la représentation du graphe).

---

Ah, alors peut être que ce à quoi je pense pourra apporter un petit quelque chose finalement ?

Citation:

---

Envoyé par Trademark

Sans lire le code source, lit la documentation, ça sera déjà ça ;-)

---

Oui j'ai commencé.

Citation:

---

Envoyé par Trademark

Il n'y a pas l'implémentation de base_gen mais, une fois de plus, je pense que cette solution alambiqué est seulement issue du mauvais design initial. Et honnêtement, je ne comprend ce que fait ta classe et à quoi ça sert.[

---

Pour l'instant, je l'ai certainement mal fait mais ce n'était qu'un début, j'ai juste construit deux classes de bases dont (c'est ce que je pensais faire jusqu'à ton avant dernier post) des classes plus concretes pour les noeuds et les val allaient hériter pour redefinir la (trop seule) fonction virtuelle get qui va bien pour le type qu'elles auraient du prendre en charge.

Tu te lances de bien grand défis pour quelqu'un qui commence la programmation :mrgreen: Et je suis impressionné que tu manipules déjà la méta-programmation après seulement 2 mois.

Cela dit, je ne comprend toujours pas pourquoi tu veux absolument mettre de l'héritage dans ta structure, je ne vois pas ce que ça apporte et j'ai l'impression (ou alors je ne sais pas lire) que tu peines à m'en donner une explication exacte. Je pense que tu devrais essayer d'atteindre un objectif simple comme représenter un graphe le plus simple possible (uni-directionnel, sans données sur les arêtes) et coder un algorithme de parcours de graphe dessus. Ça te permettra d'aller au bout d'une implémentation et de te mettre plus facilement à la place de l'utilisateur. C'est impossible d'arriver au meilleur design du premier coup sans y aller itérativement :-)

J'ai déjà codé une classe graphe simple, avec un seul type en paramètre, une sous classe DFIterator, une autre sous classe BFIterator, via une matrice, puis via des listes...
Et ça m'a tellement énervé de me dire et si ? et si ? et si ? que je l'ai effacée de mon disque dur en me disant qu'il fallait faire mieux.... et c'est ce que je cherche à faire.

Pour l'héritage... alors... duquel parles tu en fait ?
J'en ai deux en têtes, un visible dans le dernier bout de code que j ai posté et un autre qui n'est qu implicite...

Héritage 1 : Voilà l'idée (que tu as battue en brèche) qui soutenait le second (l'implicite) :
J'ai des nœuds de plusieurs types que je veux mettre dans un graphe, donc je fais un premier patron de Node qui dérive d'une classe de base.
Le graphe ne 'contenant' que des pointeurs vers cette classe de base.
C'est grosso modo ce que tu me dis il me semble en me disant de ne coder une classe de graphe qui ne prend qu'un seul type de valeur de nœud et de laisser l'utilisateur se débrouiller.
J'allais un (tout petit) peu plus loin en fournissant ce patron et cette classe de base.

Puis au bout d'un moment (avec de bonnes et de mauvaises raisons) je me suis convaincu que les classes de nœuds et de liens devaient être des sous classes de la classe graphe.
L'idée étant : l'utilisateur veut créer un graphe avec des valeurs de nœuds int, char et des flag int ? ok, il va instancier un objet de type Graph<2,int,char, int> et je vais faire en sorte que ça marche.

Héritage 2 : Partant toujours sur la même idée que plus haut, il fallait que je commence à fabriquer les classes de bases de nœuds et liens et c'est ce que j'ai commencé à faire.
De manière assez évidente je me suis dis qu'un nœud aurait un jour ou l'autre besoin de renvoyer sa valeur (et un lien son flag... je ne poursuis qu'en considérant les noeuds parce que c'est déjà assez long comme ca) il fallait que la classe de base de nœud ait toutes les fonctions virtuelles 'get' disponibles provoquant une erreur d'execution en cas d appel tandis que la classe fille chargée de char par exemple implémenterait réellement la fonction qui va bien. Dans la classe de base, toutes ses fonctions virtuelles sont surchargées grâce au type du paramètre.
Bref....
Le second héritage, donc, n'est qu'un artifice, la classe de base de nœud étant fabriquée via héritages successifs en parcourant le vecteur de types de nœuds et en insérant à chaque fois la fonction virtuelle qui va bien. J'ai fait comme ça parce que je ne vois pas comment faire autrement.

Donc voila ou j'en suis après ton post (aussi grâce aux autres mais je ne sais pas pourquoi ce que j'y ai lu a provoqué une sorte de déclic) :
Héritage 1 exit, on ne met qu'un type de nœud mais c'est exactement la version que j'ai déjà jetée une fois.

Ensuite je me suis lancé dans la fabrication de Graph et je crois que je me suis tellement amusé a tenter de meta programmer (et à engendrer Héritage 2...) que je ne me suis pas vraiment rendu compte que je ne faisais que reproduire Héritage 1...

Bref, maintenant, je me documente un peu mieux, j'essaie de stabiliser ma connaissance aléatoire de la (vraiment super pénible) syntaxe des template et je pense refaire une version de Graph sans Héritage 1.

Voilà voilà.

J'enfonce encore le clou mais j'aimerais te convaincre que l'héritage n'apporte rien dans ce contexte (même pas un peu). Si l'utilisateur voulait stocker une données de type quelconque sans relation d'héritage, il aurait souffert de l'héritage que tu forçais dans ta classe. On peut penser performance mais au delà de ça, ça veut surtout dire qu'on a pas un design très clean. Si tu veux un défi qui te fera travailler ta méta-programmation, programme deux types de graphe, l'un avec liste et l'autre avec matrice (par exemple), et code un algorithme de parcours de graphe qui fonctionne avec les deux graphes. Après essaye de coder l'algorithme tel que l'utilisateur puisse faire certaines actions pendant le parcours.

J'avais déjà cet exercice en tête oui :)
Je pensais avoir clairement dit que je te donnais raison du point de vu de l'héritage.
Je parle ici de l'héritage 1, celui que tu sembles critiquer.
Si tu as un indice pour me permettre de me débarrasser de l'héritage 2 je suis preneur vu que celui là, originellement je n'en veux pas.

J'aurais du mal de te dire comment te débarrasser de ce deuxième héritage car je n'ai pas la moindre idée de son utilité :mouarf: Si tu veux une méthode pour retourner la valeur d'un noeud ou d'une arête et bien il suffit de l'ajouter n'est-ce pas ? Pas besoin d'héritage la dedans.

Citation:

---

la classe de base de nœud étant fabriquée via héritages successifs en parcourant le vecteur de types de nœuds

---

Justement tu n'as plus ce problème vu que tu n'as plus de vecteur de types. Juste un type pour les données du noeud et un autre pour les données des arêtes.

Est il possible de poster ici un morceau de code assez conséquent pour que vous tiriez à boulets rouges dessus ou y a-t-il des sites faits pour ça (poster, je compte sur vous pour tirer...) ?