Lists/dictionaries/Lin-Kernighan

Gareth McCaughan Gareth.McCaughan at pobox.com
Mon Sep 4 02:33:01 CEST 2000

```Duncan Smith wrote:
> 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.

It seems like what you need is a priority queue. There are
lots of good data structures for that purpose, and it wouldn't
be hard to implement them in Python. (I think it's already been
done. Something in the back of my brain is saying "kjbuckets"
at me.)

A word of warning: complicated data structures with good
asymptotic performance don't always pay off. Sometimes
mediocre asymptotics and small constants of proportionality
work better. In your case, that would probably mean using
"sort" and taking advantage of the fact that it runs
nice and quickly and doesn't involve interpreting lots
of nasty slow Python code.

A concrete suggestion, if you really do need good asymptotics:
use a heap. One way to think about (and implement) a heap is as
an array of elements for which it's always true that a[i] <= a[(i-1)/2]
where "/" means integer division, as in Python. Then you can define
the following stuff (WARNING: untested code ahead...)

class Heap:
def __init__(self, elements=[]):
self.array = elements
self.n     = len(elements)
self.repair_all()

def parent(self, i):
return (i-1)/2

def children(self, i):
return 2*i+1, 2*i+2

def move_down(self, i):
"""This is a heap, except that element i may be larger than
its "children" 2*i+1 and 2*i+2. Adjust things to fix this,
by letting the renegade element "settle down" to a good place.
This doesn't do anything to resolve problems that may
occur "above" i -- if, e.g., after the operation i's
"parent" is larger than i. If you take a valid heap and
increase one element, then a "move_down" is all that's
needed to fix the heap.
Time: O(log n)."""
a,n = self.array, self.n
element = a[i]
while 1:
left,right = self.children(i)
smallest = i
if left<n  and a[left]  < element:     smallest = left
if right<n and a[right] < a[smallest]: smallest = right
if smallest == i: break   # Done!
a[i] = a[smallest]
i = smallest
a[i] = element

def repair_all(self):
"""This is a random array of values; none of the defining
relations need hold. Turn it into a heap by "move_down"ing
everything in a suitable order.
Time: O(n log n)."""
for i in range(self.n/2-1, -1, -1):   # n/2-1 .. 0.
self.move_down(i)

def move_up(self, i):
"""This is a heap, except that element i may be smaller than
its "parent" (i-2)/2. Adjust things to fix this, by letting
the renegade element "bubble up" to a good place.
This doesn't do anything to resolve problems that may
occur "below" i -- if, e.g., after the operation i's
"children" are smaller than i. If you take a valid heap
and decrease one element, then a "move_up" is all that's
needed to fix the heap.
Time: O(log n)."""
element = self.array[i]
a = self.array
p = self.parent(i)
while p>=0 and a[p]>element:
a[i] = a[p]
i,p = p,self.parent(p)
a[i] = element

def smallest(self):
"""Return the smallest element.
Time: O(1)."""
return self.array[0]

"""Add a new element to the heap by placing it at the bottom
and letting it "bubble up".
Time: O(log n)."""
self.array.append(element)
self.n = self.n+1
self.move_up(self.n-1)

def remove(self, i):
"""Remove the element with index i from the heap by
replacing it with the last element and repairing.
Time: O(log n)."""
self.n = self.n-1
self.array[i] = self.array[self.n]
self.move_down(i)

If you need to be able to get from elements to indices easily (which
you probably do, so that you can call "move_up" or "move_down" on
all the elements whose costs you've changed), you can either put indices
inside the elements (and update them in "repair" and "add") or just
work with indices everywhere. To do the former, you need to hack
"move_up" and "move_down" so that where they move an element they
index.

Then, when you make your local changes, just re-assign the costs
and call "move_up" or "move_down" on each node whose cost has changed
(depending on which way the cost has changed).

--
Gareth McCaughan  Gareth.McCaughan at pobox.com
sig under construction

```