📝

ワーシャルフロイド法をJuliaで(強引に)アニメーション

に公開
Julia
競技プログラミング
アニメーション
graphplot
tech

はじめに

競プロとかやってると、たまに聞くワーシャルフロイド法
コードは短くて悩むところないけど、これで「抜け」ないんだっけ？
とか思ったりするので、一度動画にしてみる。
Julia言語にはGraphPlotなるものがあるのでそれの練習

ワーシャルフロイド法

WikipediaとかもあるけどJuliaでは

for k ∈ 1:n , i ∈ 1:n , j ∈ 1:n
    Dist[i,j]=min(Dist[i,j],Dist[i,k]+Dist[k,j])
end
Dist  #Distは有向グラフをマトリクスにしたもの

短いです

解説

ググれば素晴らしい解説があると思いますが簡単に

負の閉路のない(クルクル回るとマイナス無限になったりしない)有向(無向)グラフで、最短の経路を求めるには
ある中継点を通った方が直通より短ければ、直通の距離をそれに書き換える。
それを各中継点で全通り調べると、それぞれ直通が最短距離の値になっている

動画

一本橋モデル

適当なランダム

動画で見たかった人は以上です
（ゆっくりみたい人は下のコード自分でいじるか、gif保存して動画プレーヤーとかで見てください）

Juliaコード

パッケージについて

あとで

using Graphs,GraphPlot,Compose,Plots
import Cairo

します。
グラフ描画にGraphs GraphPlotを用いますが、上にテキストを重ねたかったりしたので
融通を効かせる為、Compose(GraphPlotは元々この形式出力みたい)を使います。
さらに今回アニメーションにする上でPlot(ffmpeg使うだけ)、一旦png形式出力の為Cairoを使います。
Julia Programming Language Compose GraphPlot LightGraphs Positionの投稿参照

Graphs,GraphPlot について

たきろぐさんの記事を参考にしました
基本的な流れは

G1=DiGraph(5)  　　#有効グラフnode5点
add_edge!(G1,2,3)　#edge追加1
add_edge!(G1,1,4)　#edge追加2
GP=gplot(G1,layout=random_layout,nodelabel=1:5)　#描画(Jupyterとかで)


となります。
edgeの個別追加が面倒なら、マトリクスをDiGraphに食わせると0でない成分をedgeとして拾ってくれます。

Compose について

yuifuさんの記事を参考にしました

さきほどのグラフプロットに追記していきます

compose(GP1
    ,(context(), Compose.text(-0.5, -0.5, "テキストの書き込み"))
)

Plots,Cairo について

I_pppの記事(私ですが)の動画の項目でしたいのと同じなのですが、今回Composeの形式をCairoでPNGファイルにして、それをPlotsのAnimation()を使って変換します。

使ったコード

using Graphs,GraphPlot,Compose,Plots
import Cairo

