java - 有向图最小割库

Question

我正在寻找一个为有向图实现最小切割的 Scala（或 Java）图形库。

有没有你推荐我使用的图书馆？

Answer 1

JUNG有一个（用于 Java）。

检查文档 -> JUNG API Javadoc。该edu.uci.ics.jung.algorithms.flows包有一个带有getMinCutEdges()方法的类。

Answer 2

我建议将Tinkerpop Blueprints与JUNG结合使用，因为 Blueprints 具有非常好的图形界面和许多用于图形 I/O 和遍历的 Helpers，而 JUNG 已经实现了很多算法。

Tinkerpop 包含一个名为的类com.tinkerpop.blueprints.pgm.oupl.jung.GraphJung，以便您可以Graph在 JUNG 中使用任何 Tinkerpop。

例如：

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

Answer 3

看看Scala 图。它看起来不像在 API 中提供最小切割，但您可以使用它来实现您需要的任何图形算法。