graphe non orientés et oreintés Fermé

Question

Bonjour à tous, 

le problème que je rencontre est le suivant:

J'ai implémenté une bibliothèque pour afficher un graphe orienté (arcs) et le lire à partir d'un fichier. Sauf que mon prof veut maintenant que je calcule le couplage max du graphe mais non orienté (arêtes) cette fois-ci. Je ne sais pas comment faire pour avoir un graphe non orienté . J'ai besoin d'idées d'implémentation svp. Je précise que la lecture du fichier se fait dans l'un des constructeurs de la classe Cgraphe

Ma bibliothèque contient: une classe Carc contenant comme attribut:

        unsigned int uiARCdestination;  //Cette variable contient le sommet destination

une classe Csommet contenant comme attributs:


Carc** pSOMarcPartant;     //cette variable contient les sommets partants

Carc** pSOMarcArrivant;   //cette variable contient les sommets arrivants

unsigned int uiSOMnumeroSommet;   //cette variable contient le numéro du sommet 

unsigned int uiSOMnombrePartant;  //cette variable contient le nombre d'arc partant

unsigned int uiSOMnombreArrivant;

une classe Cgraphe contenant comme attributs:

        Csommet** pGRAtableau;   //cette variable contient les sommets du graphe

unsigned int uiGRAnbSommet;  //cette variable contient le nombre de sommets du graphe

Merci pour votre aide

mamiemando · Answer

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 à 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::listS etc).
https://www.boost.org/doc/libs/1_37_0/libs/graph/doc/adjacency_list.html

Bonne chance

Graphe non orientés et oreintés

1 réponse

Discussions similaires