使用Johnson算法在图中寻找基本回路（循环）的实现

Question

使用Johnson算法在图中寻找基本回路（循环）的实现

algorithmgraphcycle

4

有没有人有实现这个算法以查找循环的源代码，最好使用像SML、OCaml、Haskell、F#、Scala这样的现代静态类型语言？

- J D

你是否曾经找到过一个公共实现，在F#中输出OCaml？或者即便在C#中也可以？ - Arturo Hernandez

@ArturoHernandez：不。 - J D

让我帮你在 GitHub 上搜索一下：Haskell 或 OCaml 或 F# 或 Scala。但是，SML 没有找到相关内容。 - milahu

4个回答

1

我也曾遇到这个问题，我想到了这个 page，它列出了一些在Java和OCaml中实现Johnson算法（寻找基本电路的算法）的例子。博客文章的作者修复了原始实现中的一些问题，在上面我提供的页面中还有两种实现的修复版本。

- Alessandro S.

1

您可以在 jgrapht 实现的这里找到它。

- Vishrant

0

你是否需要使用C++和Boost Graph Library？

- mlt

2

我已经检查了Boost Graph Library，它没有实现这个算法（我引用的Johnson算法可以找到所有循环，但你提到的Johnson算法可以为稀疏图找到所有对最短路径，即不同的东西）。事实上，我很惊讶BGL实现得如此之少。我还检查了OCaml的ocamlgraph、Haskell的图形库和其他一些库，但都没有成功。 - J D

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user152468 · Accepted Answer

以下是您需要的算法的Java实现：https://github.com/1123/johnson。由于Java运行在JVM上，您也可以从Scala中使用它。