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. :( -- David Roundy
On 7/8/06, David Roundy
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.
I don't know just what you mean by reasoning recursively, but maybe you could use a list, where each element points to all the elements in front of it that it's linked to.
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. :(
If you consider a DAG as just an optimized representation for a tree then you could annotate each node with a Unique and create monadic traversal functions analogous to tree functions but using a finite map Unique -> r to memoise the results of traversal so that a node is only traversed once. Regards, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com
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.h... -- Rob Dockins Talk softly and drive a Sherman tank. Laugh hard, it's a long way to the bank. -- TMBG
On Sat, Jul 08, 2006 at 09:54:58PM -0400, Robert Dockins wrote:
Is there some reason you don't want to use FGL?
I hadn't come across it? I had been looking for DAGs and didn't end up searching for a graph library. It's starting to look like we'll only need trees after all, in which case we can write much simpler code... But thanks for the pointers, everyone! -- David Roundy
participants (4)
-
Brian Hulley -
David Roundy -
ihope -
Robert Dockins