This is now trac ticket #34809 <https://trac.sagemath.org/ticket/34809>.
On Tuesday, November 29, 2022 at 9:11:31 AM UTC-7 Matheus Maldonado wrote: > 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/f2faa5d9-5240-4f10-9e88-86fa036dd170n%40googlegroups.com.
