Discussion :

[Mikkkka]

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 :

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
 
/**
 * 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 :

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

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 :

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
 
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 !)

[Mikkkka]

En fait c'est bon, j'ai résolu mon problème en mettant un pointeur sur mon sommet racine, de la manière suivante :

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
 
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;
};

Je me demande comment je n'y ai pas pensé plus tôt.
Problème résolu

[Mikkkka]

Au cas où cela serve à quelqu'un d'autre, en fait mon problème n'était pas réglé avec le pointeur puisqu'un vertex_descriptor ne peut être récupéré, à partir du graphe, que par valeur (j'ai l'impression).
Au final j'ai réussi à faire ce que je voulais initialement en redéfinissant en quelque sorte deux fois mon arbre à l'aide d'un "type_helper".
Ça compile et tourne niquel.

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
 
template<typename Item>
struct pattern_tree {
 
    // Tree alias helper
    typedef boost::adjacency_list<
        boost::vecS, boost::vecS, boost::bidirectionalS, // collections for vertices and edges, with both out-edge and in-edge acess
        node<Item>, // vertex property
        pattern_miner::extension_flag, // edge property --> the extension type
        boost::no_property // no property
    > type_helper;
 
    // Vertex type alias
    typedef typename boost::graph_traits<type_helper>::vertex_descriptor vertex;
 
    // Tree alias
    typedef boost::adjacency_list<
        boost::vecS, boost::vecS, boost::bidirectionalS, // collections for vertices and edges, with both out-edge and in-edge acess
        node<Item>, // vertex property
        pattern_miner::extension_flag, // edge property --> the extension type
        vertex // graph property --> root of the tree
    > type;
};