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. On Tuesday, 29 November 2022 at 10:32:54 UTC-3 Matheus Maldonado wrote: > 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. > >> >> >> On Tuesday, November 29, 2022 at 7:13:43 AM UTC+1 Matheus Maldonado wrote: >> >>> 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? >>> >>> >>>> On Sunday, November 27, 2022 at 11:20:35 PM UTC-7 David Coudert wrote: >>>> >>>>> Feel free to open a ticket for this code. It's seems a good >>>>> improvement. >>>>> >>>>> On Sunday, November 27, 2022 at 5:39:34 PM UTC+1 Matheus Maldonado >>>>> wrote: >>>>> >>>>>> 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 >>>>>> >>>>> -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/85dfe630-a7e4-49b4-b889-4cbb69b325b9n%40googlegroups.com.
