haskell / haskell/cabal

Can topological sorting be sped up?

Open
#8,895 1 comment 0 reactions 0 assignees View on GitHub
type: performance
Dominant language
Haskell
Stars
1.7k
Forks
750
Avg merge
4d 3h
Merged PRs (30d)
28

Description

I noticed that `Distribution.Compat.Graph` has functions

```haskell
topSort :: Graph a -> [a]
topSort g = map (graphVertexToNode g) $ G.topSort (graphForward g)

revTopSort :: Graph a -> [a]
revTopSort g = map (graphVertexToNode g) $ G.topSort (graphAdjoint g)
```

In `Data.Graph` (call it `G`), we have `G.reverseTopSort`, which produces `reverse . G.topSort`. `G.reverseTopSort` is actually more efficient than `G.topSort`. Would it make sense to define `revTopSort` thus?

```haskell
revTopSort g = map (graphVertexToNode g) $ G.reverseTopSort (graphForward g)
```

Would that be close enough to being equivalent? I imagine it would also be possible to define

```haskell
topSort g = map (graphVertexToNode g) $ G.reverseTopSort (graphAdjoint g)
```

but that would only make sense if the adjoint was likely going to be needed for something else.

Contributor guide

Open the contributing guide

Research direction

Start by reading Distribution.Compat.Graph and Data.Graph.reverseTopSort, then compare the ordering produced by the proposed revTopSort and topSort definitions. Confirm whether the alternatives are equivalent for the graph representations used here; done means documenting the result and making the justified implementation change if appropriate.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
build-system, performance
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.