cs_ribouldinge
Messages postés3Date d'inscriptionsamedi 14 juillet 2007StatutMembreDernière intervention29 décembre 2009
-
28 déc. 2009 à 21:16
monia19
Messages postés1Date d'inscriptionmardi 6 janvier 2009StatutMembreDernière intervention13 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.
monia19
Messages postés1Date d'inscriptionmardi 6 janvier 2009StatutMembreDernière intervention13 avril 2010 13 avril 2010 à 04:14
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és519Date d'inscriptionmercredi 21 mars 2007StatutMembreDernière intervention19 décembre 201625 5 janv. 2010 à 09:53
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é :
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és3Date d'inscriptionsamedi 25 février 2006StatutMembreDernière intervention 5 avril 2010 5 janv. 2010 à 01:16
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és3Date d'inscriptionsamedi 14 juillet 2007StatutMembreDernière intervention29 décembre 2009 29 déc. 2009 à 11:10
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
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és3Date d'inscriptionsamedi 25 février 2006StatutMembreDernière intervention 5 avril 2010 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 :)
cs_ribouldinge
Messages postés3Date d'inscriptionsamedi 14 juillet 2007StatutMembreDernière intervention29 décembre 2009 28 déc. 2009 à 21:16
Pourquoi avoir utilisé Node, Edge, mais pas Vertex?
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