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/ded4fec7-2342-473a-91f8-566cc155fe28n%40googlegroups.com.
