Type de données abstrait graphe

Soyez le premier à donner votre avis sur cette source.

Vue 5 548 fois - Téléchargée 554 fois

Description

Hello,
Je propose une implémentation du type de données abstrait graphe. Le but étant de définir une structure complète permettant l'application de divers algorithmes (tri topologique, parcours en profondeur/largeur/..., ...). C'est un projet à but pédagogique réalisé dans le cadre des cours, l'idée étant de pouvoir définir une structure générique indépendante de l'implémentation (matrices de contiguïté, listes d'adjacences, ...).
Il s'agit là que d'une partie en pré-version d'un projet plus général mais j'aurais grandement apprécié avoir des retours et commentaires de développeurs plus expérimentés.

Concernant l'architecture générale, je me suis passablement inspiré de ce site http://www.brpreiss.com/books/opus5/html/page532.html#SECTION0017200000000000000000.

Je mets également à disposition une class de test. Elle est un peu brouillon mais permet de valider le fonctionnement du TDA. Comme il me reste encore pas mal de travail à faire sur les algorithmes, je ne les mettrai pas en ligne pour l'instant. Si cela vous intéresse, je les mettrai à disposition une fois le projet plus aboutit.

Conclusion :


Merci pour tous vos conseils et commentaires à venir :)

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

monia19
Messages postés
1
Date d'inscription
mardi 6 janvier 2009
Statut
Membre
Dernière intervention
13 avril 2010
-
je veux programmer un graphe en vb.net mais une probleme avec les arcs.
j'ai crée un procedure : design_arc( node s1, node s2)
mais j'ai pas trouvé une solution ?
help :(
cs_jojolemariole
Messages postés
519
Date d'inscription
mercredi 21 mars 2007
Statut
Membre
Dernière intervention
19 décembre 2016
21 -
Salut,

C'est une initiative intéressante, le graphe est vraiment une structure de données primordiale en informatique. Pour un petit jeu que j'avais fait, j'avais créé une structure de données équivalente, mais en rajoutant de la généricité :

interface Vertex<VertexType, EdgeType>
interface Edge<VertexType, EdgeType>

J'avais sans doute mis une contrainte sur les paramètres de généricité (genre extends Comparable ou autres) mais je n'ai plus le code sous les yeux. L'avantage est que tu peux faire un graphe de n'importe quoi plutôt que d'être limité à un ID pour identifier un sommet.

Qu'en penses-tu?

PS : je mettrai le code sur CS ce weekend.
smutsonberg
Messages postés
3
Date d'inscription
samedi 25 février 2006
Statut
Membre
Dernière intervention
5 avril 2010
-
Salut,
désolé pour la réponse tardive, je profitais des derniers jours de vacances :)

Oui tu as totalement raison, je faisais un peu n'importe quoi avec mes listes d'adjacence. En fait pour tous les arcs non dirigés je faisais des double liens. Si j'avais A --- B je créais un arc de A vers B et un autre de B vers A, ce qui n'a pas vraiment de sens ...

Donc j'ai corrigé l'erreur et modifié le comportement de getSuccessors() et getPredecessors(). A présent, ces 2 méthodes retournent les sommets suivants et précédents uniquement lorsque les arcs les reliant sont dirigés. J'ai également ajouté la méthode getNeighbors() qui, elle, retourne la liste de tous les voisins d'un sommet.

J'ai aussi corrigé quelques autres bugs, fais le ménage dans GraphAsLists et ajouté d'autres fonctionnalités. On se rapproche d'un résultat un peu plus correcte même s'il reste encore quelques bugs à gauche et à droite..

La classe TestGraph n'est pas à jour avec les derniers tests que j'ai effectués, si sa t'intéresse je pense que tu devrais pouvoir la modifier sans grande difficulté sinon dit le moi et je te fourni volontiers une classe de tests plus complète.

Encore merci pour tes commentaires :)
cs_ribouldinge
Messages postés
3
Date d'inscription
samedi 14 juillet 2007
Statut
Membre
Dernière intervention
29 décembre 2009
-
D'accord avec toi pour la terminologie, je n'avais pas vu les prédécesseurs et successeurs dans Node, que tu renseignes via les arcs, dans le test.

J'ai du mal à interpréter les résultats du test après la phase insertion des arcs :
Insertion des sommets :
0, 0, A
1, 0, B
2, 0, C
3, 0, D
4, 0, E

Insertion des arcs :
0, 1, 0, false
0, 2, 0, false
0, 4, 0, false
4, 1, 0, false
4, 2, 0, false
4, 3, 0, false

Si les arcs sont entrés avec un sens, ok pour les successeurs de 0,
mais pourquoi dans les résultats, le sommet 4 n'a-t-il pas comme prédécesseur 0 et successeurs 1,2,3?

Successeurs 0
4, 0, E
2, 0, C
1, 0, B

Predecesseurs 4
0, 0, A
1, 0, B
2, 0, C
3, 0, D
smutsonberg
Messages postés
3
Date d'inscription
samedi 25 février 2006
Statut
Membre
Dernière intervention
5 avril 2010
-
Apparemment les deux termes peuvent être utilisés pour désigné un sommet. Edge et arc sont également des synonymes cf : http://www.brpreiss.com/books/opus5/html/page522.html#SECTION0017102000000000000000

Après il ne s'agit que d'un choix de terminologie mais comme le pluriel de node est nodes et que le pluriel de vertex est vertices (sauf erreur de ma part) je trouve le premier plus commode et moins enclin à d'éventuelles erreurs d'inattentions. Après je te l'accorde, Vertex aurait très bien pu faire l'affaire :)

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.