News for hackers. Stuff that matters.
Re:The hunt for the missing data type by ogogmad on Monday March 04, 2024 @02:56PM (#39595186)
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?

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
Re:The hunt for the missing data type by ogogmad on Monday March 04, 2024 @03:20PM (#39595512)
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.

Re:The hunt for the missing data type by yen223 on Monday March 04, 2024 @07:13PM (#39597838)
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.