SM-3b-TheDiameterOfAGraph

4144 days ago by MathFest

One of the most basic measures of a graph $G$'s structure is its diameter: what's the maximum distance every attained between one vertex in $G$ and another? A simple-minded algorithm to compute this statistic involves computing higher and higher powers of $G$'s adjacency matrix, keeping track as we go of whether or not we've yet found a path between any given pair of vertices. The first method we require is a quick-and-dirty matrix power algorithm:
def matrix_power(m,p): if p == 1: return m else: return m * matrix_power(m,p-1) 
       
This last method in hand, we introduce the following ones. The first does the bookkeeping that allows us to tell whether we've yet found a path from any given vertex to any other; the second, as long as the first one says "no," computes higher and higher powers of the adjacency matrix, stopping the instant we know we've found a path between any two most mutually distant vertices.
def is_full(m): dim = len(m.rows())-1 for i in [0..dim]: for j in [i..dim]: if m.rows()[i][j] == 0: return False return True def diameter(m): dim = len(m.rows()) - 1 cumulative = m + matrix(dim+1,dim+1,1) d = 1 while not is_full(cumulative): d = d + 1 cumulative = cumulative + matrix_power(m,d) return d 
       
How's it work? Let's try it out on a random tree:
G = graphs.RandomBarabasiAlbert(25,1) show(G) m = matrix(G) print m diameter(m) 
       
Or maybe we'd like to check a more orderly graph:
P = graphs.PetersenGraph() show(P) mP = matrix(P) print mP diameter(mP)