Add edge coloring function

[ihincks]

What is the expected enhancement?

Edge coloring has natural applications in quantum, because, for example, given a coupling map, the edge colors of an edge coloring can be interpreted as gates which are able to be applied simultaneously.

Vizing's theorem (for simple connected graphs) says that you can always edge color a graph in deg(G) or deg(G)+1 colors, where deg(G) is the maximum degree of any vertex. Deciding which of these two cases a particular graph falls into is NP-complete. However, near-optimal polynomial time algorithms exist that use no more than deg(G)+1 colors, notably Misra-Gries edge-coloring.

Here is my Python implementation:

from typing import Set, FrozenSet, Dict, Iterable, Tuple, List
from collections import defaultdict
from itertools import count

Node = int
Edge = FrozenSet[Node]
Color = int

edge = lambda u, v: frozenset((u, v))

def misra_gries(edges: Set[Edge]) -> Dict[Edge, Color]:
    r"""Return an edge-coloring of a simple connected graph."""
    colors = {}
    adjacencies = defaultdict(set)
    for u, v in edges:
        adjacencies[u].add(v)
        adjacencies[v].add(u)

    def adjacent_colors(u: Node) -> Iterable[Tuple[Node, Color]]:
        # yield all colored nodes adjacent to u, along with their color
        for n in adjacencies[u]:
            color = colors.get(edge(u, n), None)
            if color is not None:
                yield n, color

    def is_free(c: Color, u: Node) -> bool:
        # return whether node u touches an edge of color c
        return all(color != c for _, color in adjacent_colors(u))

    def free_color(u: Node) -> Color:
        # return the first free color of node u
        used_colors = {color for _, color in adjacent_colors(u)}
        for color in count():
            if color not in used_colors:
                return color

    def maximal_fan(u: Node, v: Node) -> List[Node]:
        # return a maximal on {u, v} at u
        fan = [v]
        remaining = set(adjacent_colors(u))
        while remaining:
            for n, c in remaining:
                if is_free(c, fan[-1]):
                    fan.append(n)
                    remaining.discard((n,c))
                    break
            else:
                break
        return fan

    def cdu_path(c: Color, d: Color, u: Node) -> Set[Edge]:
        # return a cd_u path
        path = set()
        endpoints = {u}
        while endpoints:
            e = endpoints.pop()
            for n, color in adjacent_colors(e):
                if edge(e, n) not in path and color in (c,d):
                    endpoints.add(n)
                    path.add(edge(e, n))
        return path 

    remaining = set(edges)
    while remaining:
        u, v = remaining.pop()
        f = maximal_fan(u, v)
        c = free_color(u)
        d = free_color(f[-1])

        # invert the cd_u path
        path = cdu_path(c, d, u)
        for e in path:
            colors[e] = c if colors[e] == d else d

        # rotate the v...w fan left
        w = next(n for n in f[::-1] if is_free(d, n))
        for a, b in zip(f, f[1:]):
            if a == w:
                break
            colors[edge(u, a)] = colors[edge(u, b)]
        colors[edge(u, w)] = d

    return colors

And an example output

import numpy as np
from itertools import product
import matplotlib.pyplot as plt

def plot_colors(colors, all_edges=None):
    plt.scatter(*locs.T)
    for idx, (x, y) in enumerate(locs):
        plt.text(x, y, str(idx))
    remaining = set([] if all_edges is None else all_edges)
    for (a, b), c in colors.items():
        remaining.discard(edge(a, b))
        x0, y0 = locs[a]
        x1, y1 = locs[b]
        plt.plot([x0, x1], [y0, y1], color=plt.rcParams["axes.prop_cycle"].by_key()["color"][c])
    for a, b in remaining:
        x0, y0 = locs[a]
        x1, y1 = locs[b]
        plt.plot([x0, x1], [y0, y1], color="grey", alpha=0.3)

locs = [[0,2],[0,3],[0,4],[0,5],[0,6],[1,2],[1,6],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[3,0],[3,4],[3,8],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[5,2],[5,6],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[6,8],[7,0],[7,4],[7,8],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[9,2],[9,6]]
locs = np.array(locs)[:, ::-1]
edges = set()
for (idx, (x0, y0)), (jdx, (x1, y1)) in product(enumerate(locs), repeat=2):
    if idx != jdx and (x0 - x1) ** 2 + (y0 - y1) ** 2 < 1.1:
        edges.add(edge(idx, jdx))

plot_colors(misra_gries(edges))

(Note that heavy-hex happens to be 3-edge-colorable, so that this example shows how Misra Gries is not optimal, but near optimal)

[willkirby1]

