backtracking.m_coloring_problem¶

Attributes¶

`graph_coloring`(→ bool)	Determine if the graph can be colored with at most max_colors.
`is_safe`(→ bool)	Check if it is safe to assign a color to a node.
`solve`(→ bool)	Recursively try to color the graph using at most max_colors.

backtracking.m_coloring_problem.graph_coloring(graph: list[list[int]], max_colors: int, num_vertices: int) → bool¶

Determine if the graph can be colored with at most max_colors.

>>> graph_coloring([[0,1,1],[1,0,1],[1,1,0]], 3, 3)
True
>>> graph_coloring([[0,1,1],[1,0,1],[1,1,0]], 2, 3)
False

backtracking.m_coloring_problem.is_safe(node: int, color: int, graph: list[list[int]], num_vertices: int, col: list[int]) → bool¶

Check if it is safe to assign a color to a node.

>>> is_safe(0, 1, [[0,1],[1,0]], 2, [0,1])
False
>>> is_safe(0, 2, [[0,1],[1,0]], 2, [0,1])
True

backtracking.m_coloring_problem.solve(node: int, col: list[int], max_colors: int, num_vertices: int, graph: list[list[int]]) → bool¶

Recursively try to color the graph using at most max_colors.

>>> solve(0, [0]*3, 3, 3, [[0,1,0],[1,0,1],[0,1,0]])
True
>>> solve(0, [0]*3, 2, 3, [[0,1,0],[1,0,1],[0,1,0]])
True