bandwr - réduction de largeur de bande pour une matrice creuse
bandwr 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.
Dans la première séquence d'appel, sp désigne une matrice creuse; l'argument optionnel iopt 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.
La deuxième séquence d'appel correspond à la description d'un graphe : lp est un vecteur ligne de pointeurs de la description du graphe sous forme de liste d'adjacence (sa taille est le nombre de sommets du graphe + 1); ls est un vecteur ligne, tableau de sommets de la description du graphe sous forme de liste d'adjacence (sa taille est le nombre d'arêtes du graphe, c'est à dire le nombre de termes non-nuls de la matrice creuse associée). n est le nombre de sommets (dimension de sp ).
iperm 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). mrepi est la permutation inverse (mrepi(iperm) est l'identité). prof est le tableau donnant le profil de la matrice creuse après la réduction de largeur de bande si iopt vaut 1. Si iopt vaut 0 ce tableau est nul sauf pour le premier terme, donnant alors la largeur de bande. La simple commande max(prof(2:$)-prof(1:($-1))) renvoie la largeur de bande de la matrice. ierr est un entier indiquant une erreur si sa valeur est non nulle.
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');