gcp.py File Reference

model for the graph coloring problem More...

Go to the source code of this file.

Functions
def	gcp (V, E, K)
def	gcp_low (V, E, K)
def	gcp_sos (V, E, K)
def	make_data (n, prob)

Variables
	V
	E
int	K = 10
	model = gcp_low(V,E,K)
	x = model.data
dictionary	color = {}
list	models = [gcp,gcp_low,gcp_sos]
dictionary	cpu = {}
int	N = 25
	name = m.__name__
	tinit = time.clock()
	tend = time.clock()

Detailed Description

model for the graph coloring problem

Definition in file gcp.py.

Function Documentation

def gcp.gcp	(		V,
			E,
			K
	)

gcp -- model for minimizing the number of colors in a graph
Parameters:
    - V: set/list of nodes in the graph
    - E: set/list of edges in the graph
    - K: upper bound on the number of colors
Returns a model, ready to be solved.

Definition at line 9 of file gcp.py.

def gcp.gcp_low	(		V,
			E,
			K
	)

gcp_low -- model for minimizing the number of colors in a graph
(use colors with low indices)
Parameters:
    - V: set/list of nodes in the graph
    - E: set/list of edges in the graph
    - K: upper bound to the number of colors
Returns a model, ready to be solved.

Definition at line 37 of file gcp.py.

def gcp.gcp_sos	(		V,
			E,
			K
	)

gcp_sos -- model for minimizing the number of colors in a graph
(use sos type 1 constraints)
Parameters:
    - V: set/list of nodes in the graph
    - E: set/list of edges in the graph
    - K: upper bound to the number of colors
Returns a model, ready to be solved.

Definition at line 70 of file gcp.py.

def gcp.make_data	(		n,
			prob
	)

make_data: prepare data for a random graph
Parameters:
   - n: number of vertices
   - prob: probability of existence of an edge, for each pair of vertices
Returns a tuple with a list of vertices and a list edges.

Definition at line 105 of file gcp.py.