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/514463...44789.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>

[Josiah Carlson]

Chris Lasher wrote:

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.

See this implementation of a "pair heap":
http://mail.python.org/pipermail/pyt...er/069845.html
....which offers the ability to update the 'priority' of an entry in the
heap. It requires that the 'value' in (priority, value) pairs be unique
(to the heap) and hashable.

- Josiah

[Chris Lasher]

On Jun 15, 5:52 pm, Josiah Carlson <[e-mail]>
wrote:

See this implementation of a "pair heap":
http://mail.python.org/pipermail/pyt...er/069845.html
...which offers the ability to update the 'priority' of an entry in the
heap. It requires that the 'value' in (priority, value) pairs be unique
(to the heap) and hashable.

- Josiah

Hmm. I won't be able to use that heap, as I can guarantee that the
value will be identical for two nodes when they have edges to each
other and no other nodes. Any suggestions on structures that can
accompany identical priority values?

Thanks,
Chris

[Scott David Daniels]

Chris Lasher wrote:

On Jun 15, 5:52 pm, Josiah Carlson <[e-mail]>
wrote:

>See this implementation of a "pair heap":
http://mail.python.org/pipermail/pyt...er/069845.html
...which offers the ability to update the 'priority' of an entry in the
heap. It requires that the 'value' in (priority, value) pairs be unique
(to the heap) and hashable.

- Josiah

Hmm. I won't be able to use that heap, as I can guarantee that the
value will be identical for two nodes when they have edges to each
other and no other nodes. Any suggestions on structures that can
accompany identical priority values?

Thanks,
Chris

Make the priority value for element: (intended_value, id(element))
always a total order that obeys the partial order implied by
intended_value.

--
--Scott David Daniels
sc***********@acm.org