OCaml中的Graph疑惑及与Graph相关的函数

Question

我这里有这段代码：

type ('state,'letter) automaton = {
  initial    : 'state ;
  final      : 'state -> bool ;
  transition : 'letter -> 'state -> 'state ;
}   

let example_graph =
{ 
nodes = ['a'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
edges = ['h', 'g';  'k', 'f';  'f', 'b';  'f', 'c';  'c', 'b']

}

这是OCaml网站给出的关于graths的默认示例。

我的问题是，如何在 OCaml 中使用图表？我的意思是 Lists 我们有一个很大的功能页面可以帮助我们使用它，但我没有找到任何关于带有图形的预定义功能的信息。

我有一项复杂的图表工作，更准确地说，我需要用 OCaml 构建一个 automaton，但首先我想了解如何进行简单的思考例如从图表中获取 nodes，如何转换我的节点和边缘输入值，或者我如何使用我这里的图表进行测试，例如我如何在节点之间移动.. .（好吧，你能记住的每一个简单的动作，或者我能得到更多信息的任何地方都会有所帮助）

基本上我想知道网络上是否有任何地方可以让我获得有关 OCaml 中的图形或函数的更好信息，如果你们可以帮助我！

谢谢

PS: 我已经搜索过了，没有找到真正有用的东西（对于像我这样的初学者来说只有很多复杂的代码）

Answer 1

嗯，我认为 ocamlgraph 对于新的 OCaml 程序员来说有点复杂（但以后使用它会是个好主意）。

据我了解，您想以易于理解的方式处理节点和边。

首先，我会建议您使用此模块测试 Map module (with it's tutorial) because it's a fast and simple way of doing it (I implemented the Glushkov's construction，并且效果非常好）。

给你一个小见识：

type ('state,'letter) automaton = {
  initial    : 'state ;
  final      : 'state -> bool ;
  transition : 'letter -> 'state -> 'state ;
}

这就是你到现在为止看到的自动机的样子。

type ('state,'letter) automaton = {
  initial    : 'state ;
  final      : 'state -> bool ;
  transition : ('letter, 'state) list Map.Make('state);
}

这就是我的看法（这不是一个正确的实现，因为 'state 不是一个明显的有序类型，但想法就在这里）。您可以将任何州映射到州列表（如果您了解如何创建新地图，您可能会使用 Set 而不是列表）。

尝试自己实现它，它真的很有用，你可以学到很多东西。

Answer 2

OCaml 对图表有很好的支持，这要归功于我们为了程序分析而开始的 OCamlgraph library. It is well documented, and very powerful, but it relies on functors a lot, and they usually confuse OCaml newbies. So you might also consider to try another graph library。它没有发布到官方 opam 存储库，但您始终可以从我们自己的存储库获取最新的 alpha 版本：

opam repository add git://github.com/BinaryAnalysisPlatform/opam-repository.git
opam install graphlib

P.S。 Graphlib 不是 OCamlgraph 的替代品，它与 OCamlgraph 配合得很好。它只是有一点不同的重点。当 graphlib 时，OCamlGraph 更侧重于适用于任何图形表示的通用算法更侧重于图形数据结构。所以它更容易使用，但更难扩展。

OCaml中的Graph疑惑及与Graph相关的函数

Graph doubts in OCaml and functions related with graphs

ocaml

graph