4 ms·

I'd hope so; it would be pretty damn embarrassing if you couldn't do a slightly advanced fuzz buzz.

bee_rider 4y ago
A tree is just a type of graph. A graph can be represented as an adjacency matrix. So come up with that matrix, then drop it into lapack for inversion. Lapack is well optimized so this is probably a very good solution.
- dekhn 4y ago
  I haven't thought about this before, but I can't see how this would work. Instead, you'd convert to an adjacency matrix (with edge directions by only populating the upper rectangular region), then transpose the matrix, then convert back to a graph. The transpose should swap the i, j pair edge directions. Matrix inversion is super-expensive and I think it would produce somethign else entirely, probably not unlike matrix decomposition, which can extract centrality properties of the nodes. But it's super expensive.
  - bee_rider 4y ago
    Yep! It was not a serious suggestion, just a joke based on taking a circuitous route through the language.
    - dekhn 4y ago
      whew! I thought I was missing something obvious (I'm a graph/matrix nerd, can't you tell?)
      - bee_rider 4y ago
        It was a pretty nonsensical joke anyway. Something obvious that I missed which sort of spoils the joke is that if you take a binary tree, look at it as a directed graph, and then take the adjacency matrix of the graph, it is obviously not invertible. Do'h!
        dekhn 4y ago
        I don't think that's true- at least, I see literature saying that inversting the adjacency matrix of a graph is useful. Is there something about the property of the graph that makes it non-invertible?
        bee_rider 4y ago
        For sure they are useful in general. In the case of a binary tree, though -- I guess it depends on how you think of the graph. If it is directed -- a parent only points down to it's children (so, no backwards links up the tree), the adjacency matrix is clearly rank deficient. The row (or column depending on how you want the adjacency matrix to be set up) for edges going in to node 1 is empty. If we think of the graph as undirected, it is still not invertible, but I don't know that there's anything immediately intuitive about it. With 7 nodes we'd have (numbered as in a breadth first traversal): . 1 2 3 4 5 6 7 1 0 1 1 0 0 0 0 2 1 0 0 1 1 0 0 3 1 0 0 0 0 1 1 4 0 1 0 0 0 0 0 5 0 1 0 0 0 0 0 6 0 0 1 0 0 0 0 7 0 0 1 0 0 0 0 Rows 4 and 5, as well as 6 and 7 are clearly degenerate (all the leaf nodes).
- Tarq0n 4y ago
  Isn't that the idea behind graphBLAS? http://graphblas.engr.ucsb.edu/ http://graphblas.engr.ucsb.edu/
  - bee_rider 4y ago
    The area between graphs and matrices is a productive one for mining ideas out of, because they are closely related but our mental models of them are pretty different. That group thinks there are enough good ideas in the space that it is time to work on a nice, solid building-block library. They've got some pretty well known researchers on board so I bet they are right. My suggestion was just a joke, though, I don't think the inverse of the matrix that comes from a binary tree has any particular meaning.

A tree is just a type of graph. A graph can be represented as an adjacency matrix. So come up with that matrix, then drop it into lapack for inversion. Lapack is well optimized so this is probably a very good solution.

dekhn 4y ago
I haven't thought about this before, but I can't see how this would work. Instead, you'd convert to an adjacency matrix (with edge directions by only populating the upper rectangular region), then transpose the matrix, then convert back to a graph. The transpose should swap the i, j pair edge directions. Matrix inversion is super-expensive and I think it would produce somethign else entirely, probably not unlike matrix decomposition, which can extract centrality properties of the nodes. But it's super expensive.
- bee_rider 4y ago
  Yep! It was not a serious suggestion, just a joke based on taking a circuitous route through the language.
  - dekhn 4y ago
    whew! I thought I was missing something obvious (I'm a graph/matrix nerd, can't you tell?)
    - bee_rider 4y ago
      It was a pretty nonsensical joke anyway. Something obvious that I missed which sort of spoils the joke is that if you take a binary tree, look at it as a directed graph, and then take the adjacency matrix of the graph, it is obviously not invertible. Do'h!
      - dekhn 4y ago
        I don't think that's true- at least, I see literature saying that inversting the adjacency matrix of a graph is useful. Is there something about the property of the graph that makes it non-invertible?
        bee_rider 4y ago
        For sure they are useful in general. In the case of a binary tree, though -- I guess it depends on how you think of the graph. If it is directed -- a parent only points down to it's children (so, no backwards links up the tree), the adjacency matrix is clearly rank deficient. The row (or column depending on how you want the adjacency matrix to be set up) for edges going in to node 1 is empty. If we think of the graph as undirected, it is still not invertible, but I don't know that there's anything immediately intuitive about it. With 7 nodes we'd have (numbered as in a breadth first traversal): . 1 2 3 4 5 6 7 1 0 1 1 0 0 0 0 2 1 0 0 1 1 0 0 3 1 0 0 0 0 1 1 4 0 1 0 0 0 0 0 5 0 1 0 0 0 0 0 6 0 0 1 0 0 0 0 7 0 0 1 0 0 0 0 Rows 4 and 5, as well as 6 and 7 are clearly degenerate (all the leaf nodes).
Tarq0n 4y ago
Isn't that the idea behind graphBLAS? http://graphblas.engr.ucsb.edu/ http://graphblas.engr.ucsb.edu/
- bee_rider 4y ago
  The area between graphs and matrices is a productive one for mining ideas out of, because they are closely related but our mental models of them are pretty different. That group thinks there are enough good ideas in the space that it is time to work on a nice, solid building-block library. They've got some pretty well known researchers on board so I bet they are right. My suggestion was just a joke, though, I don't think the inverse of the matrix that comes from a binary tree has any particular meaning.