KokkosGraph::graph_color_distance2

Defined in header: KokkosGraph_Distance2Color.hpp

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

Colors the vertices of a graph such that every vertex, its neighbors and its neighbors’ neighbors have distict colors.

The graph must be symmetric, but it is not required to have diagonal entries. The coloring will not have distance-1 or distance-2 conflicts.

A view of length num_vertices, containing the colors will be returned through the handle: handle->get_distance2_graph_coloring_handle()->get_vertex_colors()

Parameters

handle:

an instance of KokkosKernels::KokkosKernelsHandle that stores algorithm parameters and the output colors.

num_verts:

the number of vertices in the graph.

row_map:

the graph row map.

row_entries:

the graph column indices.

Type Requirements

No type requirements will be asserted.

Example

#include "KokkosGraph_wiki_9pt_stencil.hpp"
#include "KokkosGraph_Distance1Color.hpp"
#include "KokkosGraph_Distance2Color.hpp"

// Greedy Graph Coloring
//  -Generate the graph for a rectangular grid, with a 9-point stencil
//   (each vertex is adjacent to the 8 vertices around it within 1 grid square)
//  -Run Distance-1 coloring (usual coloring: adjacent vertices must have
//  different colors)
//    -Print out the colors of each vertex in a grid
//  -Run Distance-2 coloring, and print out the colors
//    -Different constraint: two vertices separated by a path of length 1 OR 2
//     must have different colors)

int main() {
  Kokkos::initialize();
  {
    using GraphDemo::numVertices;
    RowmapType rowmapDevice;
    ColindsType colindsDevice;
    // Step 1: Generate the graph on host, allocate space on device, and copy.
    // See function "generate9pt" below.
    GraphDemo::generate9pt(rowmapDevice, colindsDevice);
    // Step 2: Create handle and run distance-1 coloring.
    {
      Handle handle;
      // Use the default algorithm (chosen based on ExecSpace)
      handle.create_graph_coloring_handle(KokkosGraph::COLORING_DEFAULT);
      // Run coloring (graph is square and symmetric)
      KokkosGraph::Experimental::graph_color(&handle, numVertices, numVertices, rowmapDevice, colindsDevice);
      // Get the colors array, and the number of colors used from the handle.
      auto colors       = handle.get_graph_coloring_handle()->get_vertex_colors();
      Ordinal numColors = handle.get_graph_coloring_handle()->get_num_colors();
      printf("9-pt stencil: Distance-1 Colors (used %d):\n", (int)numColors);
      GraphDemo::printColoring(colors, numColors);
      putchar('\n');
      // Clean up
      handle.destroy_graph_coloring_handle();
    }
    // Step 3: Create handle and run distance-2 coloring.
    {
      Handle handle;
      // Use the default algorithm (chosen based on ExecSpace)
      handle.create_distance2_graph_coloring_handle(KokkosGraph::COLORING_D2_DEFAULT);
      // Run coloring
      KokkosGraph::Experimental::graph_color_distance2(&handle, numVertices, rowmapDevice, colindsDevice);
      // Get the colors array, and the number of colors used from the handle.
      auto colors       = handle.get_distance2_graph_coloring_handle()->get_vertex_colors();
      Ordinal numColors = handle.get_distance2_graph_coloring_handle()->get_num_colors();
      printf("9-pt stencil: Distance-2 Colors (used %d):\n", (int)numColors);
      GraphDemo::printColoring(colors, numColors);
      putchar('\n');
      // Clean up
      handle.destroy_distance2_graph_coloring_handle();
    }
  }
  Kokkos::finalize();
  return 0;
}