gistfile1.txt

module Graph = struct
  type t = slot array array

  and slot =
    | Exist
    | Empty
    | Visited

  exception Missing_vertex of int

  let of_size (edges : int) : t =
    Array.make edges (Array.make edges Empty)

  let add_edge (graph : t) (left : int) (right : int) : unit =
    graph.(left).(right) <- Exist;
    graph.(right).(left) <- Exist

  let remove_edge (graph : t) (left : int) (right : int) : unit =
    graph.(left).(right) <- Empty;
    graph.(right).(left) <- Empty

  let degree (graph : t) (vertex : int) : int =
    Core.Array.count graph.(vertex) ~f:((=) Exist)

  let has_eulerian_path (graph : t) : bool =
    not @@ Core.Array.existsi graph ~f:(fun vertex _ ->
      let size = degree graph vertex in
      size = 0 || size mod 2 <> 0)

  let find_eulerian_path ?(start = 0) (graph : t) =
    let graph_size = Array.length graph in
    let find_unvisited vertex = fst @@ Core.Array.findi_exn graph.(vertex)
      ~f:(fun _ vertex -> vertex = Exist) in
    let trail = Core.Queue.create () in
    Core.Queue.enqueue trail start;
    let rec visit current =
      let subtour = Core.Queue.create () in
      let rec sub_visit current =
        match start = current with
        | true  -> ()
        | false ->
          let next = find_unvisited current in
          Core.Queue.enqueue subtour next;
          sub_visit next in
      sub_visit start;
      Core.Queue.
    in visit (find_unvisited start)

      let unvisited = Core.Array.findi graph.(item) ~f:(fun _ vertex -> vertex = Exist) in
      let subtour = Core.Queue.create () in
      Core.Queue.enqueue subtour item;
      match unvisited with
      | Some (current, _) ->
        let (unvisited, _) = Core.Array.findi_exn graph.(current) ~f:(fun _ vertex -> vertex = Exist) in
        Core.Queue.enqueue subtour unvisited
        visit
      | _ ->


end

let x =
  let graph = Graph.of_size 8 in
  Graph.add_edge graph 0 1;
  Graph.add_edge graph 0 3;
  Graph.add_edge graph 0 4;
  Graph.add_edge graph 0 5;
  Graph.add_edge graph 4 5;
  Graph.add_edge graph 1 2;
  Graph.add_edge graph 2 3;
  Graph.add_edge graph 0 6;
  Graph.add_edge graph 6 7;
  Graph.add_edge graph 0 7;
  assert (Graph.has_eulerian_path graph);