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. 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/af2d11aa-0cbe-4063-a8f7-8969d9112719n%40googlegroups.com.
