Loom abstractions

[drone29a]

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:

• multiple definitions for functions
• lack of edge types
• test are specific to current implementations

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). The add-edges* and edge definition is a little interesting since it really depends on whether a graph also implements WeightedGraph.

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 an UndirectedEdge 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.

[danielcompton]

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.

[drone29a]

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.

[aysylu]

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.