I've worked with many DAGs represented as trees just using Clojure's maps and vectors in a straightforward manner, and like you say, that's often enough to get the job done.
I think where Loom and Ubergraph really start to pay off is when you need to associate attributes to the various nodes and edges. You say a graph representation makes manipulations harder and less direct, but on the contrary, I find graph representations significantly easier to move around the structure and make modifications. Ubergraph is a persistent data structure that allows efficient adding and deletion of nodes and edges and updating of attributes (more efficient than if you stored it as a tree, and needed to rebuild the tree all the way up to the root with every change). Also, in Ubergraph all nodes are aware of their incoming edges, so you are not limited in traversing your DAG in the direction of your one-way edges as you are with a tree. There are a number of different traversals available in the alg namespace. One disadvantage of implementing a DAG as a graph rather than a tree is that with a tree, it is trivial to delete an entire subtree, whereas that would be a more complex operation with a graph representation. Hope that helps to understand the pros and cons of this particular data structure. On Thu, Apr 30, 2015 at 11:01 AM, kovas boguta <kovas.bog...@gmail.com> wrote: > I want an API that is optimized around tree traversal and replacement. > Clojure.walk and zippers can be pretty great, as of course the associative > aspect of maps and vectors. > > Going from a tree of maps and vectors to a graph representation makes > things harder and less direct. > > Theres some challenges about providing such an abstraction, was just > wondering if anyones thought about this. > > > > On Thu, Apr 30, 2015 at 1:37 PM, Mark Engelberg <mark.engelb...@gmail.com> > wrote: > >> Ubergraph can certainly represent DAGs, since DAGs are just a special >> case of directed graphs. There is also the function ubergraph.alg/dag? to >> test whether a graph is a DAG. There are included algorithms, such as >> topological sorting, which only work on a DAG, and other functions, such as >> shortest-path which will work just as well on a DAG. >> >> So what sorts of functionality would you be looking for in a DAG-only >> library? >> >> >> On Thu, Apr 30, 2015 at 6:21 AM, kovas boguta <kovas.bog...@gmail.com> >> wrote: >> >>> Very cool! >>> >>> On a related note: I would be interested in a similar library focused on >>> DAG's. Any thoughts there? >>> >>> >>> >>> >>> >>> >>> On Wed, Apr 29, 2015 at 10:00 PM, Mark Engelberg < >>> mark.engelb...@gmail.com> wrote: >>> >>>> https://github.com/Engelberg/ubergraph >>>> >>>> Ubergraph is a versatile, general-purpose graph data structure for >>>> Clojure. It is designed to complement and extend Loom, a popular Clojure >>>> collection of graph protocols and algorithms. >>>> >>>> Ubergraph implements all of Loom's protocols and draws them together in >>>> one namespace, making it a one-stop, batteries-included graph >>>> implementation. But more importantly, Ubergraph goes beyond Loom's >>>> protocols, allowing a mixture of directed and undirected edges within a >>>> single graph, multiple "parallel" edges between a given pair of nodes (aka >>>> multigraphs), multiple weight attributes per edge, and changeable weights. >>>> >>>> The ubergraph.alg namespace contains an assortment of algorithms >>>> compatible with graphs, digraphs, multigraphs, and multidigraphs (and >>>> backwards-compatible with Loom graphs). A highlight of the ubergraph.alg >>>> namespace is its feature-rich shortest-paths algorithm, which supports a >>>> number of useful search options: edge filters, node filters, goal >>>> predicates, multiple starting nodes, multiple ending nodes, using any >>>> attribute or function as the cost for an edge, and more. >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Clojure" group. >>>> To post to this group, send email to clojure@googlegroups.com >>>> Note that posts from new members are moderated - please be patient with >>>> your first post. >>>> To unsubscribe from this group, send email to >>>> clojure+unsubscr...@googlegroups.com >>>> For more options, visit this group at >>>> http://groups.google.com/group/clojure?hl=en >>>> --- >>>> You received this message because you are subscribed to the Google >>>> Groups "Clojure" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to clojure+unsubscr...@googlegroups.com. >>>> For more options, visit https://groups.google.com/d/optout. >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Clojure" group. >>> To post to this group, send email to clojure@googlegroups.com >>> Note that posts from new members are moderated - please be patient with >>> your first post. >>> To unsubscribe from this group, send email to >>> clojure+unsubscr...@googlegroups.com >>> For more options, visit this group at >>> http://groups.google.com/group/clojure?hl=en >>> --- >>> You received this message because you are subscribed to the Google >>> Groups "Clojure" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to clojure+unsubscr...@googlegroups.com. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- >> You received this message because you are subscribed to the Google >> Groups "Clojure" group. >> To post to this group, send email to clojure@googlegroups.com >> Note that posts from new members are moderated - please be patient with >> your first post. >> To unsubscribe from this group, send email to >> clojure+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en >> --- >> You received this message because you are subscribed to the Google Groups >> "Clojure" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to clojure+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/d/optout. >> > > -- > You received this message because you are subscribed to the Google > Groups "Clojure" group. > To post to this group, send email to clojure@googlegroups.com > Note that posts from new members are moderated - please be patient with > your first post. > To unsubscribe from this group, send email to > clojure+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/clojure?hl=en > --- > You received this message because you are subscribed to the Google Groups > "Clojure" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to clojure+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
