Graph Algorithms

Algorithms for processing graphs represented in CSR and COO formats. More...

Functions
template<typename MatrixType , typename ArrayType >
void	cusp::graph::breadth_first_search (const MatrixType &G, const typename MatrixType::index_type src, ArrayType &labels, bool mark_levels=true)
	Performs a Breadth-first traversal of a graph starting from a given source vertex. More...
template<typename MatrixType , typename ArrayType >
size_t	cusp::graph::connected_components (const MatrixType &G, ArrayType &components)
	Computes the connected components of a graph. More...
template<class Array2dType , class ArrayType >
void	cusp::graph::hilbert_curve (const Array2dType &coord, const size_t num_parts, ArrayType &parts)
	Partition a graph using Hilbert curve. More...
template<typename MatrixType , typename ArrayType >
size_t	cusp::graph::maximal_independent_set (const MatrixType &G, ArrayType &stencil, size_t k=1)
	Compute maximal independent set of a graph. More...
template<typename MatrixType , typename ArrayType >
MatrixType::index_type	cusp::graph::pseudo_peripheral_vertex (const MatrixType &G, ArrayType &levels)
	Compute the pseudo-peripheral vertex of a graph. More...
template<typename MatrixType , typename PermutationType >
void	cusp::graph::symmetric_rcm (const MatrixType &G, PermutationType &P)
	Compute Reverse Cuthill-McKee reordering. More...
template<typename MatrixType , typename ArrayType >
size_t	cusp::graph::vertex_coloring (const MatrixType &G, ArrayType &colors)
	Performs a vertex coloring a graph. More...

Function Documentation

template<typename MatrixType , typename ArrayType >

void cusp::graph::breadth_first_search	(	const MatrixType &	G,
		const typename MatrixType::index_type	src,
		ArrayType &	labels,
		bool	mark_levels = true
	)

Performs a Breadth-first traversal of a graph starting from a given source vertex.

Template Parameters

MatrixType	Type of input matrix
ArrayType	Type of labels array

Parameters

G	A symmetric matrix that represents the graph
src	The source vertex to begin the BFS traversal
labels	If mark_levels is false then labels will contain the level set of all the vertices starting from the source vertex otherwise labels will contain the immediate ancestor of each vertex forming a ancestor
mark_levels	Boolean value indicating whether to return level sets, false, or predecessor, true, markers tree.

See Also

http://en.wikipedia.org/wiki/Breadth-first_search

Example

#include <cusp/csr_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include bfs header file
#include <cusp/graph/breadth_first_search.h>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 4, 4);

   cusp::array1d<int,cusp::device_memory> labels(G.num_rows);

   // Execute a BFS traversal on the device
   cusp::graph::breadth_first_search(G, 0, labels);

   // Print the level set constructed from the source vertex
   cusp::print(labels);

   return 0;
}

template<typename MatrixType , typename ArrayType >

size_t cusp::graph::connected_components	(	const MatrixType &	G,
		ArrayType &	components
	)

Computes the connected components of a graph.

Template Parameters

MatrixType	Type of input matrix
ArrayType	Type of components array

Parameters

G	A symmetric matrix that represents the graph
components	Array containing the number indicating the component that each vertex belongs.

Returns

The number of components found in the graph

See Also

http://en.wikipedia.org/wiki/Connected_component_(graph_theory)

Example

#include <cusp/csr_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include connected components header file
#include <cusp/graph/connected_components.h>

#include <thrust/fill.h>
#include <thrust/replace.h>

#include <iostream>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 4, 4);

   // X is used to fill invalid edges in the graph
   const int X = cusp::ell_matrix<int,float,cusp::host_memory>::invalid_index;

   // Disconnect vertex 0
   thrust::fill(G.column_indices.begin() + G.row_offsets[0],
                G.column_indices.begin() + G.row_offsets[1],
                X);
   thrust::replace(G.column_indices.begin(), G.column_indices.end(), 0, X);

   cusp::array1d<int,cusp::device_memory> components(G.num_rows);

   // Compute connected components on the device
   size_t numparts = cusp::graph::connected_components(G, components);

   // Print the number of components and the per vertex membership
   std::cout << "Found " << numparts << " components in the graph." <<
   std::endl;
   cusp::print(components);

   return 0;
}

template<class Array2dType , class ArrayType >

void cusp::graph::hilbert_curve	(	const Array2dType &	coord,
		const size_t	num_parts,
		ArrayType &	parts
	)

Partition a graph using Hilbert curve.

Parameters

coord	Set of points in 2 or 3-D space
num_parts	Number of partitions to construct
parts	Partition assigned to each point

Template Parameters

Array2dType	Type of input coordinates array
ArrayType	Type of output partition indicator array, parts

Overview

Uses a Hilbert space filling curve to partition a set of points in 2 or 3 dimensional space.

See Also

http://en.wikipedia.org/wiki/Hilbert_curve

Example

#include <cusp/array1d.h>
#include <cusp/array2d.h>
#include <cusp/csr_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include Hilbert curve header file
#include <cusp/graph/hilbert_curve.h>

#include <iostream>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 4, 4);

   // Array that indicates partition each vertex belongs
   cusp::array1d<int,cusp::device_memory> parts(G.num_rows);

   // Partition the graph into 2 parts
   size_t num_parts = 2;

   // Allocate array of coordinates in 2D
   cusp::array2d<float,cusp::device_memory> coords(G.num_rows, 2);

   // Generate random coordinates
   cusp::copy(cusp::random_array<float>(coords.num_entries, rand()), coords.values);

   // Compute the hilbert space filling curve partitioning the points
   cusp::graph::hilbert_curve(coords, num_parts, parts);

   // Print the number of components and the per vertex membership
   cusp::print(parts);

   return 0;
}

