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 3:38:45 PM UTC-4, Stephen Kockentiedt wrote:
>>>
>>> Hello,
>>>
>>> I want to create a graph API similar to what core.matrix is for
>>> matrices. I have created some protocols which every graph implementation
>>> has to satisfy and a prototype implementation. Now I want your feedback on
>>> these protocols. Which functions do you want to see which aren't there?
>>> Which functions should be changed? Are there problems with the general
>>> design? Have you any other feedback?
>>>
>>> Here are the protocol definitions:
>>>
>>> (defprotocol PGraph
>>> "Minimal functionality of a graph."
>>> (directed? [g]
>>> "Returns true if the graph is directed and false if the
>>> graph is undirected. If it is undirected, all functions
>>> taking two nodes must be commutative with regard to
>>> these nodes.")
>>> (nodes [g]
>>> "Returns a set or sequence of all nodes of the graph. May
>>> not contain duplicates.")
>>> (has-edge? [g n1 n2]
>>> "Returns true if the graph g has an edge from node n1
>>> to node n2.")
>>> (direct-successors [g n]
>>> "Returns a set or sequence of all nodes n2 for which
>>> (has-edge? g n n2) returns true. May not contain
>>> duplicates."))
>>>
>>> (defprotocol PPredecessorGraph
>>> "Optional functionality of a graph which can give a
>>> list of all direct predecessors of a node."
>>> (direct-predecessors [g n]
>>> "Returns a set or sequence of all nodes n2 for which
>>> (has-edge? g n2 n) returns true. May not contain
>>> duplicates."))
>>>
>>> (defprotocol PEditableGraph
>>> "Minimal functionality of an editable graph."
>>> (mutable? [g]
>>> "Returns true if the graph is mutated in place.
>>> If true is returned, the other functions change
>>> the graph passed as the first argument and return
>>> the same graph object. If false is returned, the
>>> functions return a new graph and the old graph is
>>> unchaged.")
>>> (add-node [g n]
>>> "Adds the node n to the graph g. If it already
>>> contained n, the graph will not be changed.")
>>> (remove-node [g n]
>>> "Removes the node n from the graph g. If it did
>>> not contain n, the graph will not be changed.")
>>> (add-edge [g n1 n2]
>>> "Adds an edge from node n1 to node n2 to the graph g.
>>> If one or both of the nodes is not present it will
>>> be added to the graph. If the edge was already present,
>>> the graph will not be changed.")
>>> (remove-edge [g n1 n2]
>>> "Removes the edge from node n1 to the node n2 from
>>> the graph g. If it did not contain the edge, the graph
>>> will not be changed."))
>>>
>>> (defprotocol PWeightedGraph
>>> "Functionality of a graph whose edges can be weighted."
>>> (edge-weight [g n1 n2]
>>> "Returns the weight of the edge from node n1 to
>>> node n2."))
>>>
>>> (defprotocol PEditableWeightedGraph
>>> "Functionality of a weighted graph whose weights can be
>>> changed."
>>> (update-edge-weight [g n1 n2 f]
>>> "Updates the weight of the edge from node n1 to node n2,
>>> where f is a function taking the old value and returning
>>> the new one. If the graph did not contain the edge, it
>>> will be created."))
>>>
>>> (defprotocol PNodeDataGraph
>>> "Functionality of a graph which stores data with its
>>> nodes."
>>> (node-data [g n]
>>> "Returns the data of the node n."))
>>>
>>> (defprotocol PEditableNodeDataGraph
>>> "Functionality of a graph which stores editable data
>>> with its nodes."
>>> (update-node-data [g n f]
>>> "Updates the data of the node n, where f is a function
>>> taking the old value and returning the new one. If the
>>> graph did not contain the node, it will be added."))
>>>
>>> (defprotocol PEdgeDataGraph
>>> "Functionality of a graph which stores data with its edges."
>>> (edge-data [g n1 n2]
>>> "Returns the data of the edge from node n1 to node n2."))
>>>
>>> (defprotocol PEditableEdgeDataGraph
>>> "Functionality of a graph which stores editable data
>>> with its edges."
>>> (update-edge-data [g n1 n2 f]
>>> "Changes the data of the edge from node n1 to n2, where
>>> f is a function taking the old value and returning the
>>> new one. If the graph did not contain the edge, it will
>>> be added."))
>>>
>>
--
--
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/groups/opt_out.
