Directed acyclic graph algorithms#

template<typename vertex_t, typename edge_t, bool multi_gpu>
rmm::device_uvector<vertex_t> topological_sort(
raft::handle_t const &handle,
graph_view_t<vertex_t, edge_t, false, multi_gpu> const &graph_view,
bool do_expensive_check = false
)#

Compute a topological ordering of a directed acyclic graph (DAG). For every directed edge (u, v), u appears before v in the returned ordering.

Throws:

cugraph::logic_error – on erroneous input arguments, if the graph contains a cycle or if the graph is symmetric (undirected).

Template Parameters:

  • vertex_t – Type of vertex identifiers. Needs to be an integral type.

  • edge_t – Type of edge identifiers. Needs to be an integral type.

  • multi_gpu – Flag indicating whether template instantiation should target single-GPU (false) or multi-GPU (true).

Parameters:

  • handle – RAFT handle object to encapsulate resources (e.g. CUDA stream, communicator, and handles to various CUDA libraries) to run graph algorithms.

  • graph_view – Graph view object.

  • do_expensive_check – A flag to run expensive checks for input arguments (if set to true).

Returns:

Device vector containing the topological sorting levels. For each local vertex (indexed by local vertex partition offset), stores the topological level. Disconnected vertices are assigned level 0.

On this page