SM-3b-TheDiameterOfAGraph

4143 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 <module>
    
  File "/tmp/tmpiWsdgI/___code___.py", line 10, in <module>
    exec compile(u'diameter(m)
  File "", line 1, in <module>
    
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 <module>
    
  File "/tmp/tmpliUFgT/___code___.py", line 8, in <module>
    exec compile(u'diameter(mP)
  File "", line 1, in <module>
    
NameError: name 'diameter' is not defined