Топологическая сортировка в OCaml

Ответ 1

Во-первых, имейте в виду, что Objective Caml поддерживает стиль программирования, который, несмотря на синтаксические различия, довольно похож на С++, с помощью изменяемых структур данных (ссылок, массивов, хэш-таблиц) и императивных конструкций (для циклов while и while, переменное присвоение). Ниже я предполагаю, что вы на самом деле пытаетесь написать свой топологический вид в идиоматическом чистом функциональном стиле.

Чисто функциональное программирование в основном декларативно: эта функция применяется к этому значению . Это другое значение. Вот почему правая часть let x = является выражением (оценивается значением) вместо последовательности действий, которая использует return. Конечно, проблема возникает при адаптации алгоритма, который обычно описывается как последовательность шагов.

К счастью, существует шаблон (на самом деле, семейство шаблонов), который позволяет вам представить императивные алгоритмы в функциональном стиле, превратив "изменить значение X" в "вернуть новый объект, который идентичен старому, за исключением значения X".

Традиционный алгоритм DFS включает в себя переход по графику, запоминая, какие элементы уже были посещены - в общем случае (чтобы вы не посещали их более одного раза) и чтобы перейти к вашей текущей позиции (чтобы вы могли обнаруживать циклы). Таким образом, императивное состояние алгоритма DFS состоит из текущего node, набора посещенных узлов и набора узлов в текущем пути. Все эти данные должны быть предоставлены для рекурсивных вызовов, и любые постоянные изменения должны быть возвращены теми же рекурсивными вызовами.

Использование структуры графика сверху, в сочетании с представлением списка для двух наборов (это вряд ли оптимально - Set было бы лучшим выбором здесь), алгоритм выглядел бы примерно так:

let dfs graph start_node = 
  let rec explore path visited node = 
    if List.mem node path    then raise (CycleFound path) else
    if List.mem node visited then visited else     
      let new_path = node :: path in 
      let edges    = List.assoc node graph in
      let visited  = List.fold_left (explore new_path) visited edges in
      node :: visited
  in explore [] [] start_node

Три важные детали выше: во-первых, DFS говорит, что вы закончили изучение всех дочерних элементов данного node, вы должны удалить этот node из списка "текущий путь" и поместить его в "посещенный", список. Поскольку мы используем неизменяемые структуры данных, первый шаг не нужен: его единственной целью было отменить вставку node при запуске исследования, а в нашей версии список new_path не изменяется рекурсивным вызовом explore. Это пример того, где функциональные структуры данных более удобны в работе, чем императивные структуры.

Еще одна важная деталь - использование List.fold_left. Когда мы начали делать явное состояние, мы заменили неявные императивные функции типа -> unit на явные функции типа -> state -> .. -> state (принимаем состояние как параметр, возвращаем новое состояние). Итак, исследование обязательного списка, которое выглядело следующим образом:

f edge_1 ; f edge_2 ; f edge_3

Теперь выглядит так:

let state = f (f (f state edge_1) edge_2) edge_3)

Это именно то, что делает List.fold_left f state [edge_1 ; edge_2 ; edge_3]. Тоже мой собственный рог, но я хорошая статья об этом здесь.

Третий момент заключается в том, что операция "добавить элемент для установки" при использовании списков для представления множеств написана просто как element :: set, потому что это операция, которая возвращает новый набор (список), который содержит все элементы исходного набора вместе с новым элементом. Это оставляет исходный набор нетронутым (что хорошо по причинам, описанным на первом шаге) при использовании постоянного объема памяти (он создает ячейку cons - простую пару хвостового хвоста, содержащую ссылку на элемент и ссылку на набор ): вы не только получаете возможности отмены, но и делаете это без каких-либо дополнительных затрат.

Вышеупомянутый алгоритм "вставляет" узлы в visited, начиная с листьев исследования DFS, которые в вашем случае представляют те узлы, которые должны быть выполнены последними. Короче говоря, возвращаемый список топологически отсортирован - но может не содержать всех элементов, потому что исходная точка может не быть единственным корневым элементом (или даже быть корневым элементом вообще). Итак, здесь задействован дополнительный шаг обработки, который состоит в том, чтобы извлечь еще один node из графика, пока не будет изучен весь график.

