haskell / haskell/alex

Is module DFS really needed?

Open
#232 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
323
Forks
87
PR merge metrics
No merged PRs in 30d

Description

The module `DFS` implements graph algorithms. From that module, only the functions `out` and `t_close` are used externally (in NFA.hs). The functions `list_tree`, `mk_graph`, `edges`, `rev_edges`, `reverse_graph`, `scc`, `top_sort` and `dff`, and the type `Edge`, are not used.

However, there's something else that strikes me from that module, and points to a potential cleaning opportunity:

- The top comment reads _"This module is a portable version of [...] [an] encoding of [...] linear graph algorithms. This module uses balanced binary trees instead of mutable arrays to implement the depth-first search so the complexity of the algorithms is n.log(n) instead of linear."_ However, isn't linear better than n times log(n)??? Why go for the latter if you can opt for the former?

- There is an implementation of graphs in `Data.Graph` in containers (and containers is already a dependency of alex), although I haven't checked if that was there already in the earliest version of GHC supported by alex, which I think is GHC 7 (?). The two functions used externally, `out` and `t_close`, could be defined, if I understand their purpose correctly, as:

```haskell
out :: Graph -> Int -> [Int]
out = Data.Array.(!)

t_close :: Graph -> Graph
t_close g = buildG (bounds g) [ (v1, v2) | v1 <- vertices g, v2 <- reachable g v1 ]
```

List comprehensions are generally slower than map so there's probably a faster way of building `t_close` if performance is an issue here.

My questions are:
1. Should this module be replaced by a use of `Data.Graph`?
2. If not, should the unused functions mentioned above be removed?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.