begin process at 2013 05 24 01:45:34
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > MÉTHODE DE MALGRANGE (AMÉLIORÉE) POUR CHERCHER LES COMPOSANTES FORTEMENT CONNEXES D'UN GRAPHE ORIENTÉ

MÉTHODE DE MALGRANGE (AMÉLIORÉE) POUR CHERCHER LES COMPOSANTES FORTEMENT CONNEXES D'UN GRAPHE ORIENTÉ


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Classé sous :connexe, composante, graphe, malgrange Niveau :Initié Date de création :22/03/2007 Date de mise à jour :23/03/2007 08:13:58 Vu / téléchargé :6 273 / 588
Auteur : rabbbi

Ecrire un message privé
Commentaire sur cette source (5)
Ajouter un commentaire et/ou une note

 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. :)



 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

23 mars 2007 08:13:58 :
Ajout d'un destructeur utile Mise à jour du nom des données membres de la classe pour plus de lisibilité

 Sources du même auteur

Source avec Zip POINTEURS DE FONCTIONS DANS LE CAS D'UN TRI PAR SELECTION GÉ...
Source avec Zip COMMUNICATIONS DE DEUX PROCESS AVEC UN PIPE SOUS UNIX
Toutes les sources de rabbbi

 Sources de la même categorie

Source avec Zip Source avec une capture FONCTIONS EN ACTION par ringo73
CALCUL DE PI AVEC LA BIBLIOTHÈQUE GMP par lann
Source avec Zip Source avec une capture MAGEO3D, POUR GÉRER LES POINTS ET LES VECTEURS DE L'ESPACE R... par pgl10
Source avec Zip Source avec une capture ALGORITHME ACO TOILE D'ARAIGNÉE par RyBeN
Source avec Zip Source avec une capture TRAITEMENT D'IMAGE EN C++, QT par Akham75
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture REPRESENTATION GRAPHIQUE DE DONNEES par wildhawk
Source avec Zip Source avec une capture CALCULER SES MOYENNES par uaip
Source avec Zip LES GRAPHES - CYCLE HAMILTONIEN par badrsmimite
Source avec Zip Source avec une capture INTERPRETATION DE COMMANDE : CALCULATRICE ET DESSIN DE GRAPH... par rzomalala
Source avec Zip EVALUATION D'UNE EXPRESSION MATHÉMATIQUE COMPLEXE par Niels Abel

Commentaires et avis

Commentaire de yann_lo_san le 23/03/2007 01:14:08

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é.

Commentaire de rabbbi le 23/03/2007 07:51:59

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 ;) ++

Commentaire de rabbbi le 23/03/2007 08:20:37

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 :)

Commentaire de yann_lo_san le 23/03/2007 17:09:48

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.

Commentaire de PCBill le 25/02/2008 20:15:10

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.

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

graphe connexe et fortement connexe [ par zakehakim ] salut tous je cherche a un programme qui permet qui permmet de renvoie le nombre de composantes connnexe d'un graphe aide mois slvp merci d'avance fonctions sur les graphes [ par chickens ] Bonjour je ne sait si quelqu'un m'aider a faire ces fonctions ou me donner quelques idees pour m'aider a implemanter ses fonctions en C.elles sont les graphe de visibilité(road map) [ par allia007 ] A partir d’un environnement quelconque définit par des obstacles je veux créer un graphe qui permet de naviguer librement d’une arrête à une autre san le passage de parametre d'une composante [ par BedHamza ] comment faire le passage de parametre d'une composante en C++ builder par exemple : TstringGrid Conversion png en format natif [ par damd ] Bonjour, Je développe une appli embarquée qui fait du traitement d'image J'utilise des fichiers png (sans perte et avec transparence). Pour trai les états bloquants dans un graphe [ par bohi ] salut tous le monde,j'ai un projet de structure de données à propos des graphes en c,dans la 1ére étape j'ai proposé une structure de mémorisation des tracer un graphe [ par fandestargate ] Voila, apres avoir beaucoup (énormément) travaillé sur mon programme, j'ai enfin réussi a faire tout ce que je voulais faire, j'ai réussis mes iterati Les graphes [ par info8bou ] Bonjour tous le monde ; je cherche le code qui détermine si le graphe et fortement connexe ou non ,et s'il n'est pas fortement connexe afficher les co Algorithme d'affichage de graphe [ par vidalt ] Bonjour tout le monde !! :)J'ai pas mal farfouillé dans les forums pour essayer de trouver une implémentation simple d'algo affichant un graphe. Voila


Nos sponsors


Sondage...

CalendriCode

Mai 2013
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Photothèque

Photo Natur genießenPhoto Green world, abstract environmental backgrounds for your design
Photo Winter an der Nordsee, Juist, Dünen im Abendlicht 

Visiter la photothèque

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 3,058 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib [FR] AndroLib [US] FormidApps [FR] FormidApps [US]