Speed up indegree
authorDavid Feuer <David.Feuer@gmail.com>
Thu, 8 Mar 2018 00:47:45 +0000 (19:47 -0500)
committerDavid Feuer <David.Feuer@gmail.com>
Thu, 8 Mar 2018 05:25:23 +0000 (00:25 -0500)
Instead of taking the transpose of a graph and then calculating
the outdegree, calculate the indegree directly. This probably
won't actually improve performance much (if at all) until
`base-4.12` or so comes out: see
[GHC Trac #14785](https://ghc.haskell.org/trac/ghc/ticket/14785).
If we want, we can reimplement `accumArray` ourselves to work around
this problem.

Fixes #533

Data/Graph.hs

index ad97132..7f193d0 100644 (file)
@@ -348,7 +348,7 @@ outdegree  = mapT numEdges
 --
 -- > indegree (buildG (0,2) [(0,1), (1,2)]) == array (0,2) [(0,0),(1,1),(2,1)]
 indegree :: Graph -> Array Vertex Int
-indegree  = outdegree . transposeG
+indegree g = accumArray (+) 0 (bounds g) [(v, 1) | (_, outs) <- assocs g, v <- outs]
 
 -- | Identical to 'graphFromEdges', except that the return value
 -- does not include the function which maps keys to vertices.  This