Adding edge coloring algorithm for bipartite graphs

[alexanderivrii]

Summary

This PR adds a graph edge-coloring algorithm graph_bipartite_edge_color for bipartite graphs based on the paper "A simple algorithm for edge-coloring bipartite multigraphs" by Noga Alon, 2003.

The above function first checks whether the graph is indeed bipartite, and raises an exception of type GraphNotBipartite if this is not the case. Otherwise, the function edge-colors the graph and returns a dictionary with key being the edge index and value being the assigned color. This is the same output format as produced by other recently added edge-coloring functions graph_greedy_edge_color and graph_misra_gries_edge_color. The algorithm uses exactly d colors when d is the maximum degree of a node in the graph.

Usage example:

import rustworkx as rx

graph = rx.generators.heavy_hex_graph(9)
edge_colors = rx.graph_bipartite_edge_color(graph)
num_colors = max(edge_colors.values()) + 1
assert num_colors == 3

The algorithm has a runtime of O(m log m) where m is the number of edges in the graph.

A few technical details:

Internally this works with an undirected regular bipartite multigraph that

• keeps an explicit partition of its nodes into "left nodes" and "right nodes"
• only the edges connecting a left node to a right node are allowed (this is what bipartite means)
• each node in the graph has the same degree r (this is what regular means)
• each edge keeps additional data representing its multiplicity (aka weight) and whether or not the edge is bad (it is important that multiple edges connecting the same pairs of nodes are grouped into a single edges with multiplicity)

The internal data structure for the above is called RegularBipartiteMultiGraph. I don't foresee it being used anywhere outside of this PR, and so it's not marked as pub.

There is one possible optimization that is mentioned in the paper but which I have not implemented. Let r be the maximum degree of a node in the original graph. If the original bipartite graph is not regular (i.e. some of its nodes have degree less than r), then extra vertices and edges are inserted to make it regular (and of degree r) with the final edge-coloring is obtained by restricting the edge-coloring of the multi-graph to original edges. In addition (this is the mentioned possible optimization), one could group multiple "left" vertices with total degree not exceeding r into a single node in the multigraph; the same applies for subsets of right vertices.

The implementation also contains a function euler_cycles that might be useful in general, however the flavor needed here is somewhat non-standard, and so I did not expose it. The standard definition assumes that the graph is connected and an Euler cycle is a path that visits each edge exactly once and comes back to the starting vertex. In our case, however, the graph may be disconnected and the function euler_cycles returns a list of Euler cycles that visit each edge exactly once (however this is not an Euler cycle for the standard definition).

[coveralls]

Pull Request Test Coverage Report for Build 7629064353

• 0 of 0 changed or added relevant lines in 0 files are covered.
• No unchanged relevant lines lost coverage.
• Overall coverage decreased (-0.04%) to 95.94%

---

Totals
Change from base Build 7604258096:	-0.04%
Covered Lines:	16636
Relevant Lines:	17340

---

💛 - Coveralls

[alexanderivrii]

I don't think the MacOS-latest failure is related to the PR.

[mtreinish]

I don't think the MacOS-latest failure is related to the PR.

It was unfortunate timing, you pushed up new commits during a github actions outage: https://www.githubstatus.com/incidents/hmvr5kpgzc45 Now that the outage has been resolved I've re-triggered CI and it seems to be working now.

[mtreinish]

Overall this looks very good to me. I just a couple of inline questions mostly around adding some missing things to the python interface and the use of panic!().

The other thing is that since this past weekend we've moved to having Python type annotations required for all functions. I'll push a small commit to add them in this case. But for reference we've documented the process and procedure around this here: https://github.com/Qiskit/rustworkx/blob/main/CONTRIBUTING.md#type-annotations

[mtreinish]

Do you think we should expose this function from python too? We can probably have a kwarg that defaults to None for providing a partition (similar to what I just did in: #1060)

[alexanderivrii]

I don't think that having such a function is really useful (I did think so at the beginning but have changed my mind since then). Technically, we could avoid calling two_color if a partition is already given, but two_color is super-fast (since it's essentially DFS). Moreover, exposing this function to the users would probably mean making sure to handle the invalid input (i.e. making sure that the given partition is indeed a bipartite partition).

The ability to preset some colors (as in #1060) sounds very useful and it may be a good idea to similarly extend greedy_edge_color. Unfortunately I don't think we can have something similar for bipartite or for Misra-Gries edge-coloring algorithms.

[mtreinish]

The reason I asked is because this is a public function so we're exposing it to end users of the rustworkx-core library. I guess the follow on question is should this be pub or not?

[mtreinish]

This LGTM now, thanks for the quick update. I just had a quick follow up question about whether rustworkx_core::bipartite_coloring::bipartite_edge_color_given_partition should be a public function or not but otherwise I think we can go ahead and merge this.