<?xml version="1.0" encoding="ISO-8859-1" standalone="no"?> 
<!DOCTYPE MAN SYSTEM "../../manrev.dtd">
<MAN>
  <LANGUAGE>fr</LANGUAGE>
  <TITLE>bandwr  </TITLE>
  <TYPE>Scilab function  </TYPE>
  <DATE>September 1996  </DATE>
  <SHORT_DESCRIPTION name="bandwr"> réduction de largeur de bande pour une matrice creuse  </SHORT_DESCRIPTION>
  <CALLING_SEQUENCE>
  <CALLING_SEQUENCE_ITEM>[iperm,mrepi,prof,ierr] = bandwr(sp,[iopt])  </CALLING_SEQUENCE_ITEM>
  <CALLING_SEQUENCE_ITEM>[iperm,mrepi,prof,ierr] = bandwr(lp,ls,n,[iopt])  </CALLING_SEQUENCE_ITEM>
  </CALLING_SEQUENCE>
  <PARAM>
 <PARAM_INDENT>
  <PARAM_ITEM>
  <PARAM_NAME>sp  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : matrice creuse
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>lp  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers 
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>ls  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>n  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : entier
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>iopt  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : entier 
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>iperm  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>mrepi  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>prof  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : vecteur ligne d&apos;entiers
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
  <PARAM_ITEM>
  <PARAM_NAME>ierr  </PARAM_NAME>
  <PARAM_DESCRIPTION>
  <SP>
    : entier 
</SP>
  </PARAM_DESCRIPTION> 
  </PARAM_ITEM>
 </PARAM_INDENT>
  </PARAM>
  <DESCRIPTION>
  <P>
    <VERB>bandwr</VERB> résout le problème de la réduction de largeur de bande pour 
    une matrice creuse : la matrice est supposée triangulaire supérieure avec 
    une diagonale pleine.
  </P>
  <P>
    Dans la première séquence d&apos;appel, <VERB>sp</VERB> désigne une matrice creuse; 
    l&apos;argument optionnel <VERB>iopt</VERB> vaut 0 ou 1 : 1 si
    réduire le profil de la matrice est plus important que réduire la largeur 
    de bande et 0 si la largeur de bande est plus important.
  </P>
  <P>
    La deuxième séquence d&apos;appel correspond à la  description d&apos;un graphe :
    <VERB>lp</VERB> est un vecteur ligne de pointeurs de la description du 
    graphe sous forme de liste d&apos;adjacence (sa taille est le nombre de sommets 
    du graphe + 1);
    <VERB>ls</VERB> est un vecteur ligne, tableau de sommets de la description du 
    graphe sous forme de liste d&apos;adjacence (sa taille est le nombre d&apos;arêtes 
    du graphe, c&apos;est à dire le nombre de termes non-nuls de la matrice creuse 
    associée).
    <VERB>n</VERB> est le nombre de sommets (dimension de <VERB>sp</VERB>).
  </P>
  <P>
    <VERB>iperm</VERB> est le vecteur de la permutation pour réordonner les lignes et 
    les colonnes, qui réduit la largeur de bande et/ou le profil (nouvelle 
    numérotation des sommets du graphe).
    <VERB>mrepi</VERB> est la permutation inverse (mrepi(iperm) est l&apos;identité).
    <VERB>prof</VERB> est le tableau donnant le profil de la matrice creuse
    après la réduction de largeur de bande si <VERB>iopt</VERB> vaut 1. Si <VERB>iopt</VERB> 
    vaut 0 ce tableau est nul sauf pour le premier terme, donnant alors la 
    largeur de bande.
    La simple commande <VERB>max(prof(2:$)-prof(1:($-1)))</VERB> renvoie
    la largeur de bande de la matrice.
    <VERB>ierr</VERB> est un entier indiquant une erreur si sa valeur est non nulle.
  </P>
  </DESCRIPTION>
  <EXAMPLE><![CDATA[
ta=[2  1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7 7 11 13 15 12 13  9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
// LE GRAPHE
show_graph(g);
a=graph_2_mat(g,'node-node');
ww=tril(a)'+eye();
ww1=full(ww);
xset('window',1)
hist3d((ww1+tril(ww1',-1)+tril(ww1,-1)'),52,85); 
// RÉDUCTION DE LARGEUR DE BANDE POUR LA MATRICE
[iperm,mrepi,prof,ierr]=bandwr(ww);
max(prof(2:$)-prof(1:($-1)))
// GRAPHE AVEC LA NOUVELLE NUMÉROTATION
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new')
// NOUVELLE MATRICE
n=g('node_number');
yy=ww1(mrepi,mrepi);
xset('window',3)
hist3d((yy+tril(yy',-1)+tril(yy,-1)'),52,85); 
// ON COMMENCE AVEC LA MÊME MATRICE
[ij,v,mn]=spget(ww);
g1=make_graph('foo',0,n,ij(:,1)',ij(:,2)');
g1('node_x')=g('node_x');g1('node_y')=g('node_y');
// GRAPHE
//show_graph(g1,'rep');
[lp,la,ls] = adj_lists(1,n,g1('tail'),g1('head'));
[iperm,mrepi,prof,ierr]=bandwr(lp,ls,n,0);
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new');
 ]]></EXAMPLE>
</MAN>
