CODEWITHSUNDEEP
recursionf#depth-first-search
Neeraj Athalye
Neeraj Athalye

Reputation: 547

Depth First Search for adjacency list in F#

I have a list that is structured as follows: 

0 ; (0,0,G) ; []
1 ; (9,0,B) ; []
2 ; (9,9,R) ; []
3 ; (-1,-1,E) ; []
4 ; (-1,-1,E) ; []
5 ; (-1,-1,E) ; []
6 ; (-1,-1,E) ; []
7 ; (-1,-1,E) ; []
8 ; (-1,-1,E) ; []

Each item in the list has an index, a tuple and a list of its nearby neighbors which contains the neighbor's index.

My search begins at either index 1 or index 2 and I need all the paths from them to index 0. Additionally, I also need a list that contains all the indices along the path.

I have used recursion to implement this and am using a global mutable variable(blueChains) to store all the possible paths. I want to do the same without using a global variable but instead, I want the function to return the list of all paths as its causing problems in other parts of my code.

This is how my function looks: 

let rec traverseBlue index visited = 

    match index with 
    | 0 ->
        let newVisited = 0 :: visited
        blueChains <- newVisited :: blueChains
        printfn "Golden Cog Reached! Blue wins the game!"
        currentGameStatus <- WonByB 
    | ind -> 
        if not (List.contains ind visited) then
            let newVisited = ind :: visited
            blueChains <- newVisited :: blueChains
            printfn "INDEX: %i VISITED: %A" ind newVisited
            for i in tree.[ind].connectedNodes do
                traverseBlue i newVisited

The output that I get is: 

INDEX: 1 VISITED: [1]
INDEX: 3 VISITED: [3; 1]
BLUE CHAINS : [[1]; [1; 3]]

I want to get this same value for blue chains but without the use of a global variable

Upvotes: 0

Views: 193

Answers (1)

Neeraj Athalye
Neeraj Athalye

Reputation: 547

This is what I finally did thanks to @glennsl that solved my problem. 

let rec traverseBlue index visited oldBlueChains = 

let mutable blueChains = []
match index with 
| 0 ->
    let newVisited = 0 :: visited
    blueChains <- newVisited :: oldBlueChains
    printfn "Golden Cog Reached! Blue wins the game!"
    currentGameStatus <- WonByB 
    blueChains
| ind -> 
    if not (List.contains ind visited) then
        let newVisited = ind :: visited
        blueChains <- newVisited :: oldBlueChains
        printfn "INDEX: %i VISITED: %A" ind newVisited
        for i in tree.[ind].connectedNodes do
            blueChains <- (traverseBlue i newVisited blueChains) @ blueChains

Upvotes: 1

Related Questions