[Haskell-cafe] help with creating a DAG?
robdockins at fastmail.fm
Sat Jul 8 21:54:58 EDT 2006
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?
Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
More information about the Haskell-Cafe