Home Original page

Lists/dictionaries/Lin-Kernighan

Duncan Smith buzzard at contactbox.co.uk
Sun Sep 3 12:25:46 EDT 2000 
I have a tree structure with unique node labels and a (possibly not unique)
cost associated with each node.  I need to permute the tree as follows.

I need to take a node with minimum cost, make a local change to the tree,
update the costs of some local nodes, and repeat until there exists no node
with a negative associated cost.  If I use a dictionary with node labels as
keys the updating of costs is easy, but I don't know how to efficiently
extract a node label with lowest cost.  If I use a list of [cost, label]
lists I can use the sort method to identify the node with lowest cost, but
updating the costs is less efficient.

I can currently use the labels (0 to n) to index a list of costs, extract an
index of minimum cost and do the subsequent updating by assigning new costs
to the relevant indices.  But that's only possible if I consider the
permutation of a single node (and it's child).  If I want to consider the
permutation of more than one (adjacent) nodes the list indexing method
doesn't seem so straightforward as the label no longer corrsponds directly
to the permutation.  The permutation is then best described by a list of
node permutations.  So maybe I should use a list (as above) with an
associated dictionary of list index keys and permutation list values?

Computer scientists (which I am not) will possibly recognise this as a
Lin-Kernighan type algorithm.  ie. I think I can efficiently implement the
algorithm for k = 1, but for larger values of k it is awkward.  Anyone got
any idea how I can implement this efficiently?  Thanks in advance.

Duncan Smith
More information about the Python-list mailing list