Graphe non orientés et oreintés
Fermé
ValliereJodelle
Messages postés
1
Date d'inscription
mercredi 18 mai 2016
Statut
Membre
Dernière intervention
18 mai 2016
-
Modifié par ValliereJodelle le 18/05/2016 à 14:25
mamiemando Messages postés 33073 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 16 avril 2024 - 19 mai 2016 à 10:27
mamiemando Messages postés 33073 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 16 avril 2024 - 19 mai 2016 à 10:27
A voir également:
- Graphe non orientés et oreintés
- Graphe excel - Guide
- Graphe easy - Télécharger - Études & Formations
- Logiciel graphe - Télécharger - Études & Formations
- Graphe Easy - Guide
- Comment dessiner un graphe sur excel - Guide
1 réponse
mamiemando
Messages postés
33073
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
16 avril 2024
7 748
Modifié par mamiemando le 19/05/2016 à 10:32
Modifié par mamiemando le 19/05/2016 à 10:32
Bonjour,
Disons que ce que tu fais c'est un peu réinventer la roue, car tu as déjà la BGL (boost graph library) qui gère des graphes orientés, non orientés, ainsi que toutes les fonctions pour lire ou générer un fichier graphviz (et donc un rendu de graphe).
Quelque soit la nature du graphe (orienté / non orienté), tu as finalement besoin des mêmes primitives :
- accesseurs : (nombre de sommets, d'arcs, source d'un arc, cible d'un arc...) ce qui correspond dans la BGL à
- itérateurs : (itérer sur les sommets, sur les arcs, sur les arcs sortants (= sur les arcs entrants = sur les arcs entrants) d'un sommet). Selon que le graphe est orienté ou non, ces fonctions vont chercher l'information "au bon endroit". Dans la BGL ceci correspond typiquement aux fonctions et macros
D'un point de vue algébrique, tu peux voir un graphe comme une matrice M dont la case (i,j) contient l'information stockée dans l'arc (i,j). Dans le cas d'un graphe non orienté, cette matrice est symétrique, donc tu peux te contenter de stocker le triangle supérieur. Quand tu veux accéder à l'information de l'arc (i,j), tu vas en réalité accéder à M(min(i,j), max(i,j)) et ainsi toujours atterrir dans le triangle supérieur.
Voir un graphe comme une matrice pleine est une implémentation parmi tant d'autres. Si ton graphe est peu maillé, alors un grand nombre de cases contiennent l'information "pas d'arc" (typiquement la métrique infinie si ce que tes arcs stockent est la distance entre deux sommets). C'est un peu dommage de stocker quelque chose dans ce cas, on aimerait par exemple une matrice creuse pour avoir un graphe plus compact en mémoire. C'est la raison pour laquelle la BGL dont je parlais permet en plus de spécifier le stockage du graphe (voir
https://www.boost.org/doc/libs/1_37_0/libs/graph/doc/adjacency_list.html
Bonne chance
Disons que ce que tu fais c'est un peu réinventer la roue, car tu as déjà la BGL (boost graph library) qui gère des graphes orientés, non orientés, ainsi que toutes les fonctions pour lire ou générer un fichier graphviz (et donc un rendu de graphe).
Quelque soit la nature du graphe (orienté / non orienté), tu as finalement besoin des mêmes primitives :
- accesseurs : (nombre de sommets, d'arcs, source d'un arc, cible d'un arc...) ce qui correspond dans la BGL à
boost::num_vertices, boost::num_edges, boost::source, boost::target
- itérateurs : (itérer sur les sommets, sur les arcs, sur les arcs sortants (= sur les arcs entrants = sur les arcs entrants) d'un sommet). Selon que le graphe est orienté ou non, ces fonctions vont chercher l'information "au bon endroit". Dans la BGL ceci correspond typiquement aux fonctions et macros
BGL_FORALL_VERTICES, BGL_FORALL_EDGES, ....
D'un point de vue algébrique, tu peux voir un graphe comme une matrice M dont la case (i,j) contient l'information stockée dans l'arc (i,j). Dans le cas d'un graphe non orienté, cette matrice est symétrique, donc tu peux te contenter de stocker le triangle supérieur. Quand tu veux accéder à l'information de l'arc (i,j), tu vas en réalité accéder à M(min(i,j), max(i,j)) et ainsi toujours atterrir dans le triangle supérieur.
Voir un graphe comme une matrice pleine est une implémentation parmi tant d'autres. Si ton graphe est peu maillé, alors un grand nombre de cases contiennent l'information "pas d'arc" (typiquement la métrique infinie si ce que tes arcs stockent est la distance entre deux sommets). C'est un peu dommage de stocker quelque chose dans ce cas, on aimerait par exemple une matrice creuse pour avoir un graphe plus compact en mémoire. C'est la raison pour laquelle la BGL dont je parlais permet en plus de spécifier le stockage du graphe (voir
boost::vecS, boost::listSetc).
https://www.boost.org/doc/libs/1_37_0/libs/graph/doc/adjacency_list.html
Bonne chance
