︠from sage.graphs.graph_coloring import vertex_coloring

# This is the list of English actors in the order they appear
english_actor_sequence = [
     1,  2,  3,  1,  5,  4,  2,  6,  1,  3,
     2,  9,  6,  3, 10, 11,  3,  2, 12,  1,
    13, 14, 12,  2,  7,  6,  1, 13, 11,  5,
    13, 15,  7, 12, 10, 16, 17,  2,  3,  6,
    12, 17, 15,  5,  4, 13,  2,  7,  1, 14,
    10, 15,  9,  4,  2]

# Two French actors cannot take roles of English actors in consecutive scenes
actor_pairs = [(english_actor_sequence[i],english_actor_sequence[i+1]) for i in range(len(english_actor_sequence) - 1)]

# Create a graph where the English actors are nodes, the edges are whether two English actors are in consecutive scenes
# Multiedges are not needed
scene_graph = Graph(actor_pairs, multiedges=False)

# Show the graph before colouring
scene_graph.graphplot(layout='circular').show(figsize=[6,6])

# Display the info
print 'You need %d French actors.' % vertex_coloring(scene_graph, value_only=True)
print 'These are the English roles the French actors will take: '
for i in range(vertex_coloring(scene_graph, value_only=True)):
    print 'French actor %d will play the parts: ' % (i+1)
    print vertex_coloring(scene_graph)[i]

#Show the coloured graph
scene_graph.graphplot(layout='circular', partition=vertex_coloring(scene_graph)).show(figsize=[6,6])