Lists/dictionaries/Lin-Kernighan

[Gareth McCaughan]

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]

  def add(self, element):
    """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
also adjust its stored
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