OCaml 有向图顶点模块

Question

我看过一些图顶点签名，甚至想出了我自己的：

module type VERTEX = sig
    type t
    type label

    val equal : t -> t -> bool
    val create : label -> t
    val label : t -> label  
end

但是我完全不知道如何将它实现为一个模块。 t 和 label 应该是什么类型？如何根据标签创建 t？我如何从 t 获取标签？

Answer 1

根据签名实现模块就像一个迷你拼图。以下是我将如何分析它：

我在阅读该签名时的第一句话是，该签名无法构建 label 类型的值。因此，我们的实现需要更大一些，可能需要指定 type label = string.

现在，我们有：

val create : label -> t
val label : t -> label

这是一个双射（类型是"equivalent"）。实现它的最简单方法是定义 type t = label，这样它实际上只有一种类型，但从模块的外部看您并不知道这一点。

剩下的就是

type t
val equal: t -> t -> bool

我们说label = string，t = label。所以t = string和equal就是字符串相等。

轰！我们在这里：

module String_vertex : VERTEX with type label = string = struct
  type label = string
  type t = string

  let equal = String.equal

  let create x = x
  let label x = x
end

VERTEX with type label = string部分只是如果你想在同一个文件中定义它。否则，您可以执行以下操作：

(* string_vertex.ml *)
type label = string
type t = string

let equal = String.equal

let create x = x
let label x = x

并且任何采用 VERTEX 的函子 F 都可以用 F(String_vertex) 调用。不过，最好创建内容为 include VERTEX with type label = string 的 string_vertex.mli。

Answer 2

我是Graphlib的作者，这个问题直击我的心，所以我不能跳过。老实说，我在离线状态下被问过数百万次这个问题，但始终无法提供一个好的答案。

真正的问题是 OCamlGraph 库中的图形界面都乱七八糟。我们启动 Graphlib 是为了尝试修复它们。然而，OCamlGraph 是一个有价值的图算法存储库，因此我们限制自己与 OCamlGraph 接口兼容。我们的主要问题过去是现在仍然是这个 Vertex 接口，它基本上在标签集和节点集之间建立了双射。人们通常会偶然发现这一点，因为这没有意义——如果它们相同，为什么我们需要两种不同的类型，一种用于标签，另一种用于顶点？

的确，VERTEX接口最简单的实现就是下面这个模块

module Int : VERTEX with type label = int = struct
  type t = int
  type label = int
  let create x = x 
  let label x = x
end

在那种情况下，我们确实在标签集和顶点集之间有一个微不足道的双射（通过身份内函子）。

然而，更深入的观察表明，签名

val create : label -> t
val label : t -> label

并不是真正的双射，因为双射是一对一的映射。类型系统并不是真正需要或强制执行的。例如，create 函数可以是 label 到 t 的满射，其中 label 是顶点族的一些独特元素。相应地，label 函数可以是一个遗忘函子，它 returns 独特的标签并忘记其他一切。

鉴于这种方法，我们可以有另一种实现方式：

  module Labeled = struct
    type label = int
    type t = {
      label : label;
      data : "";  
    }

    let create label = {label; data = ""}
    let label n = n.label
    let data n = n.data
    let with_data n data = {n with data}
    let compare x y = compare x.label y.label
  end

在该实现中，我们使用标签作为节点的标识，并且可以将任意属性附加到节点。在这种解释中，create 函数将所有节点集划分为一组 equivalence classes，其中 class 的所有成员共享相同的身份，即，它们代表相同的真实 -不同时间点或 space 的世界实体。例如，

type color = Red | Yellow | Green
module TrafficLight = struct 
   type label = int
   type t = {
     id : label;
     color : color
   }

   let create id = {id; color=Red}
   let label t = t.id
   let compare x y = compare x.id y.id
   let switch t color = {t with color}
   let color t = t.color
end

在此模型中，我们用其 ID 号表示交通灯。颜色属性不会影响交通灯的身份（如果交通灯切换到另一种颜色，它仍然是同一个交通灯，尽管在函数式编程语言中它由两个不同的对象表示）。

上述表示的主要问题是，在所有图形教科书中，标签都以相反的含义使用——作为不透明的属性。在教科书中，他们将交通灯的颜色称为标签。节点本身将表示为一个 int。这就是为什么我说 OCamlGraph 接口一团糟（因此 Graphlib 接口）。所以，如果你不想与教科书相矛盾，那么你应该使用未标记的图（int 可能是节点的最佳表示）。如果您需要将属性附加到您的节点，您可以使用外部有限映射，即数组、映射、关联列表或任何其他字典。否则，您需要记住您的标签不是标签，而是节点。

综上所述，让我们为图形顶点指定一个更好的接口：

module type VERTEX = sig 
  type id
  type label
  type t

  val create : id -> t
  val id : t -> id
  val label : t -> label
  val with_label : t -> label -> label
end

提议的接口与您的接口兼容（因此与 OCamlGraph 兼容），因为它是同构模重命名（即，我们将 label 重命名为 id）。它还允许我们创建高效的未标记节点，其中 id = t，以及在不依赖外部映射的情况下将任意信息附加到节点。

OCaml 有向图顶点模块

OCaml directed graphs vertex module

ocaml

module

graph

directed-graph

vertex