Several implementations of graph algorithms that could be added to ubergraph.alg namespace

[jafingerhut]

A few months ago when using Ubergraph for a project, I was working with graphs that had hundreds of thousands of nodes and edges, and wrote a few graph algorithms using Ubergraph that are perhaps of more wide interest than only for my project.

I also found a few inefficiencies in the pre-traverse algorithm implemented in Loom, and exposed from ubergraph.alg. I have submitted a PR to Loom, but wanted to offer it for possible addition to Ubergraph as well, in case Loom is not updated.

The main new graph algorithm implementation is:

Strongly connected components - Loom has one, too, but this one has been tested with Ubergraph multigraphs, and has been implemented using mutable data structures internally (but taking immutable values as args, and returning immutable values as results) for better performance, achieving almost 5x faster run time on one large sample graph I have used for speed testing against Loom's implementation.

There are some more minor things, like functions for returning a "strongly connected equivalent graph" (I should check the graph algorithms literature to see if there is a standard/widely-used name for this), which, given a digraph G=(V,E), returns a graph that has one node representing each set of nodes in the same strongly connected component of G, and edges (u,v) if there is at least one edge from the strongly connected component represented by u, to the one represented by v. This can be useful as a starting point for algorithms that care about which nodes are reachable from others, and you want to reduce the size of a graph with many cycles, but preserve reachability.

Also functions for returning which sets of nodes are reachable from all nodes, construct an induced subgraph, and probably one or two other minor things.

I am planning on writing some code that calculates a transitive reduction of a graph, too, which I'd be happy to add to Ubergraph.alg if that is of interest.

I guess the first pass of questions is:

• Which of these algorithms sounds of interest for inclusion in ubergraph.alg, if any?

• For any you do find of interest, I have APIs that I have implemented so far that have been useful for me, but it seems best to start by reviewing what they take as input, and return as output, before getting into the internal implementation. The functions are all defined in this file: https://github.com/jafingerhut/cljol/blob/master/src/clj/cljol/ubergraph_extras.clj

[Engelberg]

I'd certainly be interested in incorporating more algorithms into ubergraph that are either novel, or have a better implementation than before in terms of speed or compatibility with multi-edge graphs. Thank you very much for offering your contribution.

Ubergraph's search algorithm can be converted to a traversal with :traversal true, so before adding new traversals, I'd want to know how they compare to Ubergraph's traversal, not just loom's.

I don't have a problem with targeting Java (so for example, if it were me I'd probably just use Java's Deque rather than a custom double-stack implementation), but I know there are people who want clojurescript compatibility, so I'm certainly open to cross-platform contributions.

I won't have time to actually review code for at least one week. It may be helpful if you can direct my attention to what you think are the highest priority items in your file, so I can focus my energies accordingly.

[PavlosMelissinos]

Not OP but for what it's worth, I'd like to be able to compute the critical path of a DAG and that requires a topological sort.

So I'd be rather interested in the topsort2 function.

Thanks for ubergraph by the way :)