New algorithm for graph edge coloring

[Matheus Maldonado]

Hello everyone,

I just developed a new function for coloring graph edges based on this article: https://www.sciencedirect.com/science/article/abs/pii/002001909290041S , and I'd like to know if you think it's a valuable contribution to sage and deserves a trac ticket. I compared the existing edge coloring function and the one I created, and it's a pretty good improvement in processing time for graphs with a lot of edges:

sage: g_list = [graphs RandomGNP(x, 0.7) for x in range(25)]
sage: %time c = [vizing_edge_coloring(x) for x in g_list]
CPU times: user 131 ms, sys: 9.94 ms, total: 141 ms
Wall time: 140 ms
sage: %time c = [edge_coloring(x, vizing=True) for x in g_list]
CPU times: user 18.6 s, sys: 134 μs, total: 18.6 s
Wall time: 18.6 s

I still haven't decided if this function should be standalone or if it should be called when the flag vizing is set on the existing edge_coloring function. If you have an opinion on that, please share :)

I'm pasting the code below for reference, since I haven't created a ticket and pushed my branch yet. Feedback is much appreciated!

def vizing_edge_coloring(g, hex_colors=False):
    r"""
    Compute an edge coloring with at most `\Delta + 1` colors.

    INPUT:

    - ``g`` -- a graph.

    - ``hex_colors`` -- boolean (default: ``False``); when set to ``True``, the
      partition returned is a dictionary whose keys are colors and whose values
      are the color classes (ideal for plotting)

    OUTPUT:

    - Returns a partition of the edge set into at most `\Delta + 1` matchings.

    .. SEEALSO::

        - :wikipedia:`Edge_coloring` for further details on edge coloring
        - :wikipedia:`Vizing's_theorem` for further details on Vizing's theorem

    ALGORITHM:

    This function's implementation is based on the algorithm described at [MG1992]_
   
    EXAMPLES:

    Coloring the edges of the Petersen Graph::

       sage: from sage.graphs.graph_coloring import vizing_edge_coloring
       sage: g = graphs.PetersenGraph()
       sage: vizing_edge_coloring(g)
       [[(0, 1), (2, 7), (3, 4), (6, 9)],
         [(0, 4), (2, 3), (5, 7), (6, 8)],
         [(0, 5), (1, 6), (3, 8), (7, 9)],
         [(1, 2), (4, 9), (5, 8)]]
       sage: vizing_edge_coloring(g, hex_colors=True)
        {'#00ffff': [(0, 5), (1, 6), (3, 8), (7, 9)],
        '#7f00ff': [(1, 2), (4, 9), (5, 8)],
        '#7fff00': [(0, 4), (2, 3), (5, 7), (6, 8)],
        '#ff0000': [(0, 1), (2, 7), (3, 4), (6, 9)]}

    TESTS:

    Graph without edge::

       sage: g = Graph(2)
       sage: vizing_edge_coloring(g)
       []
       sage: vizing_edge_coloring(g, hex_colors=True)
       {}
    """
    # finds every color adjacent to vertex v
    def colors_of(v):
        return [x[2] for x in g.edges_incident(v) if x[2] is not None]

    # constructs a maximal fan <f..l> of X where X is edge[0] and f is edge[1]
    def maximal_fan(edge):
        fan_center, rear = edge
        rear_colors = colors_of(rear)
        cdef list neighbors = [n for n in g.neighbors(fan_center) if g.edge_label(fan_center, n) is not None]
        cdef list fan = [rear]
        can_extend_fan = True
        while can_extend_fan:
            can_extend_fan = False
            for n in neighbors:
                if g.edge_label(fan_center, n) not in rear_colors:
                    fan.append(n)
                    rear = n
                    rear_colors = colors_of(rear)
                    can_extend_fan = True
                    neighbors.remove(n)
        return fan

    # gives each edge Xu in the fan <f..w> the color of Xu+ and uncolors Xw
    def rotate_fan(fan_center, fan):
        for i in range(1, len(fan)):
            g.set_edge_label(fan_center, fan[i - 1], g.edge_label(fan_center, fan[i]))
        g.set_edge_label(fan_center, fan[-1], None)

    # computes the maximal ab-path starting at v
    def find_path(v, a, b, path=[]):
        path_edge = [x for x in g.edges_incident(v) if x[2] == a]
        if path_edge and path_edge[0] not in path:
            path.append(path_edge[0][0] if path_edge[0][1] == v else path_edge[0][1])
            find_path(path[-1], b, a, path)
        return path

    # exchanges the color of every edge on the ab-path starting at v
    def invert_path(v, a, b):
        path = [v] + find_path(v, a, b, [])
        for i in range(1, len(path)):
            g.set_edge_label(path[i-1], path[i], a if g.edge_label(path[i-1], path[i]) == b else b)

    # returns the ´smallest´ color free at v
    def find_free_color(v):
        colors = [x[2] for x in g.edges_incident(v) if x[2] is not None]
        for c in range(g.degree(v) + 1):
            if c not in colors:
                return c

    g._scream_if_not_simple()
    # as to not overwrite the original graph's labels
    g = copy(g)
    for e in g.edge_iterator(labels=False):
        fan = maximal_fan(e)
        fan_center = e[0]
        rear = fan[-1]
        c = find_free_color(fan_center)
        d = find_free_color(rear)
        invert_path(fan_center, d, c)
        for i in range(len(fan)):
            if d not in colors_of(fan[i]):
                fan = fan[:i + 1]
                break
        rotate_fan(fan_center, fan)
        g.set_edge_label(fan_center, fan[-1], d)

    matchings = dict()
    for e in g.edge_iterator():
        matchings[e[2]] = matchings.get(e[2], []) + [(e[0], e[1])]
    classes = list(matchings.values())

    if hex_colors:
        from sage.plot.colors import rainbow
        return dict(zip(rainbow(len(classes)), classes))
    else:
        return classes

