Algorithms to implement #3
Description
Requested:
- Issue Return all negative cycles starting from specific node #78, Return all negative cycles starting from specific node
- not actually requested here but at gonum, k-shortest paths. There's an algorithm by Yen. Also a k-independent shortest paths algorithm at goraph.
Simple:
- For undirected, upper and lower would make sense. A number of algorithms process just the upper or lower triangles to process each edge once. But methods to actually extract these arcs as a directed graph might be nice.
- Similar to Equal, you could do a whole raft of set operators.
Most interesting:
- Optimal Listing of Cycles and st-Paths in Undirected Graphs, R. Ferreira +others
- Biconnected components block-cut result. (Prerequisite for Ferreira algorithm. Actually no, the paper talks about it but the efficient algorithm does something different.) Anyway, there's some code commented out in undir.go (and tests commented out in undir_test.go.) Review, complete, test, fix.
- Algorithms of "Fast Generation of Spatially Embedded Random Networks" by Eric Parsonage and Matthew Roughan, as replacements for the ad-hoc Euclidean and the n^2 Geometric.
Labeled:
- more weighted graph algorithms?
- applications specific to certain domains, like representing computer code?
- "property graph", quad, triple, or graph database algorithms.
- RDF
Others (no particular order):
- Centrality - I think some algorithms could use the biconnected block-cut tree. Algorithms from cluster package might also be useful. Eccentricity, radius, diameter, center
- Isomorphism / cannonization
- Max flow / min cut / partitioning
- Matching
- Viterbi / Baum-Welch (but these are usually done on matrices, and BW is a kind of EM, so these may or may not go in this package.)
- Planar
- More random graph generators
- All pairs shortest paths. Floyd Warshall can do this. Code I've found yields a matrix that encodes the paths -- a shortest path index? could be used to construct a shortest path tree?
- http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part3.pdf, and http://masc.cs.gmu.edu/wiki/FloydWarshall/ for example lists interesting variants of Floyd-Warshall -- connectivity and path recovery.
Alternates:
- Batagelj and Zaveršnik degeneracy is in networkx
- Sarıyüce and Pinar degeneracy looks even better
Consider algorithms offered in other libraries, from other languages as well. igraph for example has lots of interesting looking stuff. networkx pops up a lot. It wouldn't be so bad to keep up with gonum, so this library is not discounted for lack of an algorithm that gonum has. Okay, so lets list some of these:
- igraph, C/R/Python, http://igraph.org/
- Boost Graph Library, C++, http://www.boost.org/doc/libs/release/libs/graph/
- SNAP, C++, http://snap.stanford.edu/
- gonum/graph, Go, https://github.com/gonum/gonum/tree/master/graph
- graph_tool, Python over C++ and Boost, https://graph-tool.skewed.de/
- networkx, Python, https://networkx.github.io/
- scipy, Python, https://docs.scipy.org/doc/scipy/reference/sparse.csgraph.html
- lightgraphs, Julia, http://juliagraphs.github.io/LightGraphs.jl/latest/