template<typename MatrixType , typename ArrayType >

size_t cusp::graph::maximal_independent_set	(	const MatrixType &	G,
		ArrayType &	stencil,
		size_t	k = 1
	)

Compute maximal independent set of a graph.

Template Parameters

MatrixType	Type of input matrix
ArrayType	Type of components array

Parameters

G	symmetric matrix that represents a graph
stencil	array to hold the MIS(k)
k	radius of independence

Returns

The number of MIS vertices computed for G.

Overview

Computes a maximal independent set (MIS) a graph. The MIS is a set of vertices such that (1) no two vertices are adjacent and (2) it is not possible to add another vertex to thes set without violating the first property. The MIS(k) is a generalization of the MIS with the property that no two vertices in the set are joined by a path of k edges or less. The standard MIS is therefore a MIS(1).

The MIS(k) is represented by an array of {0,1} values. Specifically, stencil[i] is 1 if vertex i is a member of the MIS(k) and 0 otherwise.

See Also

http://en.wikipedia.org/wiki/Maximal_independent_set

Example

#include <cusp/csr_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include MIS header file
#include <cusp/graph/maximal_independent_set.h>

#include <iostream>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 4, 4);

   cusp::array1d<int,cusp::device_memory> stencil(G.num_rows);

   // Compute MIS on the device
   size_t num_mis = cusp::graph::maximal_independent_set(G, stencil);

   // Print the number of MIS vertices and membership stencil
   std::cout << "Computed " << num_mis << " MIS(1) vertices in the graph." <<
   std::endl;
   cusp::print(stencil);

   return 0;
}

Examples:

maximal_independent_set.cu.

template<typename MatrixType , typename ArrayType >

MatrixType::index_type cusp::graph::pseudo_peripheral_vertex	(	const MatrixType &	G,
		ArrayType &	levels
	)

Compute the pseudo-peripheral vertex of a graph.

Template Parameters

MatrixType	Type of input matrix
ArrayType	Type of components array

Parameters

G	A symmetric matrix that represents the graph
levels	Array containing the level set of all vertices from the computed pseudo-peripheral vertex.

Returns

The computed pseudo-peripheral vertex

Overview

Finds a pseduo-peripheral vertex in a graph. A peripheral vertex is the vertex which achieves the diameter of the graph, i.e. achieves the maximum separation distance.

See Also

http://en.wikipedia.org/wiki/Distance_(graph_theory)

Example

#include <cusp/csr_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include pseudo_peripheral header file
#include <cusp/graph/pseudo_peripheral.h>

#include <iostream>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 4, 4);

   cusp::array1d<int,cusp::device_memory> levels(G.num_rows);

   // Compute pseudo peripheral vertex on the device
   int pseudo_vertex = cusp::graph::pseudo_peripheral_vertex(G, levels);

   // Print the pseudo-peripheral vertex and the level set
   std::cout << "Computed pseudo-peripheral vertex " << pseudo_vertex
   << " in the graph." << std::endl;

   cusp::print(levels);

   return 0;
}

template<typename MatrixType , typename PermutationType >

void cusp::graph::symmetric_rcm	(	const MatrixType &	G,
		PermutationType &	P
	)

Compute Reverse Cuthill-McKee reordering.

Template Parameters

MatrixType	Type of input matrix
PermutationType	Type of permutation matrix

Parameters

G	A symmetric matrix that represents the graph
P	The permutation matrix that is generated by the RCM reordering

Overview

Performs a reordering on a graph represented by a symmetric sparse adjacency matrix in order to decrease the bandwidth. The reordering is computed using the Cuthill-McKee algorithm and reversing the resulting index numbers.

See Also

http://en.wikipedia.org/wiki/Cuthill-McKee_algorithm

Example

#include <cusp/array2d.h>
#include <cusp/csr_matrix.h>
#include <cusp/permutation_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include RCM header file
#include <cusp/graph/symmetric_rcm.h>

#include <iostream>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 3, 3);

   // Allocate permutation matrix P
   cusp::permutation_matrix<int,cusp::device_memory> P(G.num_rows);

   // Construct symmetric RCM permutation matrix on the device
   cusp::graph::symmetric_rcm(G, P);

   // Convert permutation to dense matrix
   cusp::array2d<float,cusp::device_memory> P_dense(P);

   // Print the permutation matrix
   cusp::print(P_dense);

   return 0;
}

template<typename MatrixType , typename ArrayType >

size_t cusp::graph::vertex_coloring	(	const MatrixType &	G,
		ArrayType &	colors
	)

Performs a vertex coloring a graph.

Template Parameters

MatrixType	Type of input matrix
ArrayType	Type of colors array

Parameters

G	A symmetric matrix that represents the graph
colors	Contains to the color associated with each vertex computed during the coloring routine

See Also

http://en.wikipedia.org/wiki/Graph_coloring

Example

#include <cusp/csr_matrix.h>
#include <cusp/print.h>
#include <cusp/gallery/grid.h>

//include coloring header file
#include <cusp/graph/vertex_coloring.h>

int main()
{
   // Build a 2D grid on the device
   cusp::csr_matrix<int,float,cusp::device_memory> G;
   cusp::gallery::grid2d(G, 4, 4);

   cusp::array1d<int,cusp::device_memory> colors(G.num_rows);

   // Execute vertex coloring on the device
   cusp::graph::vertex_coloring(G, colors);

   // Print the vertex colors
   cusp::print(colors);

   return 0;
}