<commit_before>import unittest
"""
Given an undirected graph and a number m, determine if the graph can be colored with at most m colors
such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph
means assignment of colors to all vertices.
Input:
a) A 2D array graph[V][V] where V is number of vertices in the graph. If graph[i][j] is 1, there is direct
edge from vertex i to j, otherwise graph[i][j] is 0.
b) An integer m which is maximum number of colors that can be used.
Output:
An array color[V] that should have numbers from 1 to m. color[i] should represent the color assigned
to the ith vertex. The code should return false if the graph cannot be colored using m colors.
"""

"""
Approach:
The idea is to start with vertex 1 and assign it a color. Then assign colors to subsequent vertices which
results in a "safe" assignment, ie, the color is not already assigned to any of its adjacent vertices. Backtrack
and try a new color in case none of the assignments is safe.
"""


def is_safe(graph, vertex_to_check, color, assigned):
    V = len(graph)
    for vertex in range(V):
        if vertex != vertex_to_check and graph[vertex][vertex_to_check] == 1:
            if assigned == color[vertex]:
                return False

    return True


def graph_coloring_helper(graph, color, vertex, m):
    if vertex == len(graph):
        return True
    for c in range(1, m+1):
        if is_safe(graph, vertex, color, c):
            color[vertex] = c
            if graph_coloring_helper(graph, color, vertex+1, m):
                return True
            color[vertex] = 0<commit_msg>Some refactoring<commit_after>import unittest
"""
Given an undirected graph and a number m, determine if the graph can be colored with at most m colors
such that no two adjacent vertices of the graph are colored with same color. Here coloring of a graph
means assignment of colors to all vertices.
Input:
a) A 2D array graph[V][V] where V is number of vertices in the graph. If graph[i][j] is 1, there is direct
edge from vertex i to j, otherwise graph[i][j] is 0.
b) An integer m which is maximum number of colors that can be used.
Output:
An array color[V] that should have numbers from 1 to m. color[i] should represent the color assigned
to the ith vertex. The code should return false if the graph cannot be colored using m colors.
"""

"""
Approach:
The idea is to start with vertex 1 and assign it a color. Then assign colors to subsequent vertices which
results in a "safe" assignment, ie, the color is not already assigned to any of its adjacent vertices. Backtrack
and try a new color in case none of the assignments is safe.
"""


def is_safe(graph, vertex_to_check, color, assigned):
    V = len(graph)
    for vertex in range(V):
        if graph[vertex][vertex_to_check] == 1 and assigned == color[vertex]:
            return False

    return True


def graph_coloring_helper(graph, color, vertex, m):
    if vertex == len(graph):
        return True
    for c in range(1, m+1):
        if is_safe(graph, vertex, color, c):
            color[vertex] = c
            if graph_coloring_helper(graph, color, vertex+1, m):
                return True
            color[vertex] = 0
{'fraction_non_alphanumeric': 0.0703875968992248, 'fraction_numerical': 0.006201550387596899, 'mean_word_length': 3.2447368421052634, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1273145', 'n_tokens_mistral': 904, 'n_tokens_neox': 872, 'n_words': 475}