1概要

ほとんどの場合、グラフベースのアルゴリズムを実装するときには、いくつかの効用関数も実装する必要があります。


JGraphT

はオープンソースのJavaクラスライブラリで、さまざまな種類のグラフだけでなく、最も頻繁に発生するグラフの問題を解決するための便利なアルゴリズムも提供しています。

この記事では、さまざまな種類のグラフを作成する方法と、提供されているユーティリティを使用することがいかに便利であるかについて説明します。


2 Mavenの依存関係

Mavenプロジェクトに依存関係を追加することから始めましょう。

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-core</artifactId>
    <version>1.0.1</version>
</dependency>

最新版はhttps://search.maven.org/classic/#search%7Cga%7C1%7Cg%3A%22org.jgrapht%22[Maven Central]で見つけることができます。


3グラフを作成する

JGraphTはさまざまな種類のグラフをサポートしています。


3.1. 単純グラフ

まず、

String

型の頂点を持つ単純なグラフを作成しましょう。

Graph<String, DefaultEdge> g
  = new SimpleGraph<>(DefaultEdge.class);
g.addVertex(“v1”);
g.addVertex(“v2”);
g.addEdge(v1, v2);


3.2. 有向グラフ/無向グラフ

また、有向グラフと無向グラフを作成することもできます。

この例では、有向グラフを作成し、それを使用して他の効用関数とアルゴリズムを説明します。

リンク:/uploads/Directed__graph-300×232.png[]

DirectedGraph<String, DefaultEdge> directedGraph
  = new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("v1");
directedGraph.addVertex("v2");
directedGraph.addVertex("v3");
directedGraph.addEdge("v1", "v2");//Add remaining vertices and edges


3.3. 完全グラフ

同様に、完全なグラフを生成することもできます。

リンク:/uploads/complete__graph.png[]

public void createCompleteGraph() {
    completeGraph = new SimpleWeightedGraph<>(DefaultEdge.class);
    CompleteGraphGenerator<String, DefaultEdge> completeGenerator
      = new CompleteGraphGenerator<>(size);
    VertexFactory<String> vFactory = new VertexFactory<String>() {
        private int id = 0;
        public String createVertex() {
            return "v" + id++;
        }
    };
    completeGenerator.generateGraph(completeGraph, vFactory, null);
}


3.4. マルチグラフ

リンク:/uploads/multigraph-1.png[]

単純グラフ以外に、APIはマルチグラフ(2つの頂点間に複数のパスを持つグラフ)も提供します。

その上、私達はあらゆるグラフの加重/加重またはユーザー定義の辺を持つことができます。

重み付きエッジを持つマルチグラフを作成しましょう。

public void createMultiGraphWithWeightedEdges() {
    multiGraph = new Multigraph<>(DefaultWeightedEdge.class);
    multiGraph.addVertex("v1");
    multiGraph.addVertex("v2");
    DefaultWeightedEdge edge1 = multiGraph.addEdge("v1", "v2");
    multiGraph.setEdgeWeight(edge1, 5);

    DefaultWeightedEdge edge2 = multiGraph.addEdge("v1", "v2");
    multiGraph.setEdgeWeight(edge2, 3);
}

これに加えて、変更不可能な(読み取り専用)および聞き取り可能な(外部のリスナーが変更を追跡できるようにする)グラフとサブグラフを作成できます。また、これらのグラフのすべての構成をいつでも作成できます。

APIの詳細はhttp://jgrapht.org/javadoc/[ここ]を参照してください。


4 APIアルゴリズム

これで、完全なグラフオブジェクトが完成したので、いくつかの一般的な問題とその解決策を見てみましょう。


4.1. グラフ反復

要件に従って、

BreadthFirstIterator



DepthFirstIterator



ClosestFirstIterator



RandomWalkIterator

などのさまざまなイテレータを使用してグラフを移動できます。グラフオブジェクトを渡して、それぞれのイテレータのインスタンスを作成するだけです。

DepthFirstIterator depthFirstIterator
  = new DepthFirstIterator<>(directedGraph);
BreadthFirstIterator breadthFirstIterator
  = new BreadthFirstIterator<>(directedGraph);

イテレータオブジェクトを取得したら、

hasNext()

および

next()

