Functions
def	gcp_fixed_k (V, E, K)

def	make_data (n, prob)

def	solve_gcp (V, E)

Variables
	color

	E

	K

	V

Function Documentation

◆ gcp_fixed_k()

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

References pyscipopt.expr.quicksum().

◆ make_data()

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

◆ solve_gcp()

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

Variable Documentation

◆ color

color

Definition at line 93 of file gcp_fixed_k.py.

◆ E

E

Definition at line 91 of file gcp_fixed_k.py.

◆ K

K