local/global dans un algo de parcours de graphe
Pierre-Alain Millet
pierre-alain.millet at insa-lyon.fr
Tue Apr 15 20:37:33 CEST 2008
petit nouveau sur scilab, je travaille sur des graphes issus de
modèle de système d'information.
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...)
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)
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..
je pense que c'est une question de local/global, mais je n'ai pas
encore trouvé...
donc, merci d'avance de toute aide
1/ sur l'objectif lui même... surtout si ca existe déja en beaucoup
plus simple
2/ sur l'utilisation par exec() et les conséquences sur la portée
des variables..
pam
ci-dessous, l'algo
//----------------TROUVELESCHEMINS DE LONGUEUR N
// fonction pour trouver le numéro d'une arete dans un graphe à partir
de ses sommets
function a=arete(s1,s2,g) //renvoie le numéro de l'arete dans le
graphe g par une recherche dans tail/head
a = 0;
warning(msprintf('%s %d %d','cherche arete pour ',s1,s2));
for i=1:edge_number(g) // pour toutes les aretes du graphe
if (g.tail(i)== s1)&(g.head(i)==s2)
a=i // si c'est la bonne...
elseif (g.tail(i)== s2)&(g.head(i)==s1)
a=i // si c'est l'inverse... pourra permettre de renvoyer
un flag direct/inverse ?
end,
end
pause
endfunction
// fonction qui renvoie les chemins possibles de longueur n à partir
d'un sommet s
// comme on veut boucler aux différentes longueurs possibles et qu'il
y en a peu,
// on va faire une matrice sur 3 dimensions, pour construire les
chemins de longueur n par extension de ceux de l n-1
// tna(c,i,L) est la ieme arete du chemin c de longueur L
// tns(c,i,L) est le ieme sommet du chemin c de longeur L
// comme le ieme sommet du chemin est le début de la ieme arete pour
le graphe g on a
// g.tail(tna(c,i,:))==tns(c,i,:)
// g.head(tna(c,i,:)==tns(c,i+1,:)
//on boucle sur L pour construire les chemins de longueur 1, puis 2...
jusqu'au max
// pour une longueur L on boucle sur c en remplissant le chemin
dans la ligne sur i
function [chemins,suites]=chemins(s,g,longueur) // renvoie la
matrice des chemins possibles de longueur max à partir du sommet s
// global tna = [] ; // tableau des aretes des chemins
// global tns = [] ; // tableau des étapes des chemins
// tna(c,i,L) est le numéro de la ieme arete du chemin c de longeur l (i <l )
// tns(c,i,L) est le numéro du ieme sommet du chemin c de longueur...
chemins=[];
suites=[];
// initialisation des tableaux pour les chemins de longueur 1 = les
voisins de s
i=1;
L=1;
for v=neighbors(s,g),
tna(i,1,L)=arete(s,v,g), // de longueur 1, il n'y a qu'une arete
tns(i,1,L)=s, tns(i,2,L)=v , // et deux sommets...
i=i+1,
end // on a fait les chemins de longueur 1 à partir de s
// boucle qui passe de la longueur L-1 à la longueur L
for L=2:1:longueur // on avance par longueur (en largeur d'abord),
donc à partir de la longueur 2
s=size(tna(:,1,L-1))// dimensions de la matrice des premières
aretes de chemin de longueur L-1
ncl=s(1) // donne le nombre de chemins de longueur L-1
// on se place sur le premier sommet fin du
premier chemin de longueur L-1
// ie : tns(1,L,L-1) pour le premier coup,
c'est le premier suivant de s
// warning(msprintf('%s %d','boucle pour longueur',L));
cs=1; // on initialise le compteur de chemin de longueur L
for cp=1:ncl, // pour tous les chemins précédent, on va
avancer en complétant les chemins de longueur L
// tns(cp,L,L-1) est le sommet sur lequel je
suis (dernier sommet du chemin cp)
// tna(cp,L-1,L-1) est l'arete d'ou je viens
// donc g.head(tna(cp,L-1,L-1))== tns(cp,L,L-1)
// if g.head(tna(cp,L-1,L-1))== tns(cp,L,L-1)
, , else warning "erreur sur L,cp ", L, cp, end
//je cherche les suivants de tns(cp,L,L-1)
warning(msprintf('%s %d','boucle pour chemin precédent',cp));pause
for voisin=neighbors(tns(cp,L,L-1),g)
// je cherche le numéro de l'arete
correspondant au voisin
a = arete(tns(cp,L,L-1),voisin) // si arete deja
vu, je passe
warning(msprintf('%s %d','trouve arete ',a));pause
dejavu= 0; for k=1:L-1, tna(cp,k,L-1), if a ==
tna(cp,k,L-1), dejavu =1; end, end ;
if dejavu == 1, // rien à faire on ne boucle pas...
warning(msprintf('%s %d','deja vu',a)); pause ;
else // j'ai un nouveau chemin sur lequel
avancer à remplir dans la matrice L
warning(msprintf('%s %d','pas deja vu',a)); pause ;
for k=1:L-1 // les chemins de longueur L commencent
par leur racine de longueur L-1
// warning(msprintf('%s %d','recopie chemin
L-1 pour la position',k));
tna(cs,k,L)=tna(cp,k,L-1),
tns(cs,k,L)=tns(cp,k,L-1),
end
// warning(msprintf('%s %d','nouveau chemin
cree', cs)); pause
tns(cs,L,L)=tns(cp,L,L-1); // ne pas oublier le
dernier sommet précédent
tna(cs,L,L)= a ; // je memorise la
nouvelle arete
tns(cs,L+1,L)=voisin; // et le nouveau voisin
cs=cs+1; //j'avance sur mes
chemins de longueur L
warning(msprintf('%s %d','ouvrir chemin
suivant', cs)); pause
end
end
end
end
warning(msprintf('%s %d','fin boucle générale avec nb chemin:', cs-1)); pause
chemins = tna(:,:,longueur);
suites=tns(:,:,longueur);
endfunction
//-----------------------------------------------------------
// exemple
// [ch,ss]=chemins(1,g,3);
// ch : liste des chemins de longueur 3 à partir du sommet 1
// ss : suites des sommets des chemins correspondants
//-----------------------------------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.scilab.org/pipermail/users/attachments/20080415/62aa0b92/attachment.htm>
More information about the users
mailing list