dear Keith, some years ago, someone (Jaap Spies?) thought me this trick: on any adjacency matrix A, form B = I +x*A +x^2A^2 + ... (or generating function where coefficient of x^k in Bij gives the count of paths from i to j in n steps); now rewrite as a standard geometric series (but in matrix form) as B = ( I - x*A )^-1 this gives matrix B with Bij = (rational) function of x. It was an eye-opener for me that one could do generatingfunction-stuff on matrices. But maybe you already knew that, Wouter -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Keith F. Lynch Sent: woensdag 20 februari 2013 5:08 To: math-fun@mailman.xmission.com Subject: [math-fun] Adjacency matrices (was Re: Fun with maps) I've been composing a "Fun with maps" followup, but it has grown to unwieldy length. So I'm budding off one part of it, my musings on adjacency matrices, into this email. An adjacency matrix for a graph has a[i][j] = 1 iff vertices i and j are adjacent, i.e. are separated by a single edge. The Nth power of an adjacency matrix gives the number of length-N walks (paths with possible duplication of vertices and edges) between each pair of vertices. To determine whether a set of vertices splits the graph into two (or more) separate pieces when removed, I zero the rows and columns for the vertices in the set, raise the resulting adjacency matrix to successive powers, and take the sum of all the powers. If any entries other than in the rows and columns representing the set of vertices I removed remain zero, then I know the graph has become disconnected. How do I know when to stop taking successive powers? When the number of zeros stops going down. That means I have to count them each time. I've been using this to see whether any states are completely surrounded by another state, whether any states are nestled between two states, and whether any states are hiding in the corner where three states would otherwise meet. I've been doing matrix multiplication in the obvious way. There are faster ways to multiply matrices, but they're only slightly faster, except for matrices far larger than 50 on a side. For a matrix that small, those methods may even be slower. Then I realized that there were ways I could speed things up greatly. I don't actually care how many walks there are between two vertices. All I care is whether there's at least one path, of any length. In fact, those big numbers vex me, since the number of walks can easily exceed the size of a 32-bit integer and wrap around. So I replaced: a[i][k] += b[i][j] * c[j][k]; with a[i][k] |= b[i][j] & c[j][k]; which is much faster. For those who can't read C notation, wherever I was multiplying, I'm ANDing, and wherever I was adding, I'm ORing. Also, instead of adding together the successive powers, I'm ORing them together. Is there a name for this matrix operation? It can't be original with me. Can it? Also, instead of "multiplying" matrices to get higher and higher powers, I can repeatedly "square" them. That way I don't have to count the zeros. If I "square" it six times, that's the 64th power, and since there are fewer than 64 vertices, that has to have found all possible paths. But will the sum of the 1st, 2nd, 4th, 8th, 16th, 32nd, and 64th powers necessarily find all paths? It's only finding all walks of length 1, 2, 4, 8, etc. Depending on the graph, there could be some vertices that can only be reached by a walk with certain lengths. And not just with contrived graphs. I'm pretty sure the DC Metro system is an example. Since it's a bichromatic graph (I wonder if I'm the only person ever to notice that), any round trip will contain an even number of edges. About half the stations can only be reached with a "walk" of odd length. Then I realized that there was a simple solution. Make the main diagonal of the matrix all ones, i.e. create an edge from each vertex to itself. That will ensure that anything that can be reached with a walk of length N can be reached with a walk of length N+1. And I can completely skip the summation steps, and simply use the 64th "power" of the adjacency matrix. ("Power" is in quotes because, as I said, I'm no longer multiplying, I'm ANDing and ORing.) I've coded and tested all of the above, but not what's in the remainder of this message. Also, since those are bitwise operations, I can pack each row of the matrix into a single 64-bit integer, and do a whole row's worth of operations in a single operation. Yes, I supposedly have to read down columns, too, but keep in mind that these matrices are all symmetrical, so whenever I'm supposed to look at the Jth column, I can cheat and use the Jth row instead. Those matrix tricks should give me enough speedup that searching a 50-vertex map for K_5 and K_3,3 would be feasible (assuming I wanted to do that, which I probably don't). Maybe it would run over a weekend instead of running for a year. (Keep in mind that searching for K_5 doesn't mean searching for five vertices each of which are adjacent to the other four, a search which would be very quick. It means searching for five vertices each of which has a path to the other four that doesn't go through any of the other three. (That last sentence should be taken out and shot.) Analogously with K_3,3.) _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun =============================== This email is confidential and intended solely for the use of the individual to whom it is addressed. If you are not the intended recipient, be advised that you have received this email in error and that any use, dissemination, forwarding, printing, or copying of this email is strictly prohibited. You are explicitly requested to notify the sender of this email that the intended recipient was not reached.