snowleopard
Implement transitive reduction
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.
@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?
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!
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.
@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.