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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe