この記事は、大阪工業大学 Advent Calendar 2021の13日目の記事です。研究にもマイクラのサーバMod開発にも使用しているJGraphTについて書きます。

気が向けば続きを書くかもしれません。

Kotlinでグラフ理論

昨今AndroidアプリなどではKotlinが使われてるんだしちょっとはそういうライブラリあるんかなと思ったのですけど、Kotlin専用ってなかった。で、Javaのライブラリを使います。

この記事ではKotlinを使ってグラフ理論のHello,Worldを書ければいいなレベルのものです。具体的には、簡単な簡単グラフを画像出力する程度にとどめます。

Kotlinのメソッド呼び出しと、Javaのメソッド呼び出し(できればジェネリックスぐらい)の知識を前提とします。

JGraphT

JGraphTはLGPL2.0ライセンスとEPL2.0ライセンスのデュアルライセンス下で公開されています。

ライセンスの詳細については割愛しますが、有償ソフトなどに組み込む場合には少し注意が必要です。

グラフの画像出力

使用環境は以下の通り。
- IDE: IntelliJ IDEA Community 2021.3
- ProjectJDK: openjdk-16.0.2 (Java17も使えるっちゃ使えますがなぜか安定しなかった)
- Kotlin Console Applicationで行う(環境に合わせてよしなにしてください)

Kotlinにライブラリを読み込む

必要なライブラリを読み込むため、Maven Repositoryから必要なものを探してきます。今回はcoreとextです。

2021年12月現在では1.5.1がそれぞれ最新となっています。

Mavenで読み込む場合はサイトにコピペコード書いてくれてますが、使うのはGradleなので以下のように書き換えます。これをdependencies内に追記します。

gradle.kts

import org.jetbrains.kotlin.gradle.tasks.KotlinCompile

plugins {
    kotlin("jvm") version "1.5.10"
    application
}

group = "com.github.Seaoftrees08.HelloGraph"
version = "1.0-SNAPSHOT"

repositories {
    mavenCentral()
}

dependencies {
    testImplementation(kotlin("test"))
    implementation("org.jgrapht:jgrapht-core:1.5.1")
    implementation("org.jgrapht:jgrapht-ext:1.5.1")
}

tasks.test {
    useJUnit()
}

tasks.withType<KotlinCompile>() {
    kotlinOptions.jvmTarget = "16"
}

application {
    mainClass.set("MainKt")
}

画像出力

とりあえず先にコードを貼ります。解説は後述します。

Main.kt

import com.mxgraph.layout.mxCircleLayout
import com.mxgraph.layout.mxIGraphLayout
import com.mxgraph.util.mxCellRenderer
import org.jgrapht.Graph
import org.jgrapht.ext.JGraphXAdapter
import org.jgrapht.graph.DefaultEdge
import org.jgrapht.graph.SimpleGraph
import java.awt.Color
import java.io.File
import java.io.IOException
import javax.imageio.ImageIO

fun main(args: Array<String>) {

    //簡単グラフの作成
    val graph = SimpleGraph<String, DefaultEdge>(DefaultEdge::class.java)

    //頂点の追加
    graph.addVertex("A")
    graph.addVertex("B")
    graph.addVertex("C")

    //辺の追加
    graph.addEdge("A", "B")
    graph.addEdge("B", "C")

    //画像の出力
    graph.exportPNG("graphPicture")

}

@Throws(IOException::class)
fun <V, E> Graph<V, E>.exportPNG(name: String) {
    val graphAdapter = JGraphXAdapter(this)
    val layout: mxIGraphLayout = mxCircleLayout(graphAdapter)
    layout.execute(graphAdapter.defaultParent)
    val image = mxCellRenderer.createBufferedImage(graphAdapter, null, 2.0, Color.WHITE, true, null)
    val imgFile = File("src/test/resources/$name.png")
    ImageIO.write(image, "PNG", imgFile)
    println("PNG output!")
}

解説

簡単グラフの生成

val graph = SimpleGraph<String, DefaultEdge>(DefaultEdge::class.java)

簡単グラフはSimpleGraph<V,E>としてクラスが用意されています。

VはVertex(頂点)の略で、任意のクラスを頂点とすることができますが、画像出力時に出てくる頂点名はtoString()の出力結果ですので必要があればoverrideすることをお勧めします。

EはEdge(辺)の略で、こちらは任意のクラスと使うとき少し面倒なのでDefaultEdgeで大丈夫です。(というかこれで困ったことがまだない)

頂点の追加

    graph.addVertex("A")
    graph.addVertex("B")
    graph.addVertex("C")

頂点をひとつづつ追加するだけです。面倒ならforなりforeachなりを使ってください。

面倒なことにaddAllなるメソッドは存在しません。

※vertexSet()というメソッドはグラフに存在する頂点群(Set<V>)を返すメソッドです。

辺の追加

    graph.addEdge("A", "B")
    graph.addEdge("B", "C")

頂点と同じく一つ一つ辺を追加してください。

引数の一つ目がsourceVertexで出発点、二つ目がtargetVertexで行先点ですが、今回は簡単グラフ(=無向グラフ)ですので気にしなくてokです。

画像の出力

画像自体はさして重要な要素ではないので飛ばします(コード自体もほぼコピペです)。

画像出力後に辺が矢印になっていますが、データ内部ではちゃんと無向グラフとして扱っていますので安心してください。

総評

ぶっちゃけこのライブラリあればだいたいなんでもできますが、専用の木構造がないのが少し残念でした。

おまけも少し書きますが、JGraphT自体がかなり有名なライブラリなだけあって「JGraphT ○○」と調べれば何かしら記事が出てきてくれます。親切な暇人に感謝！

それではよい年末を！

おまけ

「簡単な簡単グラフ」とかいう壊れた日本語

人間でも手軽に書ける頂点と辺がともに少ないグラフを「簡単なグラフ」と呼んでいます。

同じ頂点間を結ぶ辺および、同じ頂点へ至るような辺が存在しない無向グラフを「簡単グラフ」といいます。
よって、「簡単な簡単グラフ」は、「人間でも手軽に書けるレベルの簡単グラフ」という意味です。

参考

Hello JGraphT Complete Example

Introduction to JGraphT