[Networkit] Prio queue for integer priorities
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
KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 5379 bytes
Desc: S/MIME Cryptographic Signature
More information about the NetworKit