boost::graph est il utilisable ?

Le
Marc Boyer
Bonjour à tous,

mon titre est un rien polémique, mais j'aimerais savoir s'il
existe des utilisateurs de boost::graph sur ce forum, et s'ils
en sont contents ?

Là, j'ai un pb de graphe, et je commence à l'utiliser, mais
je suis étonné de la façon de faire un bête graphe.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Loïc Joly
Le #304519
Bonjour à tous,

mon titre est un rien polémique, mais j'aimerais savoir s'il
existe des utilisateurs de boost::graph sur ce forum, et s'ils
en sont contents ?


Je l'utilise. En suis-je content ? Je ne sais pas trop. Je trouve
l'écriture un rien compliquée, même si ça va mieux avec de l'habitude.
Je n'utilise actuellement que 2 algos, donc le retour sur investissement
n'est pas forcément évident. Je n'aime pas trop dans leur design
l'impossibilité d'arrêter de parcourir une branche de recherche dans
leurs visiteurs.

Quels problèmes rencontres-tu avec ?

--
Loïc

Marc Boyer
Le #304517
Le 15-03-2007, Loïc Joly
Bonjour à tous,

mon titre est un rien polémique, mais j'aimerais savoir s'il
existe des utilisateurs de boost::graph sur ce forum, et s'ils
en sont contents ?


Je l'utilise. En suis-je content ? Je ne sais pas trop. Je trouve
l'écriture un rien compliquée


Je trouve aussi.
Rien que l'habitude de pas avoir d'operateurs begin() et end()
mais des trucs qui renvoient une paire, ça déstabilise.

Quand à cette idée d'avoir plusieurs propriétés par noeud/arc,
je trouve ça étrange comme design.
Moi, si je veux associer un nom et un poids à un noeud, je
ferais plutôt mon type maison
struct Info{
string name();
double w;
}
et j'associe le type Info au noeud, alors quand dans la logique
de BGL, tu associes une propriété par champs...


même si ça va mieux avec de l'habitude.


Bon.

Je n'utilise actuellement que 2 algos, donc le retour sur investissement
n'est pas forcément évident.


J'avoue que là, c'est un peu un test. J'utilise la structure de
données, et je suis même pas sur d'utiliser leurs algo.
D'ailleurs, j'ai pas vu des algos qui me semble pourtant basiques,
comme avoir l'ensemble des prédecesseurs et/ou des successeurs d'un
noeud dans un graphe orienté...

Je n'aime pas trop dans leur design
l'impossibilité d'arrêter de parcourir une branche de recherche dans
leurs visiteurs.

Quels problèmes rencontres-tu avec ?


Là, c'es tout con, j'ai un fichier avec des noms de noeuds et
un autre ou les arcs sont donnés par le couple de noms de noeuds.
-- nodes.txt --
AAA
BBB
CCC
-- edges.txt --
AAA BBB xx
AAA CCC yy
CCC AAA zz

Donc je batis mon graphe avec les noms de noeud comme propriété, mais
ensuite, pour ajouter les arcs, comment je retrouve le noeud ? Je suis
obligé de me stoquer dans une map utilisateur la correspondance
nom -> noeud ? Je suis étonné que ce ne soit pas fournit (où je ne
l'ai pas trouvé...)

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)


Jean-Marc Bourguet
Le #304487
Marc Boyer
Le 15-03-2007, Loïc Joly
Bonjour à tous,

mon titre est un rien polémique, mais j'aimerais savoir s'il
existe des utilisateurs de boost::graph sur ce forum, et s'ils
en sont contents ?


Je l'utilise. En suis-je content ? Je ne sais pas trop. Je trouve
l'écriture un rien compliquée


Je trouve aussi.
Rien que l'habitude de pas avoir d'operateurs begin() et end()
mais des trucs qui renvoient une paire, ça déstabilise.

Quand à cette idée d'avoir plusieurs propriétés par noeud/arc,
je trouve ça étrange comme design.
Moi, si je veux associer un nom et un poids à un noeud, je
ferais plutôt mon type maison
struct Info{
string name();
double w;
}
et j'associe le type Info au noeud, alors quand dans la logique
de BGL, tu associes une propriété par champs...


Je n'ai jamais utilise leurs classes. J'avais regarde il y a quelque
temps. De memoire, leur approche permet de faire tres facilement des
adapteurs stateless vers des structures existantes.

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org



Marc Boyer
Le #304485
Le 16-03-2007, Jean-Marc Bourguet

Je n'ai jamais utilise leurs classes. J'avais regarde il y a quelque
temps. De memoire, leur approche permet de faire tres facilement des
adapteurs stateless vers des structures existantes.


