Parcours de graphe

[Horstman]

Tout a bord Bonjour à vous,

Voila j'ai besoin d'aide sur un problème d'ordre mathématique

Je vous présente le problème : je suis informaticien étudiant, et je développe une application lier a des classe UML, plus particulièrement de métamodel et je cherche un moyen pour trouver tous les chemins entre deux classes sélectionnées.

Hors les métamodel peuvent être assimilés à des graphes pondérés a 1 ( tous les nœuds valent 1 )

De ce que je sais, on peut découvrir tous ces chemins grâce a un théorème, le théorème du point fixe, mais je suis pas sur.

Si quelqu'un peut me le confirmer, et m'expliquer ce théorème sa serait sympa,

Merci d'avance

Cordialement

Horstman

[fatal_error]

salut,

j'ai pas compris ce que tu cherches.
bon, tu taffes sur des metamodeles.
Tu représentes un meta model par une classe.
Tu veux trouver trouver tous les chemins entre deux classes.

en théorie des graphes, un chemins est composée d'une liste de noeuds.
Ici, c'est quoi les noeuds?

si la classe est un noeud, ben entre deux classes, ya pas 36 chemins...
bref, si tu peux m'(nous) éclaircir.

[Horstman]

tout a fait

"Tu représentes un metamodel par une classe." : non pas par une classe mais par un graphe

Je redéfinit :

mon métamodel peut être définit comme un graphe ou chaque nœud est une classe ( a valeur un )

Ce que je veux, c'est pouvoir trouver tous les chemins possibles entre 2 nœuds ( donc deux classes ) ( sachant aussi que les métamodels peuvent monté à plus d'une centaine de classes )

De plus je ne cherche pas le chemins le plus cours mais bel et bien TOUS les chemins possible ( c'est a dire même si je cherche le chemin du nœud A au nœud B et qu'ils sont voisins, si il existe un autre chemin je veut pouvoir le trouver )

Si vous n'arrivez pas a comprendre oubliez les métamodels
Considérez le fait que je cherche tous les chemins possibles entres deux nœuds d'un graphe. ( et donc si il existe un théorème pour sa )

Merci d'avance

Cordialement

PS: si il y a d'autre question demander moi j'essayerais d'y repondre

[fatal_error]

ok, c'est plus clair.

J'oublie les méta modeles, et je me concentre que sur le graphe de taille N (N classes)
donc numérote les noeuds 1, 2, 3...
par exemple pour trouver toutes les chemins entre 2 et 3, on peut procéder ainsi :
compter tous les chemins de longueur 1 : 2-3 =>1 chemin
compter tous les chemins de longueur 2 : 2-x-3=> N-2 chemins (si N noeuds)
compter tous les chemins de longueur 3 : 2-x-y-3 => A(2,N-2)
une fois que tas fait pour les chemins de longueur jusqu'à n, tu fais la somme et t'as ton nombre de chemins.
bon, on va quand même expliciter le nombre de chemins en fonction de n, que je note u_n.

On prend nos deux classes 2 et 3, et on les enlèves on taff donc sur un groupe de classes de taille N-2.
Now on a u_n ou n représente le nombre de noeuds qu'on intercale entre 2 et 3 :
On a donc S, le nombre total de chemins :

cette derniere somme, c'est le début du dev en série de l'exponentielle.

On peut approximer S (majoration) par

Moyennant les erreurs de calcul
Un bon truc serait de testé sur des ptits graphes a la main voir si la formule tient, mais jai pas le courage.



Edit : je viens de me rendre compte que je réponds pas à ta question. Jles ai juste comptés. Si tu veux tous les générer, on peut trivialement générer les permes pour chaque longueur du chemin, mais ya surement mieux...
cetait surement ce que t'attendais XD

[fatal_error]

jajoute que pour N = 100, c'est chiasseux. Ne serait-ce que en espace mémoire, 98! avec un encodage de ouf de tes chemins, ca fait beaucoup beaucoup.(a titre de comparaison, 1 go, c'est 10^9 octets, 98! ca fait a peu pres 10^88)...

sil sagit d'appliquer un traitement spécifique sur chaque chemin, le probleme devient temporel.

[Horstman]

Merci je viens de réaliser en effet que sa va prendre plein de place

Je vais voir pour trouver une solution moins goumande

Merci Beaucoup