In this worksheet we'll implement an algorithm which can be used to determine, for a given tree $T$, the number $c(T)$ such that $T^k$ is claw-free if and only if $k \geq c(T)$. (The algorithm developed below appears in a recently completely manuscript on generalized independence polynomials.) The first step is to reproduce a fairly elementary method, one which finds all subsets of a given set of a given size:
def subset_size_n(L,n):
pow = list(powerset(L))
sets = []
for s in pow:
if len(s) == n:
sets.append(s)
return sets
The next method, a more graph theoretical one, finds the leaves of a tree $T$ which is input as an adjacency matrix. This simple procedure runs in time $O(n)$, where $n$ is the order of the tree $T$.
def find_leaves(m):
leaves = []
for i in [0..len(m.rows())-1]:
if sum(m.rows()[i]) == 1:
leaves.append(i)
return leaves
Now for the trickiest step: to compute the distance matrix for $T$, we put together a method which returns a list of the spheres of various radii $1,2,...,{\rm diam}(T)$, centered at a given vertex of $T$. The running time of this procedure if $O(n)$ as well, and we will end up calling it $O(\ell)$ times, when $T$ has $\ell$ leaves.
def find_spheres(m,basept):
dim = len(m.rows())-1
vertex_count = 1
rad = 1
spheres = [[basept]]
while vertex_count < dim:
new_sphere = []
if rad == 1:
for j in [0..dim]:
if m.rows()[basept][j] == 1:
new_sphere.append(j)
vertex_count = vertex_count+1
else:
for i in spheres[rad-1]:
for j in [0..dim]:
if m.rows()[i][j] == 1 and not j in spheres[rad-2] and not j in new_sphere:
new_sphere.append(j)
vertex_count = vertex_count+1
spheres.append(new_sphere)
rad = rad + 1
return spheres
Finally, we call the previous method on each leaf, and from the information contained in the resulting output we reconstruct the distance matrix, restricted to the set of $T$'s leaves:
def find_leaf_distances(m,L):
dim = len(m.rows())-1
d = [[0 for i in [0..dim]] for j in [0..dim]]
leaf_spheres = [find_spheres(m,L[i]) for i in [0..len(L)-1]]
for i in [0..len(L)-1]:
for j in [0..len(leaf_spheres[i])-1]:
for k in leaf_spheres[i][j]:
if k in L:
d[L[i]][k] = j
d[k][L[i]] = j
return d
All right...now all we have to do to find the value $c(T)$ described above is find, for each triple $\{\ell_1,\ell_2,\ell_3\}$ of leaves, the smallest distance $\rho(\ell_i,\ell_j)$, and take the maximum over all leaf triples of this value. This stage of the algorithm runs in time $O(\ell^3)$:
def find_c(d,L):
if len(L) == 2:
return False
else:
trios = subset_size_n(L,3)
return max([min([d[t[0]][t[1]],d[t[0]][t[2]],d[t[1]][t[2]]]) for t in trios])
Let's take it for a test drive!:
G = graphs.RandomBarabasiAlbert(25,1)
show(G)
m = matrix(G)
print m
L = find_leaves(m)
print L
c = find_c(find_leaf_distances(m,L),L)
print c