Re:The hunt for the missing data type
by bigbillheck on Monday March 04, 2024 @03:18PM
(#39595473)
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?
Re:The hunt for the missing data type
by bigbillheck on Monday March 04, 2024 @05:58PM
(#39597299)
> 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.
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.
Re:The hunt for the missing data type
by aweinstock on Monday March 04, 2024 @09:25PM
(#39598746)
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.
- 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?