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
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|
|