Is module DFS really needed?
- 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
Assessment
This issue has not been assessed yet.