# Lists/dictionaries/Lin-Kernighan

Duncan Smith buzzard at contactbox.co.uk
Sun Sep 3 23:36:37 CEST 2000

```k is a parameter denoting the number of possible permutations.  So if k=1
I'm only considering the n-1 possible permutations of a tree.  In that case
I can use a single list of costs with the indices corresponding to the node
labels.  With k=2 I must consider the costs of the (n-1)^2 possible pairs of
permutations.  In most cases this is the sum of the costs of the individual
permutations.  But if the permuted nodes are adjacent they must be evaluated
as a pair.  The general idea is to choose a value of k such that I can find
a good (low cost) solution in a reasonable time.  My code for k=1 is below.
However, I'd like to come up with a solution that is easier to generalise to
k=2,3,4...  If there's nothing reasonably obvious that I should be doing I
probably just need to keep working at it.  Thanks.

def Lin_Kern(self):
cost_list = []
for x in range(0, len(self.ordering)):
if self.cliques[x].pointer == 'None' or
self.cliques[self.cliques[x].pointer].pointer == 'None':
cost_list.append('None')                #should not be
permuted
else:
cost_list.append(DJT.perm_cost(self, x))    #index is node
id
while min(cost_list) < 0:
to_perm = cost_list.index(min(cost_list))
update_list = Set([to_perm, self.cliques[to_perm].pointer])
update_list = (update_list + self.cliques[to_perm].pointed +
self.cliques[self.cliques[to_perm].pointer].pointed).asList()
DJT.perm(self, to_perm)
for x in update_list:
cost_list[x] = DJT.perm_cost(self, x)

```