cpp: improves RmatGenerator and tests #1164
Conversation
c9ef083 to
fefdbe7
Compare
fefdbe7 to
f5585ca
Compare
fabratu
left a comment
There was a problem hiding this comment.
Thanks for taking care of the integration. In addition, please update the Python bindings and add tests (if needed) for the new parameter.
| } | ||
|
|
||
| // std::priority_queue doesn't support iterating over its elements. | ||
| struct PriorityQueue { |
There was a problem hiding this comment.
Better use Aux::PrioQueue instead.
|
|
||
| std::pair<node, node> RmatGenerator::sampleEdge(std::mt19937_64 &urng, uint8_t bits) { | ||
| std::pair<node, node> result{0, 0}; | ||
| while (true) { |
| entryList[lastOverfullIndex].probability -= delta; | ||
| coinFlipReplacement[curUnderfullIndex] = lastOverfullIndex; | ||
| coinFlipProbability[curUnderfullIndex] = | ||
| (uint32_t)(delta / baseProbability * std::numeric_limits<uint32_t>::max()); |
| return; | ||
| } | ||
| int curUnderfullIndex = lastUnderfullIndex; | ||
| while (true) { |
| throw std::runtime_error("Probabilities in Rmat have to sum to 1."); | ||
| defaultEdgeWeight = 1.0; | ||
|
|
||
| count size = 1 << std::min((count)12, (count)std::round(scale * 5.0 / 8.0) + 1); |
There was a problem hiding this comment.
Use static_cast instead of C-style casts.
| Graph generate() override; | ||
|
|
||
| private: | ||
| void sample(std::mt19937_64 &urng); |
There was a problem hiding this comment.
sample is a generic function name. Also, it is only used in sampleEdge and using internal states based on that. Better implement it directly as a lambda function inside sampleEdge.
| coinFlipProbability[i] = 0; | ||
| coinFlipReplacement[i] = 0; | ||
| } | ||
| double baseProbability = 1.0 / (double)size; |
| double baseProbability = 1.0 / (double)size; | ||
| count lastOverfullIndex = 0; | ||
| count lastUnderfullIndex = 0; | ||
| while (true) { |
There was a problem hiding this comment.
Avoid using while(true) for both readability and maintainability. Use do {} while(...) instead.
|
|
||
| return std::make_pair(u, v); | ||
| }); | ||
| auto drawEdge([&]() { return sampleEdge(Aux::Random::getURNG(), (uint8_t)scale); }); |
There was a problem hiding this comment.
As above (casting). Also use sampleEdge, since drawEdge simply now calls this.
| private: | ||
| void sample(std::mt19937_64 &urng); | ||
|
|
||
| std::pair<node, node> sampleEdge(std::mt19937_64 &urng, uint8_t bits); |
There was a problem hiding this comment.
Check whether urng can be moved to a member variable. This is what is normally done in other algorithm classes. This would then also remove the need for passing it as a parameter.
This code originated as bachelors thesis at MACSy, it has been copied without extensive sanity checks, feel free to comment on possible improvements.