Press "Enter" to skip to content

gonum graph の使い方(Go言語でグラフ理論)

Go言語でグラフ理論のグラフを扱うパッケージには gonum があります。しかしリファレンスには単純な GoDoc しか用意されていないみたいでして、初めて使おうとするときにはちょっと困ります。

graph/simple と graph/multi

どうやって使えばよいのかわからないという疑問を抱いている人は他にもいたようで、Google Groupsに質問が上がっていました。

回答を読むに、

  • graph/simple と graph/multi に主な実装がされている
  • とりあえず今はテストコードを読んで使い方をイメージする

ということだとわかります。名前からもわかりますが、 simple は単純グラフのこと、multi は多重グラフのことです。

グラフの作成(重み付き無向グラフの場合)

今回は、今僕が使う必要のある重み付き無向グラフ(Weighted Undirected Graph)の使い方を、GoDocとソースコードとテストコードを読んで調べました。

1. グラフを作る

とりあえず

で、重み付き無向グラフを作成できます。ただしノード・エッジは1つもありません。ここで登場する2つの引数は

  • self: セルフコネクション(両端が同じノードとなるエッジ)に対する重みの値
  • absent: エッジが存在しないノード間の重みの値

となります。とりあえず今回はセルフコネクションならば重みは0で、エッジが存在しないところは重み無限大と設定しています。

2. ノードの追加・参照

ノードの追加方法は2つ。

  • AddNode: ノードインスタンスを引数に受けて、ノードをグラフへ追加する
  • NewNode: ID等を気にせずとりあえずノードを追加する

AddNode はすでに存在するIDを用いて再び呼ぶと Panic を起こすみたいなので、ノードの存在を確認してから呼ぶと良いかもしれません。

次にノードの参照について。ノードの参照方法も2つ。

  • Node: IDを指定して参照。
  • Nodes: すべてのノードを参照。graph.Nodes型で返ってくる

ちなみにノードの削除のための関数もあります。

3. エッジの追加・参照

エッジについてもノードと似たような雰囲気です。エッジのインスタンスを作る方法はノードの場合と違って、構造体をそのまま使って作成するようです。

4. エッジリストからグラフを作る

これを応用すると、ファイルを読み込んでグラフを作成することが可能です。以下のエッジリストで定義されるグラフをGonumで作ってみます。


(描画は Python の NetworkX を使いました)

Gonumのパッケージに Edge List を読み込む関数は特に用意されてなさそうなので、Go言語のCSVパッケージを使います。

出力結果

&{-1 [{1 2 40} {2 3 30} {2 4 40} {1 5 50} {4 5 30} {5 6 50} {5 7 50} {3 4 40} {3 9 40} {6 7 30} {7 11 80} {8 11 70} {11 12 20} {11 13 30} {8 13 70} {10 13 70} {13 14 70} {13 19 40} {16 17 40} {17 18 30} {17 19 30} {4 8 50} {7 8 30} {8 9 60} {8 10 60} {10 14 30} {14 19 70} {14 21 20} {15 16 40} {12 15 40} {12 16 40} {20 21 20} {18 20 30} {19 20 30} {4 7 50} {4 9 70} {9 10 60} {7 12 90}]}

エッジのリストが出力されたので、グラフにエッジが登録されていることがわかります。

グラフの描画

これは GraphViz を使って描くことができるみたいです。つまり DOT を使うということです。他にも、 cytoscape で使う JSON を操作するためのパッケージもあるみたいです。

ただ、NetworkXの描画に慣れてしまっているので今回はちょっとパスします…

グラフの分析(最短経路問題の場合)

グラフの構造体を作ることができたので、次はそれを分析していきます。Gonumが用意しているグラフ分析パッケージは、GoDocを見たところ

  • graph/network
    • ネットワークの分析ツール
  • graph/path
    • 経路探索ツール
  • graph/topo
    • トポロジ分析ツール

の3つが用意されているみたいです。今回はpathの中に用意されているダイクストラ法を使いたいと思います。

DijkstraAllPaths

ダイクストラ法を使って、任意のノードからすべてのノードへの最短経路を得る関数 “DijkstraAllPaths” を使ってみます。グラフは先程のエッジリストのグラフを使います。

出力結果:

from 1 to 18: [[1 2 3 9 10 14 21 20 18]] 270
from 3 to 15: [[3 4 7 12 15] [3 4 8 11 12 15]] 220
from 6 to 17: [[6 7 12 16 17] [6 7 8 13 19 17]] 200

任意の二点間の最短経路が予め全て計算されるみたいです。結構便利に感じました。

Be First to Comment

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です