Ocaml: путь в графике повторяется, даже если он уже найден

Question

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

Например, вызов функции:
list_of_paths 2 7 (List.rev (bfs g1 2)) (node_succ g1) 2

возвращает:
[[2; 3; 6; 7]; [2; 3; 6; 7]; [2; 3; 4; 6; 7]; [2; 3; 6; 7]; [2; 1; 5; 6; 7]; [2; 3; 6; 7]; [2; 1; 5; 6; 7]]

Как видите, одни и те же пути повторяются. Может кто-нибудь сказать мне, где ошибка? Это код, который я написал:

type weight = int;;
type 'a graph = Gr of (int * weight * int) list;;
let g1 =  Gr [(1,3,2);(1,9,5);(2,2,3);(5,4,6);(3,1,6);(3,7,4);(6,2,7);(4,4,6)];;

let rec node_succ (Gr graph) node =
    let rec f_aux = function
        [] -> []
        | (x,y,z)::tail -> 
            if x = node then z::f_aux tail
            else if z = node then x::f_aux tail
            else f_aux tail in f_aux graph;;

let bfs graph s =
    let rec search visited_nodes = function 
        [] -> visited_nodes 
        | head::tail -> 
        if List.mem head visited_nodes then search visited_nodes tail
        else search (head::visited_nodes) (tail @ (node_succ graph head)) in search [] [s];;


let find_paths_bfs start stop graph =
    let extends paths = 
        List.map (function x -> x::paths) (List.filter (function x -> not (List.mem x paths)) (graph (List.hd paths)))
                in let rec s_aux stop = function
                    [] -> raise Not_found
                    | paths::tail -> 
                        if stop = List.hd paths then List.rev paths
                        else s_aux stop (tail @ (extends paths)) in s_aux stop [[start]];; 

let rec list_of_paths start stop reachable_nodes fun_graph_succ s =
    if reachable_nodes = [] then []
    else ((find_paths_bfs s start fun_graph_succ)@(List.tl(find_paths_bfs start stop fun_graph_succ)))
        ::(list_of_paths (List.hd reachable_nodes) stop (List.tl reachable_nodes) fun_graph_succ s);;

Функция node_succ возвращает всех возможных преемников узла.

Функция bfs возвращает все достижимые узлы из начального узла.

Функция find_paths_bfs находит один путь, начиная с узла и заканчивая другим.

Answer 1

Ваша реализация немного сложна (по крайней мере для новичка OCaml ie, как я :)). Я бы предложил сначала упростить это. Как я уже сказал, я абсолютный новичок в OCaml, поэтому возьмите следующее с недоверием (я вполне уверен, что мое решение далеко не оптимально или даже идиоматично c), но я бы go с что-то вроде:

let g1 = [(1,3,2);(1,9,5);(2,2,3);(5,4,6);(3,1,6);(3,7,4);(6,2,7);(4,4,6)];;

(* almost exact clone of your node_succ with the filtering capability added *)
let neighbors node graph except =
  let rec aux = function
    | [] -> []
    | (l,_,r)::tail ->
      if l == node then r::(aux tail)
      else if r == node then l::(aux tail)
      else aux tail
  in List.filter (fun x -> not (List.mem x except)) (aux graph)
;;

let walk graph start stop =
  let rec aux paths_found = function
    (* Unreachable branch taking into account the way we call aux; added to calm down the compliler *)
    | []::_ -> failwith "starting node is not specified"
    (* When nothing to traverse left just return the paths found *)
    | [] -> paths_found
    | (last_visited::tl as current)::left_to_traverse ->
        (* if the last visited node is equal to the stop one it means we found a target path - adding it (reversed) to the result and continue with the paths to traverse left *)
        if last_visited = stop then aux ((List.rev current)::paths_found) left_to_traverse
        (* otherwise, take the non-visited nodes that are reachable from the last visited one (except the ones from the tail that are visited already)... *)
        else match neighbors last_visited graph tl with
          (* ... and if there are none of them it means we are done with the current path, it's a dead end, just continue with the paths to traverse left *)
          | [] -> aux paths_found left_to_traverse
          (* ... and if there are some, "expand" the paths to traverse:
            1) create new path based on the current one by adding the neighbour
            2) add (1) to the paths to traverse
            3) repeat 1-2 for the next neighbour etc.
            4) continue traversing with the result of 1-3
          *)
          | ns -> 
            let next = List.fold_left (fun l x -> (x::current)::l) left_to_traverse ns in
            aux paths_found next
  in aux [] [[start]]
;;

walk g1 2 7 ;;
- : int list list = [[2; 1; 5; 6; 7]; [2; 3; 6; 7]; [2; 3; 4; 6; 7]]

UPD. Определения типов упрощены по сравнению с вашими; мой код, скорее всего, не будет работать с вашими типами из коробки.