4 ms·

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: - Ri

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?

bigbillheck 3y ago
You're a couple decades too late: https://graphblas.org https://graphblas.org
- ogogmad 3y ago
  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?
  - bigbillheck 3y ago
    > 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.
yen223 3y ago
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.
aweinstock 3y ago
The post "A Very General Method of Computing Shortest Paths" (https://r6.ca/blog/20110808T035622Z.html 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.

bigbillheck 3y ago

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

ogogmad 3y ago
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?
- bigbillheck 3y ago
  > 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.

yen223 3y ago

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.

aweinstock 3y ago

The post "A Very General Method of Computing Shortest Paths" (https://r6.ca/blog/20110808T035622Z.html 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.