Fork me on GitHub
 All Classes Files Functions Variables Groups Pages
Functions
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
MatrixTypeType of input matrix
ArrayTypeType of labels array
Parameters
GA symmetric matrix that represents the graph
srcThe source vertex to begin the BFS traversal
labelsIf 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_levelsBoolean 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/print.h>
//include bfs header file
int main()
{
// Build a 2D grid on the device
// Execute a BFS traversal on the device
// 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
MatrixTypeType of input matrix
ArrayTypeType of components array
Parameters
GA symmetric matrix that represents the graph
componentsArray 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/print.h>
//include connected components header file
#include <thrust/fill.h>
#include <thrust/replace.h>
#include <iostream>
int main()
{
// Build a 2D grid on the device
// X is used to fill invalid edges in the graph
// Disconnect vertex 0
G.column_indices.begin() + G.row_offsets[1],
X);
thrust::replace(G.column_indices.begin(), G.column_indices.end(), 0, X);
// 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
coordSet of points in 2 or 3-D space
num_partsNumber of partitions to construct
partsPartition assigned to each point
Template Parameters
Array2dTypeType of input coordinates array
ArrayTypeType 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/print.h>
//include Hilbert curve header file
#include <iostream>
int main()
{
// Build a 2D grid on the device
// Array that indicates partition each vertex belongs
// Partition the graph into 2 parts
size_t num_parts = 2;
// Allocate array of coordinates in 2D
// 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
MatrixTypeType of input matrix
ArrayTypeType of components array
Parameters
Gsymmetric matrix that represents a graph
stencilarray to hold the MIS(k)
kradius 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/print.h>
//include MIS header file
#include <iostream>
int main()
{
// Build a 2D grid on the device
// 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
MatrixTypeType of input matrix
ArrayTypeType of components array
Parameters
GA symmetric matrix that represents the graph
levelsArray 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/print.h>
//include pseudo_peripheral header file
#include <iostream>
int main()
{
// Build a 2D grid on the device
// 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
MatrixTypeType of input matrix
PermutationTypeType of permutation matrix
Parameters
GA symmetric matrix that represents the graph
PThe 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/print.h>
//include RCM header file
#include <iostream>
int main()
{
// Build a 2D grid on the device
// Allocate permutation matrix P
// Construct symmetric RCM permutation matrix on the device
// Convert permutation to dense matrix
// 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
MatrixTypeType of input matrix
ArrayTypeType of colors array
Parameters
GA symmetric matrix that represents the graph
colorsContains to the color associated with each vertex computed during the coloring routine
See Also
http://en.wikipedia.org/wiki/Graph_coloring
Example
#include <cusp/print.h>
//include coloring header file
int main()
{
// Build a 2D grid on the device
// Execute vertex coloring on the device
// Print the vertex colors
cusp::print(colors);
return 0;
}