<p>petit nouveau sur scilab, je travaille sur des graphes issus de modèle de
système d'information.</p><p>j'ai besoin de trouver pour un sommet s d'un
graphe, la liste des aretes accessibles par un chemin de longueur inférieure à
un max (ce max étant du genre la moitié du diametre du graphe). je commence par
la liste des chemins de longueur = max (le graphe étant non orienté, et le max
étant inférieur au diametre, mes chemins ne font pas tout le graphe...)</p><p>je
n'ai pas trouvé de fonctions toute faite, et je me suis lancé dans un algo basé
sur une matrice à trois dimensions.... (ci-dessous) </p><p>ca fonctionne, mais
quand je mets cette fonction dans un fichier et que je l'appelle par exec(),
j'ai des comportements curieux de variables non définies..<br /><br />je pense
que c'est une question de local/global, mais je n'ai pas encore trouvé...
</p><p>donc, merci d'avance de toute aide</p><p>1/ sur l'objectif lui même...
surtout si ca existe déja en beaucoup plus simple</p><p>2/ sur l'utilisation par
exec() et les conséquences sur la portée des
variables..</p><p>pam</p><p>ci-dessous,
l'algo</p><p>//----------------TROUVELESCHEMINS DE LONGUEUR N<br />// fonction
pour trouver le numéro d'une arete dans un graphe à partir de ses sommets<br
/>function a=arete(s1,s2,g) //renvoie le numéro de l'arete dans le graphe g par
une recherche dans tail/head<br /> a = 0;<br /> warning(msprintf('%s %d
%d','cherche arete pour ',s1,s2));<br /> for i=1:edge_number(g) // pour
toutes les aretes du graphe<br /> if (g.tail(i)== s1)&(g.head(i)==s2)
<br /> a=i // si c'est la bonne...<br /> elseif (g.tail(i)==
s2)&(g.head(i)==s1) <br /> a=i // si c'est l'inverse... pourra
permettre de renvoyer un flag direct/inverse ?<br /> end,<br /> end<br
/> pause<br />endfunction<br /><br />// fonction qui renvoie les chemins
possibles de longueur n à partir d'un sommet s<br />// comme on veut boucler aux
différentes longueurs possibles et qu'il y en a peu, <br />// on va faire une
matrice sur 3 dimensions, pour construire les chemins de longueur n par
extension de ceux de l n-1<br />// tna(c,i,L) est la ieme arete du chemin c de
longueur L <br />// tns(c,i,L) est le ieme sommet du chemin c de longeur L<br
/>// comme le ieme sommet du chemin est le début de la ieme arete pour le graphe
g on a <br />// g.tail(tna(c,i,:))==tns(c,i,:) <br />//
g.head(tna(c,i,:)==tns(c,i+1,:)<br /><br /><br />//on boucle sur L pour
construire les chemins de longueur 1, puis 2... jusqu'au max<br />// pour une
longueur L on boucle sur c en remplissant le chemin dans la ligne sur i<br /><br
/>function [chemins,suites]=chemins(s,g,longueur) // renvoie la matrice des
chemins possibles de longueur max à partir du sommet s<br />// global tna = [] ;
// tableau des aretes des chemins <br />// global tns = [] ; //
tableau des étapes des chemins <br />// tna(c,i,L) est le numéro de la ieme
arete du chemin c de longeur l (i <l )<br />// tns(c,i,L) est le numéro du
ieme sommet du chemin c de longueur...<br />chemins=[];<br />suites=[];<br />//
initialisation des tableaux pour les chemins de longueur 1 = les voisins de s<br
/>i=1;<br />L=1;<br />for v=neighbors(s,g), <br /> tna(i,1,L)=arete(s,v,g),
// de longueur 1, il n'y a qu'une arete<br /> tns(i,1,L)=s, tns(i,2,L)=v , //
et deux sommets...<br /> i=i+1, <br /> end // on a fait les
chemins de longueur 1 à partir de s<br /> <br />// boucle qui passe de la
longueur L-1 à la longueur L<br />for L=2:1:longueur // on avance par
longueur (en largeur d'abord), donc à partir de la longueur 2<br />
s=size(tna(:,1,L-1))// dimensions de la matrice des premières aretes de chemin
de longueur L-1<br /> ncl=s(1) // donne le nombre de chemins de
longueur L-1<br /> // on se place sur le premier sommet
fin du premier chemin de longueur L-1 <br /> // ie :
tns(1,L,L-1) pour le premier coup, c'est le premier suivant de s<br /> //
warning(msprintf('%s %d','boucle pour longueur',L));<br /> cs=1;
// on initialise le compteur de chemin de longueur L<br /> for
cp=1:ncl, // pour tous les chemins précédent, on va avancer en complétant
les chemins de longueur L<br /> // tns(cp,L,L-1) est le
sommet sur lequel je suis (dernier sommet du chemin cp)<br />
// tna(cp,L-1,L-1) est l'arete d'ou je viens <br />
// donc g.head(tna(cp,L-1,L-1))== tns(cp,L,L-1) <br /> //
if g.head(tna(cp,L-1,L-1))== tns(cp,L,L-1) , , else warning "erreur sur
L,cp ", L, cp, end <br /> //je cherche les suivants
de tns(cp,L,L-1)<br /> warning(msprintf('%s %d','boucle pour chemin
precédent',cp));pause<br /> for voisin=neighbors(tns(cp,L,L-1),g)<br
/> // je cherche le numéro de l'arete correspondant
au voisin<br /> a = arete(tns(cp,L,L-1),voisin) // si arete
deja vu, je passe<br /> warning(msprintf('%s %d','trouve arete
',a));pause<br /> dejavu= 0; for k=1:L-1, tna(cp,k,L-1), if a ==
tna(cp,k,L-1), dejavu =1; end, end ;<br /> if dejavu == 1, // rien
à faire on ne boucle pas...<br /> warning(msprintf('%s
%d','deja vu',a)); pause ;<br /> else // j'ai un nouveau
chemin sur lequel avancer à remplir dans la matrice L<br />
warning(msprintf('%s %d','pas deja vu',a)); pause ; <br />
for k=1:L-1 // les chemins de longueur L commencent par leur racine de
longueur L-1 <br /> // warning(msprintf('%s %d','recopie
chemin L-1 pour la position',k));<br />
tna(cs,k,L)=tna(cp,k,L-1),<br />
tns(cs,k,L)=tns(cp,k,L-1),<br /> end<br />
// warning(msprintf('%s %d','nouveau chemin cree', cs)); pause<br />
tns(cs,L,L)=tns(cp,L,L-1); // ne pas oublier le dernier sommet
précédent<br /> tna(cs,L,L)= a ; // je memorise
la nouvelle arete<br /> tns(cs,L+1,L)=voisin; // et
le nouveau voisin<br /> cs=cs+1;
//j'avance sur mes chemins de longueur L<br />
warning(msprintf('%s %d','ouvrir chemin suivant', cs)); pause<br />
end<br /> end<br /> end<br />end<br />warning(msprintf('%s %d','fin
boucle générale avec nb chemin:', cs-1)); pause<br />chemins =
tna(:,:,longueur); <br />suites=tns(:,:,longueur);<br />endfunction<br /><br
/>//-----------------------------------------------------------<br />//
exemple<br />// [ch,ss]=chemins(1,g,3);<br />// ch : liste des chemins de
longueur 3 à partir du sommet 1<br />// ss : suites des sommets des chemins
correspondants<br
/>//-----------------------------------------------------------<br
/></p><p></p><p></p>