Обнаружение цикла в неориентированном графике в Ocaml - PullRequest
Новая
       22

Обнаружение цикла в неориентированном графике в Ocaml

0 голосов
/ 12 января 2020

Кто-нибудь знает, как определить, есть ли цикл в неориентированном графе в OCaml?

Вот тип, который я использую для графа: 

type 'a graph = { nodes : 'a list; edges : ('a * 'a * int) list }

И, например, Я хотел бы проверить, содержит ли этот график циклы: 

let graph = { nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'j';]; 
              edges = [('c', 'j', 9); ('d', 'e', 8); ('a', 'b', 8); ('b', 'c', 7); ('f', 'g', 6); ('b', 'h', 4); ('a', 'd', 4); ('g', 'h', 2); ('b', 'f', 2); ('e', 'g', 1)]}

Ответы [ 3 ]

0 голосов
/ 14 января 2020

Также можно избежать посещения одного и того же ребра дважды, удалив его из списка доступных ребер; предполагая, что порядок не имеет значения среди ребер, вы можете удалить ребро следующим образом: 

let edges_remove_edge edges edge =
  let (src, dst, _) = edge in
  let rec iter edges res = match edges with
    | [] -> res
    | ((s, d, _) as e)::edges ->
       if (s = src && d = dst) then
         res @ edges
       else
         iter edges (e::res)
  in iter edges []

Удаление ребра из графа затем выполняется путем построения нового графа, который разделяет данные с предыдущим графом, но с измененный список ребер: 

let graph_remove_edge graph edge =
  { nodes = graph.nodes;
    edges = edges_remove_edge graph.edges edge }

Затем вы можете преобразовать граф по рекурсивным вызовам обхода вашего графа; пример здесь не делает ничего интересного, он просто демонстрирует структуру: 

let choose_edge graph = match graph.edges with
  | [] -> None
  | e::_ -> Some e;;

let rec visit graph = match (choose_edge graph) with
  | None -> graph
  | Some e -> visit (graph_remove_edge graph e);;

# visit graph;;
- : char graph =
{nodes = ['a'; 'b'; 'c'; 'd'; 'e'; 'f'; 'g'; 'h'; 'j']; edges = []}

Или вы отслеживаете текущий график с помощью ссылки: 

let visit2 graph =
  let g = ref graph in
  let rec v () = match (choose_edge !g) with
  | None -> ()
  | Some e -> begin g := graph_remove_edge !g e; v () end
  in v(); !g
0 голосов
/ 22 января 2020

Мне удалось обнаружить цикл с помощью структуры данных union-find.

Структура, представляющая подмножество для union-find: 

let create n =
    {parent = Array.init n (fun i -> i);
     rank = Array.init n (fun i -> 0)}

Вспомогательная функция для поиска набора элемент. Он использует метод сжатия пути: 

let rec find uf i =
  let pi = uf.parent.(i) in
  if pi == i then
     i
  else begin
     let ci = find uf pi in
     uf.parent.(i) <- ci;
     ci
  end

Функция, которая объединяет два набора x и y. Он использует объединение по рангу: 

let union ({ parent = p; rank = r } as uf) x y =
    let cx = find uf x in
    let cy = find uf y in
    if cx == cy then raise (Failure "Cycle detected") else  begin
       if r.(cx) > r.(cy) then
          p.(cy) <- cx
       else if r.(cx) < r.(cy) then
          p.(cx) <- cy
       else begin
          r.(cx) <- r.(cx) + 1;
          p.(cy) <- cx
       end
    end

Я создал функцию для проверки наличия цикла. 

let thereIsCycle c1 c2 g subset =
  let isCycle = try Some (union subset (findIndex c1 g.nodes) (findIndex c2 g.nodes)) with _ -> None in
      match isCycle with
     | Some isCycle -> false
     | None -> true

let rec findIndex x lst =
    match lst with
    | [] -> raise (Failure "Not Found")
    | h :: t -> if x = h then 0 else 1 + findIndex x t
0 голосов
/ 13 января 2020

Как на направленных, так и на ненаправленных графиках присутствие цикла определяется с использованием поиск в глубину . Грубо говоря, вы пересекаете график, и если прогулка содержит повторяющиеся узлы, то возникает цикл.

Обычно для маркировки уже посещенных узлов используется дополнительная структура данных. Например, мы можем использовать заданную структуру данных (используя vanilla OCaml), 

module Nodes = Set.Make(struct 
                 type t = int
                 let compare = compare
               end)

let dfs {edges} f x = 
 let rec loop visited x = function
   | [] -> x 
   | (src,dst,data) :: rest -> 
     let x = f src data in
     let visited = Nodes.add src visited in
     if Nodes.mem dst visited 
     then loop visited x rest
     else ... in
  loop Nodes.empty x edges

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

Если вы не делаете это для упражнения, я бы посоветовал вам использовать некоторую существующую библиотеку Graph в OCaml, например, OCamlgraph ( docs ) или Graphlib ( документы ).

...