Qiskit / retworkx / 545

97%

push

travis-ci-com

Add graph greedy color function (#77)

* Add graph greedy color function

This commit adds a new function for getting the greedy coloring using a
largest first strategy.

* Add simple tests and fix bugs

This commit adds some simple tests to start and fixes bugs found via the
testing. Given the number of logic issues in the first draft of the
function we need more thorough testing prior to merging.

* Adjust sort key to be consistent with expectations

The sorting we were using was different then the equivalent function in
networkx this is trying to match. Instead of doing a stable sort and
then reversing this could result in a different sorting order than what
someone migrating from the equivalent networkx function would expect.
This commit changes the sort key to be the
{number of nodes} - {number of neighbors} to address this. It also has
the advantage of speeding it up because we don't have to do the inplace
reverse.

* Calculate sort keys upfront

This commit reworks the sorting to calculate the keys upfront all at
once prior to doing the sorting and storing them in a hashmap. Then the
sort function is just based on a hashmap value lookup. This makes the
number of times we run sorting key function (which gets a count of
neighbors and subtracts the node count from it) less which speeds up the
run time.

* Add docs

* Add comment explaining sort key

* Handle edge case of large degrees in multigraphs

This commit fixes an edge case in the new function where we'd get
incorrect results if the degree of a node was greater than the number of
nodes in the graph. We previously would cause an overflow by subtracting
number of nodes - degree and the reverse ordering was broken because the
node with the large degree is now a larger number instead of a smaller
number. This fixes this issue by using the Reverse struct from std::cmp
[1] and making the sort key Reverse(degree). The hash map previously
used is kept in ... (continued)

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

1053 of 1256 relevant lines covered (83.84%)

1644.88 hits per line