"グラフマトリクスの通常描画"
function plotGraph(B;INF=10^3)
    A=copy(B)
    A[A.==INF].=0
    circleGraphPlot(A,edgelabel=filter(≠(0),A'))
end
"経路の上書き描画用"
function plotGraphVia(B,ijk=(1,1,1))
    (i,j,k)=ijk
    n=size(B)[1]
    A=zeros(n,n)
    A[i,k]=1
    A[k,j]=1
    nodefillc=[colorant"turquoise" for _ in 1:n]
    nodefillc[[i,j,k]].=colorant"orange"
#     nodefillc[k]=colorant"green"
    circleGraphPlot(A
        ,edgestrokec=[colorant"orange" for _ in 1:2]
        ,nodefillc=nodefillc
     )
end
"更新があった描画用"
function plotGraphUp(B,ijk=(1,1,1))
    (i,j,k)=ijk
    A=zeros(size(B)...)
    A[i,j]=1
    nodefillc=[colorant"turquoise" for _ in 1:n]
    nodefillc[[i,j]].=colorant"red"
    nodefillc[k]=colorant"orange"
    circleGraphPlot(A
        ,edgestrokec=[colorant"red"]
        ,nodefillc=nodefillc
     )
end
"グラフ固定描写"
function circleGraphPlot(A;kws...)
    n=size(A)[1]
    gplot(DiGraph(A)
        ,layout=circular_layout
        ,nodelabel=1:size(A)[1]
        ;kws...
    )
end
"アニメのフレーム追加"
function addAnim!(anim,draw)
    f=anim.frames
    tmpfilename=joinpath(anim.dir,string(length(f),pad=6)*".png")
    Compose.draw(PNG(tmpfilename,4inch,4inch,dpi=128),draw)
    push!(f,tmpfilename)
end
"グラフ描写(Compse形式)に文字追加"
function drawGraph(dist,ijk;Up=false,INF=10^3)
    (i,j,k)=ijk
    (ij,ik,kj)=(dist[i,j],dist[i,k],dist[k,j])
    genINF(x)= (x ≥ INF ? "INF" : x)
    output = compose(
         plotGraphVia(dist,ijk)
        ,plotGraph(dist,INF=INF)
        ,(context(), Compose.text(-1.1, -1.02, "経路$i→$k→$j: $(genINF(ik+kj)) = $(genINF(ik)) + $(genINF(kj))\n経路$i→$j  : $(genINF(ij))"))
        ,(context(), rectangle(), fill("white"))
    )
    Up && (output=compose(
            plotGraphUp(dist,ijk)
            ,(context(),Compose.text(-0.1, 0, "$(genINF(ij))→$(genINF(ik+kj)) "))
            ,output)
    )
    return output
end
"ワーシャルフロイドメインから呼ばれる関数"
function addGraphAnim!(anim,dist,ijk;Up=false,INF=10^3)
    draw=drawGraph(dist,ijk,Up=Up,INF=INF)
    for _ in 1:(Up ? 20 : 1)
        addAnim!(anim,draw)
    end
end

"ワーシャルフロイドメイン関数"
function FWAlgoPlot(A)
    Dist=copy(A)
    n=size(A)[1]
    
    # 繋がってない部分は大きな値として計算させる
    INF=10^3
    Dist[Dist.==0].=INF
    for i in 1:n
        Dist[i,i]=0
    end

    anim=Animation()

    n=size(A)[1]
    for k in 1:n , i in 1:n , j in 1:n
        addGraphAnim!(anim,Dist,(i,j,k),INF=INF)
        if Dist[i,j]>Dist[i,k]+Dist[k,j]
            addGraphAnim!(anim,Dist,(i,j,k),Up=true,INF=INF)
            Dist[i,j]=Dist[i,k]+Dist[k,j]
        end
    end
    Dist[Dist.==INF].=0
    Dist,anim    
end

#一本道
A=[
 0  5  0  0  0  0  0  0
 0  0 11  0  0  0  0  0
 0  0  0  3  0  0  0  0
 0  0  0  0 21  0  0  0
 0  0  0  0  0  4  0  0
 0  0  0  0  0  0  8  0
 0  0  0  0  0  0  0  1
 0  0  0  0  0  0  0  0
]

Dist,anim1=FWAlgoPlot(A)
mp4(anim1,"anim_test1.mp4",fps=60) #上の動画はgif出力

#適当なランダム
n=8
A=zeros(Int,n,n)
for _ in 1:n*2 ; A[rand(1:n),rand(1:n)]=rand(0:5n);end
for i in 1:n ; A[i,i]=0;end

Dist,anim2=FWAlgoPlot(A)
mp4(anim2,"anim_test2.mp4",fps=60)　#上の動画はgif出力2

注意点とかハマり点として

・gplotはいい感じでnode配置してくれるけど、デフォがランダムなのでlayoutで指定か第2,3引数に直接X,Y値(のベクトル)を指定しないと動画に向かない
　（layoutはXYを返す関数を指定するものの様）
・そんで、描画の融通が効かないので、更新のedgeとかもう一個グラフ作って重ねたりした
・細かい指定(線幅とか)もしてみたけど、PNG出力時にいろいろ無効になってしまう
・edgeの無(0)とグラフマトリクスの断絶(INF)がかち合うので、変換が必要
・mp4出力したいときはPNGファイルの縦幅2の倍数でないと駄目なので、inch✕dpiで指定
・最短距離更新の止め画は無駄に同じPNGファイルを吐き出した

最後に

GraphPlotなるパッケージ見つけて、なんか動画いけるんじゃねと思ったけど
細かいとこは面倒だった
これでワーシャルフロイド法が分かりやすくなったかと言えば・・・
（そう言う人がいればいいな）

Discussion