Javaのグラフ

投稿日: 2019-10-18 2022-10-19
タグ: Java

1. 概要

このチュートリアルでは、データ構造としてのグラフの基本的な概念を理解します。

また、Javaでの実装と、グラフで可能なさまざまな操作についても説明します。また、グラフの実装を提供するJavaライブラリについても説明します。

2. グラフのデータ構造

グラフは、ソーシャルメディアプラットフォーム上の人々のネットワークのように、接続されたデータを格納するためのデータ構造です。

グラフは頂点とエッジで構成されます。 頂点はエンティティ（たとえば、人）を表し、エッジはエンティティ（たとえば、人の友情）間の関係を表します。

これをよりよく理解するために、単純なグラフを定義しましょう。

ここでは、5つの頂点と6つのエッジを持つ単純なグラフを定義しました。円は人を表す頂点であり、2つの頂点を結ぶ線は、オンラインポータル上の友達を表すエッジです。

エッジのプロパティに応じて、この単純なグラフにはいくつかのバリエーションがあります。次のセクションでそれらを簡単に見ていきましょう。

ただし、このチュートリアルのJavaの例では、ここに示されている単純なグラフのみに焦点を当てます。

2.1. 有向グラフ

これまでに定義したグラフには、方向のないエッジがあります。これらのエッジがそれらの方向を特徴とする場合、結果のグラフは有向グラフとして知られています。

この例としては、オンラインポータルのフレンドシップで誰がフレンドリクエストを送信したかを表すことができます。

ここでは、エッジの方向が固定されていることがわかります。エッジは双方向にすることもできます。

2.2. 加重グラフ

繰り返しになりますが、単純なグラフには、偏りのない、または重み付けされていないエッジがあります。代わりに、これらのエッジが相対的な重みを運ぶ場合、このグラフは重み付きグラフと呼ばれます。

これの実用的なアプリケーションの例は、オンラインポータルでの友情がどれほど古いかを表すことです。

ここでは、エッジに重みが関連付けられていることがわかります。これは、これらのエッジに相対的な意味を提供します。

3. グラフ表現

グラフは、隣接行列や隣接リストなどのさまざまな形式で表すことができます。それぞれが異なる設定で長所と短所を持っています。

このセクションでは、これらのグラフ表現を紹介します。

3.1. 隣接行列

隣接行列は、グラフの頂点の数に相当する次元の正方行列です。

マトリックスの要素は通常、値「0」または「1」を持ちます。値「1」は行と列の頂点間の隣接を示し、それ以外の場合は値「0」を示します。

前のセクションの単純なグラフの隣接行列がどのように見えるかを見てみましょう。

この表現は、実装がかなり簡単で、クエリも効率的です。ただし、占有スペースに関しては効率が低くなります。

3.2. 隣接リスト

隣接リストは、リストの配列に他なりません。配列のサイズは、グラフの頂点の数に相当します。

配列の特定のインデックスにあるリストは、その配列インデックスによって表される頂点の隣接する頂点を表します。

前のセクションの単純なグラフの隣接リストがどのように見えるかを見てみましょう。

この表現は作成が比較的難しく、クエリの効率が低くなります。ただし、より優れたスペース効率を提供します。

このチュートリアルでは、隣接リストを使用してグラフを表します。

4. Javaのグラフ

Javaには、グラフデータ構造のデフォルトの実装がありません。

ただし、Javaコレクションを使用してグラフを実装できます。

頂点を定義することから始めましょう：

class Vertex {
    String label;
    Vertex(String label) {
        this.label = label;
    }

    // equals and hashCode
}

上記の頂点の定義はラベルのみを特徴としていますが、これはPersonやCityなどの可能なエンティティを表すことができます。

また、 equals（）メソッドとhashCode（）メソッドは、Javaコレクションを操作するために必要であるため、これらをオーバーライドする必要があることに注意してください。

前に説明したように、グラフは、隣接行列または隣接リストのいずれかとして表すことができる頂点とエッジのコレクションに他なりません。

ここで隣接リストを使用してこれを定義する方法を見てみましょう。

class Graph {
    private Map<Vertex, List<Vertex>> adjVertices;
    
    // standard constructor, getters, setters
}

ここでわかるように、クラス Graph は、JavaコレクションのMapを使用して隣接リストを定義しています。

グラフを介した[X103X]作成、更新、検索 など、グラフデータ構造で可能な操作がいくつかあります。

より一般的な操作のいくつかを実行し、Javaでそれらを実装する方法を確認します。

5. グラフの突然変異操作

まず、グラフのデータ構造を変更するためのいくつかのメソッドを定義します。

頂点を追加および削除するメソッドを定義しましょう。

void addVertex(String label) {
    adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
}

void removeVertex(String label) {
    Vertex v = new Vertex(label);
    adjVertices.values().stream().forEach(e -> e.remove(v));
    adjVertices.remove(new Vertex(label));
}

これらのメソッドは、頂点セットから要素を追加および削除するだけです。

次に、エッジを追加するメソッドも定義しましょう。

void addEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    adjVertices.get(v1).add(v2);
    adjVertices.get(v2).add(v1);
}

このメソッドは、新しい Edge を作成し、隣接する頂点Map。を更新します。

同様の方法で、 removeEdge（）メソッドを定義します。

void removeEdge(String label1, String label2) {
    Vertex v1 = new Vertex(label1);
    Vertex v2 = new Vertex(label2);
    List<Vertex> eV1 = adjVertices.get(v1);
    List<Vertex> eV2 = adjVertices.get(v2);
    if (eV1 != null)
        eV1.remove(v2);
    if (eV2 != null)
        eV2.remove(v1);
}

次に、これまでに定義したメソッドを使用して、以前に描画した単純なグラフを作成する方法を見てみましょう。

Graph createGraph() {
    Graph graph = new Graph();
    graph.addVertex("Bob");
    graph.addVertex("Alice");
    graph.addVertex("Mark");
    graph.addVertex("Rob");
    graph.addVertex("Maria");
    graph.addEdge("Bob", "Alice");
    graph.addEdge("Bob", "Rob");
    graph.addEdge("Alice", "Mark");
    graph.addEdge("Rob", "Mark");
    graph.addEdge("Alice", "Maria");
    graph.addEdge("Rob", "Maria");
    return graph;
}

最後に、特定の頂点の隣接する頂点を取得するメソッドを定義します。

List<Vertex> getAdjVertices(String label) {
    return adjVertices.get(new Vertex(label));
}

6. グラフのトラバース

グラフデータ構造とそれを作成および更新するための関数が定義されたので、グラフをトラバースするためのいくつかの追加関数を定義できます。グラフ内の検索など、意味のあるアクションを実行するには、グラフをトラバースする必要があります。

グラフをトラバースするには、深さ優先トラバーサルと幅優先トラバーサルの2つの方法があります。

6.1. 深さ優先探索

深さ優先トラバーサルは任意のルート頂点から始まり、は同じレベルの頂点を探索する前に、各ブランチに沿って可能な限り深く頂点を探索します。

深さ優先探索を実行するメソッドを定義しましょう。

Set<String> depthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<String>();
    Stack<String> stack = new Stack<String>();
    stack.push(root);
    while (!stack.isEmpty()) {
        String vertex = stack.pop();
        if (!visited.contains(vertex)) {
            visited.add(vertex);
            for (Vertex v : graph.getAdjVertices(vertex)) {              
                stack.push(v.label);
            }
        }
    }
    return visited;
}

ここでは、スタックを使用して、トラバースする必要のある頂点を格納しています。

前のサブセクションで作成したグラフでこれを実行してみましょう。

assertEquals("[Bob, Rob, Maria, Alice, Mark]", depthFirstTraversal(graph, "Bob").toString());

ここでは、トラバーサルのルートとして頂点「Bob」を使用していることに注意してください。ただし、これは他の頂点でもかまいません。

6.2. 幅優先探索

比較すると、幅優先探索は任意のルート頂点から始まり、グラフ内で深くなる前に、同じレベルですべての隣接する頂点を探索します。

次に、幅優先探索を実行するメソッドを定義しましょう。

Set<String> breadthFirstTraversal(Graph graph, String root) {
    Set<String> visited = new LinkedHashSet<String>();
    Queue<String> queue = new LinkedList<String>();
    queue.add(root);
    visited.add(root);
    while (!queue.isEmpty()) {
        String vertex = queue.poll();
        for (Vertex v : graph.getAdjVertices(vertex)) {
            if (!visited.contains(v.label)) {
                visited.add(v.label);
                queue.add(v.label);
            }
        }
    }
    return visited;
}

幅優先トラバーサルは、キューを使用して、トラバースする必要のある頂点を格納することに注意してください。

同じグラフでこのトラバーサルをもう一度実行してみましょう。

assertEquals(
  "[Bob, Alice, Rob, Mark, Maria]", breadthFirstTraversal(graph, "Bob").toString());

ここでも、ここで「ボブ」であるルート頂点は、他の頂点でもかまいません。

7. グラフ用のJavaライブラリ

Javaでは常にグラフを最初から実装する必要はありません。グラフの実装を提供する、いくつかのオープンソースおよび成熟したライブラリが利用可能です。

次のいくつかのサブセクションでは、これらのライブラリのいくつかについて説明します。

7.1. JGraphT

JGraphT は、グラフデータ構造用のJavaで最も人気のあるライブラリの1つです。単純なグラフ、有向グラフ、加重グラフなどを作成できます。

さらに、グラフデータ構造で可能な多くのアルゴリズムを提供します。以前のチュートリアルの1つでは、JGraphTについてさらに詳しく説明しています。

7.2. Google Guava

Google Guava は、グラフデータ構造とそのアルゴリズムを含むさまざまな機能を提供するJavaライブラリのセットです。

シンプルなGraph、 ValueGraph 、およびNetworkの作成をサポートします。これらは、MutableまたはImmutableとして定義できます。

7.3. Apache Commons

Apache Commons は、再利用可能なJavaコンポーネントを提供するApacheプロジェクトです。これには、グラフデータ構造を作成および管理するためのツールキットを提供するCommonsGraphが含まれます。これは、データ構造を操作するための一般的なグラフアルゴリズムも提供します。

7.4. Sourceforge JUNG

Javaユニバーサルネットワーク/グラフ（JUNG）は、グラフとして表現できるデータのモデリング、分析、および視覚化のための拡張可能な言語を提供するJavaフレームワークです。

JUNGは、クラスタリング、分解、最適化などのルーチンを含む多くのアルゴリズムをサポートしています。

これらのライブラリは、グラフのデータ構造に基づいた多数の実装を提供します。 グラフに基づくより強力なフレームワークもあります。たとえば、 Apache Giraph は、現在Facebookでユーザーが作成したグラフを分析するために使用されています。また、 Apache TinkerPop 、グラフデータベースの上で一般的に使用されます。

8. 結論

この記事では、データ構造としてのグラフとその表現について説明しました。 Javaコレクションを使用してJavaで非常に単純なグラフを定義し、グラフの一般的な走査も定義しました。

また、グラフの実装を提供するJavaプラットフォーム以外のJavaで利用可能なさまざまなライブラリについても簡単に説明しました。

いつものように、例のコードはGitHubでから入手できます。

getdocs

13036