Re: Graph API
If you'd like to take a stab at integrating your proposed protocol into Loom, I'd be happy to merge the changes. Thanks! On Tuesday, June 18, 2013 1:12:04 PM UTC-4, Stephen Kockentiedt wrote: That sounds great! I'll mail you my complete code in case you want to take a look at it or want to use parts of it. And in case I can help in any other way, feel free to ask. Am Dienstag, 18. Juni 2013 18:44:33 UTC+2 schrieb Aysylu Biktimirova: Stephen, thanks for reaching out to me! I really like your ideas and agree with the issues you pointed out in Loom's API. I'd like to incorporate your ideas into Loom to improve its API and have 1 graph library in Clojure. I'm actively working on it and would be happy to combine our efforts. There's one implementation of the API, as far as I know, https://github.com/aysylu/loom/blob/titanium/src/loom/titanium.clj, which integrates Loom with Titanium. I'm planning to refactor it out of Loom and release as a separate project. Since I'm the author and the only maintainer of Titanium+Loom, I'd be happy to handle the transition. On Tuesday, June 18, 2013 3:10:23 AM UTC-4, Stephen Kockentiedt wrote: My bad. I did only find the original repository of loom and thought it was abandoned. I should have taken more care while looking at it. My approach was apparently the same in abstracting multiple graph implementations under one API. However, I see some problems with Loom's API, namely: 1. The specifications of the protocol functions are very sparse. E.g., which nodes shall a directed graph return from neighbors? Successors, predecessors or both? 2. How do I know if the graph implementation works by mutating the given object or returning a new one? 3. Loom assumes that every graph is editable. That is definitely not the case. 4. I think a protocol should be as easy to implement as possible. The additional functionality can be given by functions relying on the protocol functions. E.g., in the user API of my code, there is a function direct-predecessors which provides this functionality (albeit slow) for graph implementations which did not implement the corresponding protocol function: (defn direct-predecessors Returns a set or sequence of all nodes n2 for which (has-edge? g n2 n) returns true. May not contain duplicates. [g n] (if (satisfies? p/PPredecessorGraph g) (p/direct-predecessors g n) (filter #(p/has-edge? g % n) (p/nodes g E.g., implementations of Loom's API need to provide two implementations of neighbors and need to implement add-nodes* instead of only add-node*. This may not be much more work to do. However, the easier the API, the more implementations there will be. Please, don't get me wrong. I think that Loom is a great project, has the same goals and, in terms of functionality, is way ahead of my efforts. Said all that, I definitely don't want there to be two competing graph APIs. That would be counterproductive. I see the following possible solutions: 1. I keep the code to myself and let loom be the sole graph API. 2. We transfer the advantages of my proposal to Loom and change its API. Do you know of any implementations of the API outside Loom itself? If there are none, this should be possible without much trouble. Also, the README states that the API is alpha-stage. 3. I publish my code and each API can be implemented in terms of the other one. I'm not sure that this is possible in a simple way. Maybe each protocol could be extended to java.lang.Object, which calls the protocols of the other API, but I don't know if that is feasible. Please tell me what you think. I will also send Aysylu an email so that she can chime in on the conversation. Am Dienstag, 18. Juni 2013 07:02:52 UTC+2 schrieb Rob Lachlan: Loom was indeed working on this, and it's a very nice library. One thing that I particularly liked about Justin's design, was the ability to run a graph algorithm without worrying about conforming to a particular graph representation. See for example the bread first search function, here: https://github.com/jkk/loom/blob/master/src/loom/alg_generic.clj#L110 All the bfs function requires is a neighbors function and and a start vertex. Simple and easy to use. Justin had said that he won't be actively developing loom for the forseeable future; I was hoping to develop it further, but I only got as far as implementing a max flow algorithm before the rest of my life got in the way of my plans. I know that Aysylu was doing a fair amount of work on loom, so I'd guess that her repo is the most advanced one. Stephen: I think the set of protocols above is good, better than Loom's in fact; notably, the decision to make direct-predecessors optional is the correct one, and a lot of graph libraries get that wrong. If you want to compare how loom did it: https://github.com/jkk/loom/blob/master/src/loom
Re: Graph API
Stephen, thanks for reaching out to me! I really like your ideas and agree with the issues you pointed out in Loom's API. I'd like to incorporate your ideas into Loom to improve its API and have 1 graph library in Clojure. I'm actively working on it and would be happy to combine our efforts. There's one implementation of the API, as far as I know, https://github.com/aysylu/loom/blob/titanium/src/loom/titanium.clj, which integrates Loom with Titanium. I'm planning to refactor it out of Loom and release as a separate project. Since I'm the author and the only maintainer of Titanium+Loom, I'd be happy to handle the transition. On Tuesday, June 18, 2013 3:10:23 AM UTC-4, Stephen Kockentiedt wrote: My bad. I did only find the original repository of loom and thought it was abandoned. I should have taken more care while looking at it. My approach was apparently the same in abstracting multiple graph implementations under one API. However, I see some problems with Loom's API, namely: 1. The specifications of the protocol functions are very sparse. E.g., which nodes shall a directed graph return from neighbors? Successors, predecessors or both? 2. How do I know if the graph implementation works by mutating the given object or returning a new one? 3. Loom assumes that every graph is editable. That is definitely not the case. 4. I think a protocol should be as easy to implement as possible. The additional functionality can be given by functions relying on the protocol functions. E.g., in the user API of my code, there is a function direct-predecessors which provides this functionality (albeit slow) for graph implementations which did not implement the corresponding protocol function: (defn direct-predecessors Returns a set or sequence of all nodes n2 for which (has-edge? g n2 n) returns true. May not contain duplicates. [g n] (if (satisfies? p/PPredecessorGraph g) (p/direct-predecessors g n) (filter #(p/has-edge? g % n) (p/nodes g E.g., implementations of Loom's API need to provide two implementations of neighbors and need to implement add-nodes* instead of only add-node*. This may not be much more work to do. However, the easier the API, the more implementations there will be. Please, don't get me wrong. I think that Loom is a great project, has the same goals and, in terms of functionality, is way ahead of my efforts. Said all that, I definitely don't want there to be two competing graph APIs. That would be counterproductive. I see the following possible solutions: 1. I keep the code to myself and let loom be the sole graph API. 2. We transfer the advantages of my proposal to Loom and change its API. Do you know of any implementations of the API outside Loom itself? If there are none, this should be possible without much trouble. Also, the README states that the API is alpha-stage. 3. I publish my code and each API can be implemented in terms of the other one. I'm not sure that this is possible in a simple way. Maybe each protocol could be extended to java.lang.Object, which calls the protocols of the other API, but I don't know if that is feasible. Please tell me what you think. I will also send Aysylu an email so that she can chime in on the conversation. Am Dienstag, 18. Juni 2013 07:02:52 UTC+2 schrieb Rob Lachlan: Loom was indeed working on this, and it's a very nice library. One thing that I particularly liked about Justin's design, was the ability to run a graph algorithm without worrying about conforming to a particular graph representation. See for example the bread first search function, here: https://github.com/jkk/loom/blob/master/src/loom/alg_generic.clj#L110 All the bfs function requires is a neighbors function and and a start vertex. Simple and easy to use. Justin had said that he won't be actively developing loom for the forseeable future; I was hoping to develop it further, but I only got as far as implementing a max flow algorithm before the rest of my life got in the way of my plans. I know that Aysylu was doing a fair amount of work on loom, so I'd guess that her repo is the most advanced one. Stephen: I think the set of protocols above is good, better than Loom's in fact; notably, the decision to make direct-predecessors optional is the correct one, and a lot of graph libraries get that wrong. If you want to compare how loom did it: https://github.com/jkk/loom/blob/master/src/loom/graph.clj On Monday, June 17, 2013 1:14:34 PM UTC-7, dgrnbrg wrote: I think that there's already a project working on this called Loom. The furthest-developed fork is here: https://github.com/aysylu/loom which appears to have protocols for graphs, bindings to Titanium (the Clojurewerkz graph DB library), visualization support, and implementations of several algorithms. Maybe there's a way to incorporate these projects? On Monday, June 17, 2013
