spcompack

ユーティリティ関数spcompakは圧縮隣接形式を
標準隣接形式に変換する際に使用されます.

// A is the sparse matrix:
A=[1,0,0,0,0,0,0;
   0,1,0,0,0,0,0;
   0,0,1,0,0,0,0;
   0,0,1,1,0,0,0;
   0,0,1,1,1,0,0;
   0,0,1,1,0,1,0;
   0,0,1,1,0,1,1];
A=sparse(A);
//この行列の場合,標準隣接形式は以下のように定義されます:
xadj=[1,2,3,8,12,13,15,16];
adjncy=[1, 2, 3,4,5,6,7, 4,5,6,7, 5, 6,7, 7];
//(sp2adj参照).
// ベクトル xadjの増分は,各列の非ゼロ要素の数を指定します.
// すなわち,列1には 2-1=1個のエントリが存在
//          列2には 3-2=1個のエントリが存在
//          列3には 8-3=5個のエントリが存在
//          列3には 12-8=4個のエントリが存在
//  など
// これらのエントリの行インデックスは隣接ベクトルにより例えば
// 以下のように指定でます
// adjncy (3:7)=adjncy(xadj(3):xadj(4)-1)=[3,4,5,6,7] 
// これは, 列3の5=xadj(4)-xadj(3)個のエントリのインデックスを
// 3,4,5,6,7 としたことを意味します.

// 圧縮表現では,隣接する重複するシーケンスは消去されます.
// ここで,隣接表現では並び 4,5,6,7および7が消去されます.
// 標準構造(xadj,adjncy)は圧縮形式(lindx,xlindx)を受け付けます
lindx=[1, 2, 3,4,5,6,7, 5, 6,7];
xlindx=[1,2,3,8,9,11];
//(Aの列 4 および 7は消去されます).
//Aは(xadj,xlindx,lindx)により再構築できます.
[xadj,adjncy,anz]= sp2adj(A);
adjncy-spcompack(xadj,xlindx,lindx)