Functions¶

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)
[]
>>> color([], 2)  # empty graph
[]
>>> color([[0]], 1)  # single node, 1 color
[0]
>>> color([[0, 1], [1, 0]], 1)  # 2 nodes, 1 color (impossible)
[]
>>> color([[0, 1], [1, 0]], 2)  # 2 nodes, 2 colors (possible)
[0, 1]

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