backtracking.coloring

Graph Coloring also called “m coloring problem” consists of coloring a given graph with at most m colors such that no adjacent vertices are assigned the same color

Wikipedia: https://en.wikipedia.org/wiki/Graph_coloring

Functions

color(→ list[int])	Wrapper function to call subroutine called util_color
util_color(→ bool)	Pseudo-Code
valid_coloring(→ bool)	For each neighbour check if the coloring constraint is satisfied

Module Contents

backtracking.coloring.color(graph: list[list[int]], max_colors: int) → list[int]

Wrapper function to call subroutine called util_color which will either return True or False. If True is returned colored_vertices list is filled with correct colorings

>>> graph = [[0, 1, 0, 0, 0],
...          [1, 0, 1, 0, 1],
...          [0, 1, 0, 1, 0],
...          [0, 1, 1, 0, 0],
...          [0, 1, 0, 0, 0]]

>>> max_colors = 3
>>> color(graph, max_colors)
[0, 1, 0, 2, 0]

>>> max_colors = 2
>>> color(graph, max_colors)
[]

backtracking.coloring.util_color(graph: list[list[int]], max_colors: int, colored_vertices: list[int], index: int) → bool

Pseudo-Code

Base Case: 1. Check if coloring is complete

1.1 If complete return True (meaning that we successfully colored the graph)

Recursive Step: 2. Iterates over each color:

Check if the current coloring is valid:

2.1. Color given vertex 2.2. Do recursive call, check if this coloring leads to a solution 2.4. if current coloring leads to a solution return 2.5. Uncolor given vertex

>>> graph = [[0, 1, 0, 0, 0],
...          [1, 0, 1, 0, 1],
...          [0, 1, 0, 1, 0],
...          [0, 1, 1, 0, 0],
...          [0, 1, 0, 0, 0]]
>>> max_colors = 3
>>> colored_vertices = [0, 1, 0, 0, 0]
>>> index = 3

>>> util_color(graph, max_colors, colored_vertices, index)
True

>>> max_colors = 2
>>> util_color(graph, max_colors, colored_vertices, index)
False

backtracking.coloring.valid_coloring(neighbours: list[int], colored_vertices: list[int], color: int) → bool

For each neighbour check if the coloring constraint is satisfied If any of the neighbours fail the constraint return False If all neighbours validate the constraint return True

>>> neighbours = [0,1,0,1,0]
>>> colored_vertices = [0, 2, 1, 2, 0]

>>> color = 1
>>> valid_coloring(neighbours, colored_vertices, color)
True

>>> color = 2
>>> valid_coloring(neighbours, colored_vertices, color)
False