@ajavadia suggested that I comment on this, since we have been thinking about the same problem. Using the fact that edge coloring is the same as vertex coloring on the dual graph (line graph), one can use vertex coloring methods, which seem to be more widely implemented. In the example below I use networkx's greedy_color function (https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.coloring.greedy_color.html), which has a number of different built-in coloring strategies. It also comes up with a 4-coloring of the graph Ian used, also with only one red edge. So this is another option.

from typing import Set, FrozenSet, Dict, Iterable, Tuple, List
from collections import defaultdict
import numpy as np
from itertools import product, count
import matplotlib.pyplot as plt
import networkx as nx

Node = int
Edge = FrozenSet[Node]
Color = int

edge = lambda u, v: frozenset((u, v))

locs = [[0,2],[0,3],[0,4],[0,5],[0,6],[1,2],[1,6],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[3,0],[3,4],[3,8],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[5,2],[5,6],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[6,8],[7,0],[7,4],[7,8],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[9,2],[9,6]]
locs = np.array(locs)[:, ::-1]
edges = set()
for (idx, (x0, y0)), (jdx, (x1, y1)) in product(enumerate(locs), repeat=2):
    if idx != jdx and (x0 - x1) ** 2 + (y0 - y1) ** 2 < 1.1:
        edges.add(edge(idx, jdx))

graph = nx.Graph(edges)
# Here is where the edge coloring happens: using networkx's greedy_color function, which has a number of built-in strategies.
edge_coloring = nx.greedy_color(nx.line_graph(graph))

# Convert to the same form as Ian's function output:
colors = {edge(e[0], e[1]):color for e, color in edge_coloring.items()}

def plot_colors(colors, all_edges=None):
    plt.scatter(*locs.T)
    for idx, (x, y) in enumerate(locs):
        plt.text(x, y, str(idx))
    remaining = set([] if all_edges is None else all_edges)
    for (a, b), c in colors.items():
        remaining.discard(edge(a, b))
        x0, y0 = locs[a]
        x1, y1 = locs[b]
        plt.plot([x0, x1], [y0, y1], color=plt.rcParams["axes.prop_cycle"].by_key()["color"][c])
    for a, b in remaining:
        x0, y0 = locs[a]
        x1, y1 = locs[b]
        plt.plot([x0, x1], [y0, y1], color="grey", alpha=0.3)

plot_colors(colors)

[ShellyGarion]

For certain useful coupling maps one can do dedicated coloring algorithms (see the list of relevant coupling maps here: https://qiskit.org/documentation/stubs/qiskit.transpiler.CouplingMap.html)

• 2-coloring for line and ring
• 3-coloring for hex and heavy-hex
• 4-coloring for grid and heavy-square

See the following example for a 3-coloring of a heavy hex (all the hexagons are colored the same).

[ihincks]

Thanks @ShellyGarion, I didn't know that was in there. Is it exposed as a method (I don't immediately see it), or is it tucked away in draw()?

@willkirby1 neat, I sort of just assumed that wouldn't work well, but didn't bother to try it! I wonder if there are cases where it fails at near-optimality, or if it always works well for planar graphs?

[willkirby1]

@willkirby1 neat, I sort of just assumed that wouldn't work well, but didn't bother to try it! I wonder if there are cases where it fails at near-optimality, or if it always works well for planar graphs?

@ihincks good question, but I have only tried it for examples, so I have no high-level insight. I guess I wouldn't trust it to always give a good coloring even on planar without some better theoretical understanding, but for specific applications at least it is something to try and check how well it does. I like @ShellyGarion's coloring though, I also didn't know it was in there.

[ShellyGarion]

I don't think that we have coloring algorithms for the specific coupling maps (line/ring/hex/heavy-hex/grid/heavy-grid), my suggestion is to add them according to the picture above (and similar ones).

[ihincks]

I don't think that we have coloring algorithms for the specific coupling maps (line/ring/hex/heavy-hex/grid/heavy-grid), my suggestion is to add them according to the picture above (and similar ones).

Got it, thanks!

[alexanderivrii]

A simple observation is that for both 4-colorings above we can locally change the colors to get valid 3-colorings. In Ian's coloring we can change the color of the (11, 17)-edge from red to orange, and the color of the (10, 11)-edge from orange to green. In Will's coloring we can change the color of the (9, 10)-edge from red to orange, and the color of the (9, 5)-edge from orange to green. Are there known algorithms that try to do a local search for a valid coloring? (And if not, we could possible think of some),

[mtreinish]

I think we can close this now as #870 and #902 merged adding a misra gries and greedy edge coloring algorithm to rustworkx. Both of these functions were included in the most recent 0.14.0 release. However, if I'm missing something please feel free to reopen this, or open a new issue if there are other edge coloring algorithms you think should be added to rustworkx.