Как представить структуру данных графа, используя список краев в 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 , которая может быть лучшим источником идей, чем все, что я могу придумать!