Boost graph -> mettre le type de sommet comme propriété du graphe
Bonjour à tous,
Je viens demander de l'aide car j'ai un problème et je sèche un peu, j'ai fait des recherches et je n'ai rien trouvé.
En fait j'utilise la librairie de graphes dans boost, que je trouve vraiment excellente et qui convient parfaitement à ce que je souhaite faire.
A partir de la classe template boost::adjacency_list, je souhaite faire un typedef correspondant à un graphe dirigé où les sommets sont de type "node" et les arcs de type "extension".
Voici le code correspondant à ces deux types :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/**
* Possible extensions
*/
enum class extension{i_extension, s_extension};
template<typename Item>
struct node {
Item item_;
int support_;
/**
* Default, copy and members init constructors
*/
node() : item_{}, support_(-1) {}
node(const node<Item>& other) : item_(other.item_), support_(other.support_) {}
node(const Item& item, int support) : item_(item), support_(support) {}
}; |
Maintenant, si je défini mon graphe dirigé de la manière suivante, tout compile bien :
Code:
1
2
3
4
5
6
7
8
9
10
11
|
template<typename Item>
struct pattern_graph {
// directed graph alias
typedef boost::adjacency_list<
boost::vecS, boost::vecS, boost::bidirectionalS, // collections for vertices and edges, with both out-edge and in-edge access
node<Item>, // vertex property --> the current pattern informations
extension_flag, // edge property --> the extension type
boost::no_property // graph property --> no property
> type;
}; |
Cependant, mon graphe dirigé est en fait un arbre. Je souhaite donc mettre, en tant que propriété du graphe, son nœud racine. C'est là que les choses se compliquent, puisque je dois mettre le type de sommet comme propriété du graphe dans sa définition, sachant que le type de sommet a lui même besoin de la définition du graphe. J'avais déjà eu ce type de problème dans des cas plus simples que j'avais facilement résolu en déclarant par exemple un "struct vertex;" ou bien "class vertex;", etc. pour le définir plus loin. Mais là ça veut pas.
Je vous donne le code qui pose problème :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
template<typename Item>
struct pattern_tree {
struct vertex; // <- Problème ici, comment déclarer
// Tree alias
typedef boost::adjacency_list<
boost::vecS, boost::vecS, boost::bidirectionalS, // collections for vertices and edges, with both out-edge and in-edge access
node<Item>, // vertex property --> the current pattern informations
extension, // edge property --> the extension type
vertex // graph property --> root of the tree
> type;
// Vertex descriptor alias
typedef typename boost::graph_traits<type>::vertex_descriptor vertex;
}; |
Dans le code exemple j'ai mis "struct vertex;" mais essayé avec un peu tout ce que je pouvais. En fait le compilateur me dit qu'il a besoin de la définition complète du sommet pour définir le graphe et inversement. Pour l'instant j'ai trouvé une parade en définissant mon graphe sans nœud racine comme propriété du graphe et conservant la racine de manière externe. Mais ça me plait moyen.
Au final je me demande si ce que je veux faire est vraiment faisable sans passer par quelque chose d'un peu plus "tordu".
J'en appelle donc à votre aide :)
Merci,
Bonne soirée (et bonne année aussi !)
