Méthode de malgrange (améliorée) pour chercher les composantes fortement connexes d'un graphe orienté

0/5 (5 avis)

Vue 10 492 fois - Téléchargée 1 021 fois

Description

Ce code implémente une classe de recherche de composantes fortement connexes d'un graphe orienté quelconque. J'ai utilisé la méthode de Malgrange un petit peu améliorée au niveau du calcul de la puissance de la matrice associée (au lieu de calculer M^k, je calcule (I+M)^(2^i) qui permet d'avoir une complexité moins importante : O(n^4) contre O(n^3*log(n)).

L'interêt est bien sur de trouver ces composantes très rapidement en entrant les successeurs des sommets de votre graphe et il les affiche.

J'implémenterais peut-être une interface graphique un jour parce que le mode console c'est moyen pour du C++ ^^

Voila, comme d'habitude je suis ouvert à toutes remarques/critiques/améliorations etc. :)

Codes Sources

A voir également

Ajouter un commentaire Commentaires
PCBill Messages postés 48 Date d'inscription lundi 25 décembre 2006 Statut Membre Dernière intervention 29 septembre 2009
25 févr. 2008 à 20:15
Merci pour votre code, mais apparemment ça ne marche pas du tou :
j'ai essayé plusieurs exemples, et au lieu d'afficher les composantes fortement connexes, il m'affiche les sommets du graph !!!! votre réaction ?

merci.
yann_lo_san Messages postés 1137 Date d'inscription lundi 17 novembre 2003 Statut Membre Dernière intervention 23 janvier 2016 23
23 mars 2007 à 17:09
En modélisation objet, ton proto 'Produit_matriciel' se définit en tant qu'outil de toutes les instances de ta classe, donc bien en tant que fonction globale à ta classe, c.a.d méthode static.
En Java ou en C# ce serait le cas.
Mais cela reste de la forme et non du fond.
Bonne continuation.
rabbbi Messages postés 3 Date d'inscription jeudi 21 septembre 2006 Statut Membre Dernière intervention 23 mars 2007
23 mars 2007 à 08:20
A la fin de Cgraph::Malgrange() on doit ajouter :

for(int i=0;i<m_size_alpha;i++)
{
delete[] *(I+i);
}

Cela libère la place prise par la matrice Identité

Omission de ma part sry :)
rabbbi Messages postés 3 Date d'inscription jeudi 21 septembre 2006 Statut Membre Dernière intervention 23 mars 2007
23 mars 2007 à 07:51
Salut,

"A quoi sert donc ton destructeur qui ne libère aucune des multiples allocations que tu fais" : --> bonne question ^^ il faut que je mette le nouveau code mis à jour desolé :-/

"Pourquoi ne pas faire une méthode statique à la place d'un proto qui tombe du ciel après ta class." :
--> Le proto ne "tombe pas du ciel". Si tu as bien lu le code tu verra que ce produit matriciel s'applique à des matrices qui ne sont pas membres de la classe. Il y a plusieurs possibilités de traiter cela : j'ai choisi la fonction en dehors de ma classe : c'est un choix ...

Concernant les noms des membres, c'est vrai que je n'ai pas pris le temps de bien les ecrire je vais corriger cela (ce code a été codé rapidement pour me servir dans d'autres applications sur les graphes mais bon je vais rectifier si ca dérange)

Merci de ton commentaire en tout cas ;) ++
yann_lo_san Messages postés 1137 Date d'inscription lundi 17 novembre 2003 Statut Membre Dernière intervention 23 janvier 2016 23
23 mars 2007 à 01:14
Salut,
A quoi sert donc ton destructeur qui ne libère aucune des multiples allocations que tu fais ?
Pourquoi ne pas faire une méthode statique à la place d'un proto qui tombe du ciel après ta class.
Certain membre commencent par m_... d'autres non, c'est limite question lisibilité.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.