JGraphT TopologicalOrderIterator

JGraphTのTopologicalOrderIteratorクラスのメモ。

概要

TopologicalOrderIteratorは、JGraphTでトポロジカルソートを行うクラス。
（トポロジカルソートされた順序で頂点（vertex）を返すIterator）

import org.jgrapht.traverse.TopologicalOrderIterator;

TopologicalOrderIteratorのコンストラクターはどんなGraphも受け付けられるようになっているが、
グラフの実態としてはDAG（有向非巡回グラフ）でないといけない模様。
（閉路があるとjava.lang.IllegalArgumentException: Edge would induce a cycleが発生する）

例

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DirectedAcyclicGraph;
import org.jgrapht.traverse.TopologicalOrderIterator;

public class DagExample {

    static void example() {
        var dag = new DirectedAcyclicGraph<String, DefaultEdge>(DefaultEdge.class);
        for (int i = 0; i < 5; i++) {
            dag.addVertex(Character.toString('a' + i));
        }
        dag.addEdge("a", "e");
        dag.addEdge("b", "e");
        dag.addEdge("d", "c");
        dag.addEdge("e", "c");

        for (var i = new TopologicalOrderIterator<>(dag); i.hasNext();) {
            var vertex = i.next();
            System.out.println(vertex);
        }
    }

↓実行結果

a
b
d
e
c