[FEA]: Add an experimental DAWN BFS backend for unrenumbered single-GPU BFS

[lxrzlyr]

[FEA]: Add an experimental DAWN BFS backend for unrenumbered single-GPU BFS

Is this a new feature, an improvement, or a change to existing functionality?

New Feature

Priority

Medium

Problem

BFS and unweighted shortest-path traversal remain important building blocks for graph analytics. Existing GPU BFS implementations are already strong, but there is still room to explore traversal formulations that expose more regular parallel work and reduce some traditional frontier-management overheads.

DAWN is a matrix-operation-optimized shortest-path method that was presented at ICS 2024 and included in the conference's Best Paper Nominees session. I have recently had time to adapt the method toward cuGraph and would like to discuss whether it can be contributed as an experimental BFS backend first, then iterated with the RAPIDS/cuGraph maintainers toward a production-quality implementation.

The intent is not to bypass cuGraph's existing BFS path, but to create a focused experimental path where the method can be reviewed, benchmarked, and shaped by the NVIDIA/RAPIDS team.

Ideal solution

Add an experimental DAWN BFS backend with a constrained initial scope:

• single-GPU execution
• unrenumbered graphs only (renumber=false)
• non-transposed storage only (store_transposed=false)
• distances-only output
• no predecessor output
• explicit rejection of unsupported graph modes

The first API shape I propose is:

• a C++ internal entry point for SG DAWN BFS
• a C API compatibility wrapper returning cugraph_paths_result_t
• a lower-overhead C API where the caller provides a graph-sized distance output buffer

This lets the method be evaluated without changing the default cuGraph BFS behavior. If maintainers agree with the direction, the implementation can then evolve toward the preferred cuGraph API and dispatch model.

My goal is not to keep DAWN as a standalone research path inside the repository, but to preserve its performance advantages while adapting it to cuGraph's architecture. I would appreciate maintainer guidance on the missing features and integration requirements needed for this to become a maintainable cuGraph component.

Alternatives considered

• Keep DAWN outside cuGraph as a standalone research prototype. This is simpler, but it does not help evaluate whether the method can become a reliable graph-analytics building block inside a production GPU library.
• Replace the existing BFS path directly. I do not think that is the right first step. A constrained experimental backend gives maintainers room to review correctness, API semantics, performance methodology, and integration boundaries before any broader change.
• Use only a benchmark harness without adding an API. That would make performance comparison easier, but would not exercise ownership, result semantics, graph-mode validation, or C API integration.

Additional context

The DAWN paper is:

DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted Graphs.

Public references:

• ICS 2024 accepted papers: https://ics2024.github.io/paper.html
• DAWN publication entry: https://researchr.org/publication/FengWZLLL24
• DAWN arXiv preprint: https://arxiv.org/abs/2208.04514

I have a prototype PR branch that adds focused C API tests and performs an aligned single-source comparison against cuGraph BFS under the same constraints:

• SG
• renumber=false
• store_transposed=false
• predecessor=false
• 10 sources per graph
• 10 repeats per source

The current local validation shows correctness passing on 147 MatrixMarket graphs with a geomean speedup of 6.70x in this constrained mode. I would like to work with the maintainers on the right benchmark corpus, CI coverage, and API boundary before treating this as more than experimental.

Code of Conduct

• I agree to follow cuGraph's Code of Conduct.
• I have searched the open feature requests and have found no duplicates for this feature request.