D2 Graph Coloring

KokkosGraph: Distance-2 Graph Coloring and Bipartite Graph Partial Coloring

Header File: KokkosGraph_Distance2Color.hpp

Basic Example

Handle handle;
handle.create_distance2_graph_coloring_handle();
KokkosGraph::Experimental::graph_color_distance2(&handle, numVertices, G.row_map, G.entries);
auto colors = handle.get_distance2_graph_coloring_handle()->get_vertex_colors();
Ordinal numColors = handle.get_distance2_graph_coloring_handle()->get_num_colors();
handle.destroy_distance2_graph_coloring_handle();

This is from a full working example kokkos-kernels/example/wiki/graph/KokkosGraph_wiki_coloring.cpp.

Handle Setup

void KokkosKernelsHandle::create_distance2_graph_coloring_handle(
    KokkosGraph::GraphColoringAlgorithmDistance2 coloring_type = KokkosGraph::COLORING_D2_DEFAULT);

Available algorithms

KokkosGraph::COLORING_D2_DEFAULT: COLORING_D2_NB_BIT on all parallel devices, and COLORING_D2_SERIAL for Serial device.
KokkosGraph::COLORING_D2_VB: Straightforward algorithm that uses a nested loop to check the colors of neighbors-of-neighbors. Generally the slowest algorithm.
KokkosGraph::COLORING_D2_VB_BIT: Same as COLORING_D2_VB, but with the optimization of using a 32-bit integer as a bitset to track forbidden colors, rather than using an array of 32 bools.
KokkosGraph::COLORING_D2_VB_BIT_EF: COLORING_D2_VB_BIT, but with an optimization that can skip some edges.
KokkosGraph::COLORING_D2_NB_BIT: Generally the fastest algorithm. Unlike the VB (vertex-based) algorithms, it does not use a nested loop over neighbors-of-neighbors and instead propagates forbidden colors to "nets" (hyperedges), allowing vertices to be processed in O(degree) instead of O(degree^2) time.
KokkosGraph::COLORING_D2_SERIAL: an optimized version of NB_BIT for serial execution.

All algorithms except KokkosGraph::COLORING_D2_SERIAL are nondeterministic.

Getting the coloring sub-handle

GraphColorDistance2HandleType is a member typedef of KokkosKernelsHandle.

GraphColorDistance2HandleType* KokkosKernelsHandle::get_distance2_graph_coloring_handle();

Getting the vertex colors, and the number of colors used

color_view_type GraphColorDistance2Handle::get_vertex_colors();
nnz_lno_type GraphColorDistance2Handle::get_num_colors();

Note: color values use 1-based numbering, i.e. 1 is the first color and so on.

Handle Cleanup

void KokkosKernelsHandle::destroy_distance2_graph_coloring_handle();

Distance-2 Greedy Coloring on an Undirected (Symmetric) Graph

This computes a distance-2 coloring on an undirected graph. This satisfies the condition that every vertex must have a different color than all its neighbors, and its neighbors' neighbors. It tries to minimize the number of unique colors used, but doesn't necessarily produce an optimal coloring.

template<class KernelHandle, typename InRowmap, typename InEntries>
void KokkosGraph::Experimental::graph_color_distance2(
    KernelHandle *handle,
    typename KernelHandle::nnz_lno_t num_verts,
    InRowmap row_map,
    InEntries row_entries);

Parameters:

handle: a pointer to a KokkosKernelsHandle
num_verts: the number of vertices in the graph
row_map: the CRS row pointers array
row_entries: the CRS column indices array

Requirements:

Graph is symmetric (undirected).
Diagonal entries of the graph have no effect on the coloring.
create_distance2_graph_coloring_handle() has been called on the handle
row_map.extent(0) == num_verts + 1
row_map(num_verts) == row_entries.extent(0)

Bipartite Graph Row Coloring

This problem is closely related to distance-2 coloring, but can work on any non-square and/or non-symmetric graph. This performs distance-2 coloring on the left part of a bipartite graph. The vertices in the left part are rows in the adjacency matrix, and the vertices in the right part are columns in the adjacency matrix. The constraint is now that each row may not have the same color as any other row that shares a neighbor. In other words, all the rows of a given color will have disjoint sets of adjacent columns.

template<class KernelHandle, typename InRowmap, typename InEntries>
void KokkosGraph::Experimental::bipartite_color_rows(
    KernelHandle *handle,
    typename KernelHandle::nnz_lno_t num_rows,
    typename KernelHandle::nnz_lno_t num_columns,
    InRowmap row_map,
    InEntries row_entries,
    bool is_symmetric = false)

Parameters:

handle: a pointer to a KokkosKernelsHandle
num_rows: the number of rows in the adjacency matrix (each row will be assigned a color)
num_columns: the number of columns in the adjacency matrix
row_map: the CRS row pointers array
row_entries: the CRS column indices array
is_symmetric: whether the graph is known to be symmetric. If true, can avoid computing the explicit transpose internally.

Requirements:

create_distance2_graph_coloring_handle() has been called on the handle (there is not a separate sub-handle for bipartite partial coloring, and all the same algorithms are supported).
row_map.extent(0) == num_verts + 1
row_map(num_verts) == row_entries.extent(0)

Bipartite Graph Column Coloring

This is exactly the same as bipartite graph row coloring, except that columns are assigned colors, not rows. Computing a column coloring on G is equivalent to computing a row coloring on G^T.

template<class KernelHandle, typename InRowmap, typename InEntries>
void KokkosGraph::Experimental::bipartite_color_columns(
    KernelHandle *handle,
    typename KernelHandle::nnz_lno_t num_rows,
    typename KernelHandle::nnz_lno_t num_columns,
    InRowmap row_map,
    InEntries row_entries)

Parameters:

handle: a pointer to a KokkosKernelsHandle
num_rows: the number of rows in the adjacency matrix
num_columns: the number of columns in the adjacency matrix (each column will be assigned a color)
row_map: the CRS row pointers array
row_entries: the CRS column indices array

Requirements:

create_distance2_graph_coloring_handle() has been called on the handle (there is not a separate sub-handle for bipartite partial coloring, and all the same algorithms are supported).
row_map.extent(0) == num_verts + 1
row_map(num_verts) == row_entries.extent(0)

Note that there is no is_symmetric option for bipartite_color_columns(). This is because if the graph is symmetric, row coloring and column coloring are equivalent.

SAND2020-6474 O