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)], []] 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/24ec8e80-3e11-4b04-8f19-d50e66768a39n%40googlegroups.com.
