Skip to content

Is module DFS really needed? #232

@ivanperez-keera

Description

@ivanperez-keera

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:

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?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions