有向圖最小切割庫

Question

我正在尋找一個爲有向圖實現最小切割的S​​cala（或Java）圖庫。

有什麼圖書館，你會推薦我使用？

Answer 1

JUNG有一個（對於Java）。

檢查文檔 - > JUNG API Javadoc。 edu.uci.ics.jung.algorithms.flows包裝有a class和getMinCutEdges()方法。

Answer 2

看看Scala graph。它看起來並不像它在API中提供最小的切割，但是你可以用它來實現你需要的任何圖形算法。

Answer 3

我建議使用Tinkerpop Blueprints與JUNG一起使用，因爲Blueprints有一個非常好的圖形接口和許多Helper for Graph I/O和Traversal，而JUNG已經實現了很多算法。

TinkerPop有關包括一類名爲com.tinkerpop.blueprints.pgm.oupl.jung.GraphJung，讓你可以使用任何TinkerPop有關Graph內JUNG。

例如：

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