Add isAcyclic, topSort, dfs and other graph analysis functions to ToGraph

[fosskers]

Or likewise, isCircular. Basically, a top-level function to determine if some Graph type is a DAG or not.

As last time (thanks again), I suspect there's some composition of the exposed primitives that "just works", but nothing jumped out at me after a brief scan of the API.

Thoughts?

[snowleopard]

@fosskers Thanks! I agree, this is a useful function to add. If you don't necessarily need a polymorphic function, the implementation is quite simple:

isDag :: Ord a => AdjacencyMap a -> Bool
isDag = isJust . topSort

You'll just need to convert your graph data type to AdjacencyMap.

With the new ToGraph type class (coming soon in algebraic-graphs-0.2), I believe we could even add it as a separate method, giving you isAcyclic :: (ToGraph g, Ord (ToVertex g)) => g -> Bool.

[fosskers]

Ah ha! So it was just a simple thing. And luckily for me, I'm already using AdjacencyMap.

From the Haddocks:

Compute the topological sort of a graph or return Nothing if the graph is cyclic.

Perhaps I should have used my eyes to read 😢

[snowleopard]

No problem :) I'll keep the issue open, to remember to add a few methods to ToGraph class. I guess, we'll need to add not just isAcyclic but also topSort, dfs, etc.

[fosskers]

So isJust . topSort tells us if there's a cycle, which by itself is still very useful. Would it be hard to report the values of the vertices that are causing the cycle?

[snowleopard]

@fosskers To find the cycle, you can use the scc function. It returns you a graph whose vertices are strongly-connected components, and if any component contains more than a single vertex it is a cycle.

Here is one possible way to use is:

cycles :: Ord a => AdjacencyMap a -> [AdjacencyMap a]
cycles x = [ induce (`Set.member` c) x | c <- cs ]
  where
    cs = filter (\c -> Set.size c > 1) $ vertexList (scc x)

We obtain the list cs which contains non-singleton components (i.e. cyclic subgraphs), and then compute corresponding induced subgraphs of the original graph. As a result you can see all cycles in isolation.

For example:

> cycles $ path [1, 2, 3]
[]

> cycles $ circuit [1, 2, 3]
[edges [(1,2),(2,3),(3,1)]]

> cycles $ circuit [1, 2, 3] + path [3, 4, 5] + circuit [5, 6, 7]
[edges [(1,2),(2,3),(3,1)],edges [(5,6),(6,7),(7,5)]]

[fosskers]

Holy crap that's fantastic. I'm going to try that out right away.

[fosskers]

Alright, looking good! Thanks a lot, once again.

[snowleopard]

@fosskers Great! I'll keep this issue open -- isAcyclic seems like a useful function to add to the API.

[fosskers]

Woops, my bad.