Zenn
📈

[Package] SimpleWeightedGraphs.jlのグラフ操作でハマった点 (2021/3時点)

2021/03/23に公開
Julia
tech

背景

Juliaを利用するグラフ操作は比較的良いパフォーマンスを出すことが知られており (ブログ記事 Benchmark of popular graph/network packages v2を参照してください)，計算と同じく簡単なグラフ操作についてもJuliaを利用して処理を書きたくなります．基本的なグラフ処理は LightGraphs.jl がカバーしています．

グラフ処理によく利用されているライブラリとしては，PythonのNetworkXがあります．PythonのNetworkXは汎用性が高く作られており，有向・無向グラフけではなく，属性付きグラフなどについても比較的統一的なインタフェースを提供しています．一方でJuliaの場合には，属性付きのグラフは MetaGraphs.jl が，重み付きグラフについては SimpleWeightedGraphs.jl が，グラフ描画については例えば GraphPlot.jl がそれぞれカバーしています．

簡単な例

PythonのNetworkXとの比較をするときに一番気をつける点として，LightGraphs.jl では格納されている頂点が V=\{1,\dots,N\} という形であると想定されていることです．例えばPythonのNetworkXでは

import networkx as nx
G = nx.Graph()
G.add_node(1)
G.add_node(3)
G.add_node(5)
# G.add_nodes_from([1, 3, 5])

の形でノードが 1, 3, 5 であるようなグラフを作成できます．一方でJuliaでは

using LightGraphs
g = Graph(3) # ノード数3 [1, 2, 3] のグラフを作成する

という形になり，基本的には任意整数インデクスのようなnetworkxタイプの実装はやらない設計になっています．グラフに頂点を追加する操作自体は add_vertex! もしくは add_vertices! が実装されています (末尾の ! はJuliaの慣習で引数を変更する操作であることを示唆しています)．

using LightGraphs
g = Graph(3) # ノード数3 [1, 2, 3] のグラフを作成する
add_vertex!(g) # ノードを追加して，[1, 2, 3, 4] とする
add_vertices!(g, 5) # ノードを5つ追加して，[1, 2, 3, 4, 5, 6, 7, 8, 9] とする

その他の操作については，辺の追加は add_edge!，削除は rem_edge! などの関数が用意されています．全ての頂点を取得するイテレータは vertices(g) の形で，辺は edges(g) の形で取得できます．ノード数や辺数は nv(g) や ne(g) が対応します．辺 e=\{u,v\} については，端点uとvは src(e) と dst(e) の形で取得できます．

辺の削除挙動の比較 (LightGraphs.jl vs SimpleWeightedGraphs.jl)

ここでは三角形のグラフを用意し，ノードと辺を取得してみます．

LightGraphs.jlを試す

using LightGraphs
g = Graph(3)
add_edge!(g, 1, 2)
add_edge!(g, 1, 3)
add_edge!(g, 2, 3)

# ノードアクセスの例
julia> for n in vertices(g)
         println(n)
       end
1
2
3

# 辺アクセスの例
julia> for e in edges(g)
         println(src(e), "--", dst(e))
       end
1--2
1--3
2--3

ここで辺 \{1,2\} を削除した場合の挙動を見ます．意図したとおりに動作していそうですね．

julia> rem_edge!(g, 1, 2)
true

julia> println("|V|=$(nv(g)), |E|=$(ne(g))")
|V|=3, |E|=2

julia> for e in edges(g)
         println(src(e), "--", dst(e))
       end
1--3
2--3

SimpleWeightedGraphs.jlを試す

using LightGraphs, SimpleWeightedGraphs
g = Graph(3)
add_edge!(g, 1, 2, 0.5) # w12 = 0.5
add_edge!(g, 1, 3, 0.8) # w13 = 0.8
add_edge!(g, 2, 3, 2.0) # w23 = 2.0

# ノードアクセスの例
julia> for n in vertices(g)
         println(n)
       end
1
2
3

# 辺アクセスの例
julia> for e in edges(g)
         println(src(e), "--", dst(e), " w=", e.weight)
       end
1--2 w=0.5
1--3 w=0.8
2--3 w=2.0

ここで辺 \{1,2\} を削除した場合の挙動を見ます．

julia> rem_edge!(g, 1, 2)
true

julia> println("|V|=$(nv(g)), |E|=$(ne(g))")
|V|=3, |E|=3

julia> for e in edges(g)
         println(src(e), "--", dst(e), " w=", e.weight)
       end
1--2 w=0.0 # <-------- !!!!!!!!!!!!!!!!!???????????
1--3 w=0.8
2--3 w=2.0

このように，面白くない挙動を示します．実際のところ実装上の本当の理由は分からないですが，SimpleWeightedGraphs は辺情報を (おそらく) SparseArray などで管理しており，辺の削除を 「重み=0.0」 という形で実装しているようです．この仕様に気づかないで辺の削除を入れた処理をすると，重みが0.0に設定したけれども辺として情報が残っており，無限ループに陥る可能性があります (陥りました)．ちなみにこれは bug として報告されているので，直される可能性もあります．

https://github.com/JuliaGraphs/SimpleWeightedGraphs.jl/issues/66

今回SimpleWeightedGraphsを利用した自分の実装では，次のような形でとりあえずの対処をしました．

el = collect(edges(G))  ## collectすると本当は良くない気がする
for i in 1:length(el), j in i+1:length(el)
    e1, e2 = el[i], el[j]
    (u1, u2) = src(e1), dst(e1)
    (v1, v2) = src(e2), dst(e2)

    # ここです (e1.weight / e2.weight == 0.0 で良かったですかね)
    (G.weights[u1, u2] == 0.0) && continue
    (G.weights[v1, v2] == 0.0) && continue

    # 以下別の処理が続く…
end

Discussion