backtracking.m_coloring_problem
===============================

.. py:module:: backtracking.m_coloring_problem


Attributes
----------

.. autoapisummary::

   backtracking.m_coloring_problem.num_vertices


Functions
---------

.. autoapisummary::

   backtracking.m_coloring_problem.graph_coloring
   backtracking.m_coloring_problem.is_safe
   backtracking.m_coloring_problem.solve


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:data:: num_vertices