gcp_fixed_k.py File Reference

solve the graph coloring problem with fixed-k model More...

Go to the source code of this file.

Functions
def	gcp_fixed_k (V, E, K)
def	solve_gcp (V, E)
def	make_data (n, prob)

Variables
	V
	E
	K
	color

Detailed Description

solve the graph coloring problem with fixed-k model

Definition in file gcp_fixed_k.py.

Function Documentation

def gcp_fixed_k.gcp_fixed_k	(		V,
			E,
			K
	)

gcp_fixed_k -- model for minimizing number of bad edges in coloring a graph
Parameters:
    - V: set/list of nodes in the graph
    - E: set/list of edges in the graph
    - K: number of colors to be used
Returns a model, ready to be solved.

Definition at line 9 of file gcp_fixed_k.py.

def gcp_fixed_k.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 74 of file gcp_fixed_k.py.

def gcp_fixed_k.solve_gcp	(		V,
			E
	)

solve_gcp -- solve the graph coloring problem with bisection and fixed-k model
Parameters:
    - V: set/list of nodes in the graph
    - E: set/list of edges in the graph
Returns tuple with number of colors used, and dictionary mapping colors to vertices

Definition at line 39 of file gcp_fixed_k.py.