Breadth First Search with F#

There are many ways to represent graphs in F#. I here use a very straightforward way to represent a graph as an adjacency list as:


  let adjList = [[1; 2; 3]; [0; 4];  [0; 4]; [0; 4];  [1; 2; 3; 5; 6; 7]; [4; 8]; [4; 8]; [4; 8]; [5; 6; 7] ];;
Meaning node0 is adjacent to node1, node2, node3
              node1 is adjacent to node0, node4
and so on.


Here the code:


let clearIntersection list array =
List.filter (fun x -> not ((array : int array).[x] = 1)) list
;;


let SetArrayValues (theArray : int []) (markList : int list) (aValue : int) =
let rec MarkHead markList =
match markList with
| head::tail -> Array.set theArray head aValue
MarkHead tail
| [] -> []
MarkHead markList
;;


let MarkVisited visited markList =
SetArrayValues visited markList 1
;;


let MarkParents parents children theParent =
SetArrayValues parents children theParent
;;


let GetPath parents curr =
let rec traverse parents curr path =
let father = (parents : int array).[curr]
let path = curr::path
if father = -1
then path
else traverse parents father path
traverse parents curr []
;;


let BFS adjList s t = 
let n = (adjList : int list list).Length
let visited = (Array.zeroCreate n : int array)
let parents = Array.create n -1
let q = []
let loc = s
Array.set visited loc 1
let q = loc::q
let nextQ = []
let rec traverse q nextQ =
match q with
| head::tail -> let neighbors = (adjList : int list list).[head]
let children = clearIntersection neighbors visited
  MarkParents parents children head
    let posFound = ListContains children t
if posFound > -1
then GetPath parents posFound
else
MarkVisited visited children
let nextQ = children @ nextQ
traverse tail nextQ
| [] -> match nextQ with
| head::tail -> traverse nextQ []
| [] -> []
traverse q nextQ
;;


--------------------------------------------------------
And you can call it like this:


let adjList = [[1; 2; 3];
[0; 4];
[0; 4];
[0; 4];
[1; 2; 3; 5; 6; 7];
[4; 8];
[4; 8];
[4; 8];
[5; 6; 7]
];;

BFS adjList 0 8;;
----------------------------------------------------------------------------------------
find a path from 0 to 8 by breadth-first-search


In the console, the output would look as shown below:

It had been a while since I posted some F# stuff.