Qiskit / qiskit / 10945817672

89%

Build Type

push

github

Committed by web-flow

Commit Message

Make dense layout algorithm deterministic when run in parallel (#13133)

* 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

Run Details

5 of 5 new or added lines in 1 file covered. (100.0%)

25 existing lines in 4 files now uncovered.

73475 of 82767 relevant lines covered (88.77%)

359927.03 hits per line