Adjacency Matrix and Matrix Operations

I created an adjacency matrix for a mesh, using the Mesh Topology component from Parakeet. The adjacency matrix A become interesting though when you take its powers, for example A^2 , gives the number of walks of length two for each vertex, and the Trace(A^3)/6 gives the number of triangles. Matrix multiplication in GH is pretty limited.; I’ve done it for A^2 here but it actually requires using the standard multiplication component. Once you start getting into higher powers, it will become extremely onerous, and I have no idea how do do Trace.

adjacency (14.3 KB)

Alright, I just figured out Trace, but it still seems like a workaround.

I have no idea what that thing is (nor Trace) but it could be helpful if you explain what are you trying to achieve via “Matrix operations (*)” (BTW: an Adj Matrix of that kind is a square symmetric Matrix Zero except R/C cell values (i.e. 1) derived from a classic Mesh VV connectivity Tree).

(*) for instance: Islands, Dijkstra, Kruskal, Hamiltonian, MST etc etc out of a Mesh (as Graph).

C’mon Peter, you must know what Trace is. Is the problem I said Trace(A) and not Tr(A)?
I know you can get mesh topology from any number of plugins; I just happen to choose Parakeet. The irony is, many of them must have an adjacency matrix internalized to do what they do, so I’m probably recreating something that’s already there. By matrix operations, I mean things like Tr, raising to a power, eigenvalues, and even just extracting a matrix element. I’m reading about Spectral Graph Theory, where the eigenvalues of the adjacency matrix play a prominent role and was trying to use GH. Probably not the best idea, but there you are.

Well … you are after Graphs after all (meaning that you use the Mesh as a Graph). Anyway I have a vast variety of Graph related C# things (most are internal, mind) … so if you can elaborate more upon what exactly you want to do (paths/routing/clustering for instance) maybe I could post something.

Get this classic sum-up from Yale (and a latest from Stanford):

SpectTut.pdf (1.1 MB)
SGT_Stanford_Valiant.pdf (227.7 KB)

BTW: It is most unlikely that you can do anything “realistic” without code … but hope dies last anyway.

Given the opportunity here’s how to get 7 out of the 9 conn trees on Mesh Lists (2 dim paths).

1 Like

Thank you for the publications Peter.