S-JIS[2022-10-06] 変更履歴

JGraphT DirectedAcyclicGraph

JGraphTのDirectedAcyclicGraphクラスのメモ。

概要

JGraphTでDAG（有向非巡回グラフ）を扱うのがDirectedAcyclicGraphクラス。

import org.jgrapht.graph.DirectedAcyclicGraph;

例

頂点（vertex）をStringで扱う例。

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DirectedAcyclicGraph;
public class DagExample {

    static void example() {
        var dag = new DirectedAcyclicGraph<String, DefaultEdge>(DefaultEdge.class);

        dag.addVertex("a");
        dag.addVertex("b");
        dag.addVertex("c");
        dag.addVertex("d");

        dag.addEdge("a", "b");
        dag.addEdge("a", "c");
        dag.addEdge("b", "d");
        dag.addEdge("c", "d");

        System.out.println(dag); //→ ([a, b, c, d], [(a,b), (a,c), (b,d), (c,d)])
    }

DirectedAcyclicGraphには型引数<V, E>がある。
Vに頂点（vertex）として扱うクラスを指定する。（この例ではString）
Eは辺（edge）を扱うクラスで、何でも指定できる（「E extends」という形になっていない）が、基本的にDefaultEdgeを指定する。
コンストラクターにはClass<E>（基本的にはDefaultEdge.class）を指定する。

DirectedAcyclicGraphインスタンスを生成したら、まず頂点（vertex）を全て登録する。
（辺（edge）を登録する際は、指定されたvertexが存在していないとエラーになる）

それから辺（edge）を登録していく。

DirectedAcyclicGraphのメソッド

戻り型 メソッド（例） 説明
Set<V> vertexSet = dag.vertexSet(); 全ての頂点（vertex）を取得する。
Set<E> edgeSet = dag.edgeSet(); 全ての辺（edge）を取得する。
boolean b = dag.containsVertex("a"); 頂点（vertex）が存在しているかどうか。
boolean b = dag.containsEdge("a", "b");
b = dag.containsEdge(edge);		 辺（edge）が存在しているかどうか。
E edge = dag.getEdge("a", "b"); 辺（edge）を取得する。
存在しない場合はnullが返る。
Set<V> vertexSet = dag.getAncestors("d"); 自分より前にある全ての頂点（vertex）を取得する？
Set<V> vertexSet = dag.getDescendants("a"); 自分より後にある全ての頂点（vertex）を取得する？
Set<E> edgeSet = dag.edgesOf("b"); 繋がっている辺（edge）を取得する。
自分が接続先や接続元になっているものが一緒に返される。
Set<E> edgeSet = dag.incomingEdgesOf("b"); 自分が接続先になっている（自分に入ってくる）辺（edge）を取得する。
Set<E> edgeSet = dag.outgoingEdgesOf("b"); 自分が接続元になっている（自分から出ている）辺（edge）を取得する。
V vertex = dag.getEdgeSource(edge); 辺（edge）の接続元（vertex）を返す。
V vertex = dag.getEdgeTarget(edge); 辺（edge）の接続先（vertex）を返す。
int degree = dag.degreeOf("b"); 繋がっている辺（edge）の数を返す。
int degree = dag.inDegreeOf("b"); 自分に入ってくる辺（edge）の数を返す。
int degree = dag.outDegreeOf("b"); 自分から出ている辺（edge）の数を返す。
void dag.setEdgeWeight("a", "b", 1.0);
dag.setEdgeWeight(edge, 1.0);		 　
double weight = dag.getEdgeWeight(edge); 　
GraphType type = dag.getType(); グラフの詳細情報を取得する。
type.isDirected()等でGraphの性質が確認できる。

他に、頂点（vertex）や辺（edge）を追加削除するadd/remove系メソッドがある。

辺（edge）の基本的なクラスであるDefaultEdgeからは、接続元・先（vertex）を取得できない。（getterメソッドの可視性がprotectedになっている）
dag.getEdgeSource(edge), dag.getEdgeTarget(edge)で取得する。

JGraphT目次へ戻る / Javaへ戻る / 技術メモへ戻る
メールの送信先：ひしだま