discrete_optimization.coloring package

Subpackages

Submodules

discrete_optimization.coloring.coloring_model module

Implementation of the famous graph coloring problem (https://en.wikipedia.org/wiki/Graph_coloring).

Graph coloring problem consists at assigning different colors to vertexes in a graph. The only constraint is that adjacent vertices should be colored by different colors

class discrete_optimization.coloring.coloring_model.ColoringProblem(graph: Graph, subset_nodes: Set[Hashable] | None = None, constraints_coloring: ConstraintsColoring | None = None)[source]

Bases: Problem

Coloring problem class implementation.

graph

a graph object representing vertices and edges.

Type:

Graph

number_of_nodes

number of nodes in the graph

Type:

int

subset_nodes

subset of nodes id to take into account in the optimisation.

Type:

Set[Hashable]

nodes_name

list of id of the graph vertices.

Type:

List[Hashable]

index_nodes_name

dictionary node_name->index

Type:

Dict[Hashable, int]

index_to_nodes_name

index->node_name

Type:

Dict[int, Hashable]

count_colors(colors_list: List[int]) → int[source]
count_colors_all_index(colors_list: List[int]) → int[source]
count_violations(variable: ColoringSolution) → int[source]

Count number of violation in graph coloring solution.

Parameters:

variable – ColoringSolution to evaluate the number of violation to the color constraint

Returns: an integer representing the number of edges (link between 2 vertices) where the colors are equal (thus being a violation)

evaluate(variable: ColoringSolution) → Dict[str, float][source]

Evaluation implementation for ColoringProblem.

Compute number of colors and violation of the current solution.

evaluate_from_encoding(int_vector: List[int], encoding_name: str) → Dict[str, float][source]

Can be used in GA algorithm to build an object solution and evaluate from a int_vector representation.

Parameters:

  • int_vector – representing the colors vector of our problem

  • encoding_name – name of the attribute in ColoringSolution corresponding to the int_vector given. In our case, will only work for encoding_name=”colors”

Returns: the evaluation of the (int_vector, encoding) object on the coloring problem.

get_attribute_register() → EncodingRegister[source]

Attribute documenation for ColoringSolution object.

Returns: an EncodingRegister specifying the colors attribute.

get_dummy_solution() → ColoringSolution[source]

Returns a dummy solution.

A dummy feasible solution consists in giving one different color per vertices. Returns: A feasible and dummiest ColoringSolution

get_objective_register() → ObjectiveRegister[source]

Specifies the default objective settings to be used with the evaluate function output.

get_solution_type() → Type[Solution][source]

Returns the class of a solution instance for ColoringProblem.

is_in_subset_index(index: int) → bool[source]
is_in_subset_nodes(node: Hashable) → bool[source]
satisfy(variable: ColoringSolution) → bool[source]

Check the color constraint of the solution.

Check for each edges in the graph if the allocated color of the vertices are different. When one counterexample is found, the function directly returns False.

Parameters:

variable (ColoringSolution) – the solution object we want to check the feasibility

Returns: boolean indicating if the solution fulfills the constraint.

class discrete_optimization.coloring.coloring_model.ColoringSolution(problem: Problem, colors: List[int] | ndarray | None = None, nb_color: int | None = None, nb_violations: int | None = None)[source]

Bases: Solution

Solution class for graph coloring problem.

The object contains a pointer to the problem instance, a list or numpy array giving colors values to each vertices of the graph. number of different colors or violation can also be stored to avoid some unnecessary computation (think about local search algorithms).

problem

instance of the graph coloring problem

Type:

ColoringProblem

colors

list/array of the same size of problem.number_of_nodes number. It should contain integer values representing discrete colors.

Type:

Union[List[int], np.array]

nb_color

number of different colors present in colors attributes. can be used directly by the problem.evaluate function if this attribute is provided (be careful to keep coherence between colors and nb_color !)

Type:

Optional[int]

change_problem(new_problem: Problem) → None[source]

Change the reference to the problem instance of the solution.

If two coloring problems have the same number of nodes, we can build a solution of the problem from the solution of another one.

Parameters:

new_problem – One another ColoringProblem.

Returns: None, but change in place the object

copy() → ColoringSolution[source]

Efficient way of copying a coloring solution without deepcopying unnecessary attribute (problem).

Algorithms can therefore copy this object, modify mutable attributes of interest (i.e colors) without modifying the initial object.

Returns: A copy that can be considered as a deep copy of the current object.

lazy_copy() → ColoringSolution[source]

Shallow copy of the coloring solution object.

Examples

x = y.lozy_copy() id(x) == id(y) # will be false x.colors==y.colors # will be true

Returns: a new ColoringSolution object where the mutable attributes will point to the same object

than the original.

to_reformated_solution() → ColoringSolution[source]

Computes a new solution where the colors array has a value precede chain (see more details https://www.minizinc.org/doc-2.5.3/en/lib-globals.html#index-62) property.

Examples : [1, 4, 4, 3, 2, 4] doesnt respect the value_precede_chain because 4 appears before 2 and 3. A transformed vector would be : [1, 2, 2, 3, 4, 2]. For the coloring problem it is the same solution but this time we respect value_precede.

The resulting solution is equivalent for the optimization problem to solve, but can reduce a lot the search space Returns: New ColoringSolution object with value precede chain property.

class discrete_optimization.coloring.coloring_model.ConstraintsColoring(color_constraint: Dict[Hashable, int])[source]

Bases: object

Data structure to store additional constraints. Attributes will grow .. attribute:: color_constraint

dictionary filled with color constraint.

type:

Dict[Hashable, int]

nodes_fixed() → Set[Hashable][source]
discrete_optimization.coloring.coloring_model.compute_constraints_penalty(coloring_solution: ColoringSolution, coloring_problem: ColoringProblem, constraints_coloring: ConstraintsColoring)[source]
discrete_optimization.coloring.coloring_model.transform_color_values_to_value_precede(color_vector: List[int]) → List[int][source]

See method ColoringSolution.to_reformated_solution().

Parameters:

color_vector (List[int]) – vector representing colors of vertices

Returns: A vector with value precede chain property

discrete_optimization.coloring.coloring_model.transform_coloring_problem(coloring_problem: ColoringProblem, subset_nodes: Set[Hashable] | None = None, constraints_coloring: ConstraintsColoring | None = None) → ColoringProblem[source]

discrete_optimization.coloring.coloring_parser module

discrete_optimization.coloring.coloring_parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → List[str][source]

Get datasets available for coloring.

Params:
data_folder: folder where datasets for coloring whould be find.

If None, we look in “coloring” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.coloring.coloring_parser.parse(input_data: str) → ColoringProblem[source]

From a text input, initialise a coloring problem instance.

Parameters:

input_data – text input in the format of {data_home}/coloring files

Returns: a ColoringProblem instance

discrete_optimization.coloring.coloring_parser.parse_file(file_path: str) → ColoringProblem[source]

From an absolute path to a coloring text file, return the corresponding coloring instance :param file_path: absolute path to the file :type file_path: str

Returns: a ColoringProblem instance

discrete_optimization.coloring.coloring_plot module

discrete_optimization.coloring.coloring_plot.plot_coloring_solution(solution: ColoringSolution, name_figure: str = '')[source]

discrete_optimization.coloring.coloring_solvers module

Utility module to launch different solvers on the coloring problem.

discrete_optimization.coloring.coloring_solvers.look_for_solver(domain: ColoringProblem) → List[Type[SolverColoring]][source]

Given an instance of ColoringProblem, return a list of class of solvers.

Parameters:

domain (ColoringProblem) – coloring problem instance

Returns: list of solvers class

discrete_optimization.coloring.coloring_solvers.look_for_solver_class(class_domain: Type[ColoringProblem]) → List[Type[SolverColoring]][source]

Given a class domain, return a list of class of solvers.

Parameters:

class_domain – should be ColoringProblem

Returns: list of solvers class

discrete_optimization.coloring.coloring_solvers.return_solver(method: Type[SolverColoring], problem: ColoringProblem, **kwargs: Any) → SolverColoring[source]

Return the solver initialized with the coloring problem instance

Parameters:

  • method – class of the solver to use

  • problem – coloring problem instance

  • **args – specific options of the solver

Returns (SolverDO) : a solver object.

discrete_optimization.coloring.coloring_solvers.solve(method: Type[SolverColoring], problem: ColoringProblem, **kwargs: Any) → ResultStorage[source]

Solve a coloring instance with a given class of solver.

Parameters:

  • method – class of the solver to use

  • problem – coloring problem instance

  • **args – specific options of the solver

Returns: a ResultsStorage objecting obtained by the solver.

discrete_optimization.coloring.coloring_toolbox module

discrete_optimization.coloring.coloring_toolbox.compute_cliques(g: Graph, nb_max: int | None = None) → Tuple[List[List[Hashable]], bool][source]

Compute nb_max cliques for a given graph (possibly a graph from a coloring model).

A clique of a graph is a subset of nodes that are all adjacent to each other. This is quite relevant for coloring problem where the color of nodes of a clique will have to be different.

Params:

g: a network x Graph nb_max: max number of cliques to return.

Returns: A list of cliques and a boolean indicating if all cliques have been computed.

Module contents