Discussion :

[nina2007]

Bonjour à tous,
je débute avec boostGraph, je commence par effectuer un petit test. cependant,
j'ai une petite question:
voilà, le bout de code: je crée deux noeuds dans un graphe avec un arc qui relie ces deux noeuds
je voudrai lors du parcours des arcs du graphe (ici un seul arc), afficher les etiquettes des noeuds (ici 12 et 20)

le problème est que là, il m'affiche 0 et 1 (comme des index ou des identifiants des noeuds lors de leurs construction

si vous avez une idée merci de m'aider

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
28
29
30
 
typedef adjacency_list<vecS, vecS, undirectedS, int, int> Graph;
Graph _Bgraphe;
 typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
 
Vertex v1 = add_vertex(_Bgraphe);
Vertex v2 = add_vertex(_Bgraphe);
 
_Bgraphe[v1] = 12;
_Bgraphe[v2] = 20;
 
graph_traits<Graph>::vertex_iterator v_it, v_end, debut;
boost::tie(debut,v_end) = vertices(_Bgraphe);
 
//parcours des neouds
for (v_it=debut;v_it!=v_end;v_it++)
{std::cout<<_Bgraphe[*v_it];
 
 
}
  boost::add_edge(v1, v2, _Bgraphe); 
 
std::cout << "edges(g) = ";
    graph_traits<Graph>::edge_iterator ei, ei_end;
 
  for (tie(ei, ei_end) = edges(_Bgraphe); ei != ei_end; ++ei)
      {
std::cout<<"source ";
 std::cout << boost::source(*ei, _Bgraphe);std::cout << "\n cible ";
 std::cout << boost::target(*ei, _Bgraphe);

[3DArchi]

Bonjour,
Si ça peut t'aider, il y a un tutoriel Boost.Graph : Implémentation des graphes en C++ par Matthieu Brucher disponible dans la page tutoriel.

[nina2007]

oui...J'ai vu ce lien Merci
mais boost graph c'est tellement compliquée
j'arrive pas à comprendre trés bien son principe

[JulienDuSud]

oui...J'ai vu ce lien Merci
mais boost graph c'est tellement compliquée
j'arrive pas à comprendre trés bien son principe

Ben Boost::Graph, c'est l'arsenal lourd pour effectuer des opérations sur des graph.

Il est assez complet mais c'est vrai qu'il est très lourd pour une utilisation simple. Il serait préférable d'implémenter ta propre structure de graph si tu travailles pas avec des centaines de milliers de noeuds...

[nina2007]

oui tu as raison...sauf que là, je dois manipuler des graphes avec des cycles
et je voudrai utiliser des algos prêts et efficace tel que le tri topologique
(qui existe en boost graph)
par contre, j'aurai aussi besoin d'un algo de détection de cycle...est ce que ça existe d'aprés toi?

merci

[CedricMocquillon]

Tu mets des poids négatifs sur tes arcs (-1) en ajoutant un super noeud source (connecté à tout tes noeuds du graphe) et un super noeud puits (connecté à tout tes noeuds du graphe) et tu cherches le plus court chemin de la source au puits avec Bellman

[nina2007]

au fait je suis encore loin de cette tache là...Je suis encore dans la phase construction du graphe
mais merci pour ta réponse. Je m'en servirai à temps