473,246 Members | 1,291 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,246 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 4323
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

38
by: Aaron W. LaFramboise | last post by:
Hello, I understand that an easy way to make the standard std::priority_queue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the...
6
by: Der Andere | last post by:
Are priority queues implemented in the STL in Visual Studio 6? If no, which is the easiest way to simulate them? Multisets? BTW: The container contains pointers to instances of a class. The...
1
by: Der Andere | last post by:
I posted this reaction in a thread quite far below so I fear people won't read it. I got stuck now for quite a while and just don't know what to try else. Thanks, Matthias > > Are priority...
1
by: Jim Strathmeyer | last post by:
So, I've been looking for a wrapper class for STL priority queues, and haven't been able to find one. (Websearching for info about the STL sure shows how much it's changed over the past few years.)...
5
by: Dan H. | last post by:
Hello, I have implemented a C# priority queue using an ArrayList. The objects being inserted into the priority queue are being sorted by 2 fields, Time (ulong) and Priority (0-100). When I...
6
by: imutate | last post by:
How do you use std::priority_queue to store say an index type (call it intidx) and sort using another integer type (but smallest weight at the top) ? How do you pop off the top index ? I mean...
3
by: PicO | last post by:
i need some explanation about the difference between priority queue & set & heap ... as they all sort the data in ( n log n ) ... but the only i see that priority queue only can pop the top (...
4
by: jjh5030 | last post by:
This is a programming assignment. You are asked to work with pointers. Be aware that error messages are often not very helpful when your pointers point to bad locations. Therefore, reserve...
1
by: kieselchen | last post by:
hej, i would like to use the stl priority queue, but i occasionally have to remove random elements form the queue. is there any possibility for that? concert problem: i'd like to use priority...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...

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.