メソッドを使用して反復を実行できます。


4.2. 最短経路を見つける


org.jgrapht.alg.shortestpath

パッケージには、Dijkstra、Bellman-Ford、Astar、FloydWarshallなどのさまざまなアルゴリズムの実装が用意されています。

ダイクストラのアルゴリズムを使って最短経路を見つけましょう。

@Test
public void whenGetDijkstraShortestPath__thenGetNotNullPath() {
    DijkstraShortestPath dijkstraShortestPath
      = new DijkstraShortestPath(directedGraph);
    List<String> shortestPath = dijkstraShortestPath
      .getPath("v1","v4").getVertexList();

    assertNotNull(shortestPath);
}

同様に、Bellman-Fordアルゴリズムを使って最短経路を求めるには、

@Test
public void
  whenGetBellmanFordShortestPath__thenGetNotNullPath() {
    BellmanFordShortestPath bellmanFordShortestPath
      = new BellmanFordShortestPath(directedGraph);
    List<String> shortestPath = bellmanFordShortestPath
      .getPath("v1", "v4")
      .getVertexList();

    assertNotNull(shortestPath);
}


4.3. 強連結サブグラフの検索

実装に入る前に、強く関連した部分グラフが何を意味するのかを簡単に見てみましょう。サブグラフは、その頂点の各ペアの間にパスがある場合にのみ強く接続されていると言われます。

この例では、現在の頂点が何であるかに関係なく、任意の頂点に移動できる場合、\ {v1、v2、v3、v4}は強連結サブグラフと見なすことができます。

上の画像に示されている有向グラフには、このような4つのサブグラフをリストできます。

すべての強連結サブグラフを一覧表示するための実装

@Test
public void
  whenGetStronglyConnectedSubgraphs__thenPathExists() {

    StrongConnectivityAlgorithm<String, DefaultEdge> scAlg
      = new KosarajuStrongConnectivityInspector<>(directedGraph);
    List<DirectedSubgraph<String, DefaultEdge>> stronglyConnectedSubgraphs
      = scAlg.stronglyConnectedSubgraphs();
    List<String> stronglyConnectedVertices
      = new ArrayList<>(stronglyConnectedSubgraphs.get(3)
      .vertexSet());

    String randomVertex1 = stronglyConnectedVertices.get(0);
    String randomVertex2 = stronglyConnectedVertices.get(3);
    AllDirectedPaths<String, DefaultEdge> allDirectedPaths
      = new AllDirectedPaths<>(directedGraph);

    List<GraphPath<String, DefaultEdge>> possiblePathList
      = allDirectedPaths.getAllPaths(
        randomVertex1, randomVertex2, false,
          stronglyConnectedVertices.size());

    assertTrue(possiblePathList.size() > 0);
}


4.4.


オイラー回路

グラフ

G

のオイラー回路は、

G

のすべての頂点と辺を含む回路です。それを持っているグラフはオイラーグラフです。

グラフを見てみましょう。

リンク:/uploads/eulerian__circuit-1.png[]

public void createGraphWithEulerianCircuit() {
    SimpleWeightedGraph<String, DefaultEdge> simpleGraph
      = new SimpleWeightedGraph<>(DefaultEdge.class);
    IntStream.range(1,5)
      .forEach(i-> simpleGraph.addVertex("v" + i));
    IntStream.range(1,5)
      .forEach(i-> {
        int endVertexNo = (i + 1) > 5 ? 1 : i + 1;
        simpleGraph.addEdge("v" + i,"v" + endVertexNo);
    });
}

これで、APIを使用してグラフにEulerian Circuitが含まれているかどうかをテストできます。

@Test
public void givenGraph__whenCheckEluerianCycle__thenGetResult() {
    HierholzerEulerianCycle eulerianCycle
      = new HierholzerEulerianCycle<>();

    assertTrue(eulerianCycle.isEulerian(simpleGraph));
}
@Test
public void whenGetEulerianCycle__thenGetGraphPath() {
    HierholzerEulerianCycle eulerianCycle
      = new HierholzerEulerianCycle<>();
    GraphPath path = eulerianCycle.getEulerianCycle(simpleGraph);

    assertTrue(path.getEdgeList()
      .containsAll(simpleGraph.edgeSet()));
}


