Graphe générique C++

Version imprimable

15/04/2014, 20h26
Phuy38

Graphe générique C++
Bonjour à tous,

Je suis bloqué depuis une semaine sur ce programme et j’espère que vous allez pouvoir m'aider. ;)
Je doit réaliser un graphe générique en c++.
Voila comment je fait les choses.

Pour le graphe générique en lui même j'ai trois templates GGraphe, GSommet, GArete déclaré de la manière suivante
Code:

1 2 3 4 template <typename TGraphe, typename USommet, typename VArete > class GGraphe{
C'est la première fois que je fait de la généricité en c++ alors déjà est ce que la déclaration des classes ce fait bien comme ça avec des templates ?

Ensuite est ce que dans l'implémentation chaque méthodes doit avoir écrit a nouveau template et les trois types génériques que je vais utiliser de la manière suivante ?
Code:

1 2 3 4 template <typename TGraphe, typename USommet, typename VArete> GGraphe<TGraphe, USommet, VArete>::GGraphe() { }
Maintenant la partie où je bloque.
On suppose maintenant que un utilisateur souhaite créer des classes qui héritent du graphe générique. Donc l'utilisateur crée trois classes (par exemple) Molecule, Atom, Arete. Pour chaque classes il fait hérité la classe générique correspondante. Pour Molecule : GGraphe.

Je déclare la classe comme ca :
Code:

1 2 class Molecule : virtual public GGraphe <Molecule, Atom, Liaison>{
C'est ici que j'ai un problème. Quand je compile il me dit que "Molecule" n'est pas définit, en effet puisqu'il est en train de compiler la classe Molecule donc elle n'existe pas encore. J'ai alors essayer de mettre ca juste avant de déclarer la classe.
Code:

1 2 class Molecule;
Et alors il le compilateur me dit qu'il ne connait pas les méthodes qui sont dans la classe Molecule.

Voila

Est ce que vous pouvez m'apporter votre aide ?
Merci d'avance.
15/04/2014, 23h58
Emmanuel Deloget
Citation:
Envoyé par Phuy38

Bonjour à tous,

Je suis bloqué depuis une semaine sur ce programme et j’espère que vous allez pouvoir m'aider. ;)
Je doit réaliser un graphe générique en c++.
Voila comment je fait les choses.

Pour le graphe générique en lui même j'ai trois templates GGraphe, GSommet, GArete déclaré de la manière suivante

Code:

1 2 3 4 template <typename TGraphe, typename USommet, typename VArete > class GGraphe{
Mmmmoui... Peut-être.

Citation:

Envoyé par Phuy38

C'est la première fois que je fait de la généricité en c++ alors déjà est ce que la déclaration des classes ce fait bien comme ça avec des templates ?

Oui. Tu peux utiliser class en lieu et place de typename (synonyme et sémentiquement plus juste, à moins que GArete puisse être un int).
Citation:
Envoyé par Phuy38

Ensuite est ce que dans l'implémentation chaque méthodes doit avoir écrit a nouveau template et les trois types génériques que je vais utiliser de la manière suivante ?

Code:

1 2 3 4 template <typename TGraphe, typename USommet, typename VArete> GGraphe<TGraphe, USommet, VArete>::GGraphe() { }
Tu peux aussi définir les fonctions dans le corps de la classe :
Code:

1 2 3 4 5 6 7 8 9 10 template <class Graph, class Vertex, class Link> class graph { public: graph() { ... } };
Pour les fonctions qui ne sont pas trop longue, ça sera moins lourd à gérer.
Citation:
Envoyé par Phuy38

Maintenant la partie où je bloque.
On suppose maintenant que un utilisateur souhaite créer des classes qui héritent du graphe générique. Donc l'utilisateur crée trois classes (par exemple) Molecule, Atom, Arete. Pour chaque classes il fait hérité la classe générique correspondante. Pour Molecule : GGraphe.

Je déclare la classe comme ca :

Code:

1 2 class Molecule : virtual public GGraphe <Molecule, Atom, Liaison>{

C'est ici que j'ai un problème. Quand je compile il me dit que "Molecule" n'est pas définit, en effet puisqu'il est en train de compiler la classe Molecule donc elle n'existe pas encore. J'ai alors essayer de mettre ca juste avant de déclarer la classe.
Que veut dire cette déclaration ? Une molécule est un graphe de molécule ?

Il me semblait que c'était un graphe d'atomes.

Je met le doigt sur ce qui me gène dans ta déclaration ci dessus : template <typename TGraphe, typename USommet, typename VArete> class CGraphe;

Pourquoi est-ce que la classe graphe est définie à partir d'un graphe ? Ca na pas vraiment de sens. Un graphe est une entité composée de sommets et d'arrêtes qui lient ces sommets (des liens). Un lien a des propriétés (arbitraire + sens si le lien est directionnel), et les sommets ont des propriétés arbitraires aussi - donc il est logique que les deux soient traités de manière génériques par ta définition. Mais le paramètre TGraphe, à quoi sert-il ? La, je ne comprends pas.
Citation:
Envoyé par Phuy38

Code:

1 2 class Molecule;

Et alors il le compilateur me dit qu'il ne connait pas les méthodes qui sont dans la classe Molecule.
Et pour cause. Tu crée un lien cyclique indirecte entre Molecule et elle-même, et ce lien indirect a besoin de connaître Molecule. Ca ne peut pas marcher :)
16/04/2014, 01h04
Mikkkka
Salut,

J'ai l'impression que tu fais plus compliqué que nécessaire, tu as juste besoin de définir une classe générique :
Code:

1 2 3 4 5 template <class vertex_type, class edge_type > class graph{ ...... }
Après, pour représenter ta molécule, il faut te demander quel type va représenter tes atomes et quel type va représenter tes liaisons. Le plus simple, selon moi, est d'utiliser des std::string pour les deux, même si en terme de performance c'est tout pourri ça à le mérite d'être peut être plus intuitif.
Ainsi si tu veux faire un graphe qui représente une molécule tu peux faire un typedef :
Code:

1 2 typedef graph<std::string, std::string> molecule;
Est-ce que tu pourrais donner plus de code, qu'est ce qu'il y a d'implémenté à l'intérieur de ta classe ?
Quel type de molécule tu souhaites représenter ?
Peut-il y avoir plusieurs liaisons entre deux atomes (du coup ce n'est plus un graphe mais un multigraphe, la complexité augmente) ?

Choisir une structure de graphe n'est pas forcément évident et dépends vraiment de ta problématique.