Juliaで可到達行列を求める - システムとモデリング

DSM(DesignStructureMatrix)のシーケンシングに必要なDSMの可到達行列をJuliaのプログラムで求めてみます。

可到達行列とは

以下のスライドの説明がわかりやすいと思います。

http://ise.me.tut.ac.jp/lectures/decision-making/DSS12-2.pdf

f:id:Otepipi:20190528052034p:plain

DSMの隣接行列Aに単位行列Iを足した $(A+I)$ を、n乗して $(A+I)^{n} = (A+I)^{n-1}$ となったときの $(A+I)^{n}$ が可到達行列です。ただし、このときの行列の演算はブール演算になります。

$1 \times 1 = 1$
$1 \times 0 = 0$
$1 + 1 = 1$
$1 + 0 = 0$

何に使うのか

この演算で得た可到達行列法を一定のアルゴリズムでレベル分けすることで、DSMのシーケンシングが可能になります。（以下の記事を参照）

otepipi.hatenablog.com

Juliaでの実装

Juliaでの実装は以下のようになります。

using LinearAlgebra

function calcReachableMatrix(DSM)

    I = zeros(size(DSM)) + Diagonal(ones(size(DSM))); #単位行列の生成

    calcmax = 1000

    for i  = 1 : calcmax
        

       global R1 = (DSM+I)^i
        (Rindex) =findall(x-> 1<x , R1);
        R1[Rindex] = ones(size(Rindex)); #ブール演算のかわり

        R2 = (DSM+I)^(i+1)
        (Rindex) =findall(x-> 1<x , R2);
        R2[Rindex] = ones(size(Rindex)); #ブール演算のかわり

        if R1 == R2
            break
        end
  
    end

    return R1
end

DSM = [0 0 0 0 1 0;1 0 1 1 1 0;0 0 0 1 1 0; 0 0 1 0 0 0 ; 0 0 0 0 0 0; 0 1 0 0 1 0 ]; #DSMの定義

Reachablematrix = calcReachableMatrix(DSM)

元のDSMは以下のようなものです

julia> DSM
6×6 Array{Int64,2}:
 0  0  0  0  1  0
 1  0  1  1  1  0
 0  0  0  1  1  0
 0  0  1  0  0  0
 0  0  0  0  0  0
 0  1  0  0  1  0

それが今回のプログラムによって可到達行列に変換されます。

julia> calcReachableMatrix(DSM)
6×6 Array{Float64,2}:
 1.0  0.0  0.0  0.0  1.0  0.0
 1.0  1.0  1.0  1.0  1.0  0.0
 0.0  0.0  1.0  1.0  1.0  0.0
 0.0  0.0  1.0  1.0  1.0  0.0
 0.0  0.0  0.0  0.0  1.0  0.0
 1.0  1.0  1.0  1.0  1.0  1.0

これでDSMのシーケンシングをJuliaで実行するのに1歩近づきました。

今回はここまでにします。