Graph

template<memory_space_t space, typename vertex_t, typename edge_t, typename weight_t, class ...graph_view_t>
class graph_t : public gunrock::graph::graph_view_t

Variadic inheritence based graph class, inherit only what you need from the formats implemented. See detail/base.hxx for the graph_base_t implementation. Things to consider:

• Coordinate graph view is equivalent to an edge list.

• Compressed sparse row/column view are equivalent to each other in terms of complexity.

Operation	Adjacency Matrix	COO	Adj. List	CSR/CSC
scan	O(n^2)	O(m)	O(m+n)	O(m+n)
get neighbors	O(n)	O(m)	O(d)	O(d)
is edge	O(1)	O(m)	O(d)	O(d)
insert edge	O(1)	O(1)	O(1) or O(d)	O(m+n)
delete edge	O(1)	O(m)	O(d)	O(m+n)

Template Parameters:

• space – memory space to use for the graph (device or host).

• vertex_t – index type of the vertices, must be integral type.

• edge_t – index type of the edges, must be integral type.

• weight_t – type of the edge weights.

• graph_view_t – internal view of the graph, must be a class from among the valid implementations, see graph/csr.hxx, graph/csc.hxx, graph/coo.hxx.

template<typename vertex_t>
struct vertex_pair_t

vertex pair of source and destination, accessed using .source and .destination;

Template Parameters:

vertex_t – vertex type.

template<typename edge_t>
struct edge_pair_t

Todo:

: Cannot remember what this is for.

Properties

struct graph_properties_t

define graph properties, this includes is the graph directed? is the graph weighted? Add more properties that we should support. I can think of graph types (multigraph, cyclic, …), or negative edge support, etc.

enum gunrock::graph::view_t

Available graph views.

Values:

enumerator csr

CSR-based view.

enumerator csc

CSC-based view.

enumerator coo

COO-based view.

enumerator invalid

Invalid-view.

Functions on Graph

template<typename graph_type>
__host__ __device__ double gunrock::graph::get_average_degree(graph_type const &G)

Get the average degree of a graph.

Template Parameters:

graph_type – graph type.

Parameters:

G – graph to get the average degree.

Returns:

double average degree of the graph.

template<typename graph_type>
__host__ __device__ double gunrock::graph::get_degree_standard_deviation(graph_type const &G)

Get the degree standard deviation of a graph. This method uses population standard deviation, therefore measuring the standard deviation over the entire population (all nodes). This can be sped up by only taking a small sample and using sqrt(accum / graph.get_number_of_vertices() - 1) as the result.

Template Parameters:

graph_type – graph type.

Parameters:

G – graph to get the degree standard deviation.

Returns:

double degree standard deviation of the graph.

template<typename graph_type, typename histogram_t>
void gunrock::graph::build_degree_histogram(graph_type const &G, histogram_t *histogram, gcuda::stream_t stream = 0)

build a log-scale degree histogram of a graph.

Todo:

maybe a faster implementation will maybe be creating a segment array (which is just number of neighbors per vertex), and then sort and find the end of each bin of values using an upper_bound search. Once that is achieved, compute the adjacent_difference of the cumulative histogram.

Template Parameters:

• graph_type – graph type.

• histogram_t – histogram type.

Parameters:

• G – graph to build the histogram.

• histogram – histogram pointer to build.

• stream – execution stream to use.

template<typename graph_type>
void gunrock::graph::remove_self_loops(graph_type &G)

Utility to remove self-loops, so, if we have an edge between vertex_0 and vertex_0, that edge will be removed as it is a self-loop.

Todo:

need an implementation.

Template Parameters:

graph_type – graph type.

Parameters:

G – graph to remove self-loops.

Graph Builder

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::csr_t<space, vertex_t, edge_t, weight_t> &csr)

Builds a graph using CSR object.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• csr – csr_t format with graph’s data.

Returns:

graph_t the graph itself.

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::coo_t<space, vertex_t, edge_t, weight_t> &coo)

Builds a graph using COO object.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• coo – coo_t format with graph’s data.

Returns:

graph_t the graph itself.

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::csc_t<space, vertex_t, edge_t, weight_t> &csc)

Builds a graph using CSC object.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• csc – csc_t format with graph’s data.

Returns:

graph_t the graph itself.

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::coo_t<space, vertex_t, edge_t, weight_t> &coo, format::csr_t<space, vertex_t, edge_t, weight_t> &csr)

Builds a graph that supports COO and CSR.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• coo – coo_t format with graph’s data.

• csr – csr_t format with graph’s data.

Returns:

graph_t the graph itself.

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::csc_t<space, vertex_t, edge_t, weight_t> &csc, format::csr_t<space, vertex_t, edge_t, weight_t> &csr)

Builds a graph that supports CSC and CSR.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• csc – csc_t format with graph’s data.

• csr – csr_t format with graph’s data.

Returns:

graph_t the graph itself.

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::coo_t<space, vertex_t, edge_t, weight_t> &coo, format::csc_t<space, vertex_t, edge_t, weight_t> &csc)

Builds a graph that supports COO and CSC.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• coo – coo_t format with graph’s data.

• csc – csc_t format with graph’s data.

Returns:

graph_t the graph itself.

template<memory_space_t space, typename edge_t, typename vertex_t, typename weight_t>
auto gunrock::graph::build(graph::graph_properties_t properties, format::coo_t<space, vertex_t, edge_t, weight_t> &coo, format::csc_t<space, vertex_t, edge_t, weight_t> &csc, format::csr_t<space, vertex_t, edge_t, weight_t> &csr)

Builds a graph that supports COO, CSC and CSR.

Template Parameters:

• space – memory space for the graph (host or device).

• edge_t – Edge type of the graph.

• vertex_t – Vertex type of the graph.

• weight_t – Weight type of the graph.

Parameters:

• properties – Graph properties.

• coo – coo_t format with graph’s data.

• csc – csc_t format with graph’s data.

• csr – csr_t format with graph’s data.

Returns:

graph_t the graph itself.