グラフ理論の文脈におけるグラフとは、頂点と辺によって構成されるデータ構造です。 グラフで表すことのできる構造は実世界の様々な場面に存在し、またプログラミング上で必要（有用）となる場面も多くあります。
一方でグラフをソースコードで表現する場合、その構造や各種操作・アルゴリズムなどまで実装することを考えるとなかなか一苦労でもあります。
今回はJava上でグラフ構造を表現し、グラフ上のアルゴリズムまで提供するライブラリである「JGraphT」の使い方を紹介します。
JGraphTの紹介
詳しい説明は公式ページまたはGitHubを参照いただくのが一番ですが、一言で表現すればJava用のグラフ構造・アルゴリズムライブラリです。 importするだけでグラフ表現や探索、最短路計算などのアルゴリズムを使用することができます。
機能
JGraphTは様々なグラフを表現することができ、現時点（2018年9月）の最新バージョン（1.2.0）において
- 有向・無向グラフ
- 重み付き辺
- ループ
- 多重辺
はもちろんのこと
- read-only
- listenable
などプログラミング上便利な機能も備えています。
さらに
- 最短路問題
- 強連結分解
などを解くアルゴリズムも複数含まれており、例えば最短路問題を解くためにダイクストラ法やベルマンフォード法、A*法などの中から選択することができます。
JGraphTの使い方
JGraphTは多くの機能を持つ一方で導入や使い方はいたってシンプルです。
導入
まずはライブラリを入手します。 Sourceforgeからファイルをダウンロードしクラスパスの通った場所に置くか、Mavenを使用していれば
<groupId>org.jgrapht</groupId> <artifactId>jgrapht-core</artifactId> <version>1.2.0</version>
のようにdependencyを追加することで使用可能となります。
その後、ソースコードに
import org.jgrapht.Graph;
といったようにimport文を記載すれば、ソースコード内でJGraphTの機能を使用することができるようになります。
使用例
ここでは使い方の例として、独自クラスの頂点と辺からなるグラフを作成し、そのグラフ上での最短路を求めるコードを紹介します。
詳細な機能一覧やその使い方などは公式のユーザーガイドやAPIドキュメントを参照してください。
まず以下のようなStationクラスを考えます。 これは電車の駅を表しており、グラフにおける頂点に相当します。
次に駅間の移動を表すLineクラスを考えます。 移動に必要な時間と料金をメンバとして持っており、グラフにおける辺に相当します。
グラフの頂点、辺に使用するクラスはこのように独自に定義することができます。 ただし、それぞれのクラスにequalsメソッドとhashCodeメソッドを定義する必要があります。
以下がStationを頂点、Lineを辺としたグラフを作成し、その上での最短路を求めるコードです。
以下が実行結果です。
所要時間: 43.0分 経路: 渋谷 新宿 立川 各区間での所要時間: 山手線: 7分 中央線: 36分
以上のように、JGraphTを用いることで非常に簡単にグラフを作成し、アルゴリズムを実行することができます。
グラフを表現するためのライブラリは他にも存在するかと思いますが、JGraphTは選択肢の１つとして非常に有力なものであるかと思います。