[scilab-Users] local/global dans un algo de parcours de graphe

[Pierre-Alain Millet]

point 2 résolu... comme souvent, on ne cherche pas du bon coté. Le  
problème de variable n'était qu'un pb d'initialisation dans un cas  
particulier... rien à voir avec exec() et la portée des variables..

sur le point 1, tout avis sur l'algo proposé pour trouver les chemins  
possibles est le bienvenue.... Je me dis que ca devrait exister en  
standard...

pam


Quoting Pierre-Alain Millet <pierre-alain.millet at insa-lyon.fr>:

>
>
>   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
> //-----------------------------------------------------------