Repo Added
|
Files
914
|
Badge
Embed ▾
README BADGES
|
push
github
Make dense layout algorithm deterministic when run in parallel (#13133) (#13190) * Make dense layout algorithm deterministic when run in parallel The dense layout algorithm is trying to find the densest k subgraph of the connectivity graph. To do this it performs a BFS from each node in the in graph of k nodes to determine the subgraph with the most number of edges. But in cases of ties where there are subgraphs with the same number of edges the exact output would be determined by the iteration order that we're evaluating a BFS search. However, this algorithm runs in parallel in most cases and the exact iteration order isn't going to be stable when running in parallel. It will depend on which threads finish first. This commit fixes this potential non-determinism in the algorithm by defaulting to the lower node index's trial results instead of relying on the execution order. This should mean we return identical results regardless of how many threads are run or how quickly they execute. * Add release note * Also handle the use_error case too (cherry picked from commit 65bb09efa) Co-authored-by: Matthew Treinish <mtreinish@kortar.org>
5 of 5 new or added lines in 1 file covered. (100.0%)
12 existing lines in 2 files now uncovered.66871 of 74507 relevant lines covered (89.75%)
216048.95 hits per line
Coverage | ∆ | File | Lines | Relevant | Covered | Missed | Hits/Line |
---|