local/global dans un algo de parcours de graphe

classic Classic list List threaded Threaded
2 messages Options
pam pam
Reply | Threaded
Open this post in threaded view
|

local/global dans un algo de parcours de graphe

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

pam pam
Reply | Threaded
Open this post in threaded view
|

Re: local/global dans un algo de parcours de graphe

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 <[hidden email]>:

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