Data Structures in ReasonML: #8 Graph

Graph.re

/* Graph */
exception Not_found;

type nodes = list(int);

type edges = list((int, int));

type graph =
  | Empty
  | Graph(nodes, edges);

module type Graph = {
  type t = int;
  let empty: graph;
  let addNode: (t, graph) => graph;
  let addEdge: (t, t, graph) => graph;
  let removeNode: (t, graph) => graph;
  let removeEdge: (t, t, graph) => graph;
  let path: (t, t, graph) => list(t);
  let relations: graph => int;
  let size: graph => int;
};

module Graph: Graph = {
  type t = int;
  let empty = Empty;
  let addNode = (node, graph) =>
    switch (graph) {
    | Empty => Graph([node], [])
    | Graph(nodes, edges) => Graph([node, ...nodes], edges)
    };
  let removeNode = (node, graph) =>
    switch (graph) {
    | Empty => Empty
    | Graph([], edges) => Graph([], edges)
    | Graph(nodes, edges) =>
      Graph(
        List.filter(n => n !== node, nodes),
        List.filter(((f, t)) => node !== f && node !== t, edges),
      )
    };
  let addEdge = (from_, to_, graph) =>
    switch (graph) {
    | Empty => Empty
    | Graph(nodes, edges) => Graph(nodes, [(from_, to_), ...edges])
    };
  let removeEdge = (from_, to_, graph) =>
    switch (graph) {
    | Empty => Empty
    | Graph(nodes, []) => Graph(nodes, [])
    | Graph(nodes, edges) =>
      Graph(
        nodes,
        List.filter(((f, t)) => from_ !== f || to_ !== t, edges),
      )
    };
  let size = graph =>
    switch (graph) {
    | Empty => 0
    | Graph(nodes, _) => List.length(nodes)
    };
  let relations = graph =>
    switch (graph) {
    | Empty => 0
    | Graph(_, edges) => List.length(edges)
    };
  let getNeighbors = (from_, cond, graph) =>
    switch (graph) {
    | Empty => []
    | Graph(_, edges) =>
      List.fold_left(
        (list, (fr_, to_)) =>
          if (fr_ == from_ && cond(to_)) {
            [to_, ...list];
          } else if (to_ == from_ && cond(fr_)) {
            [fr_, ...list];
          } else {
            list;
          },
        [],
        edges,
      )
    };
  let rec listPath = (from_, to_, graph) =>
    switch (to_) {
    | [] => raise(Not_found)
    | [first, ..._] =>
      if (first === from_) {
        to_;
      } else {
        let possiblePaths =
          List.map(
            t => listPath(from_, [t, ...to_], graph),
            getNeighbors(first, a => ! List.mem(a, to_), graph),
          );
        List.fold_left(
          (shortestPath, path) =>
            switch (shortestPath, path) {
            | ([], []) => []
            | (currentPath, []) => currentPath
            | ([], path) => path
            | (currentPath, path) =>
              if (List.length(path) < List.length(currentPath)) {
                path;
              } else {
                currentPath;
              }
            },
          [],
          possiblePaths,
        );
      }
    };
  let path = (from_, to_, graph) =>
    if (from_ === to_) {
      [to_];
    } else {
      listPath(from_, [to_], graph);
    };
};

let run = () => {
  let printPath = path =>
    List.fold_left((s, v) => s ++ string_of_int(v) ++ " ", "", path);
  let t = Graph.empty;
  let t = Graph.addNode(1, t);
  let t = Graph.addNode(2, t);
  let t = Graph.addNode(3, t);
  let t = Graph.addNode(4, t);
  let t = Graph.addNode(5, t);
  let t = Graph.addEdge(1, 2, t);
  let t = Graph.addEdge(1, 4, t);
  let t = Graph.addEdge(2, 5, t);
  let t = Graph.addEdge(3, 4, t);
  let t = Graph.addEdge(3, 5, t);
  let t = Graph.addEdge(4, 5, t);
  Js.log2("Size is 5: ", Graph.size(t) === 5);
  Js.log2("Relations is 6: ", Graph.relations(t) === 6);
  Js.log2("path from 5 to 1 is 5 2 1 -> ", printPath(Graph.path(5, 1, t)));
  Js.log2("path from 2 to 4 is 2 1 4 -> ", printPath(Graph.path(2, 4, t)));
  let t = Graph.removeEdge(1, 2, t);
  let t = Graph.removeEdge(4, 5, t);
  Js.log2("Relations is 4:", Graph.relations(t) === 4);
  Js.log2(
    "path from 5 to 1 is 5 3 4 1 -> ",
    printPath(Graph.path(5, 1, t)),
  );
  Js.log2(
    "path from 2 to 4 is 2 5 3 4 -> ",
    printPath(Graph.path(2, 4, t)),
  );
  let t = Graph.addEdge(1, 2, t);
  let t = Graph.addEdge(4, 5, t);
  Js.log2("Relations is 6:", Graph.relations(t) === 6);
  Js.log2("path from 5 to 1 is 5 4 1 -> ", printPath(Graph.path(5, 1, t)));
  Js.log2("path from 2 to 4 is 2 1 4 -> ", printPath(Graph.path(2, 4, t)));
  let t = Graph.removeNode(3, t);
  Js.log2("Size is 4: ", Graph.size(t) === 4);
  Js.log2("Relations is 4: ", Graph.relations(t) === 4);
  Js.log2("path from 5 to 1 is 5 4 1 -> ", printPath(Graph.path(5, 1, t)));
  Js.log2("path from 2 to 4 is 2 1 4 -> ", printPath(Graph.path(2, 4, t)));
};

run();