Add two_color and is_bipartite #1002
Conversation
Pull Request Test Coverage Report for Build 6502172051
💛 - Coveralls |
| /// expected_colors.insert(NodeIndex::new(4), 1); | ||
| /// assert_eq!(coloring, expected_colors) | ||
| /// ``` | ||
| pub fn two_color<G>(graph: G) -> Option<DictMap<G::NodeId, u8>> |
There was a problem hiding this comment.
A general question about Rust: is there a performance penalty from using DictMap vs a vector (indexed by NodeIndex or something), i.e. is lookup / insertion into DictMap of order O(1) or of O(log n)?
There was a problem hiding this comment.
DictMap is basically just a IndexMap alias with a custom default hash algorithm. So lookup/insertion is O(1) but unlike a HashMap it retains insertion order. I went for using a dict map here because there is no guarantee that the node indices are contiguous or a sequence. The simplest example of that is if the input graph is a StableGraph with nodes removed in the middle. In general I'd expect a Vec would be faster here, but since we need this function to be general to handle all sorts of different types of graphs this seemed like the best option for the return type.
There was a problem hiding this comment.
It’s slower than a vector but still pretty fast (O(1)). It keeps the insertion order but that is what users expect from a Python dictionary-like structure
This commit adds new functions to rustworkx, two_color() and is_bipartite(), which are used to compute a two coloring for a graph and then determine if a givn graph is bipartite. The two_color() function is added to rustworkx-core as the python is_bipartite() function just wraps it and converts the output to a bool if a two coloring is possible or not. This commit is based on top of Qiskit#998 and will need to be rebased after that merges.
b46a72a to
0b94c19
Compare
| /// expected_colors.insert(NodeIndex::new(4), 1); | ||
| /// assert_eq!(coloring, expected_colors) | ||
| /// ``` | ||
| pub fn two_color<G>(graph: G) -> Option<DictMap<G::NodeId, u8>> |
There was a problem hiding this comment.
It’s slower than a vector but still pretty fast (O(1)). It keeps the insertion order but that is what users expect from a Python dictionary-like structure
This commit adds new functions to rustworkx, two_color() and
is_bipartite(), which are used to compute a two coloring for a graph and
then determine if a givn graph is bipartite. The two_color() function is
added to rustworkx-core as the python is_bipartite() function just wraps
it and converts the output to a bool if a two coloring is possible or
not.
This commit is based on top of #998 and will need to be rebased after
that merges.
You can see a diff of just the contents of this PR here:
https://github.com/Qiskit/rustworkx/compare/mtreinish:retworkx:add-isolates...mtreinish:retworkx:add-two-color?expand=1