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> -- http://mail.python.org/mailman/listinfo/python-list
