Detecting connected acyclic through Tarjan strongly connected components variant

Question

I want to verify that a given directed graph is connected and acyclic (DAG). I have implemented a modification of the Tarjan's strongly connected components algorithm in imperative style (as the original).

Every suggestion to improve simplicity, readability and suitable use of F# constructs will be wellcome.

Note: the current algorithm returns the value for acyclic property for the first cluster in disconnected graphs. I'm ok with that. Once I know it is not DAG I no need to analyze it further. But with this in mind I suppose the algorithm could be improved.

open System.Collections.Generic

type GraphKind = {
        acyclic : bool;
        connected : bool
    }

 let kindOfGraph getChildren v numNodes =

    let stack = Stack<_>()
    let visited = Dictionary<_,int * int>(HashIdentity.Structural)
    let discovered = HashSet<_>(HashIdentity.Structural)
    let sccs = ref 0
    let order = ref 0

    let rec scc getChildren v = 

        stack.Push (v)
        visited.Add(v, (!order, !order))
        incr order

        let vindex, vlink = visited.[v] 

        getChildren v
        |> List.map (fun w -> 
            if not <| visited.ContainsKey w then
                scc getChildren w
                visited.[v] <- (vindex, min vlink (snd visited.[w]))
            else if not <| discovered.Contains w then
                visited.[v] <- (vindex,min vlink (fst visited.[w])) 
        ) |> ignore

        let idx, lnk = visited.[v]

        if idx = lnk then

            let rec getscc (s : Stack<_>) root =
                let w = s.Pop()
                discovered.Add w |> ignore
                match w with
                | x when x = root -> ()
                | _ -> getscc s root

            getscc stack v   
            incr sccs

    scc getChildren v
    {
        acyclic = (!sccs = !order);
        connected = (!order = numNodes)
    }

And some tests using FsUnit and NUnit

open NUnit.Framework
open FsUnit

[<TestFixture>]
type ``kind of graph`` () =

let aTree = function
| 1 -> [2; 3]
| 2 -> [4; 5]
| _ -> [] 

let aTriangle = function
| 1 -> [2]
| 2 -> [3]
| 3 -> [1]

let aConnectedAcyclic = function
| 1 -> [2; 3]
| 2 -> [4; 5; 6]
| 4 -> [7]
| 6 -> [8; 9]
| 3 -> [10; 11; 13]
| 10 -> [9; 12]
| 11 -> [13]
| _ -> []

let aDisconnectedAcyclic = function
| 1 -> [2; 3]
| 4 -> [5]
| _ -> []

let aDisconnectedCyclic = function
| 1 -> [2]
| 2 -> [3]
| 3 -> [1]
| 4 -> [5]
| _ -> []

let aSingleNode = function | _ -> []

[<Test>] member x.
    ``given a tree`` () =
        kindOfGraph aTree 1 5 |> should equal { acyclic = true; connected = true}

[<Test>] member x.
    ``given a connected triangle`` () =
        kindOfGraph aTriangle 1 3 |> should equal { acyclic = false; connected = true}

[<Test>] member x.
    ``given a connected acyclic graph`` () =
        kindOfGraph aConnectedAcyclic 1 13 |> should equal { acyclic = true; connected = true}    

[<Test>] member x.
    ``given a single node`` () =
        kindOfGraph aSingleNode 1 1 |> should equal { acyclic = true; connected = true}    

[<Test>] member x.
    ``given a disconnected acyclic graph`` () =
        kindOfGraph aDisconnectedAcyclic 1 5 |> should equal { acyclic = true; connected = false}    

 [<Test>] member x.
    ``given a disconnected cyclic graph`` () =
        kindOfGraph aDisconnectedCyclic 1 5 |> should equal { acyclic = false; connected = false}    

Answer 1

I don't think graph algorithms work well with functional programming: you have to track which nodes were already visited and that pretty much requires global mutable state. You can simulate mutable state in a purely functional way by adding a parameter and a return value to the graph-walking function, but that quickly becomes tedious.

Because of that, I think that using imperative F#, or maybe even better, C# is a good choice here.

---

Your code does not tell you whether the graph is weakly connected, it tells you whether all nodes are reachable from the first node. (I'm assuming you're not interested in strongly connected graphs, because that implies cycles.) For example, given:

let aLine = function
| 0 -> [1]
| 1 -> [2]
| 2 -> [3]
| 3 -> []

Then (kindOfGraph aLine 0 4).connected returns true, while (kindOfGraph aLine 1 4).connected returns false. I don't know whether this is a bug in the code or whether you're misusing the word "connected" to mean something different, I could imagine both being the case.

---

I don't like that you're representing the graph as a function (plus the first node and size). I think that graph should be a self contained data structure, maybe something like Map<int, int list>.

---

I don't understand why are you using Tarjan's algorithm here.

To find out whether a graph contains cycles, DFS is enough.

To find whether all nodes are reachable from a specific node, simplified DFS (that doesn't try other starting nodes) will work.

To find whether a graph is weakly connected is more complicated. I think the simplest way would be to convert it to an undirected graph (by adding the reverse of each edge) and then performing DFS on that.

---

Since you're not actually interested in the connected and acyclic properties separately and since you're aware that your code is not always accurate when it comes to being acyclic, I would return only a single boolean value, not a record with misleading field names.