Discussion :

[kochfet]

Bonjour,

Comment implémenter un graphe avec C++. Mon graphe est constitué d'un ensemble des nœuds de différents types et un ensemble des arcs aussi avec différents types.

Merci d'avance.

[Trademark]

En utilisant ta tête (Ou en nous proposant un code de base, ou en explicitant tes idées, il faut toujours donner une base !).

[Neckara]

Bonjour,

Il y a 1001 façon d'implémenter des graphes en C++, le tout serait de savoir ce que tu vas en faire, à quelle "fréquence" et de savoir si tu préfère avoir quelque chose de plus rapide mais utilisant plus de mémoire ou l'inverse.

Sinon un petit lien qui pourra t'aider.

[camboui]

Autant proposer ce lien directement

[gbdivers]

Ou, pour un tutoriel pour orienté débutant, Commencer facilement avec Boost Graph (oui, c'est de l'auto-promo, et alors ? )

[kochfet]

Merci pour toutes les réponses. Mais, dans mon travail je n'ai pas besoin d'aucun algorithme offert par Boost.graph. Est il utile donc de l'utiliser?

[Neckara]

Merci pour toutes les réponses. Mais, dans mon travail je n'ai pas besoin d'aucun algorithme offert par Boost.graph. Est il utile donc de l'utiliser?

Un bon programmeur est un programmeur féniant (enfin tant qu'il ne délocalise pas son travail en Chine ) donc si boost peut t'éviter de coder toi-même des fonctions et te faire gagner du temps n'hésite pas.
Bien sûr si tu as des contraintes spécifiques (ex : contrainte de taille du programme, etc...) tu seras peut être obligé de le réécrire toi-même.

Il ne faut aussi pas oublier qu'un code présent dans une bibliothèque a moins de chances d'être boggué que le code qu'on écrit nous-même.

[white_tentacle]

Est-ce que c’est un travail d’étude ?

Car si c’est un travail d’étude, le but est d’apprendre à modéliser un graphe, pas de prendre une librairie qui te mâche le travail.

Dans un autre cas, c’est impossible de répondre de manière générale à ta question. J’ai plutôt envie de dire que à moins que tu aies de bonnes raisons de ne pas le faire, oui ça vaut probablement le coup. Mais sans connaître ton besoin précis…

[kochfet]

Mon but est de représenter une requête SQL sous forme d'un graphe. J'ai une structure précise de ce graphe : un ensemble des nœuds de différents types (des noeuds qui représentent les variables dans la clause from...) et un ensemble des liens (des liens qui représentent la jointure, des liens qui représentent les quantificateurs existentiels...). Par exemple,

- chaque variable déclarée dans la clause from va être transformée à un nœud que j'ai l'appeler un nœud Ns, ce nœud possède une propriété qui est le prédicat défini sur la variable.

- Chaque expression de jointure dans la clause where va être transformé à un lien de jointure Lj. Ce lien possède une propriété qui est la condition de jointure

- ...

[white_tentacle]

C’est pas plutôt un hyperarbre une requête sql*?

[kochfet]

En fait, je veux savoir comment transformer une requête SQL sous forme d'un graphe. Autrement dit, comment récupérer les différentes parties de la requête (les variables dans la clause from, les prédicats définis sur ces variables dans la clause where, les conditions de jointure, les attributs de projection....) avec un code écrit en C++ ?

[white_tentacle]

Il te faut un parseur SQL. Mais je pense que tu auras un arbre, pas un graphe .

Aucune idée de s’il en existe de facilements intégrables, sinon, ça doit se faire avec spirit ou autres, mais je pense que la grammaire SQL est quand même un assez gros morceau.

[ternel]

Il existe toujours la solution de "l'œil du libre".
La bibliothèque libre Sqlite implémente une grammaire SQL, donc, tu peux regarder son code.
C'est une piste comme une autre.