[Networkit] Prio queue for integer priorities

Henning Meyerhenke henning.meyerhenke at kit.edu
Sun Jun 28 13:47:59 CEST 2015


I pushed a priority queue for integer priorities to the Dev branch, 
Aux::PrioQueueForInts. It is based on a bucket list data structure, so 
that operations have amortized constant time.

One of the many use cases is if you track the degrees of a static graph 
in which the algorithm "virtually" deletes nodes and edges (no need to 
make a copy of the original graph).

Examples are path growing matching (already uses it) and k-core 
decomposition (uses the same idea but so far a custom data structure).

Implementors are encouraged to use it where appropriate. Feedback is 
very welcome, as always.



Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5379 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150628/90d1392d/attachment.p7s>

More information about the NetworKit mailing list