Heuh, tu peux préciser ce que tu appelles "adapteurs stateless vers
des structures existantes" ?

Marc
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)

Jean-Marc Bourguet
Le #304484
Marc Boyer
Le 16-03-2007, Jean-Marc Bourguet

Je n'ai jamais utilise leurs classes. J'avais regarde il y a quelque
temps. De memoire, leur approche permet de faire tres facilement des
adapteurs stateless vers des structures existantes.


Heuh, tu peux préciser ce que tu appelles "adapteurs stateless vers
des structures existantes" ?


Tu as un graphe existant avec l'info qui est accessible d'une maniere ou
d'une autre (pas necessairement des membres). Tu veux utiliser l'interface
de boost sans pour autant creer des nouveaux objets.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org


Loïc Joly
Le #304444

Rien que l'habitude de pas avoir d'operateurs begin() et end()
mais des trucs qui renvoient une paire, ça déstabilise.


Ca a des avantages. A tel point que certains voudraient avoir la même
chose sur la STL. En particulier, on peut aisément passer à un
algorithme la valeur de retour d'une fonction, ce qui serait moins aisé
si on devait lui passer deux itérateurs.


Quand à cette idée d'avoir plusieurs propriétés par noeud/arc,
je trouve ça étrange comme design.
Moi, si je veux associer un nom et un poids à un noeud, je
ferais plutôt mon type maison
struct Info{
string name();
double w;
}
et j'associe le type Info au noeud, alors quand dans la logique
de BGL, tu associes une propriété par champs...


Là ou j'ai pu lui voir de l'intérêt, c'est pour définir génériquement un
algorithme. Comment ferais-tu pour indiquer à un algo ne connaissant pas
le type Info d'utiliser le w comme poids dans ton cas. Sachant que cet
algo devrait aussi pouvoir travailler sur un graphe où les noeuds n'ont
pas intrinsèquement de poids, mais en ont un juste localement, pour les
besoins d'une fonction.

Mais je reconnais que la syntaxe d'utilisation n'est pas claire, et que,
comme souvent hélàs avec boost, la doc n'est pas évidente du tout.

Je n'utilise actuellement que 2 algos, donc le retour sur investissement
n'est pas forcément évident.



J'avoue que là, c'est un peu un test. J'utilise la structure de
données, et je suis même pas sur d'utiliser leurs algo.
D'ailleurs, j'ai pas vu des algos qui me semble pourtant basiques,
comme avoir l'ensemble des prédecesseurs et/ou des successeurs d'un
noeud dans un graphe orienté...


C'est pas dans la catégorie algo, puisque ce sont justement les trucs de
base sur lesquels les algos sont construits. Ce sont les éléments
décrits dans les différents concepts de graphes, comme par exemple
in_edges, out_edge, adjacent_vertices, inv_adjacent_vertices.


Là, c'es tout con, j'ai un fichier avec des noms de noeuds et
un autre ou les arcs sont donnés par le couple de noms de noeuds.
-- nodes.txt --
AAA
BBB
CCC
-- edges.txt --
AAA BBB xx
AAA CCC yy
CCC AAA zz

