Revisiting BFS

What is BFS

• BFS is a way of creating a sequence with all elements of a tree or graph
• It consists in returning all elements with depth N, and then the elements with depth N+1, until elements are over
• The initial depth is 0

The common solution

• The typical imperative implementation of BFS relies on a queue
• The current element is pulled out of the queue, and its children are pushed in

Questioning the common solution

• The relation between the queue, the way it works, and the BFS definition is not clear
• Is it possible to rely on pure functional data structures instead of mutation?

First discovery

• The queue in the imperative solution is divided in two parts: | children with depth N | children with depth N+1|
• Now is clear what we do is returning children in the same level, and meanwhile conveniently recording and postponing children in the next level
• We could have separate lists for children in different levels
• We could annotate each level with its corresponding number, so we can filter later which levels do we need

First restriction

• BFS in a graph requires to mark which nodes we have visited, while in a tree we don't, since in the latter case there's no possibility to create an infinite loop
• the function returning the children can take care independently of marking or not, depending on wether is a graph or a tree. That way the BFS implementation can be delivered from that concern, and thus is cleaner and more general.

Second restriction

• In functional programming instead of representing mutation in a block of code, we create a new instance of it substituting the old value by the new one.
• You can see the difference in comparing the following two blocks of code:

using System;

int[] MoveFromTo() {
    var from = new List<int>(new int[] { 1, 2, 3 });
    var to = new List<int>();
    while (from.Count > 0) {
        to.Add(from[0]);
        from.RemoveAt(0);
    }
    return to.ToArray();
}

let moveFromTo () =
    let rec loop from to' =
        match from with
        | [] -> (from, to')
        | x::xs -> 
            // here we replace to' by x::to' in a new instance of loop
            loop xs (x::to')
    
    let from = [1; 2 ;3]
    let to' = []
    loop from to'

How the implementation works

• GetChildren is our generic way of getting children from whatever nested structure we are dealing with (trees, graphs)
• Along with the list of children it returns and instance of itself. This is needed because is the functional way of updating the collection where we store visited nodes.
• Our List.fold processes each element x in level. In each iteration of it needs an updated GetChildren instance, which stores the visited nodes. You can see in the function passed as parameter how xs is replaced by xs @ ys and gc for newGc, for the next iteration.
• Once the fold finishes we have in nextLevel all the nodes of level n+1. Since nextLevel is the replacement for level and our bfs function operates on particular level instances, then is time to call bfs with nextLevel. In case nextLevel is empty, we return the empty sequence and stop the recursive calls.

type GetChildren<'a> = { get: 'a -> (GetChildren<'a> * 'a list) }

let rec bfs (gc: GetChildren<'a>, n: int, level: 'a list) =
  seq {
    yield (n, level)

    let nextLevel =
      level
      |> List.fold
        (fun (gc, xs) x ->
          let newGc, ys = gc.get x
          (newGc, xs @ ys)
        )

        (gc, []) // initial state
        
    yield! 
        match nextLevel with
        | _, [] -> Seq.empty
        | (chl, nl) -> bfs  (chl, n+1, nl)
  }

Testing the implementation with a graph

type Graph<'a when 'a: comparison> = Map<'a, List<'a>>

let graphChildren (g: Graph<'a>) =
  let rec children visited =
    { get =
        fun x ->
          if Set.contains x visited then
            // x is already visited, no need to mark it as visited
            (children visited, [])
          else
            let newChildren = Set.add x visited |> children

            match Map.tryFind x g with
            | Some xs -> (newChildren, xs)
            | None -> (newChildren, []) }

  children Set.empty

let g = Map [ 1, [ 2; 3; 4 ]; 2, [ 5; 6 ]; 3, [ 7; 8 ]; 4, [ 9; 10 ] ]

bfs (graphChildren g, 0, [ 1 ]) |> Seq.iter (printfn "%A")

(0, [1])
(1, [2; 3; 4])
(2, [5; 6; 7; 8; 9; 10])

Testing the implementation with a tree

In a tree by visiting a node there's no way of going back to it, since there are no cycles. Keeping that in mind, we can rely on a sequence of children to be consumed by bfs. As long as we put children in the order bfs expects them, the implementation will be correct.

Example: We know if bfs gets the children of node X, then after that it will ask for children of node X+1, where X and X+1 are consecutive nodes in the same level.

type Tree<'a> = Node of 'a * Tree<'a> list

let rec childrenSeq (Node(_, xs)) =
  seq {
    match xs with
    | [] -> ()
    | _ ->
      let nodeValues = xs |> List.map (fun (Node(x, _)) -> x)
      yield nodeValues

    for x in xs do
      yield! childrenSeq x
  }

let treeChildren (t: Tree<'a>) =
  let chs = childrenSeq t |> Seq.toList

  let rec loop (chs: ('a list) list) =
    { get =
        fun _ ->
          match chs with
          | [] -> (loop [], [])
          | head::tail -> (loop tail, head) }

  loop chs

let t =
  Node(
    1,
    [ Node(2, [ Node(5, []); Node(6, []) ])
      Node(3, [ Node(7, []); Node(8, []) ])
      Node(4, [ Node(9, []); Node(10, []) ]) ]
  )

bfs (treeChildren t, 0, [ 1 ]) |> Seq.iter (printfn "%A")

(0, [1])
(1, [2; 3; 4])
(2, [5; 6; 7; 8; 9; 10])