[C/C++]definition de graphe
Fermé
Tartouffe
Messages postés
37
Date d'inscription
mercredi 22 août 2007
Statut
Membre
Dernière intervention
8 décembre 2011
-
5 sept. 2007 à 18:15
mamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 6 sept. 2007 à 10:20
mamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 6 sept. 2007 à 10:20
A voir également:
- [C/C++]definition de graphe
- 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
5 réponses
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 748
6 sept. 2007 à 10:20
6 sept. 2007 à 10:20
A ben si tu veux faire du C++ c'est beaucoup plus simple, tu utilises directement la lib boost. Sinon une matrice d'adjacence c'est juste une structure qui à la case (i,j) pointe vers la structure associé à l'arc (i,j). Ca décrit la moitié de ton graphe (les arcs). Il faut en plus stocker le contenu des sommets.
Si tu es prêt à passer à boost (librairie gratuite) voici les concepts importants pour débuter.
Enjeux
Boost c'est vraiment LA librairie à utiliser si tu veux manipuler des gros graphes génériques. Tu manipules les doigts dans le nez des graphes avec des milliers de sommets et de noeuds, avec des structures très propres et plein d'outils super pratiques
- la plupart des algorithmes de la théorie des graphes sont déjà implémentés (dijkstra, flot max, composantes fortement connexes...)
- il n'y a pas plus rapide
- un graphe se définit en quelques lignes de code
- c'est un peu déroutant au début mais à l'usage facile à manipuler une fois qu'on a compris les concepts.
Afin de ne pas te noyer (et comme je ne sais pas si c'est ce que tu vas utiliser au final), je vais te faire à présent une petite introduction à boost pour que tu vois les concepts, quitte à les réutiliser si tu dois/veux réimplémenter ta propre structure de graphe.
Installation
Sous linux (sachant que c'est disponible sous windows aussi, cf site de boost) il suffit d'installer le paquet de développement boost. Sous debian il suffit de taper en root :
Prérequis
Il est important que tu saches manipuler une structure template et que tu saches à quoi correspond l'opérateur :: en C++ sinon tu vas rien capter.
Il faut aussi que tu saches utiliser ton compilateur de manière un peu plus évoluée car pour compiler un programme avec boost il faut lui spécifier ou se trouvent les headers dans la librairies. Sous linux c'est en général dans /usr/include/boost, donc pour compiler plop.cpp il faut taper :
Terminologie
Pour simplifier et que tu perçoives les notations boost, je vais supposer que ta matrice d'adjacence est une matrice, donc que l'on peut décrire un sommet par un entier et un arc par une paire d'entier
- l'entier qui identifie un sommet est appelé vertex descriptor
- la paire d'entier formée d'un vertex descriptor source et d'un vertex descriptor destination est appelé edge_descriptor
- la structure associée au contenu d'un sommet est appelé vertex bundled
- la structure asoocié au contenu d'un arc est appelé edge bundled
A l'instar de la STL, boost propose d'itérer sur différents ensembles particuliers du graphe
- les sommets du graphe (vertex_iterator)
- les arcs du graphe (edge_iterator)
- les arcs sortants d'un sommet du graphe (out_edge_iterator)
- selon la manière dont ta matrice d'adjacence a été choisie tu peux éventuellement avoir aussi un in_edge_iterator (mais c'est 2 fois plus couteux en mémoire).
Parfois tu verras dans boost des histoires de traits. Ce sont simplement des structures template qui ne contiennent que des typedef.
Utilisation
La première étape c'est de définir les structures associées au vertex_bundled et edge_bundled de ton graphe. En effet les graphes boost sont en fait des structures templates (génériques) permettant d'encapsuler n'importe quelle structure de sommet ou d'arc, boost s'occupe juste de stocker intelligemment les données et de te permettre d'y accéder facilement et rapidement.
Je vais noter :
- g le graphe
- v le vertex descriptor d'un sommet
- vit le vertex_iterator de ce sommet
- node le vertex bundled de ce sommet.
- e le edge descriptor d'un arc
- eit le edge iterator de ce sommet
- link le edge bundled de ce sommet
Avec ces notations tu as les équivalences :
v <=> *vit
node <=> g[v] <=> g[*vit]
e <=> *eit
link <=> g[e] <=> g[*eit]
Les ensembles que je t'ai décris précédemment sont caractérisés par un iterator de début et un iterator de fin. Je vais noter graph_t le type du graphe boost, qu'il faut avoir défini auparavant. Exemples
Si jusque là tu as tout compris et que tu es intéressé par boost, tu peux commencer à regarder un premier exemple ici car je n'ai pas le temps de faire tout le tutoriel en une matinée :
https://www.boost.org/doc/libs/1_72_0/libs/graph/example/dijkstra-example.cpp
Bonne chance
Si tu es prêt à passer à boost (librairie gratuite) voici les concepts importants pour débuter.
Enjeux
Boost c'est vraiment LA librairie à utiliser si tu veux manipuler des gros graphes génériques. Tu manipules les doigts dans le nez des graphes avec des milliers de sommets et de noeuds, avec des structures très propres et plein d'outils super pratiques
- la plupart des algorithmes de la théorie des graphes sont déjà implémentés (dijkstra, flot max, composantes fortement connexes...)
- il n'y a pas plus rapide
- un graphe se définit en quelques lignes de code
- c'est un peu déroutant au début mais à l'usage facile à manipuler une fois qu'on a compris les concepts.
Afin de ne pas te noyer (et comme je ne sais pas si c'est ce que tu vas utiliser au final), je vais te faire à présent une petite introduction à boost pour que tu vois les concepts, quitte à les réutiliser si tu dois/veux réimplémenter ta propre structure de graphe.
Installation
Sous linux (sachant que c'est disponible sous windows aussi, cf site de boost) il suffit d'installer le paquet de développement boost. Sous debian il suffit de taper en root :
aptitude install libboost-graph-dev
Prérequis
Il est important que tu saches manipuler une structure template et que tu saches à quoi correspond l'opérateur :: en C++ sinon tu vas rien capter.
Il faut aussi que tu saches utiliser ton compilateur de manière un peu plus évoluée car pour compiler un programme avec boost il faut lui spécifier ou se trouvent les headers dans la librairies. Sous linux c'est en général dans /usr/include/boost, donc pour compiler plop.cpp il faut taper :
g++ -W -Wall -I/usr/include/boost plop.cpp
Terminologie
Pour simplifier et que tu perçoives les notations boost, je vais supposer que ta matrice d'adjacence est une matrice, donc que l'on peut décrire un sommet par un entier et un arc par une paire d'entier
- l'entier qui identifie un sommet est appelé vertex descriptor
- la paire d'entier formée d'un vertex descriptor source et d'un vertex descriptor destination est appelé edge_descriptor
- la structure associée au contenu d'un sommet est appelé vertex bundled
- la structure asoocié au contenu d'un arc est appelé edge bundled
A l'instar de la STL, boost propose d'itérer sur différents ensembles particuliers du graphe
- les sommets du graphe (vertex_iterator)
- les arcs du graphe (edge_iterator)
- les arcs sortants d'un sommet du graphe (out_edge_iterator)
- selon la manière dont ta matrice d'adjacence a été choisie tu peux éventuellement avoir aussi un in_edge_iterator (mais c'est 2 fois plus couteux en mémoire).
Parfois tu verras dans boost des histoires de traits. Ce sont simplement des structures template qui ne contiennent que des typedef.
Utilisation
La première étape c'est de définir les structures associées au vertex_bundled et edge_bundled de ton graphe. En effet les graphes boost sont en fait des structures templates (génériques) permettant d'encapsuler n'importe quelle structure de sommet ou d'arc, boost s'occupe juste de stocker intelligemment les données et de te permettre d'y accéder facilement et rapidement.
Je vais noter :
- g le graphe
- v le vertex descriptor d'un sommet
- vit le vertex_iterator de ce sommet
- node le vertex bundled de ce sommet.
- e le edge descriptor d'un arc
- eit le edge iterator de ce sommet
- link le edge bundled de ce sommet
Avec ces notations tu as les équivalences :
v <=> *vit
node <=> g[v] <=> g[*vit]
e <=> *eit
link <=> g[e] <=> g[*eit]
Les ensembles que je t'ai décris précédemment sont caractérisés par un iterator de début et un iterator de fin. Je vais noter graph_t le type du graphe boost, qu'il faut avoir défini auparavant. Exemples
graph_t::vertex_iterator vit,vend;
for(boost::tie(vit,vend)=boost::vertices(g);vit!=vend;++vit){
// le sommet courant est associé au vertex iterator vit, je parcours ici les sommets du graphe
}
graph_t::edge_iterator eit,eend;
for(boost::tie(eit,eend)=boost::edges(g);eit!=eend;++eit){
// l'arc courant est associé au edge iterator eit, je parcours ici les arcs du graphe
}
Si jusque là tu as tout compris et que tu es intéressé par boost, tu peux commencer à regarder un premier exemple ici car je n'ai pas le temps de faire tout le tutoriel en une matinée :
https://www.boost.org/doc/libs/1_72_0/libs/graph/example/dijkstra-example.cpp
Bonne chance
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 748
5 sept. 2007 à 20:50
5 sept. 2007 à 20:50
Sans plus de précision, j'imagine que tu fais simplement allusion à une structure de donnée qui encapsule un graphe G(V,E) (de la théorie des graphes), c'est à dire
- un ensemble de sommets V
- un ensemble d'arc E qui connecte deux noeuds appartenant à V, éventuellement orienté du sommet source au sommet destination.
https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes
Chaque noeud et chaque arc peut encapsuler un certains nombre d'informations :
Exemple : pour le problème de plus court chemin, les arcs stockent les métriques associées à chaque arc, et les noeuds le nom des sommets.
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
A noter que la librairie boost permet de manipuler des graphes génériques en C++.
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/dijkstra_shortest_paths.html
Bonne chance
- un ensemble de sommets V
- un ensemble d'arc E qui connecte deux noeuds appartenant à V, éventuellement orienté du sommet source au sommet destination.
https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes
Chaque noeud et chaque arc peut encapsuler un certains nombre d'informations :
Exemple : pour le problème de plus court chemin, les arcs stockent les métriques associées à chaque arc, et les noeuds le nom des sommets.
https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
A noter que la librairie boost permet de manipuler des graphes génériques en C++.
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/dijkstra_shortest_paths.html
Bonne chance
Tartouffe
Messages postés
37
Date d'inscription
mercredi 22 août 2007
Statut
Membre
Dernière intervention
8 décembre 2011
4
5 sept. 2007 à 21:17
5 sept. 2007 à 21:17
merci pour cet explication est-ce que ceci est juste:
struct noeud{
int val;
struct noeud t[2];
};
struct graphe{
struct noeud *racine;
};
struct noeud{
int val;
struct noeud t[2];
};
struct graphe{
struct noeud *racine;
};
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 748
6 sept. 2007 à 01:00
6 sept. 2007 à 01:00
Ca n'a aucune chance de compiler car tu définis ta structure noeud à partir d'un tableau de struct noeud. Or à ce stade le compilateur ne sais pas quelle taille en mémoire allouer donc ca va planter. La seule façon de faire en C, c'est d'utiliser des pointeurs. En effet un pointeur (une adresse) fait toujours la même taille et peut donc être utilisé.
A priori un graphe n'est pas caractérisé par un noeud racine, c'est juste une sous classe de graphe qui est concerné (les arbres). Dans ton cas je partirais plus sur un truc du genre.
Le plus simple c'est de représenter le graphe par une matrice d'adjacence. Ceci caractérise la représentation d'un graphe. Cette matrice d'adjacence peut être représentée par des listes chaînées croisées, ou directement une matrice. Tu dois programmer impérativement en C ou tu peux faire du C++ ?
A priori un graphe n'est pas caractérisé par un noeud racine, c'est juste une sous classe de graphe qui est concerné (les arbres). Dans ton cas je partirais plus sur un truc du genre.
Le plus simple c'est de représenter le graphe par une matrice d'adjacence. Ceci caractérise la représentation d'un graphe. Cette matrice d'adjacence peut être représentée par des listes chaînées croisées, ou directement une matrice. Tu dois programmer impérativement en C ou tu peux faire du C++ ?
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Tartouffe
Messages postés
37
Date d'inscription
mercredi 22 août 2007
Statut
Membre
Dernière intervention
8 décembre 2011
4
6 sept. 2007 à 09:44
6 sept. 2007 à 09:44
non non je peut faire du C++
tu pourais me donner la structure d'une matrice d'adjacence stp
tu pourais me donner la structure d'une matrice d'adjacence stp
