[Networkit] Prio queue for integer priorities

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


Hello,

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.

Best,
Henning



-- 

=======================================================
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