Priority Queue with Mutable Elements

[Chris Lasher]

Hello,

I am working with large graphs (~150,000 to 500,000 nodes) which I
need decompose node-by-node, in order of a node's value. A node's
value is determined by the sum of its edge weights. When a node is
removed from the graph, its neighbors' values must be updated to take
into account the removed edges.

I was told to look for a priority queue in Python. I had a look at the
heapq module. It looks like it supports ordering on insertion, but I'm
unsure how to update the queue once a node's value changes.
Additionally, I need the queue to be sorted on a particular attribute
of the node objects, and don't see a way to do that other than
override the __cmp__ method. Should I just use a list and use .sort()
or sorted()? That seems like it could be horribly inefficient.

I found Andrew Snare's PQueue extension module [1] , which supports
updating values in the priority queue by reassignment. It appeared to
be broken in Python2.5 [2] but I found the offending line (a call to
PyMem_DEL) and changed it (to PyObject_FREE) and it appears to be
working fine. I would prefer to limit external depedencies for my
modules, however.

Many thanks for your insight and advice,
Chris

[1] http://py.vaults.ca/apyllo.py/514463245.769244789.44776582
[2] http://tinyurl.com/363dg9 or <http://groups.google.com/group/
comp.lang.python/browse_thread/thread/
ca6a43a413c43780/30745e0bc7b584f7?lnk=gst&q=priority
+queue&rnum=4#30745e0bc7b584f7>