Implement transitive reduction

[ocharles]

I have found myself wanting the transitive reduction of a graph a few times. Could this be added to alga?

The transitive reduction of a finite directed acyclic graph (a directed graph without directed cycles) is unique and is a subgraph of the given graph. However, uniqueness fails for graphs with (directed) cycles, and for infinite graphs not even existence is guaranteed.

May pose a problem, I haven't given that much thought yet.

[snowleopard]

@ocharles Sure, transitive reduction is a useful operation to have, we should add it.

We haven't yet figured out how to deal with acyclic graphs in a nice way (#154), so for now we could think of the following type signature, with Nothing returned if the graph is cyclic:

transitiveReduction :: Ord a => AdjacencyMap a -> Maybe (AdjacencyMap a)

Here is a straightforward but very inefficient implementation:

-- This goes into Algebra.Graph.AdjacencyMap.Algorithm
transitiveReduction :: Ord a => AdjacencyMap a -> Maybe (AdjacencyMap a)
transitiveReduction g
    | not (isAcyclic g) = Nothing
    | otherwise         = Just $ vertices vs `overlay` edges es
  where
    vs = vertexList g
    es = filter (not . transitive) (edgeList g)
    jumpGraph         = let t = transitiveClosure g in compose t t
    transitive (x, y) = hasEdge x y jumpGraph

A quick sanity check:

λ> transitiveReduction $ 1 * 2
Just (edge 1 2)
λ> transitiveReduction $ 1 * 2 + 2 * 1
Nothing
λ> transitiveReduction $ 1 * 2 * 3 * 4
Just (edges [(1,2),(2,3),(3,4)])
λ> transitiveReduction $ 1 * 2 * 3 + 4 * 5 * 6
Just (edges [(1,2),(2,3),(4,5),(5,6)])
λ> transitiveReduction $ vertices [1..10] + clique [7,6..4]
Just (overlay (vertices [1,2,3,8,9,10]) (edges [(5,4),(6,5),(7,6)]))

If your graphs are not very big then this should be OK. Could you give it a try?

[ocharles]

Clean! I will give this a try, I don't actually have any graphs at hand atm - just planning some future work that might end up needing this!

[evanrelf]

FWIW the function posted above has worked fine for me. My graphs have thousands of vertices and tens of thousands of edges, though that's probably small.

[snowleopard]

@evanrelf Great, thanks for sharing your experience! Unless someone else beats me to it, I'm going to add this function to the library as soon as I find some time.