Discussion :

[ralf91]

Bonjour,

J'ai une une liste de points stockés dans une liste Vector, en fait j'ai plusieurs liste de points, chaque liste décrit un chemin, je souhaiterais transformer ces liste en un seul graphe (structure de donnée de type graphe) qui contient mes points comme nœud et les nœuds attachés à ce nœud comme nœuds fils ?

j'ai vu rapidement Boost sur ce site, mais je pense que c'est assez compliqué pour ce que je veux faire ! car en fait moi je veux juste créer le graphe et le parcourir c'est tout ?

auriez vous une piste pour le faire ?
merci pour votre aide

[ZiGoM@r]

Pour la structure, quelque chose comme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class GraphNode
{
    [...]
 
    // fonction parcourir
 
    [...]
 
    std::vector<GraphNode*> edges;
 
    Point pos; // si besoin
 
};

Pour la conversion vers cette structure, une map<Point, GraphNode*> pour retrouver l'adresse des nœuds correspondants à insérer dans la liste des arêtes du nœud précédent devrait suffire.

[bretus]

Bonsoir,

@ralf91, Je t'avoue que j'ai trouvé les graphes boost très déstabilisant au début, mais je pense qu'ils méritent d'être étudiés si tu te mets à faire du traitement de graphe.

Le plus dur consiste à choisir la structure adaptée à ton problème (les différents paramètres de adjacency_list http://www.boost.org/doc/libs/1_47_0...ing-graph-type) et à comprendre que la structure influence les fonctionnalités disponibles.

Comme souvent dans boost, il manque une "facade" pour les besoins simples où l'on veut que ça marche, même de façon sous-optimale (un peu comme std::find sur un vecteur).

j'ai vu rapidement Boost sur ce site, mais je pense que c'est assez compliqué pour ce que je veux faire ! car en fait moi je veux juste créer le graphe et le parcourir c'est tout ?

Le fait est que tu vas vite vouloir parcourir les arcs sortant d'un sommet sans parcourir la liste complète des arcs, associer des informations aux sommets et aux arcs, etc... D'où l'intérêt d'apprendre à se servir de boost::graph plutôt que de passer 3 fois plus de temps à monter ta propre structure.


PS :
- ZiGoM@r ton graphe ressemble beaucoup à un arbre. En outre, il est impossible d'associer la moindre information aux arcs/arrêtes du graphe. Ensuite, niveau parcours, il manque un truc.
- La façon la plus simple de représenter un graphe dans le "cas général" (arcs parallèles, orienté ou non, ...) consiste à gérer une liste d'arcs matérialisés par un sommet source et un sommet cible. Ca marche plutôt bien en BDD où l'on peut indexer la source et la cible... Pour le reste, la recherche des arcs incidents à un sommet est lente.

[gbdivers]

Bonjour

Quelques notes permettant d'utiliser boost.graph (version simple et généraliste, donc pas optimisée en fonction d'une problématique spécifique) :

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <boost/graph/adjacency_list.hpp>
 
// Les structures qui contiennent les informations sur les vertices, edges et graph
struct EdgeProperties { std::string name; unsigned id; };
struct VertexProperties { ... };
struct GraphProperties { ... };
 
// un graph générique
typedef boost::adjacency_list 
   <boost::vecS, boost::vecS, boost::bidirectionalS,
   boost::property<boost::vertex_bundle_t, VertexProperties>,  // vertex properties
   boost::property<boost::edge_bundle_t, EdgeProperties>,  // edges properties
   boost::no_property  // graph properties (pas de propriétés pour le graph ici mais on pourrait utiliser GraphProperties aussi)
> Graph;
 
Graph  g;
 
// Ajout vertex
const Graph::vertex_descriptor v1 = boost::add_vertex(VertexProperties(...), g);
// Accès à un vertex
VertexProperties& properties = get(boost::vertex_bundle, g)[v1];
 
// Création d'un edge
const std::pair<Graph::edge_descriptor, bool> e1 = boost::add_edge(v1, v2, EdgeProperties{...}, g);
// Accès à un edge
if (e1.second)
   get(boost::edge_bundle, g)[e1.first] = EdgaData{"Edge 1", 5};
 
// Récupérer tous les vertices
std::pair<vertex_iterator_t, vertex_iterator_t> iterators = boost::vertices(g);
// Nombre de vertices
boost::graph_traits<Graph>::vertices_size_type s = num_vertices(g);
 
// Récupérer tous les edges
std::pair<edge_iterator_t, edge_iterator_t> iterators = boost::edges(g);
// Récupérer les edges partant d'un vertex
std::pair<out_edge_iterator_t, out_edge_iterator_t> iterators = boost::out_edges(v1, g);
// Récupérer les edges arrivant sur un vertex
std::pair<in_edge_iterator_t, in_edge_iterator_t> iterators = boost::in_edges(v1, g);
// récupérer les vertices adjacent à un vertex
std::pair<adjacency_iterator_t, adjacency_iterator_t> iterators = = adjacent_vertices(v1, g);
// récupérer un vertex a partir d'un edge
Graph::vertex_descriptor v1 = boost::source(e1.first, g);
Graph::vertex_descriptor v2 = boost::target(e1.first, g);

Avec cela, tu as les fonctions de base pour manipuler les graph de boost. Ensuite, tu utilises les itérateurs fournis avec les algorithmes standards de la STL.

Par contre, même si le code que j'ai donné est relativement simple, il est bien sur préférable d'apprendre correctement boost.graph (il existe un livre spécifiquement pour cette bibliothèque : The Boost Graph Library - User Guide and Reference Manual, de Jeremy Siek)

[bretus]

Bonjour,

Bonne initiative gbdivers, j'avais la flemme

Sinon, voir dans boost/libs/graph/example.

[ralf91]

Bonjour,

Merci pour vos réponses,
Je n'ai pas besoin de nommer ni les sommets ni les aretes, en effet, j'ai une liste de points, deux points de la liste qui sont dans deux cases successives doivent etre "reliés", je vais l'expliquer à travers un exemple c'est plus simple :
Soit la liste :

p1 p2 p3 p4 p5

cela veut dire que p1 a p2 comme fils (voisins) p2 a p1 et p3 comme voisins, p3 a p2 et p4 etc.

c'est tout ce que je veux faire, ensuite, je dois bien-sur pouvoir le parcourir ! vous pensez que c'est vraiment plus rapide de passer par boost::Graph ?

[bretus]

Bonjour,

Est-ce que tu reconnais deux points identiques au sein de deux listes de points?

p1 p2 p3 p4 p5
p6 p2 p7 p8 p1

Tu veux faire quels genres de parcours?

[ralf91]

oui, j'ai presque dans tous les cas un point d'une liste qui apparait dans une autre liste pour que le tout soit connexe.

Pour le parcours j'ai pensé à ajouter un attribut "marqueur" pour indiqué si je suis déjà passé par ce nœud ou pas.