如何使用OCaml中的边缘列表表示图形数据结构？

Question

我试图使用不相交的联合和记录来表示图形.以下代码导致语法错误.如何在彼此引用时定义两个变量？

type 'a vertex = 
  |Empty
  |Vertex of 'a * 'a list;; (*a tuple consisting of any type of element and a list of vertex*);

let v0 = Vertex(0,[v1]) in
let v1=Vertex(1,[v0]);;

如果我将代码修改为:

let rec v0 = Vertex(0,[v1]) and  v1=Vertex(1,[v0]);;

我会得到v0:

[Vertex (1,
  [Vertex (0,
    [Vertex (1,
      [Vertex (0,
        [Vertex (1,
          [Vertex (0,
            [Vertex (1,
              [Vertex (0,
                [Vertex (1,
                  [Vertex (0,
                    [Vertex (1,
                      [Vertex (0,
                        [Vertex (1,
                          [Vertex (0,
                            [Vertex (1,
                              [Vertex (0,
                                [Vertex (1,
                                  [Vertex (0,
                                    [Vertex (1,
                                      [Vertex (0,
                                        [Vertex (1,
                                          [Vertex (0,
                                            [Vertex (1,
                                              [Vertex (0,
                                                [Vertex (1,
                                                  [Vertex (0,
                                                    [Vertex (1,
                                                      [Vertex (0,
                                                        [Vertex (1,
                                                          [Vertex (0,
                                                            [Vertex (1,
                                                              [Vertex (0,
                                                                [Vertex (1,
                                                                  [Vertex (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [Vertex
                                                                    (1,
                                                                    [Vertex
                                                                    (0,
                                                                    [...])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])])]

这似乎不是我想要的......

定义包含顶点列表或数组的图形记录的最佳方法是什么？显然我不能这样做:

type graph = {
    vertex_set:array};;

我收到以下消息:

Error: The type constructor array expects 1 argument(s),
       but is here applied to 0 argument(s)

Answer 1

您的类型定义中存在错误.我很确定你想要的是:

type 'a vertex = 
  |Empty
  |Vertex of 'a * 'a vertex list

您可以使用let rec以下方法定义此类型的值:

let rec v0 = Vertex(0, [v1]) and v1 = Vertex(1, [v0])

根据我的经验,很难处理这类价值观.OCaml是一种急切的语言,因此使用循环值进行计算很困难.

对于第二个问题,编译器试图告诉你,array它本身不是一个类型.你需要说什么这是一个数组的.

type 'a vertices = {
    vertex_set: 'a vertex array;
}

如果你想要一个顶点列表而不是一个数组(可能是个好主意),它看起来像这样:

type 'a vertices = {
    vertex_set: 'a vertex list;
}

在我看来,你有两个问题.首先,您需要了解如何在OCaml中指定类型和值.这不是很难,你可以在这里得到很好的建议.其次,您需要决定用于表示图形的数据结构.这更难,而且没有全面的最佳方法.您可能不希望使用本身就是图形的数据结构(如上所述).更现实的可能性是:邻接矩阵,或具有其外边缘列表的顶点集合.为避免创建循环结构,您只需引用顶点而不是直接将它们包含在边列表中.例如,如果顶点在数组中,则可以通过数组索引引用它们.

有一个名为ocamlgraph的图书馆可能比我想出的任何东西都更好的思想来源!