12

How do you define a directed acyclic graph (DAG) (of strings) (with one root) best in Haskell?

I especially need to apply the following two functions on this data structure as fast as possible:

  1. Find all (direct and indirect) ancestors of one element (including the parents of the parents etc.).
  2. Find all (direct) children of one element.

I thought of [(String,[String])] where each pair is one element of the graph consisting of its name (String) and a list of strings ([String]) containing the names of (direct) parents of this element. The problem with this implementation is that it's hard to do the second task.

You could also use [(String,[String])] again while the list of strings ([String]) contain the names of the (direct) children. But here again, it's hard to do the first task.

What can I do? What alternatives are there? Which is the most efficient way?

EDIT: One more remark: I'd also like it to be defined easily. I have to define the instance of this data type myself "by hand", so i'd like to avoid unnecessary repetitions.

6
  • 2
    data Family = Ego { parents, children :: [String] }; type DAG = Map String Family? If you store parents as well as children, both find operations should be reasonably fast. May 6, 2013 at 21:04
  • 1
    Or have two maps. One from parents to children, second from children to parents. Choose the way fits you best.
    – Adrian
    May 6, 2013 at 21:08
  • I added an additional remark in the original question which makes your suggetion difficult. May 6, 2013 at 21:12
  • @MekeorMelire Define your own map-like datatype. You can start with type Map k v = [(k, v)].
    – user824425
    May 6, 2013 at 21:14
  • 1
    Cheap, fast, correct, pick two. Err, you can have two of 1. easy/fast finding of parents, 2. easy/fast finding of children, 3. simple representation. Consider the tradeoffs and take your pick. May 6, 2013 at 21:27

1 Answer 1

2

Have you looked at the tree implemention in Martin Erwig's Functional Graph Library? Each node is represented as a context containing both its children and its parents. See the graph type class for how to access this. It might not be as easy as you requested, but it is already there, well-tested and easy-to-use. I have used it for more than a decade in a large project.

1
  • Any idea about its speed over Haskell maps? I want to use this library but my graphs are pretty big.
    – Dilawar
    Jun 7, 2013 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.