4.5. ハミルトニアン回路

各頂点を一度だけ訪れる

GraphPath

は、ハミルトニアンパスと呼ばれます。

  • ハミルトニアンサイクル(またはハミルトニアン回路)は、パスの最後の頂点から最初の頂点まで(グラフ内に)エッジがあるようなハミルトニアンパスです。


HamiltonianCycle.getApproximateOptimalForCompleteGraph()

メソッドを使用して、完全グラフに対する最適ハミルトニアンサイクルを見つけることができます。

このメソッドは、概算の最小巡回セールスマンツアー(ハミルトニアンサイクル)を返します。最適解はNP完全であるため、これは多項式時間で実行されるまともな近似です。

public void
  whenGetHamiltonianCyclePath__thenGetVerticeSequence() {
    List<String> verticeList = HamiltonianCycle
      .getApproximateOptimalForCompleteGraph(completeGraph);

    assertEquals(verticeList.size(), completeGraph.vertexSet().size());
}


4.6. サイクル検出器

グラフにサイクルがあるかどうかも確認できます。現在、

CycleDetector

は有向グラフのみをサポートしています。

@Test
public void whenCheckCycles__thenDetectCycles() {
    CycleDetector<String, DefaultEdge> cycleDetector
      = new CycleDetector<String, DefaultEdge>(directedGraph);

    assertTrue(cycleDetector.detectCycles());
    Set<String> cycleVertices = cycleDetector.findCycles();

    assertTrue(cycleVertices.size() > 0);
}


5グラフの可視化

  • JGraphTはグラフの視覚化を生成してそれらを画像として保存することを可能にします** 、まずhttps://search.maven.org/search?q=a:jgrapht-ext%20AND%20g:org.jgrapht[jgrapht- Maven Centralからの拡張子依存関係:

<dependency>
    <groupId>org.jgrapht</groupId>
    <artifactId>jgrapht-ext</artifactId>
    <version>1.0.1</version>
</dependency>

次に、3つの頂点と3つの辺を持つ単純な有向グラフを作成しましょう。

@Before
public void createGraph() {

    File imgFile = new File("src/test/resources/graph.png");
    imgFile.createNewFile();

    DefaultDirectedGraph<String, DefaultEdge> g =
      new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

    String x1 = "x1";
    String x2 = "x2";
    String x3 = "x3";

    g.addVertex(x1);
    g.addVertex(x2);
    g.addVertex(x3);

    g.addEdge(x1, x2);
    g.addEdge(x2, x3);
    g.addEdge(x3, x1);
}

このグラフを視覚化することができます。

@Test
public void givenAdaptedGraph__whenWriteBufferedImage__thenFileShouldExist() throws IOException {

    JGraphXAdapter<String, DefaultEdge> graphAdapter =
      new JGraphXAdapter<String, DefaultEdge>(g);
    mxIGraphLayout layout = new mxCircleLayout(graphAdapter);
    layout.execute(graphAdapter.getDefaultParent());

    BufferedImage image =
      mxCellRenderer.createBufferedImage(graphAdapter, null, 2, Color.WHITE, true, null);
    File imgFile = new File("src/test/resources/graph.png");
    ImageIO.write(image, "PNG", imgFile);

    assertTrue(imgFile.exists());
}

ここで、コンストラクタ引数としてグラフを受け取る

JGraphXAdapter

を作成し、それに

__mxCircleLayout

__を適用しました。

これは視覚化を円形にレイアウトします。

また、

mxCellRenderer

を使用して

BufferedImage

を作成してから、ビジュアライゼーションをpngファイルに書き込みます。

  • ブラウザまたは私たちのお気に入りのレンダラで最終的な画像を見ることができます。**

詳細はhttps://jgraph.github.io/mxgraph/docs/manual__javavis.html[公式文書]にあります。


6. 結論

JGraphTは、ほぼすべての種類のグラフとさまざまなグラフアルゴリズムを提供します。いくつかの一般的なAPIの使用方法について説明しました。ただし、http://jgrapht.org/[公式ページ]でいつでもライブラリを探索できます。

これらすべての例とコードスニペットの実装はhttps://github.com/eugenp/tutorials/tree/master/algorithms-miscellaneous-2[over on Github]で見つけることができます。