📂グラフ理論

ジュリアのグラフ分析パッケージ Graphs.jl

紹介

Graphs.jlは、PythonのNetworkXと同じようにグラフ(ネットワーク)分析のためのパッケージだ。LightGraphs.jlというパッケージをリブートして作られた。

Graphs.jlの目標は、PythonのNetworkXなどのライブラリの例に従って、Juliaでのネットワークとグラフ分析のための高性能なプラットフォームを提供することだ。

Graphs.jlプロジェクトは、2021年10月にアーカイブされたLightGraphs.jlパッケージのリブートであり、GitHubのsbromberger/LightGraphs.jlで引き続き利用可能だ。

コード

コードは全体的にNetworkXに似ている。まだうまく使うのは難しいみたいだ。

インストール

JuliaのREPLで] add Graphsと入力してインストールする。

(@v1.7) pkg> add Graphs

ローディングとバージョンチェック

julia> using Graphs
julia> using Pkg

julia> Pkg.status("Graphs")
  [86223c79] Graphs v1.7.1

グラフ作成

NetworkXと同様に、Graph()やDiGraph()でヌルグラフを作る。頂点のデフォルトタイプはInt64で、サブタイプでのみ作れる。グラフの情報は$\left\{ \left| V \right|, \left| E \right| \right\}$で表示される。

julia> G = Graph()
{0, 0} undirected simple Int64 graph

julia> G = DiGraph()
{0, 0} directed simple Int64 graph

julia> G = Graph{Float64}()
ERROR: TypeError: in SimpleGraph, in T, expected T<:Integer, got Type{Float64}

julia> G = Graph{UInt64}()
{0, 0} undirected simple UInt64 graph

頂点の追加と削除

NetworkXではノードの名前でノードを追加するが、Graphs.jlでは頂点が$1$から始まって$2,3,\dots$の順に追加される。

julia> add_vertex!(G)
true

julia> G
{1, 0} undirected simple Int64 graph

julia> add_vertex!(G)
true

julia> G
{2, 0} undirected simple Int64 graph

add_vertices!(G, n)で$n$個の頂点を追加する。

julia> add_vertices!(G, 3)
3

julia> G
{5, 0} undirected simple Int64 graph

rem_vertex!(G, v)で特定の頂点を削除できるが、削除後空いた番号なしに自動的に整列されることに注意。例えば、頂点が$V = \left\{ 1,2,3,4,5 \right\}$の時に$2$を削除すると、$3, 4, 5$の名前が$2, 3, 4$に変わる。

julia> G = Graph(5)
{5, 0} undirected simple Int64 graph

julia> rem_vertex!(G, 2)
true

julia> G
{4, 0} undirected simple Int64 graph

julia> has_vertex(G, 2)
true

julia> has_vertex(G, 5)
false

エッジの追加と削除

rem_vertex!(G, 2)で二番目の頂点を削除すると、上で説明したように元の三番目の頂点が新しい二番目の頂点になるが、エッジは異なる結果になる。バグのようだ。

julia> G = Graph(5)
{5, 0} undirected simple Int64 graph
julia> add_edge!(G, 1, 2)
true
julia> add_edge!(G, 2, 3)
true
julia> add_edge!(G, 3, 4)
true
julia> G
{5, 3} undirected simple Int64 graph

julia> has_edge(G, 1, 2)
true
julia> has_edge(G, 2, 3)
true
julia> has_edge(G, 3, 4)
true


julia> rem_vertex!(G, 2)
true
julia> G
{4, 1} undirected simple Int64 graph
julia> has_vertex(G, 2)
true
julia> has_edge(G, 1, 2)
false
julia> has_edge(G, 2, 3)
false
julia> has_edge(G, 3, 4)
true

環境

• OS: Windows10
• バージョン: Julia 1.7.1, Graphs 1.7.1