Javaのグラフ構造・アルゴリズムライブラリ「JGraphT」の使い方

グラフ理論の文脈におけるグラフとは、頂点と辺によって構成されるデータ構造です。グラフで表すことのできる構造は実世界の様々な場面に存在し、またプログラミング上で必要（有用）となる場面も多くあります。

一方でグラフをソースコードで表現する場合、その構造や各種操作・アルゴリズムなどまで実装することを考えるとなかなか一苦労でもあります。

今回は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クラスを考えます。これは電車の駅を表しており、グラフにおける頂点に相当します。

public class Station {
    private final String name;

    Station( String name ) {
        this.name = name;
    }

    public String getName() {
        return this.name;
    }

    @Override
    public String toString() {
        return "Station [name=" + name + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals( Object obj ) {
        if ( this == obj ) return true;
        if ( obj == null ) return false;
        if ( getClass() != obj.getClass() ) return false;
        Station other = (Station)obj;
        if ( name == null ) {
            if ( other.name != null ) return false;
        } else if ( ! name.equals( other.name ) ) {
            return false;
        }
        return true;
    }
}

次に駅間の移動を表すLineクラスを考えます。移動に必要な時間と料金をメンバとして持っており、グラフにおける辺に相当します。

public class Line {
    private final String name;
    private final int time;

    Line( String name,int time ) {
        this.name = name;
        this.time = time;
    }

    public String getName() {
        return this.name;
    }
    public int getTime() {
        return this.time;
    }

    @Override
    public String toString() {
        return "Line [name=" + name + ", time=" + time + "]";
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        result = prime * result + time;
        return result;
    }

    @Override
    public boolean equals( Object obj ) {
        if ( this == obj ) return true;
        if ( obj == null ) return false;
        if ( getClass() != obj.getClass() ) return false;
        Line other = (Line)obj;
        if ( name == null ) {
            if ( other.name != null ) return false;
        } else if ( ! name.equals( other.name ) ) {
            return false;
        }
        if ( time != other.time ) {
            return false;
        }
        return true;
    }
}

グラフの頂点、辺に使用するクラスはこのように独自に定義することができます。ただし、それぞれのクラスにequalsメソッドとhashCodeメソッドを定義する必要があります。

以下がStationを頂点、Lineを辺としたグラフを作成し、その上での最短路を求めるコードです。

import org.jgrapht.Graph;
import org.jgrapht.GraphPath;
import org.jgrapht.graph.WeightedMultigraph;
import org.jgrapht.alg.interfaces.ShortestPathAlgorithm.SingleSourcePaths;
import org.jgrapht.alg.shortestpath.DijkstraShortestPath;

public class ShortestPath {
    public static void main( String args[] ) {
        // グラフオブジェクトを作成
        Graph<Station,Line> graph = new WeightedMultigraph<>(Line.class);

        // 頂点となる駅
        Station shibuya = new Station( "渋谷" );     // 渋谷
        Station shinjuku = new Station( "新宿" );   // 新宿
        Station kichijoji = new Station( "吉祥寺" ); // 吉祥寺
        Station tachikawa = new Station( "立川" ); // 立川

        // 辺となる路線
        Line chuo_shinjuku_tachikawa = new Line( "中央線", 36);
        Line chuo_shinjuku_kichijoji = new Line( "中央線", 12 );
        Line chuo_kichijoji_tachikawa = new Line( "中央線", 27 );
        Line yamanote_shibuya_shinjuku = new Line( "山手線", 7 );
        Line keio_shibuya_kichijoji = new Line( "京王井の頭線", 17 );

        // 頂点を追加
        graph.addVertex( shibuya );
        graph.addVertex( shinjuku );
        graph.addVertex( kichijoji );
        graph.addVertex( tachikawa );

        // 辺を追加
        graph.addEdge( shinjuku, tachikawa, chuo_shinjuku_tachikawa );
        graph.addEdge( shinjuku, kichijoji, chuo_shinjuku_kichijoji );
        graph.addEdge( kichijoji, tachikawa, chuo_kichijoji_tachikawa );
        graph.addEdge( shibuya, shinjuku, yamanote_shibuya_shinjuku );
        graph.addEdge( shibuya, kichijoji, keio_shibuya_kichijoji );

        // 辺の重みを追加
        graph.setEdgeWeight( chuo_shinjuku_tachikawa, chuo_shinjuku_tachikawa.getTime() );
        graph.setEdgeWeight( chuo_shinjuku_kichijoji, chuo_shinjuku_kichijoji.getTime() );
        graph.setEdgeWeight( chuo_kichijoji_tachikawa, chuo_kichijoji_tachikawa.getTime() );
        graph.setEdgeWeight( yamanote_shibuya_shinjuku, yamanote_shibuya_shinjuku.getTime() );
        graph.setEdgeWeight( keio_shibuya_kichijoji, keio_shibuya_kichijoji.getTime() );

        // 最短路問題を解く (渋谷からすべての駅までの最短路を求める)
        DijkstraShortestPath<Station,Line> dijkstra = new DijkstraShortestPath<>( graph );
        SingleSourcePaths<Station,Line> paths = dijkstra.getPaths( shibuya );

        // 立川までの最短路を取得する
        GraphPath<Station,Line> path = paths.getPath( tachikawa );

        // 最短路の長さ (重みの総和) を取得する
        System.out.println( "所要時間: " + path.getWeight() + "分" );

        System.out.println( "" );

        // 最短路上の頂点を取得する
        System.out.println( "経路:" );
        for ( Station station : path.getVertexList() ) {
            System.out.println( station.getName() );
        }
        System.out.println( "" );

        // 最短路上の辺を取得する
        System.out.println( "各区間での所要時間:" );
        for ( Line line : path.getEdgeList() ) {
            System.out.println( line.getName() + ": " + line.getTime() + "分" );
        }
    }
}

以下が実行結果です。

所要時間: 43.0分

経路:
渋谷
新宿
立川

各区間での所要時間:
山手線: 7分
中央線: 36分

以上のように、JGraphTを用いることで非常に簡単にグラフを作成し、アルゴリズムを実行することができます。

グラフを表現するためのライブラリは他にも存在するかと思いますが、JGraphTは選択肢の１つとして非常に有力なものであるかと思います。