[David Coudert]

Feel free to open a ticket for this code. It's seems a good improvement.

[dmo...@deductivepress.ca]

I agree that this seems to be a good improvement.  I think it should replace the current "vizing" algorithm, instead of adding a new function to the namespace.

A minor issue is that (if I understand correctly) the current vizing algorithm always gives a colouring with Delta + 1 colours.  If that is correct, then the code may need to be modified to have an option that matches this behaviour, until the traditional 1-year deprecation period has passed.

Also, I think the "hex_colors" option should be deleted. Instead, it would be nice to put this code into the documentation as an example that demonstrates how to print the colouring.

[Matheus Maldonado]

On Monday, 28 November 2022 at 03:48:18 UTC-3 dmo...@deductivepress.ca wrote:

I agree that this seems to be a good improvement.  I think it should replace the current "vizing" algorithm, instead of adding a new function to the namespace.

A minor issue is that (if I understand correctly) the current vizing algorithm always gives a colouring with Delta + 1 colours.  If that is correct, then the code may need to be modified to have an option that matches this behaviour, until the traditional 1-year deprecation period has passed.

I see. If the algorithm finds a Delta coloring, I just need to change the color of a random edge to a new one. Sounds a little counter-intuitive, but I understand the reason behind it. 

 

Also, I think the "hex_colors" option should be deleted. Instead, it would be nice to put this code into the documentation as an example that demonstrates how to print the colouring.

 Any specific reason for this? 

[David Coudert]

FYI, the current Vizing algorithm is not well tested and the returned edge coloring may have an empty set of colors

sage: from sage.graphs.graph_coloring import edge_coloring
sage: G = graphs.PetersenGraph()
sage: edge_coloring(G, vizing=True)
[[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)],
 [(0, 4), (1, 2), (3, 8), (6, 9)],
 [(0, 5), (2, 7)],
 [(1, 6), (3, 4), (5, 8), (7, 9)]]
sage: G = graphs.StarGraph(4)
sage: edge_coloring(G, vizing=True)
[[(0, 1)], [(0, 2)], [(0, 3)], [(0, 4)], []]

[Matheus Maldonado]

On Tuesday, 29 November 2022 at 05:05:50 UTC-3 David Coudert wrote:

FYI, the current Vizing algorithm is not well tested and the returned edge coloring may have an empty set of colors

sage: from sage.graphs.graph_coloring import edge_coloring
sage: G = graphs.PetersenGraph()
sage: edge_coloring(G, vizing=True)
[[(0, 1), (2, 3), (4, 9), (5, 7), (6, 8)],
 [(0, 4), (1, 2), (3, 8), (6, 9)],
 [(0, 5), (2, 7)],
 [(1, 6), (3, 4), (5, 8), (7, 9)]]
sage: G = graphs.StarGraph(4)
sage: edge_coloring(G, vizing=True)
[[(0, 1)], [(0, 2)], [(0, 3)], [(0, 4)], []]

If I understand correctly, the algorithm does that because the only possible coloring for this graph takes Delta colors, and the Vizing flag forces Delta+1 colors, creating an "empty color". If that isn't intended, then does dmo's suggestion of maintaining this behavior for every graph make sense? If it is intended though,  I'd have to add an edge case that appends an empty array to the result if Delta == number of edges, which sounds a bit counter-intuitive, just like giving a random edge a new color to force a Delta+1 coloring. 

[Matheus Maldonado]

There are some other points I forgot to mention:

Figuring out if the optimal edge coloring of a graph takes Delta or Delta+1 colors is an NP-hard problem and can take exponential time. This is not what my algorithm does. It may return a Delta coloring, but in a non-deterministic way.

What I suggest we do is: keep the current MILP implementation to find out if a Delta coloring exists, this way if the user is interested in this optimal coloring, he can set the flag Vizing to false and get what he needs. If there is no Delta coloring, or the user doesn't really care about the optimal solution, then we use my algorithm to find the coloring faster. There is no situation where the MILP solution does not find a Delta coloring and my algorithm does, so the only moment my implementation could return a Delta coloring is when the flag Vizing == true, and it shouldn't bother the user. I cannot think of any reason why someone would strictly need a Delta+1 coloring, but if they really need one they can give a random edge a new color.

I also think we should keep the hex_colors implementation, so that no code that depends on it breaks.

If anyone opposes this, please let me know. I'll be opening the ticket in a few hours.

[dmo...@deductivepress.ca]

This is now trac ticket #34809.