Skip to content

Instantly share code, notes, and snippets.

@RobertTalbert

RobertTalbert/GraphColoring.py

Created March 9, 2015 18:43
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RobertTalbert/9389b95826f757dbd3ec to your computer and use it in GitHub Desktop.
Save RobertTalbert/9389b95826f757dbd3ec to your computer and use it in GitHub Desktop.
Download ZIP
Raw
GraphColoring.py
'''The following code implements a graph coloring in Sage.
+ The first line loads a package for Sage specifically to deal with graph coloring.
+ Replace g with any graph. The default below is a randomly generated graph with 10
nodes and a 0.5 chance of two nodes being adjacent.
+ vertex_coloring(g) generates a partition of the nodes according to color.
+ The partition=colors option in the last line will actually color the nodes according to the partition.
'''
from sage.graphs.graph_coloring import *
g = graphs.RandomGNP(10, 0.5) # Or your favorite graph, entered as a dictionary, matrix, special graph, etc.
colors = vertex_coloring(g)
g.show(partition=colors)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment