Graph Coloring

The graph_color_symbolic function resides in the KokkosGraph::Experimental namespace. A kernel handle is used to set options such as execution space, memory space, team size, and which algorithm implementation is used.

Header File: KokkosGraph_graph_color.hpp

Usage:

KokkosGraph::Experimental::graph_color (
    KernelHandle *handle,
    typename KernelHandle::nnz_lno_t num_rows,
    typename KernelHandle::nnz_lno_t num_cols,
    lno_row_view_t_ row_map,
    lno_nnz_view_t_ entries,
    bool is_symmetric = true)

Requirements:

• row_map and entries represent the graph in compressed sparse row format
• num_rows == num_cols
• The input graph must be structurally symmetric, meaning that if (i,j) is an entry, then so is (j,i).
  • Except: any entry (i,j) where j >= num_rows is ignored. This is useful for coloring the local subgraph of a distributed matrix.
• Diagonal entries (self-loops) are ignored.

Outputs:

• Get the view of colors: handle->get_graph_coloring_handle()->get_vertex_colors();
  • Note: color values use 1-based numbering, i.e. 1 is the first color and so on.
• Get the number of colors used: handle->get_graph_coloring_handle()->get_num_colors()

Coloring Algorithms:

• COLORING_DEFAULT
• COLORING_SERIAL
• COLORING_VB
• COLORING_VBBIT
• COLORING_VBCS
• COLORING_EB

EXAMPLE

https://github.com/kokkos/kokkos-kernels/blob/master/unit_test/graph/Test_Graph_graph_color.hpp