Или, другими словами, запуск нового исследования DFS из каждого node в графике, но игнорирование любых ранее изученных узлов, что эквивалентно сохранению списка посещенных элементов из одной разведки DFS в следующую.

Используя небольшую настройку для нашего предыдущего алгоритма, это занимает всего две строки:

let dfs graph visited start_node = 
  let rec explore path visited node = 
    if List.mem node path    then raise (CycleFound path) else
    if List.mem node visited then visited else     
      let new_path = node :: path in 
      let edges    = List.assoc node graph in
      let visited  = List.fold_left (explore new_path) visited edges in
      node :: visited
  in explore [] visited start_node

let toposort graph = 
  List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph

Настройка состоит в том, чтобы позволить вызывающему абоненту dfs указать список уже посещенных узлов. Перенос списка посещаемых узлов при запуске DFS из каждого node выполняется с помощью List.fold_left точно так же, как и раньше.

EDIT: кроме типа исключения, здесь нет ничего, что ограничивало бы тип элементов на графике. Однако исключение не может быть полиморфным, поэтому у вас есть два возможных решения. Первый заключается в том, чтобы отказаться от фактического возврата любых данных вместе с исключением:

exception CycleFound

... raise CycleFound ...

Это вернет тип toposort обратно к более универсальному ('a * ('a list)) list -> 'a list.

Другим решением является довольно продвинутый OCaml: вам нужно сделать модуль, который содержит исключение и топологическую сортировку в этом конкретном типе, следующим образом:

module type NODE = sig
  type t 
end

module type Topo = functor (Node:NODE) -> struct 
  exception CycleFound of Node.t list      
  let dfs ...
  let sort ...  
end

Это сделает тип Topo(Node).sort be (Node.t * (Node.t list)) list -> Node.t list, что означает, что вы можете отсортировать любой тип, который вы хотите, определив модуль node с этим типом:

type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve

module Node = struct 
  type t = recipe 
end

let graph = [ Wheat, [Eggs,Milk,Mix] ;
              Milk,  [Mix] ;
              Eggs,  [Mix] ;
              Mix,   [Cook] ;
              Cook,  [Serve] ;
              Serve, [] ]

module RecipeTopo = Topo(Node)

let sorted = RecipeTopo.sort graph

Ответ 2

[Если вы не знаете термин, где я пишу DAG ниже, я имею в виду "направленный ациклический граф" или набор из/в ребра, соединяющие вершины, такие, что циклов нет.]

Один из способов сделать это - расширить ваш частичный порядок (ваша структура DAG) в полный порядок (так что для каждой пары различных вершин u и v либо u является преемником v, либо наоборот). Затем вы можете упорядочить свои вершины: u подходит до v, если v является преемником u.

Вы можете построить свой общий порядок, начиная с пустого графика и добавляя по одному краю за раз от вашей оригинальной группы DAG. То есть элемент (u, [v1; v2;...; vn]) в вашей оригинальной DAG соответствует ребрам (u, v1), (u, v2),..., (u, vn). Для каждого такого ребра (u, v) найдем предшественники P из u и преемники S of v из вашего общего порядка. Затем добавьте (p, s) к вашему полному порядку для всех p из P U {u} и s из S U {v}.

сейчас! Более быстрый способ сделать это - найти корень в исходной DAG (т.е. Вершине без предшественников) и выполнить первый поиск глубины из этого корня, гарантируя, что вы никогда не будете посещать одну и ту же вершину дважды. Каждый раз, когда вы возвращаетесь в свой обход, вы "выводите" вершину, которую вы оставляете. Таким образом, вы строите топологический тип своей DAG. Если остались какие-то вершины, прополощите полоскание и повторите, пока все не закончится.

Ответ 3

Сначала вы должны попробовать DFS, это проще и полезно.

Ответ 4

Я не знаю OCaml, но есть простой алгоритм в Wikipedia, аккредитованный в Kahn, который я успешно использовал (переписывание на Python). Это довольно просто, поэтому, возможно, вы можете перевести его в OCaml. Вот он:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)