java - 有向グラフ 最小カット ライブラリ

Question

有向グラフの最小カットを実装する Scala (または Java) グラフ ライブラリを探しています。

私が使用することをお勧めするライブラリはありますか?

Answer 1

JUNGには 1 つ (Java 用) があります。

ドキュメント -> JUNG API Javadoc を確認してください。edu.uci.ics.jung.algorithms.flowsパッケージには、メソッドを持つクラスがあります。getMinCutEdges()

Answer 2

Scala グラフを見てください。APIで最小カットを提供しているようには見えませんが、必要なグラフアルゴリズムを実装するために使用できます.

Answer 3

Tinkerpop ブループリントはJUNGと組み合わせて使用​​することをお勧めします。なぜなら、ブループリントにはグラフ用の非常に優れたインターフェースと、グラフ I/O およびトラバーサル用の多くのヘルパーがあるからです。一方、JUNG にはすでに多くのアルゴリズムが実装されています。

com.tinkerpop.blueprints.pgm.oupl.jung.GraphJungTinkerpop には、JUNG 内で任意の Tinkerpop を使用できるように名前が付けられたクラスが含まれていますGraph。

例えば：

Graph graph = ... // construct a particular Blueprints graph implementation
PageRank<Vertex,Edge> pageRank = new PageRank<Vertex, Edge>(new GraphJung(graph), 0.15d);
pageRank.evaluate();