[Haskell-cafe] help with creating a DAG?

[Robert Dockins]

On Saturday 08 July 2006 12:25 pm, David Roundy wrote:
> Hi all,
>
> I'm wanting to create a data structure to hold a directed acyclic
> graph (which will have patches represented by edges), and haven't yet
> been able to figure out a nice representation.  I'd like one that can
> be reasoned with recursively, or as closely to recursively as
> possible.  The problem is one of dependency relations between darcs
> patches, and "normally" reduces to a simple tree, with conflict
> resolution patches bringing branches of the tree back together.  Trees
> I know how to handle intuitively and elegantly, but DAGs are a whole
> different question.
>
> I looked for papers, and there was one on "an initial-algebra approach
> to DAGs" that looked promising, but I'm afraid I wasn't able to fully
> understand it, and it is able to describe more complicated DAGs than
> I'd like to support.
>
> Anyhow, any suggestions from persons with experience with this sort of
> thing would be great.  These are getting to be data structures that
> are more complicated than anything I'm comfortable with.  :(


Is there some reason you don't want to use FGL?

http://web.engr.oregonstate.edu/~erwig/fgl/haskell/
http://haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive.html



-- 
Rob Dockins

Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
       -- TMBG