Donc je batis mon graphe avec les noms de noeud comme propriété, mais
ensuite, pour ajouter les arcs, comment je retrouve le noeud ? Je suis
obligé de me stoquer dans une map utilisateur la correspondance
nom -> noeud ? Je suis étonné que ce ne soit pas fournit (où je ne
l'ai pas trouvé...)


C'est aussi ce que j'ai fait dans mon cas.

--
Loïc


Marc Boyer
Le #304359
Le 17-03-2007, Loïc Joly

Rien que l'habitude de pas avoir d'operateurs begin() et end()
mais des trucs qui renvoient une paire, ça déstabilise.


Ca a des avantages. A tel point que certains voudraient avoir la même
chose sur la STL. En particulier, on peut aisément passer à un
algorithme la valeur de retour d'une fonction, ce qui serait moins aisé
si on devait lui passer deux itérateurs.


Oui, peut-être. Je n'en suis qu'à la phase "je découvre"...
J'aurais bien aimé une petite intro qui explique et justifie
ce choix.

Quand à cette idée d'avoir plusieurs propriétés par noeud/arc,
je trouve ça étrange comme design.
Moi, si je veux associer un nom et un poids à un noeud, je
ferais plutôt mon type maison
struct Info{
string name();
double w;
}
et j'associe le type Info au noeud, alors quand dans la logique
de BGL, tu associes une propriété par champs...


Là ou j'ai pu lui voir de l'intérêt, c'est pour définir génériquement un
algorithme. Comment ferais-tu pour indiquer à un algo ne connaissant pas
le type Info d'utiliser le w comme poids dans ton cas. Sachant que cet
algo devrait aussi pouvoir travailler sur un graphe où les noeuds n'ont
pas intrinsèquement de poids, mais en ont un juste localement, pour les
besoins d'une fonction.


Ben, on demande à l'utilisateur de fournir un opérateur
double getPoids(edge_descriptor), et on l'utilise. Non ?
J'ai raté un truc ?

Mais je reconnais que la syntaxe d'utilisation n'est pas claire, et que,
comme souvent hélàs avec boost, la doc n'est pas évidente du tout.


Oui, et j'ai fait l'effort d'achetter le bouquin après avoir galéré
sur la doc en ligne. C'est plus facile pour moi.

Je n'utilise actuellement que 2 algos, donc le retour sur investissement
n'est pas forcément évident.


J'avoue que là, c'est un peu un test. J'utilise la structure de
données, et je suis même pas sur d'utiliser leurs algo.
D'ailleurs, j'ai pas vu des algos qui me semble pourtant basiques,
comme avoir l'ensemble des prédecesseurs et/ou des successeurs d'un
noeud dans un graphe orienté...


C'est pas dans la catégorie algo, puisque ce sont justement les trucs de
base sur lesquels les algos sont construits. Ce sont les éléments
décrits dans les différents concepts de graphes, comme par exemple
in_edges, out_edge, adjacent_vertices, inv_adjacent_vertices.


Je pensais à la fermeture transitive de ça.
Pred( x ) = { y | y -> n_1 -> .... -> n_k -> x }

Donc je batis mon graphe avec les noms de noeud comme propriété, mais
ensuite, pour ajouter les arcs, comment je retrouve le noeud ? Je suis
obligé de me stoquer dans une map utilisateur la correspondance
nom -> noeud ? Je suis étonné que ce ne soit pas fournit (où je ne
l'ai pas trouvé...)


C'est aussi ce que j'ai fait dans mon cas.


Bon. Et c'est ce que Douglas Gregor m'a dit de faire.
Mais j'étais étonné que ce ne soit pas montré dans la doc.
Ca me semble une manière hyper basique de construire un graphe.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)



Michel Decima
Le #304312

Pour repondre a ta question initiale: oui, Boost.Graph est utilisable,
en particulier si tu as l'intention de faire tourner des algorithmes sur
des graphes de grande taille ( plusieurs dizaines de milliers de
noeuds). En revanche, si tu ne veux pas faire de calculs sur des
graphes, mais plutot de la manipulation/edition/affichage, c'est pas
forcement le meilleur choix.



Rien que l'habitude de pas avoir d'operateurs begin() et end()
mais des trucs qui renvoient une paire, ça déstabilise.
Ca a des avantages. A tel point que certains voudraient avoir la même

chose sur la STL. En particulier, on peut aisément passer à un
algorithme la valeur de retour d'une fonction, ce qui serait moins aisé
si on devait lui passer deux itérateurs.


Oui, peut-être. Je n'en suis qu'à la phase "je découvre"...
J'aurais bien aimé une petite intro qui explique et justifie
ce choix.


Une autre raison possible, c'est que ca ca reduit le nombre de
fonctions. Sur un graphe de type AdjacencyList, il y a au moins 6
fonctions qui renvoient des iterateurs: vertices(), edges(),
adjacent_vertices(), inv_adjacent_vertices(), out_edges(), et
in_edges(). Si la convention begin/end avait ete utilisée, ca
doublerait le nombre.
Et il y a aussi le fait que dans le cas des graphes, on a quasiment
toujours besoin de traiter/obtenir une paire d'iterateurs, contrairement
a la STL ou parfois un seul iterateur suffit comme pour find() par
exemple. Et alors c'est plus logique de renvoyer les deux en meme
temps, avec un hybride entre le pattern Iterator classique et les
iterateurs de la STL.

Quand à cette idée d'avoir plusieurs propriétés par noeud/arc,
je trouve ça étrange comme design.
Moi, si je veux associer un nom et un poids à un noeud, je
ferais plutôt mon type maison
struct Info{
string name();
double w;
}
et j'associe le type Info au noeud, alors quand dans la logique
de BGL, tu associes une propriété par champs...




Tu peux utiliser une structure comme celle-ci avec des graphes Boost,
ca s'appelle les "bundled properties" (bien caché dans la doc, cf le
fichier bundles.html). La declaration du graphe deviendrait quelque
chose comme ca:

typedef boost::adjacency_list<
boost::listS, boost::vecS,
boost::bidirectionalS,
Info >
Graph;

Et pour l'utilisation, tu as une syntaxe a base d'operator[] pour
acceder aux membres:

Graph g;
Graph::vertex_descriptor v = add_vertex( g );
g[ v ].name = "AAA":
g[ v ].w = 42;

Pour appeler un algorithme qui travaille sur un membre particulier, il
faut transformer celui ci en PropertyMap en utilisant un pointeur sur
membre:

boost::property_map<Graph, double Info::*>::type
wg = get( &Info::w, g );

Je ne sais pas si ca marche aussi avec des pointeurs sur fonction membres.

Là ou j'ai pu lui voir de l'intérêt, c'est pour définir génériquement un
algorithme. Comment ferais-tu pour indiquer à un algo ne connaissant pas
le type Info d'utiliser le w comme poids dans ton cas. Sachant que cet
algo devrait aussi pouvoir travailler sur un graphe où les noeuds n'ont
pas intrinsèquement de poids, mais en ont un juste localement, pour les
besoins d'une fonction.


Ben, on demande à l'utilisateur de fournir un opérateur
double getPoids(edge_descriptor), et on l'utilise. Non ?
J'ai raté un truc ?


Oui, je crois que tu as raté ce que voulais dire Loic. L'exemple qu'il
donne, c'est un algo qui a besoin _en_interne_ d'une propriete poids sur
les noeuds, et c'est l'algo qui va ajouter dynamiquement et
temporairement cette propriete poids au graphe, sans que tu n'aie rien a
faire de plus. Tu pourrais evidemment fournir toi-meme un functor (ou
plutot une PropertyMap dans le cas present), mais ca t'obligerais a
connaitre le fonctionnement interne de tous les algorithmes que tu vas
utiliser pour ajouter leurs propriétés internes a ton graphe, avec tous
les problemes qui vont avec (plus d'encapsulation, conflits,
sur-consommation mémoire, etc.)


Donc je batis mon graphe avec les noms de noeud comme propriété, mais
ensuite, pour ajouter les arcs, comment je retrouve le noeud ? Je suis
obligé de me stoquer dans une map utilisateur la correspondance
nom -> noeud ? Je suis étonné que ce ne soit pas fournit (où je ne
l'ai pas trouvé...)
C'est aussi ce que j'ai fait dans mon cas.



Bon. Et c'est ce que Douglas Gregor m'a dit de faire.
Mais j'étais étonné que ce ne soit pas montré dans la doc.
Ca me semble une manière hyper basique de construire un graphe.


C'est effectivement tres basique, et l'absence de cette fonctionnalite
m'a etonné au début. D'un autre coté, comme la map ne sert qu'a la
creation, ca me semble raisonnable qu'elle ne soit pas embarquée dans le
graphe lui meme, puisqu'elle n'est pas utile par la suite. Et donc on
finit tous par creer des outils externes de construction a base de map,
qui eux pourraient être fournis par défaut. D'un autre coté, comme c'est
assez trivial, est-ce vraiment necessaire ?

MD.



Marc Boyer
Le #304311
Le 19-03-2007, Michel Decima

Pour repondre a ta question initiale: oui, Boost.Graph est utilisable,
en particulier si tu as l'intention de faire tourner des algorithmes sur
des graphes de grande taille ( plusieurs dizaines de milliers de
noeuds).


Non, juste un millier de noeuds pour le moment.

En revanche, si tu ne veux pas faire de calculs sur des
graphes, mais plutot de la manipulation/edition/affichage, c'est pas
forcement le meilleur choix.


Si, il y a pas mal de calcul.

Oui, peut-être. Je n'en suis qu'à la phase "je découvre"...
J'aurais bien aimé une petite intro qui explique et justifie
ce choix.


Une autre raison possible, c'est que ca ca reduit le nombre de
fonctions. Sur un graphe de type AdjacencyList, il y a au moins 6
fonctions qui renvoient des iterateurs: vertices(), edges(),
adjacent_vertices(), inv_adjacent_vertices(), out_edges(), et
in_edges(). Si la convention begin/end avait ete utilisée, ca
doublerait le nombre.
Et il y a aussi le fait que dans le cas des graphes, on a quasiment
toujours besoin de traiter/obtenir une paire d'iterateurs, contrairement
a la STL ou parfois un seul iterateur suffit comme pour find() par
exemple. Et alors c'est plus logique de renvoyer les deux en meme
temps, avec un hybride entre le pattern Iterator classique et les
iterateurs de la STL.


OK

Quand à cette idée d'avoir plusieurs propriétés par noeud/arc,
je trouve ça étrange comme design.
Moi, si je veux associer un nom et un poids à un noeud, je
ferais plutôt mon type maison
struct Info{
string name();
double w;
}
et j'associe le type Info au noeud, alors quand dans la logique
de BGL, tu associes une propriété par champs...




Tu peux utiliser une structure comme celle-ci avec des graphes Boost,
ca s'appelle les "bundled properties" (bien caché dans la doc, cf le
fichier bundles.html).


