# SM-3b-TheDiameterOfAGraph

## 4308 days ago by nhanbaoho

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(30,1) show(G) m = matrix(G) print m diameter(m)
  30 x 30 dense matrix over Integer Ring (type 'print m.str()' to see all of the entries) Traceback (click to the left of this block for traceback) ... NameError: name 'diameter' is not defined  30 x 30 dense matrix over Integer Ring (type 'print m.str()' to see all of the entries) Traceback (most recent call last): File "", line 1, in File "/tmp/tmpiWsdgI/___code___.py", line 10, in exec compile(u'diameter(m) File "", line 1, in NameError: name 'diameter' is not defined
Or maybe we'd like to check a more orderly graph:
P = graphs.PetersenGraph() show(P) mP = matrix(P) print mP diameter(mP)
  [0 1 0 0 1 1 0 0 0 0] [1 0 1 0 0 0 1 0 0 0] [0 1 0 1 0 0 0 1 0 0] [0 0 1 0 1 0 0 0 1 0] [1 0 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 0 1 1 0] [0 1 0 0 0 0 0 0 1 1] [0 0 1 0 0 1 0 0 0 1] [0 0 0 1 0 1 1 0 0 0] [0 0 0 0 1 0 1 1 0 0] Traceback (click to the left of this block for traceback) ... NameError: name 'diameter' is not defined  [0 1 0 0 1 1 0 0 0 0] [1 0 1 0 0 0 1 0 0 0] [0 1 0 1 0 0 0 1 0 0] [0 0 1 0 1 0 0 0 1 0] [1 0 0 1 0 0 0 0 0 1] [1 0 0 0 0 0 0 1 1 0] [0 1 0 0 0 0 0 0 1 1] [0 0 1 0 0 1 0 0 0 1] [0 0 0 1 0 1 1 0 0 0] [0 0 0 0 1 0 1 1 0 0] Traceback (most recent call last): diameter(mP) File "", line 1, in File "/tmp/tmpliUFgT/___code___.py", line 8, in exec compile(u'diameter(mP) File "", line 1, in NameError: name 'diameter' is not defined