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/d717b9cd-1c38-4c48-bf43-d05a14f215a9n%40googlegroups.com.
