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/a77f6852-f1f1-4b41-aa6c-893711d559b5n%40googlegroups.com.
