Qiskit / rustworkx / 7629401816
94%

DEFAULT BRANCH: main
Ran
Jobs 1
Files 96
Run time 9s
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst
coverage: 95.94% (-0.04%) from 95.98%
7629401816

push

github

web-flow 
Adding edge coloring algorithm for bipartite graphs (#1026)

### 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... (continued)

16636 of 17340 relevant lines covered (95.94%)

1802369.01 hits per line

Jobs
ID Job ID Ran Files Coverage
1 7629401816.1 96
95.94
 GitHub Action Run
Source Files on build 7629401816