Closed alexanderivrii closed 3 months ago
Changes Missing Coverage | Covered Lines | Changed/Added Lines | % | ||
---|---|---|---|---|---|
src/coloring.rs | 28 | 29 | 96.55% | ||
rustworkx-core/src/coloring.rs | 162 | 170 | 95.29% | ||
<!-- | Total: | 191 | 200 | 95.5% | --> |
Files with Coverage Reduction | New Missed Lines | % | ||
---|---|---|---|---|
src/shortest_path/all_pairs_bellman_ford.rs | 6 | 95.53% | ||
rustworkx-core/src/coloring.rs | 36 | 90.02% | ||
<!-- | Total: | 42 | --> |
Totals | |
---|---|
Change from base Build 9259965164: | -0.2% |
Covered Lines: | 17254 |
Relevant Lines: | 18007 |
I am confused about the "stubs" problems: what are these and how should I fix them?
rustworkx.GreedyStrategy cannot be subclassed at runtime, but isn't marked with @final in the stub
rustworkx.GreedyStrategy.Degree is not present in stub
rustworkx.GreedyStrategy.Saturation is not present in stub
rustworkx.rustworkx.GreedyStrategy cannot be subclassed at runtime, but isn't marked with @final in the stub
rustworkx.rustworkx.GreedyStrategy.Degree is not present in stub
rustworkx.rustworkx.GreedyStrategy.Saturation is not present in stub
I think I have addressed all of the comments from the previous review, this is ready for another round! :)
Thanks @mtreinish, as suggested (and later discussed offline) I have retained the older version of the coloring functions in rustworkx-core and removed using the unnecessary NodeIndexable
trait, making the code backwards compatible, at the expense of introducing two new function greedy_node_coloring_with_coloring_strategy
and greedy_edge_color_with_coloring_strategy
. I could not think of shorter names. I have made their return type to be Result<Dict<...>, E>
instead of Dict<...>
, which allows error handling. I have renamed the enums to ColoringStrategy
and the function argument to strategy
, as per your suggestions, I like these much better.
Description
This PR adds two more standard coloring strategies to greedy node/edge coloring functions
graph_greedy_color
andgraph_greedy_edge_color
.In the literature the first strategy is known as "saturation", "DSATUR" or "SLF". We dynamically choose the vertex that has the largest number of different colors already assigned to its neighbors, and, in case of a tie, the vertex that has the largest number of uncolored neighbors.
The second strategy is known as "greedy independent sets" or "GIS". We greedily find independent subsets of the graph, and assign a different color to each of these subsets.
This addresses #1137, modulo the fact that there are quadrillions of different greedy node coloring algorithms, and each comes with trillion variations.
Both new strategies can be combined with
preset_color_fn
(for node coloring).There is also a new Rust enum
GreedyStrategy
exposed as a python class that allows to specify which of the three currently supported greedy strategies is used. This is, calling the functions from the Python code would be as follows:Update: the
greedy_graph_edge_color
function has been also extended to support thepreset_color_fn
argument (though in this case it's an optional map from an edge index to either a color or toNone
)