Comment by ogogmad | Hacker News Reader

Comment by ogogmad | Hacker News Reader

I suspect a lot of graph theory can be reduced to abstract algebra. You consider matrices over lots of different scalar types. The scalar types should be:

- Rigs (rings without negation),

- idempotent (that is, where x + x = x for all x),

- equipped with involution (so that undirected graphs can be made the default by restricting the matrices which represent graphs to only self-adjoint matrices),

- and the entries of the matrix can be restricted to a *-ideal. Note that a *-ideal can be considered a scalar type in its own right.

Different choices of the above scalar types can be used to capture different graph types: Weighted, directed, undirected, bipartite.

There's no clue to physical implementation, other than that sparse graphs can be treated like sparse matrices. Anybody tried this? How did it work out?

The post "A Very General Method of Computing Shortest Paths" (https://r6.ca/blog/20110808T035622Z.html) shows that the Gauss-Jordan algorithm for solving matrix equations, the Floyd-Warshall algorithm for all-pairs shortest paths, and Kleene's algorithm for converting DFAs to regular expressions, are all the same algorithm on matrices of elements from a star-semiring.

According to the article, the physical implementation of graphs is precisely the thing you cannot ignore, because the performance difference between a generic solution and a "correct" solution is huge, basically the difference between the algorithm not completing and the algorithm completing.

That's the reason why it's hard to come up with a single one-size-fits-all graph implementation.

You're a couple decades too late: https://graphblas.org

If you read what I wrote, you'd see I never claimed originality. Anyway, that's cool. I'll need to check how much abstract algebra stuff they use.

Using semirings (uh, rigs) alone isn't impressive. Do they consider semirings with more algebraic structure attached to them?

> Using semirings (uh, rigs) alone isn't impressive. Do they consider semirings with more algebraic structure attached to them?

Wiki says they have R, the two tropical semirings, the 'max-min' semiring, and GF(2). The tropical and max-min have your idempotency requirement, all but the max-min have involution.

Reply on news.ycombinator.com