471,342 Members | 1,974 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,342 software developers and data experts.

Priority Queue with Mutable Elements

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>

Jun 15 '07 #1
3 4158
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
Jun 15 '07 #2
On Jun 15, 5:52 pm, Josiah Carlson <josiah.carl...@sbcglobal.net>
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

Jun 16 '07 #3
Chris Lasher wrote:
On Jun 15, 5:52 pm, Josiah Carlson <josiah.carl...@sbcglobal.net>
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
Jun 16 '07 #4

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

38 posts views Thread by Aaron W. LaFramboise | last post: by
6 posts views Thread by Der Andere | last post: by
1 post views Thread by Der Andere | last post: by
1 post views Thread by Jim Strathmeyer | last post: by
5 posts views Thread by Dan H. | last post: by
6 posts views Thread by imutate | last post: by
4 posts views Thread by jjh5030 | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.