Add different greedy strategies for node coloring #1137
Comments
mtreinish
added a commit
that referenced
this issue
May 30, 2024
…ategies (#1138) This PR adds two more standard coloring strategies to greedy node/edge coloring functions graph_greedy_color and graph_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: import rustworkx as rx graph = rx.generators.generalized_petersen_graph(5, 2) coloring = rx.graph_greedy_color(graph, greedy_strategy=rx.GreedyStrategy.Degree) coloring = rx.graph_greedy_color(graph, greedy_strategy=rx.GreedyStrategy.Saturation) coloring = rx.graph_greedy_color(graph, greedy_strategy=rx.GreedyStrategy.IndependentSet) coloring = rx.graph_greedy_color(graph) coloring = rx.graph_greedy_edge_color(graph) coloring = rx.graph_greedy_edge_color(graph, greedy_strategy=rx.GreedyStrategy.Degree) coloring = rx.graph_greedy_edge_color(graph, greedy_strategy=rx.GreedyStrategy.Saturation) coloring = rx.graph_greedy_edge_color(graph, greedy_strategy=rx.GreedyStrategy.IndependentSet) The greedy_graph_edge_color function has been also extended to support the preset_color_fn argument (though in this case it's an optional map from an edge index to either a color or to None) * initial commit * fix and test * python formatting * creating enums * also passing greedy strategy to edge coloring functions; improving docstrings * release notes' * python test * reno fix * reno fix * minor cleanup * small rust cleanup * adding greedy node coloring using maximal independent set + reworked tests * updating top-level source, tests and docs * docs * applying fix from code review * adding IndependentSet to pyi as well * Adding a table that describes greedy strategies available * converting table to sphinx-style * fix reference to footnotes * docs improvements * another attempt * attempt to extend API with preset_color_fn for edges * minor * finally compiling * fixing pyi API and edding python tests * adding rustworkx-core tests * adding arguments to docstrings * expanding release note * another docs fix * Update releasenotes/notes/saturation-greedy-color-109d40f189590d3a.yaml Co-authored-by: Matthew Treinish <[email protected]> * a round of renaming * restoring greedy_node_coloring API for backwards compatibility * restoring greedy_edge_coloring API for backwards compatibility * fix to rustworkx coloring * changing return type of new rustworkx-core functions to be Result * black * removing NodeIndexable in node coloring functions * and from edge coloring functions * suggestions from code review * suggestions from code review * release note update --------- Co-authored-by: Matthew Treinish <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
What is the expected enhancement?
This tracks the rustworkx part of Qiskit/qiskit#11779 (comment). The request is to add other standard greedy node coloring strategies, such as the "saturation first" strategy: always picking the node that has the largest number of different colors assigned to its neighbors, and, in case of a tie, the node that has the largest number of uncolored neighbors.
This will be immediately followed up by a PR.
The text was updated successfully, but these errors were encountered: