TYPE DE DONNÉES ABSTRAIT GRAPHE
cs_ribouldinge
Messages postés
3
Date d'inscription
samedi 14 juillet 2007
Statut
Membre
Dernière intervention
29 décembre 2009
-
28 déc. 2009 à 21:16
monia19 Messages postés 1 Date d'inscription mardi 6 janvier 2009 Statut Membre Dernière intervention 13 avril 2010 - 13 avril 2010 à 04:14
monia19 Messages postés 1 Date d'inscription mardi 6 janvier 2009 Statut Membre Dernière intervention 13 avril 2010 - 13 avril 2010 à 04:14
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/51016-type-de-donnees-abstrait-graphe
https://codes-sources.commentcamarche.net/source/51016-type-de-donnees-abstrait-graphe
13 avril 2010 à 04:14
j'ai crée un procedure : design_arc( node s1, node s2)
mais j'ai pas trouvé une solution ?
help :(
5 janv. 2010 à 09:53
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.
5 janv. 2010 à 01:16
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 :)
29 déc. 2009 à 11:10
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
29 déc. 2009 à 00:33
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 :)
28 déc. 2009 à 21:16