CodeS-SourceS est hébergé par Frontier.fr

Cliquez ici pour mettre ce site au démarrage de votre navigateur

AccueilCodesTutorielsForumsEmploiLivresConnexion

begin process at 2008 11 22 22:21:27

TUTORIAUX EF par Matthieu MEZIL

CODEPLEX : SEADRAGON AJAX INTELLISENSE HELPER par nicoboo

VS2008 ET LE MESSAGE "UNABLE TO START DEBUGGING FOR [YOUR EXE]" par jay

SHAREPOINT 2007 : ZONES ET URL INTERNES par anouvel

.NET 4.0 / SILVERLIGHT 2 : CHANGEMENTS BRISANTS SUR LES TYPES STRING ET CHAR par coq

RE : PB CODE PROBABILITé par jeanphilippe37

DYNAMIC C par Diraam

COMPARER DEUX NOMBRES par alexey27

RE : [WIN32] COMMENT LAISSER LE STYLE WINDOWS 9* à UNE BOITE DE DIALOGUE ALORS QUE LA FENêTRE PRINCIPALE EST AU STYLE XP ? par jeffy131

RE : ECRIRE DANS UN FICHIER TEXTE AVEC ESPACES par BastienL21

+ de logiciels à télécharger

1 293 840 membres
621 nouveaux aujourd'hui
14 527 membres club

Trouver une ressource

Trouvez une ressource parmi 39 013 codes, 1 203 884 messages d'aide etc...

Recherche: dans [ Dernières recherches ]

Filtre:Tous les codes.NET uniquementExclure .NET

Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

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

Information sur la source

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é: 2 572 / 343

Auteur : rabbbi

Ecrire un message privé

Note :
Aucune note

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

Pour les "Membres Club", vous pouvez télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

CGraph.cpp 6 198 octets
Exemple_execution.txt 2 790 octets
header.h 429 octets
main.cpp 272 octets

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

POINTEURS DE FONCTIONS DANS LE CAS D'UN TRI PAR SELECTION GÉ...

COMMUNICATIONS DE DEUX PROCESS AVEC UN PIPE SOUS UNIX

Toutes les sources de rabbbi

Sources de la même categorie

[C ANSI] TAS (PRIORITY QUEUE) par coucou747

FRACTIONS_DLL, UNE DLL QUI CALCULE DES FRACTIONS par ghuysmans99

ALGORITHME POUR ÉVALUER LES EXPRESSIONS ARITHMETIQUES par shnaykhs

CONVERTISSEUR DE NOMBRE DE BASE EN BASE par G3nt002008

ALGORITHME DE DJIKSTRA par mohtouati

Toutes les sources de la catégorie Maths & Algorithmes

Sources en rapport avec celle ci

REPRESENTATION GRAPHIQUE DE DONNEES par wildhawk

CALCULER SES MOYENNES par uaip

LES GRAPHES - CYCLE HAMILTONIEN par badrsmimite

INTERPRETATION DE COMMANDE : CALCULATRICE ET DESSIN DE GRAPH... par rzomalala

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

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 Recherche : Algorithme Matrice d'Adjacence -> Dessin du graphe [ par olafleur ] Bonjour, je suis à la recherche d'un algorithme qui me permettrait de prendre la matrice d'adjacence d'un graphe et de dessiner celui-ci. Quelqu'un a 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 Insérer un graphe [ par laurielle ] Comment puis-je insérer un graphe avec des courbes temps réel dans une CDialog? Qu'est-ce qu'il faut que j'utilise?Je fais un projet MFC en Visual C++ insertion d'un graphe excel ss visual C++ [ par pipic ] Slt Peut-on insérer un graphe excel ss Visual C++ ?merciByeBye pipic... traceur de graphe en C [ par domain ] Bonjour,Je dois réaliser un traceur de graphe en C avec:- analyseur lexical- analyseur sémantique- évaluateur- afficheurje pense avoir assez bien comp Transformer une matrice en graphe [ par fred23 ] Bonjour,J'ai un tableau de type Board[i][j] à transformer en graphe.J'utilise Dev C++.Qui pourrais m'aider.Merci.Fred23.