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/d05b49cf-a310-4351-8253-c2b26ab0658cn%40googlegroups.com.