OK, merci du pointeur.

La declaration du graphe deviendrait quelque
chose comme ca:

typedef boost::adjacency_list<
boost::listS, boost::vecS,
boost::bidirectionalS,
Info >
Graph;

Et pour l'utilisation, tu as une syntaxe a base d'operator[] pour
acceder aux membres:

Graph g;
Graph::vertex_descriptor v = add_vertex( g );
g[ v ].name = "AAA":
g[ v ].w = 42;


Ca a l'ai pas mal. Pour le moment, je me traine un

typedef boost::adjacency_list<boost::listS, boost::listS,
boost::directedS,
boost::property<boost::vertex_color_t,
MaClasse> >

Et je fais plein de
color_map p= get(vertex_color, graph);
et j'y accède pas là.

Pour appeler un algorithme qui travaille sur un membre particulier, il
faut transformer celui ci en PropertyMap en utilisant un pointeur sur
membre:

boost::property_map<Graph, double Info::*>::type
wg = get( &Info::w, g );

Je ne sais pas si ca marche aussi avec des pointeurs sur fonction membres.


ok

Là ou j'ai pu lui voir de l'intérêt, c'est pour définir génériquement un
algorithme. Comment ferais-tu pour indiquer à un algo ne connaissant pas
le type Info d'utiliser le w comme poids dans ton cas. Sachant que cet
algo devrait aussi pouvoir travailler sur un graphe où les noeuds n'ont
pas intrinsèquement de poids, mais en ont un juste localement, pour les
besoins d'une fonction.


Ben, on demande à l'utilisateur de fournir un opérateur
double getPoids(edge_descriptor), et on l'utilise. Non ?
J'ai raté un truc ?


Oui, je crois que tu as raté ce que voulais dire Loic. L'exemple qu'il
donne, c'est un algo qui a besoin _en_interne_ d'une propriete poids sur
les noeuds, et c'est l'algo qui va ajouter dynamiquement et
temporairement cette propriete poids au graphe, sans que tu n'aie rien a
faire de plus. Tu pourrais evidemment fournir toi-meme un functor (ou
plutot une PropertyMap dans le cas present), mais ca t'obligerais a
connaitre le fonctionnement interne de tous les algorithmes que tu vas
utiliser pour ajouter leurs propriétés internes a ton graphe, avec tous
les problemes qui vont avec (plus d'encapsulation, conflits,
sur-consommation mémoire, etc.)


OK, je crois que je vois.

Donc je batis mon graphe avec les noms de noeud comme propriété, mais
ensuite, pour ajouter les arcs, comment je retrouve le noeud ? Je suis
obligé de me stoquer dans une map utilisateur la correspondance
nom -> noeud ? Je suis étonné que ce ne soit pas fournit (où je ne
l'ai pas trouvé...)
C'est aussi ce que j'ai fait dans mon cas.



Bon. Et c'est ce que Douglas Gregor m'a dit de faire.
Mais j'étais étonné que ce ne soit pas montré dans la doc.
Ca me semble une manière hyper basique de construire un graphe.


C'est effectivement tres basique, et l'absence de cette fonctionnalite
m'a etonné au début. D'un autre coté, comme la map ne sert qu'a la
creation, ca me semble raisonnable qu'elle ne soit pas embarquée dans le
graphe lui meme, puisqu'elle n'est pas utile par la suite. Et donc on
finit tous par creer des outils externes de construction a base de map,
qui eux pourraient être fournis par défaut. D'un autre coté, comme c'est
assez trivial, est-ce vraiment necessaire ?


Au moins un exemple dans la doc.

Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)




Gabriel Dos Reis
Le #305615
Loïc Joly
| > Bonjour à tous,
| > mon titre est un rien polémique, mais j'aimerais savoir s'il
| > existe des utilisateurs de boost::graph sur ce forum, et s'ils
| > en sont contents ?
|
| Je l'utilise. En suis-je content ? Je ne sais pas trop. Je trouve
| l'écriture un rien compliquée, même si ça va mieux avec de
| l'habitude.

Ah bon ? T'aimes pas les visiteurs templates et les pointeurs
intelligents ? Il paraît que c'est que c'est le must pour du code
dit « C++ moderne » ?

-- Gaby
Publicité
Poster une réponse
Anonyme