<commit_before>from __future__ import print_function
import numpy as np
import scipy.sparse as sp
import minimum_degree as md
from ordering.csr_utils import cols_in_row
from ordering.misc_utils import invert_permutation

def rows_in_col(m, c):
    assert isinstance(m, sp.csc_matrix)
    return m.indices[m.indptr[c]:m.indptr[c+1]]

def get_permuted_sp_matrices(m, inv_row_p, inv_col_p):
    A = m.tocoo()
    A.row = inv_row_p[A.row]
    A.col = inv_col_p[A.col]
    return A.tocsr(), A.tocsc()

def coloring(m, inv_row_p, inv_col_p):
    # The permutation must give a matrix in Hessenberg form
    row_major, col_major = get_permuted_sp_matrices(m, inv_row_p, inv_col_p)
    ncols = col_major.shape[1]
    # Initially all column colors are set to the invalid "color" -1
    column_colors = np.full(ncols, -1, np.int32)
    # If color i is available: color_available[i] is 1, otherwise 0
    # Initially, "color" 0 is available 
    color_available = np.ones(1, np.int8)
    # Iterate through columns backwards, from right to left
    for c in reversed(xrange(ncols)):
        # All rows containing c
        for r in rows_in_col(col_major, c):
            # All other columns in those rows, c's "neighbors"
            cols = cols_in_row(row_major, r)
            idx = np.flatnonzero(cols==c)
            # cols in r: [ left | c | right]
            # only the right index set has been processed so far
            right = cols[idx+1:]
            used_colors = column_colors[right]
            color_available[used_colors] = 0
        #print('Colors available:\n%s' % color_available)
        index = np.flatnonzero(color_available)[0]
        column_colors[c] = index
        color_available = np.ones(max(index+2, color_available.size), np.int8)
    print('Colors:\n%s' % column_colors)

if __name__=='__main__':  
    m = sp.dok_matrix((3,3), dtype=np.int8)
    m[0,0] = m[0,1] = m[0,2] = 1
    m[1,0] = m[1,1]          = 2
    m[2,2] = 3
    print(m.todense(), '\n')
    # row_p and col_p store the current permutation
    row_p = np.arange(m.shape[0], dtype=np.int32)
    col_p = np.arange(m.shape[1], dtype=np.int32) 
    #
    md.DEBUG = True
    # TODO Index violation in slice causes a weird error, give better error msg
    m_csr = m.tocsr() 
    md.min_degree_ordering(m_csr, row_p, col_p, rbeg=0, rend=3, cbeg=0, cend=3)
    
    coloring(m_csr, invert_permutation(row_p), invert_permutation(col_p))<commit_msg>Printing color count and lower bound on the chromatic number<commit_after>from __future__ import print_function
import numpy as np
import scipy.sparse as sp
import minimum_degree as md
from ordering.csr_utils import cols_in_row
from ordering.misc_utils import invert_permutation

def rows_in_col(m, c):
    assert isinstance(m, sp.csc_matrix)
    return m.indices[m.indptr[c]:m.indptr[c+1]]

def get_permuted_sp_matrices(m, inv_row_p, inv_col_p):
    A = m.tocoo()
    A.row = inv_row_p[A.row]
    A.col = inv_col_p[A.col]
    return A.tocsr(), A.tocsc()

def coloring(m, inv_row_p, inv_col_p):
    # The permutation must give a matrix in Hessenberg form
    row_major, col_major = get_permuted_sp_matrices(m, inv_row_p, inv_col_p)
    ncols = col_major.shape[1]
    # Initially all column colors are set to the invalid "color" -1
    column_colors = np.full(ncols, -1, np.int32)
    # If color i is available: color_available[i] is 1, otherwise 0
    # Initially, "color" 0 is available 
    color_available = np.ones(1, np.int8)
    # chromatic number >= max nonzeros in a row
    lb_chromatic_number = 0
    # Iterate through columns backwards, from right to left
    for c in reversed(xrange(ncols)):
        # All rows containing c
        for r in rows_in_col(col_major, c):
            # All other columns in those rows, c's "neighbors"
            cols = cols_in_row(row_major, r)
            lb_chromatic_number = max(lb_chromatic_number, cols.size)
            idx = np.flatnonzero(cols==c)
            # cols in r: [ left | c | right]
            # only the right index set has been processed so far
            right = cols[idx+1:]
            used_colors = column_colors[right]
            color_available[used_colors] = 0
        #print('Colors available:\n%s' % color_available)
        index = np.flatnonzero(color_available)[0]
        column_colors[c] = index
        color_available = np.ones(max(index+2, color_available.size), np.int8)
    print('Colors:\n%s' % column_colors)
    print('Color count: %d (>=%d)'%(color_available.size-1,lb_chromatic_number)) 

if __name__=='__main__':  
    m = sp.dok_matrix((3,3), dtype=np.int8)
    m[0,0] = m[0,1] = m[0,2] = 1
    m[1,0] = m[1,1]          = 2
    m[2,2] = 3
    print(m.todense(), '\n')
    # row_p and col_p store the current permutation
    row_p = np.arange(m.shape[0], dtype=np.int32)
    col_p = np.arange(m.shape[1], dtype=np.int32) 
    #
    md.DEBUG = True
    # TODO Index violation in slice causes a weird error, give better error msg
    m_csr = m.tocsr() 
    md.min_degree_ordering(m_csr, row_p, col_p, rbeg=0, rend=3, cbeg=0, cend=3)
    
    coloring(m_csr, invert_permutation(row_p), invert_permutation(col_p))
{'fraction_non_alphanumeric': 0.1123025930980698, 'fraction_numerical': 0.017547280171573407, 'mean_word_length': 3.097444089456869, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 5, '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': '4292336', 'n_tokens_mistral': 1936, 'n_tokens_neox': 1855, 'n_words': 470}