-
Notifications
You must be signed in to change notification settings - Fork 108
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Loom abstractions #66
Comments
Just to add something slightly related, when ordering of seqs changes in a new Clojure version, it can break some of the Loom tests, because they expect things like edges to be in a certain order, e.g. [n1 n2] in 1.6 may be [n2 n1] in 1.7. |
Here's the (incomplete) implementation I'm working on: https://github.com/mattrepl/loom-impl The benefit over the existing undirected implementation is it's always weighted (a default weight of 1 can be used) so that algorithms expecting a weight value will still work. It uses an UndirectedEdge type to avoid double edges. It avoids a nested maps of weights which is a bit nasty to update efficiently and is too slow if transients or mutation isn't used. |
Hey @mattrepl, sorry for the delay in responding to this and another issue and PR. I'm working through all outstanding items and will respond shortly. |
Hi @aysylu, I was taking a stab at writing an alternative implementation of a weighted, undirected graph and have brushed up to a few points where we might consider tightening the API. I'm not sure how to fix them but figured I'd share in case you have suggestions.
A few things I've encountered:
These are sometimes inefficient (
loom.graph/graph
) or inconsistent based on the particular implementation (EditableGraph/add-edges*
defining edges to be [n1 n2] if unweighted or [n1 n2 w] if weighted). Theadd-edges*
and edge definition is a little interesting since it really depends on whether a graph also implementsWeightedGraph
.The lack of edge types is not necessarily an appropriate solution for the
add-edges*
inconsistency, but the default implementations of the undirected graphs could be improved with anUndirectedEdge
type with tests for equality based on both incident nodes rather than leaking implementation details and resulting in an undirected graph really being a directed graph with double the edges–an edge for each direction. I've taken such an approach with the basic implementation I wrote.It'd be handy if Loom offered a test suite for general classes of graphs rather than use hardcoded references to the default implementations. I'm thinking of something similar to the test suite provided by core.matrix. There would be a set a tests for directed graphs, undirected graphs, weighted graphs, etc.
I have time to help with these minor issues, but want to coordinate with you and others using and developing Loom first.
The text was updated successfully, but these errors were encountered: