グラフ理論ライブラリのJGraphTを使ってみた

Java

JGraphT

JGraphTは、Javaのグラフライブラリです。グラフの描画ではなく、グラフ理論のモデルとアルゴリズムの方にフォーカスしています。とても使いやすかったので、紹介してみます。

無向グラフ

UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(
        DefaultEdge.class);
g.addVertex("a"); g.addVertex("b"); g.addVertex("c");
g.addEdge("a", "b");
g.addEdge("b", "c");

System.out.println(g.vertexSet());
System.out.println(g.edgeSet());
System.out.println(g.edgesOf("c"));

[a, b, c]
[(a : b), (b : c)]
[(b : c)]

有向グラフ

DirectedGraph<String, DefaultEdge> g = new SimpleDirectedGraph<String, DefaultEdge>(
        DefaultEdge.class);
g.addVertex("a"); g.addVertex("b"); g.addVertex("c");
g.addEdge("a", "b");
g.addEdge("b", "c");

System.out.println(g.incomingEdgesOf("b"));
System.out.println(g.outgoingEdgesOf("b"));

[(a : b)]
[(b : c)]

ダイクストラ法による最短経路計算

WeightedGraph<String, DefaultWeightedEdge> g = new SimpleWeightedGraph<String, DefaultWeightedEdge>(
        DefaultWeightedEdge.class);
g.addVertex("a"); g.addVertex("b"); g.addVertex("c");
g.setEdgeWeight(g.addEdge("a", "b"), 4);
g.setEdgeWeight(g.addEdge("a", "c"), 1);
g.setEdgeWeight(g.addEdge("c", "b"), 2);

System.out.println(DijkstraShortestPath.findPathBetween(g, "a", "b"));

[(a : c), (c : b)]

ノードの探索

WeightedGraph<String, DefaultWeightedEdge> g = new SimpleWeightedGraph<String, DefaultWeightedEdge>(
        DefaultWeightedEdge.class);
g.addVertex("a"); g.addVertex("b"); g.addVertex("c");
g.setEdgeWeight(g.addEdge("a", "b"), 4);
g.setEdgeWeight(g.addEdge("a", "c"), 1);
g.setEdgeWeight(g.addEdge("c", "b"), 2);

// 以下は最短距離優先。他にも幅優先、深さ優先など選択可
ClosestFirstIterator<String, DefaultWeightedEdge> it =
        new ClosestFirstIterator<String, DefaultWeightedEdge>(g, "a");
while (it.hasNext()) {
    System.out.println(it.next());
}

a
c
b

連結性の判定

UndirectedGraph<String, DefaultEdge> g = new SimpleGraph<String, DefaultEdge>(
        DefaultEdge.class);
g.addVertex("a"); g.addVertex("b"); g.addVertex("c");
g.addEdge("a", "b");

ConnectivityInspector<String, DefaultEdge> inspector =
        new ConnectivityInspector<String, DefaultEdge>(g);
System.out.println(inspector.connectedSets());

[[b, a], [c]]

他にも、biconnectivity（二重連結性）の判定やvertex cover（頂点被覆）の計算などができます。

グラフ理論のアルゴリズムを自前で実装するのは結構大変なので、JGraphTはとても便利だと思います。ぜひ試してみてください。