Discussion :

[dj_benz]

Bonjour,

Je suis débutant avec l'utilisation de Boost::Graph, et je rencontre un problème avec le type que je souhaite. Mon but est très simple: créer un graphe dont les arcs et les sommets ont un nom (std::string).

Voilà mon code:

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
 
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
 
typedef boost::adjacency_list<
    boost::vecS, // type de liste d'arcs
    boost::vecS, // type de liste de sommets
    boost::undirectedS, // type de graphe
    std::string, // type d'arcs
    std::string  // type de sommets
> MyGraph;
 
int main(int argc, char** argv) 
{ 
    MyGraph g;
    boost::add_edge("A", "B", g); 
    boost::add_edge("B", "C", g); 
    boost::add_edge("A", "D", g); 
    return 0; 
}

Mais voilà l'erreur que j'ai:

main.cpp: invalid conversion from `const char*' to `unsigned int'

Le compilateur attend un int. Comment lui dire que je veux appeler mes sommets par un string, et pas un int?

Merci!

[dj_benz]

Sans réponse et sans solutions, malgré mes recherches, j'ai décidé d'abandonner la lib Boost et de créer ma propre structure de graphes.

Merci quand même au forum pour l'aide qu'il apporte (habituellement!)

[Matthieu Brucher]

As-tu lu mon tutoriel sur comment fonctionne Boost.Graph, ainsi que l'exemple final ? http://matthieu-brucher.developpez.c...mentation/#LIV

[dj_benz]

Oui, ton tutoriel est un des premiers que j'ai lus à propos des graphes Boost. Au passage, il est très bien fait et j'ai compris pas mal de détails que je n'avais pas saisi quand j'ai lu la doc Boost.

J'ai fait des essais avec

Code :

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

boost::property<boost::vertex_name_t, std::string>

mais je n'ai pas réussi à faire ce que je voulais.
En effet, on ne peut pas facilement "appeler" un sommet par son nom, du genre:

Code :

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

boost::add_edge("A", "B", g);

La plupart des exemples que j'ai vus, qui utilisent des string comme nom des sommets, utilisent des enum pour les noms.

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
24
25
26
27
 
  enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp, 
                 foo_o, bar_cpp, bar_o, libfoobar_a,
                 zig_cpp, zig_o, zag_cpp, zag_o, 
                 libzigzag_a, killerapp, N };
  const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
                         "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
                         "zig.cpp", "zig.o", "zag.cpp", "zag.o",
                         "libzigzag.a", "killerapp" };
 
  typedef std::pair<int, int> Edge;
  Edge used_by[] = {
    Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
    Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
    Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
    Edge(zow_h, foo_cpp), 
    Edge(foo_cpp, foo_o),
    Edge(foo_o, libfoobar_a),
    Edge(bar_cpp, bar_o),
    Edge(bar_o, libfoobar_a),
    Edge(libfoobar_a, libzigzag_a),
    Edge(zig_cpp, zig_o),
    Edge(zig_o, libzigzag_a),
    Edge(zag_cpp, zag_o),
    Edge(zag_o, libzigzag_a),
    Edge(libzigzag_a, killerapp)
  };

et ensuite, le programme utilise des int pour "nommer" ses sommets (et fait appel à son tableau pour retrouver les noms).

Mais comment appeler un sommet grâce à son nom? En faisant une recherche dans le tableau? Est-ce bien optimisé?

[Matthieu Brucher]

Je pense qu'il vaut mieux avoir une propriété donnant un numéro de sommet, puis une autre propriété avec le nom, quitte à avoir une map donnant l'un en fonction de l'autre.

Mais je dois avouer que je n'ai plus utilisé Graph depuis longtemps, et effectivement, c'est difficile d'arriver à comprendre ce qu'on fait réellement

[JolyLoic]

L'intérêt de boost::graph n'est pas tant les structures de graphes qu'il propose, que les algorithmes qui sont fournis, et qui peuvent entre autre s'appliquer à n'importe quelle structure de graphe, moyennant une adaptation raisonnable.

Donc je dirais donc, si tu veux ta propre syntaxe en terme de structure, ok, mais ce n'est pas pour autant une raison de laisser tomber boost::graph.

[dj_benz]

Merci pour vos réponses.

Les algorithmes que je dois utiliser sont très simples (détection des sous-graphes connexes, pour l'utilisation en câblage électrique: recherche des équipotentielles). C'est la seule recherche que je fais dans le graphe, la librairie serait donc plus difficile à configurer que l'algo à réécrire sur ma structure.

Cependant, si à l'avenir, j'ai des traitements complexes à réaliser sur mes structures, je me pencherai effectivement sur cette librairie, comme je l'ai fait à mes débuts avec la stl (qui me fait gagner un temps incalculable maintenant).

Merci encore.